正規表現から DFA への直接変換

Aho 等 COMPILERS PRINCIPLES, TECHNIQUES, AND TOOLS 2007 (ドラゴン・ブック) 3.9 節の前半、 「正規表現から DFA への直接変換」を C++11 で書いてみました。 単純化した正規表現から DFA 遷移表を作ります。 コマンドライン引数に与えた正規表現から作成した遷移表を標準出力へ流しだします。

Core regular expression to Deterministic Finite Automata, DFA

扱える正規表現は、 次の生成規則のものに限ります。 文字クラス等の便利な記法がなく、 量指定子には、 クリーネ閉包しかありません。

expression : concat ('|' concat)* ;
concat : piece* ;
piece : atom '*'? ;
atom : letter | '(' expression ')' ;

ちなみに、 ドラゴン・ブックによると、 このアルゴリズムをベル研 lex が使っているとあります。 一方、 GNU flexソースコードを読んでみると、 このアルゴリズムではなく、 その一つ前の NFA を経由して DFA に変換するアルゴリズムを採用しています。

ドラゴン・ブックのアルゴリズムでは、 まず正規表現の抽象構文木を作ります。 それから、 抽象構文木の全ノードに nullable 真偽値、 firstpos 集合、 lastpos 集合を求めて記録します。 集合の要素は、 文字ノードの位置です。 同じ文字であっても、 正規表現に現れる場所が異なると、 別の位置として出現位置を割り振ります。 なお、 下の例の最後のシャープ記号は AST の終端を表すもので、 内部で生成したものであって、 シャープ文字ではありません。

(a|b)*abb #
 1 2  345 6

AST ルートの firstpos 集合 = {1, 2, 3}
1 の followpos 集合 = {1, 2, 3}
2 の followpos 集合 = {1, 2, 3}
...
5 の followpos 集合 = {6}

続いて、 このアルゴリズムの要点である、 上の位置がついているノードの followpos 集合を求めます。 nullable、 firstpos、 lastpos を求めたのは、 followpos を求めるための前準備です。 欲しいのは各 followpos と AST のルートの firstpos です。 ある文字の位置のfollowpos 集合とは、 簡単に言いきると、 その文字から次に移ることが可能な文字の位置を要素とする集合のことです。 例えば、 位置 1 からは、 位置 1、 位置 2、 位置 3 に移ることができるので、 位置 1 の集合は、 これら 3 つを要素に持ちます。

後は、 ルートの firstpos 集合から始めて、 上の場合なら a と b の文字ごとに、 辿っていける経路を followpos 集合を使って調べ上げて、 遷移グラフの経路をリストアップすると DFA 遷移表ができあがります。

以上のように、 このアルゴリズムは位置の集合を扱います。 位置の集合は、 抽象構文木のノードに書き込むことにしました。

#include <memory>
#include <set>

struct re_ast_type {
    int m_op;
    std::shared_ptr<re_ast_type> m_lhs;
    std::shared_ptr<re_ast_type> m_rhs;
    int m_code;
    int m_pos;                // このノードの位置

    bool m_nullable;
    std::set<int> m_firstpos; // 位置を要素とするソート済み集合
    std::set<int> m_lastpos;
    std::set<int> m_followpos;
};

dfa_construct は、 アルゴリズム 3.36 の図 3.62 の自然言語表記を C++11 に翻訳したメソッドです。 from 集合のすべての要素 pos について、 対応する LETTER ノードの文字記号が code の場合に、 そのノードの followpos 集合との和をとります。 m_place は位置 pos から LETTER ノードへのポインタを求めるための索引で、 構文解析器が作成します。

void
re_dfa_type::dfa_construct (void)
{
    std::deque<re_dstate_type> dstate;
    std::deque<re_dstate_type>::iterator from;
    std::deque<re_dstate_type>::iterator to;

    int seq = 0;
    dstate_insert (dstate, seq, m_matched.m_re->m_firstpos);
    while ((from = dstate_unmarked (dstate)) != dstate.cend ()) {
        from->m_marked = true;
        for (int code : m_letter) {
            std::set<int> u;
            for (int pos : from->m_set) {
                std::shared_ptr<re_ast_type> re = m_place[pos];
                if (code == re->m_code && LETTER == re->m_op)
                    re_set_union (u, u, re->m_followpos); // u |= followpos
            }
            if (! u.empty ()) {
                to = dstate_insert (dstate, seq, u);
                m_dtran.push_back({from->m_id, from->m_sharped,
                                   code,
                                   to->m_id, to->m_sharped});
            }
        }
    }
}