e+ と e? も DFA へ直接変換

正規表現から DFA への直接変換」を拡張して e+ と e? も DFA に変換できるようにします。 e+ は 1 回以上の e の繰り返しで、 ee* と同じです。 e? は e があるかないかで (e|) と同じです。

Core regular expression to Deterministic Finite Automata, DFA

生成規則の piece 記号に、 この 2 つを追加します。

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

構文解析器が作る抽象構文木では、 PLUS ノードと QUES ノードとします。

e1|e2|e3    =>  (OR (OR <e1> <e2>) <e3>)
e1 e2 e3    =>  (CAT (CAT <e1> <e2>) <e3>)
e*          =>  (STAR <e>)
e+          =>  (PLUS <e>)
e?          =>  (QUES <e>)
a           =>  (LETTER a)
            =>  (EPSILON)

e+ は ee*、 e? は (e|) と同じだということを利用して、 nullable、 firstpos、 lastpos を求めると、 直感通りになっています。

nullable(e+) == nullable(ee*)
             == nullable(e) && nullable(e*)
             == nullable(e) && true
             == nullable(e)

nullable(e?) == nullable(e|)
             == nullable(e) || nullable(ε)
             == nullable(e) || true
             == true

firstpos(e+) == firstpos(ee*)
             == nullable(e) ? firstpos(e) ∪ firstpos(e*) : firstpos(e)
             == nullable(e) ? firstpos(e) ∪ firstpos(e) : firstpos(e)
             == nullable(e) ? firstpos(e) : firstpos(e)
             == firstpos(e)

firstpos(e?) == firstpos(e|)
             == firstpos(e) ∪ firstpos(ε)
             == firstpos(e) ∪ {}
             == firstpos(e)

lastpos(e+)  == lastpos(ee*)
             == nullable(e*) ? lastpos(e) ∪ lastpos(e*) : lastpos(e*)
             == lastpos(e) ∪ lastpos(e*)
             == lastpos(e) ∪ lastpos(e)
             == lastpos(e)

lastpos(e?)  == lastpos(e|)
             == lastpos(e) ∪ lastpos(ε)
             == lastpos(e) ∪ {}
             == lastpos(e)

e? は (e|) で OR ノードなので、 followpos を求めるときに使いません。 e+ は ee* で CAT ノードなので、 followpos を求めるときに利用します。

def loop_followpos(ee*)
    for x in lastpos(e)
        followpos(x) ∪= firstpos(e*)

ここで、 firstpos(e*) は firstpos(e) と同じですから、

def loop_followpos(ee*)
    for x in lastpos(e)
        followpos(x) ∪= firstpos(e)

これは e* のふるまいと同じです。

def loop_followpos(e*)
    for x in lastpos(e)
        followpos(x) ∪= firstpos(e)

以上を反映して試してみると、 ab+c の DFA 遷移表は、 abb*c と同等のものに変換されます。

$ ./regexp-to-dfa 'ab+c'
S1 'a' S2
S2 'b' S3
S3 'b' S3
S3 'c' S4#
$ ./regexp-to-dfa 'abb*c'
S1 'a' S2
S2 'b' S3
S3 'b' S3
S3 'c' S4#

ab?c も a(b|)c と同等のものに変換されます。

$ ./regexp-to-dfa 'ab?c'
S1 'a' S2
S2 'b' S3
S2 'c' S4#
S3 'c' S4#
$ ./regexp-to-dfa 'a(b|)c'
S1 'a' S2
S2 'b' S3
S2 'c' S4#
S3 'c' S4#