キャプチャ注釈付き DFA の作り方私案

2015 年 9 月 14 日 この稿のやりかた、 キャプチャ対象ごとに遷移先状態を別に分ける方法は、 もはや利用していません。 今は、アクション表を使い、 遷移元状態と文字クラスの組み合わせに対してアクションを実行するようにしています。

これまで、HTTP/1.1 サーバのために、部分文字列のキャプチャを含む正規表現から決定性有限状態遷移機械 (DFA) の遷移表を作成してきました。 これらは、正規表現を目で追いながら手作業で DFA の遷移表へ書き下してきたのですが、 If-Match 用のリストでミスをしてしまったことから、 手順化ができそうかどうか、 できるならプログラムで自動生成できるようにならないか、考えてみることにします。 今回は、 手順化を検討します。

具体例として、 If-Match 用のリストの次の正規文法から、 キャプチャ注釈付き DFA へ変換をおこないます。 PEG と正規表現の間の子のような記法にしています。

    (?: ('*') \s*
    |   (?:',' [\s,]*)? ('W/'? '"' [\x21\x23-\x7e]* '"') \s*
        (?:',' [\s,]*   ('W/'? '"' [\x21\x23-\x7e]* '"') \s*)*
        (?:',' [\s,]*)? )

キャプチャする範囲を丸括弧で囲む記法になっていますが、これを一文字単位の注釈に書き直します。前回のエントリのようにキャプチャ指定はビットマップで表すことにし、2 でバッファへ push_back し、4 でバッファをベクタへ push_back してバッファをクリアする動作を表すことにします。 文字への注釈はビックリマークに続けてビットマップを書き添えることにします。

    (?: '*'!6 \s*
    |   (?:',' [\s,]*)? (?:(?:'W'!2 '/'!2)? '"'!2 (?:[\x21\x23-\x7e]!2)* '"'!6) \s*
        (?:',' [\s,]*   (?:(?:'W'!2 '/'!2)? '"'!2 (?:[\x21\x23-\x7e]!2)* '"'!6) \s*)*
        (?:',' [\s,]*)? )

これから非決定性有限状態遷移機械 (NFA) を作ります。 キャプチャ注釈付きの文字は、 NFA でも注釈付きにしておきます。

    N1: ε N2 | ε N7
    N2: '*'!6 N3
    N3: ε N4 | ε N6
    N4: \s N5
    N5: ε N4 | ε N6
    N6: $
    N7: ',' N8 | ε N11
    N8: ε N9 | ε N11
    N9: \s N10 | ',' N10
    N10: ε N9 | ε N11
    N11: 'W'!2 N12 | ε N13
    N12: '/'!2 N13
    N13: '"'!2 N14
    N14: ε N15 | ε N17
    N15: [\x21\x23-\x7e]!2 N16
    N16: ε N15 | ε N17
    N17: '"'!6 N18
    N18: ε N19 | ε N21
    N19: \s N20
    N20: ε N19 | ε N21
    N21: ε N22 | ε N37
    N22: ',' N23
    N23: ε N24 | ε N26
    N24: \s N25 | ',' N25
    N25: ε N24 | ε N26
    N26: 'W'!2 N27 | ε N28
    N27: '/'!2 N28
    N28: '"'!2 N29
    N29: ε N30 | ε N32
    N30: [\x21\x23-\x7e]!2 N31
    N31: ε N30 | ε N32
    N32: '"'!6 N33
    N33: ε N34 | ε N36
    N34: \s N35
    N35: ε N34 | ε N36
    N36: ε N22 | ε N37
    N37: ',' N38 | ε N41
    N38: ε N39 | ε N41
    N39: \s N40 | ',' N40
    N40: ε N39 | ε N41
    N41: $

コンパイラ―原理・技法・ツール (Information & Computing)」(文献1)の「アルゴリズム 3.20 部分集合構成法」を使って、 NFA から DFA へ変換します。

    {N1}: ',' {N8} | '*'!6 {N3} | 'W'!2 {N12} | '"'!2 {N14}
    {N3}: \s {N5} | $
    {N5}: \s {N5} | $
    {N8}: \s {N10} | ',' {N10} | 'W'!2 {N12} | '"'!2 {N14}
    {N10}: \s {N10} | ',' {N10} | 'W'!2 {N12} | '"'!2 {N14}
    {N12}: '/'!2 {N13}
    {N13}: '"'!2 {N14}
    {N14}: '"'!6 {N18} | [\x21\x23-\x7e]!2 {N16}
    {N16}: '"'!6 {N18} | [\x21\x23-\x7e]!2 {N16}
    {N18}: \s {N20} | ',' {N23, N38} | $
    {N20}: \s {N20} | ',' {N23, N38} | $
    {N23, N38}: \s {N25, N40} | ',' {N25, N40} | 'W'!2 {N27} | '"'!2 {N29} | $
    {N25, N40}: \s {N25, N40} | ',' {N25, N40} | 'W'!2 {N27} | '"'!2 {N29} | $
    {N27}: '/'!2 {N28}
    {N28}: '"'!2 {N29}
    {N29}: '"'!6 {N33} | [\x21\x23-\x7e]!2 {N31}
    {N31}: '"'!6 {N33} | [\x21\x23-\x7e]!2 {N31}
    {N33}: \s {N35} | ',' {N23, N38} | $
    {N35}: \s {N35} | ',' {N23, N38} | $

このキャプチャ注釈付きの DFA で、キャプチャ注釈付き文字による遷移先の状態に注目すると、 その状態へ遷移する他の文字もすべて同じキャプチャ注釈がついていることに気がつきます。そこで、 キャプチャ注釈を文字から遷移先の状態の注釈へ移しかえることにします。さらに、$ を含む受理状態をもつ状態には 1 のキャプチャをつけることにします。

    {N1}: ',' {N8} | '*' !7{N3} | 'W' !2{N12} | '"' !2{N14}
    !7{N3}: \s !1{N5} | $
    !1{N5}: \s !1{N5} | $
    {N8}: \s {N10} | ',' {N10} | 'W' !2{N12} | '"' !2{N14}
    {N10}: \s {N10} | ',' {N10} | 'W' !2{N12} | '"' !2{N14}
    !2{N12}: '/' !2{N13}
    !2{N13}: '"' !2{N14}
    !2{N14}: '"' !7{N18} | [\x21\x23-\x7e] !2{N16}
    !2{N16}: '"' !7{N18} | [\x21\x23-\x7e] !2{N16}
    !7{N18}: \s !1{N20} | ',' !1{N23, N38} | $
    !1{N20}: \s !1{N20} | ',' !1{N23, N38} | $
    !1{N23, N38}: \s !1{N25, N40} | ',' !1{N25, N40} | 'W' !2{N27} | '"' !2{N29} | $
    !1{N25, N40}: \s !1{N25, N40} | ',' !1{N25, N40} | 'W' !2{N27} | '"' !2{N29} | $
    !2{N27}: '/' !2{N28}
    !2{N28}: '"' !2{N29}
    !2{N29}: '"' !7{N33} | [\x21\x23-\x7e] !2{N31}
    !2{N31}: '"' !7{N33} | [\x21\x23-\x7e] !2{N31}
    !7{N33}: \s !1{N35} | ',' !1{N23, N38} | $
    !1{N35}: \s !1{N35} | ',' !1{N23, N38} | $

これから、状態をグループ分けして、状態数を最小化します。グループ分けのアルゴリズムは文献1「アルゴリズム 3.39 DFA の状態最小化」にしたがいますが、 注釈が異なっている状態を別のグループへ分割するように条件を追加します。

    {N1}: ',' {N8} | '*' !7{N3} | 'W' !2{N12} | '"' !2{N14}

    {N8}:  \s {N10} | ',' {N10} | 'W' !2{N12} | '"' !2{N14}
    {N10}: \s {N10} | ',' {N10} | 'W' !2{N12} | '"' !2{N14}

    !2{N12}: '/' !2{N13}
    !2{N27}: '/' !2{N28}

    !2{N13}: '"' !2{N14}
    !2{N28}: '"' !2{N29}

    !2{N14}: '"' !7{N18} | [\x21\x23-\x7e] !2{N16}
    !2{N16}: '"' !7{N18} | [\x21\x23-\x7e] !2{N16}
    !2{N29}: '"' !7{N33} | [\x21\x23-\x7e] !2{N31}
    !2{N31}: '"' !7{N33} | [\x21\x23-\x7e] !2{N31}

    !7{N33}: \s !1{N35} | ',' !1{N23, N38} | $
    !7{N18}: \s !1{N20} | ',' !1{N23, N38} | $

    !1{N35}: \s !1{N35} | ',' !1{N23, N38} | $
    !1{N20}: \s !1{N20} | ',' !1{N23, N38} | $

    !1{N23, N38}: \s !1{N25, N40} | ',' !1{N25, N40} | 'W' !2{N27} | '"' !2{N29} | $
    !1{N25, N40}: \s !1{N25, N40} | ',' !1{N25, N40} | 'W' !2{N27} | '"' !2{N29} | $

    !7{N3}: \s !1{N5} | $

    !1{N5}: \s !1{N5} | $

グループに DFA の状態を割りふります。

      S1: ',' S2 | '*' !7S9 | 'W' !2S3 | '"' !2S4
      S2: \s  S2 | ',' S2 | 'W' !2S3 | '"' !2S4
    !2S3: '/' !2S4
    !2S4: '"' !2S5
    !2S5: '"' !7S6 | [\x21\x23-\x7e] !2S5
    !7S6: \s  !1S7 | ',' !1S8 | $
    !1S7: \s  !1S7 | ',' !1S8 | $
    !1S8: \s  !1S8 | ',' !1S8 | 'W' !2S3 | '"' !2S5 | $
    !7S9: \s !1S10 | $
    !1S10: \s !1S10 | $

これで、 キャプチャ注釈付きの DFA が得られました。