行指向 HTML5 タグ用の正規表現エンジン

これは HTML5 タグを行指向でタグの前のインデント空白列と、 タグの後の行末空白と改行コードも含めて行全体にマッチングさせたい用途向けに組んだ、 特定パターン専用の正規表現エンジンです。 タグ名と要素の文字位置をリストアップすることができます。

素朴なバックトラック仮想マシンにカスタム化した文字クラス判定命令と、 文字位置をリストアップするための限定されたキャプチャ機能をもっています。 汎用のキャプチャ機能を組み込むと大げさになりすぎるので、 必要最小限にして単純化してあります。

仮想マシンの文字照合命令は N. Wirth の表駆動 LL(1) 解析器から、 バックトラック制御命令は PEG 用仮想マシン Ierusalimschy VM から取り入れて、 その上に簡易キャプチャ機能を追加しました。 なお、 前者は 「アルゴリズム+データ構造=プログラム 第一版」(1976)、 もしくは後に章を切り分けて独立させた「翻訳系構成法序論」(1984) に記載されています。 この書籍の英文原文の電子版が Wirth 教授のウェブページで公開されていますが、 現在の版では紹介文程度で説明が乏しいため古い版を当たった方が良いでしょう。

enum {
    EPSILON = 0, PCHAR = 1, NCHAR = 2, NSTART = 3, SPACE = 4, BLANK = 5,
    LF = 10, CR = 13, BOL = 16, SPLIT = 17, JOIN = 18, MATCH = 19,
    MARK0 = 20, MARK1 = 21, SAVE = 22
};

struct instruction_type {
    char sym;
    unsigned char succ;
    unsigned char fail;
};

static inline int
ord (std::string const& str, std::size_t s, std::size_t eos)
{
    return s < eos ? static_cast<unsigned char> (str[s]) : 0;
}

static inline int
code (int const c)
{
    return c > 128 ? 7 : CODE_TABLE[c];
}

static bool
scanloop_html5tag (std::string const& str, std::size_t& pos, std::vector<std::size_t>& capture)
{
    struct trail_type {
        unsigned int ctl;
        std::size_t pos;
        std::size_t mark0;
        std::size_t mark1;
        std::size_t cap;
    };
    std::vector<trail_type> trail;
    std::size_t mark0, mark1;
    std::size_t const eos = str.size ();
    unsigned int ctl = 0;
    do {
        bool succ = true;
        int sym = PATTERN[ctl].sym;
        switch (sym) {
        case EPSILON:
            break;
        case BOL:
            succ = (pos == 0 || '\n' == ord (str, pos - 1, eos));
            break;
        case SPLIT:
            trail.push_back ({PATTERN[ctl].fail, pos, mark0, mark1, capture.size ()});
            break;
        case JOIN:
            trail.pop_back ();
            break;
        case MATCH:
            return true;
        case MARK0:
            mark0 = pos;
            break;
        case MARK1:
            mark1 = pos;
            break;
        case SAVE:
            capture.push_back (mark0);
            capture.push_back (mark1);
            break;
        default:
            if (sym <= BLANK)
                succ = (code (ord (str, pos, eos)) & (1U << (sym - 1U))) != 0;
            else
                succ = (ord (str, pos, eos) == sym);
            if (succ)
                ++pos;
            break;
        }
        ctl = succ ? PATTERN[ctl].succ : PATTERN[ctl].fail;
        if (ctl == 0 && ! trail.empty ()) {
            ctl = trail.back ().ctl;
            pos = trail.back ().pos;
            mark0 = trail.back ().mark0;
            mark1 = trail.back ().mark1;
            capture.resize (trail.back ().cap);
            trail.pop_back ();
        }
    } while (ctl > 0);
    capture.clear ();
    return false;
}

動かすには、 パターン・マッチングのための命令列と文字クラス集合の判定表が必要です。 命令列は正規表現を直訳したような代物です。 文字クラス集合の要素は一つ一つがビットベクトルになっていて、 文字が属する文字集合に対応するビットを立ててあります。

命令は第一欄が文字・文字集合・制御命令コード、 第二欄が成功時に次に実行する命令の番地、 第二欄は失敗時に次に実行する命令の番地が入ります。 飛び先の番地は絶対アドレスです。 ただし、 ゼロ番地は失敗を表しておりジャンプ先番地ではありません。 例えば、 2番地は現在の文字位置の文字が BLANK 文字集合の要素だったら 2 番地を繰り返し、 要素でないときは次の 3 番地へ移す命令になっています。 このように成功時と失敗時の飛び先番地を文字照合命令から得るのが Wirth の LL(1) マシンのやりかたです。 Wirth のマシンにはバックトラックに対応していないので、 そこは Ierusalimschy VM の SPLIT 命令と JOIN 命令を使っています。 SPLIT 命令は第二欄から失敗時の再試行命令の入る番地をとりだして他の状況変数と一緒に記録します。 JOIN 命令は失敗時用の記録を一つ廃棄します。 キャプチャは 2 つのマーク変数へ一時的に記録し、 確定した段階で SAVE 命令でキャプチャリストへ追加します。 SPLIT 時点でキャプチャリストの長さを記録しており、 バックトラックのときにキャプチャリストを切り詰めます。

static const instruction_type PATTERN[] = {
    /*  0*/ {SPLIT,   1U,  4U},
    /*  1*/ {BOL,     2U,  0U},
    /*  2*/ {BLANK,   2U,  3U},
    /*  3*/ {JOIN,    4U,  0U},
    /*  4*/ {'<',     5U,  0U},
    /*  5*/ {MARK0,   6U,  0U},
    /*  6*/ {NSTART,  7U, 36U},
    /*  7*/ {NCHAR,   7U,  8U},
    /*  8*/ {MARK1,   9U,  0U},
    /*  9*/ {SAVE,   10U,  0U},
    /* 10*/ {SPACE,  11U, 34U},
    /* 11*/ {SPACE,  11U, 12U},
    /* 12*/ {MARK0,  13U,  0U},
    /* 13*/ {NSTART, 14U, 34U},
    /* 14*/ {NCHAR,  14U, 15U},
    /* 15*/ {MARK1,  16U,  0U},
    /* 16*/ {SPLIT,  17U, 33U},
    /* 17*/ {SPACE,  17U, 18U},
    /* 18*/ {'=',    19U,  0U},
    /* 19*/ {JOIN,   20U,  0U},
    /* 20*/ {SPACE,  20U, 21U},
    /* 21*/ {'"',    22U, 24U},
    /* 22*/ {'"',    32U, 23U},
    /* 23*/ {PCHAR,  22U,  0U},
    /* 24*/ {'\'',   25U, 27U},
    /* 25*/ {'\'',   32U, 26U},
    /* 26*/ {PCHAR,  25U,  0U},
    /* 27*/ {'`',    28U, 30U},
    /* 28*/ {'`',    32U, 29U},
    /* 29*/ {PCHAR,  28U,  0U},
    /* 30*/ {NSTART, 31U,  0U},
    /* 31*/ {NCHAR,  31U, 32U},
    /* 32*/ {MARK1,  33U,  0U},
    /* 33*/ {SAVE,   10U,  0U},
    /* 34*/ {'/',    35U, 35U},
    /* 35*/ {'>',    44U,  0U},
    /* 36*/ {'/',    37U,  0U},
    /* 37*/ {MARK0,  38U,  0U},
    /* 38*/ {NSTART, 39U,  0U},
    /* 39*/ {NCHAR,  39U, 40U},
    /* 40*/ {MARK1,  41U,  0U},
    /* 41*/ {SAVE,   42U,  0U},
    /* 42*/ {SPACE,  42U, 43U},
    /* 43*/ {'>',    44U,  0U},
    /* 44*/ {SPLIT,  45U, 50U},
    /* 45*/ {BLANK,  45U, 46U},
    /* 46*/ {LF,     49U, 47U},
    /* 47*/ {CR,     48U,  0U},
    /* 48*/ {LF,     49U, 49U},
    /* 49*/ {JOIN,   50U,  0U},
    /* 50*/ {MATCH,   0U,  0U},
};

static const unsigned char CODE_TABLE[128] = {
    0,  0,  0,  0,  0,  0,  0,  0,  0,25U, 9U,  0,  0, 9U,  0,  0,
    0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
  25U, 1U, 1U, 1U, 1U, 1U, 1U, 1U, 1U, 1U, 1U, 1U, 1U, 3U, 3U, 1U,
   3U, 3U, 3U, 3U, 3U, 3U, 3U, 3U, 3U, 3U, 7U, 1U,  0, 1U,  0, 1U,
   1U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U,
   7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 1U, 1U, 1U, 1U, 7U,
   1U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U,
   7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 1U, 1U, 1U, 1U,  0
};