HABA 動作説明

HABA は LALR(1) の構文解析器です。解析ボタンを押すと、入力された文字列に対して字句解析と構文解析を行なって構文木を作成します。それを生成規則に変換し、終端記号を抽出して字句解析要素とダミー要素をそれぞれ取得します。さらにクロージャー、状態遷移、構文解析表を作成し、最終的に文法を JavaScript のプログラムで出力します。

このページではサンプルとして次の足し算文法を入力文字列として使用します。

Multi ::= Num ('+' Num)* ;
Num ::= "[0-9]+" ;
Space ::= "\s+" ;

「大文字小文字を無視する」かどうかは最後の JavaScript の出力に影響するだけなので、ここでは設定しません。

結果、構文木

字句解析、構文解析、コンパイルの全てに成功すると結果欄に「成功」と表示されます。それ以外の場合はエラーメッセージが表示されます。

構文解析まで成功すれば、コンパイルに失敗したとしても構文木以下の各結果が出力されて「表示」チェックボックスが押せるようになります。逆に構文解析、あるいはその前段の字句解析でエラーがあった場合は「表示」チェックボックスは無効のままです。

構文木を表示させると HABA の文法に従った構文木が表示されます。

  • Gram
    • Rule
      • Name: Multi
      • ::=
      • Expr
        • List
          • Term
            • Fact
              • Name: Num
          • Term
            • Fact
              • Quot
                • (
                • Expr
                  • List
                    • Term
                      • Fact
                        • Fixd: '+'
                    • Term
                      • Fact
                        • Name: Num
                • )
            • Rept: *
      • ;
    • Rule
      • Name: Num
      • ::=
      • Expr
        • List
          • Term
            • Fact
              • Flex: "[0-9]+"
      • ;
    • Rule
      • Name: Space
      • ::=
      • Expr
        • List
          • Term
            • Fact
              • Flex: "\s+"
      • ;

字句解析要素、ダミー要素

構文木から終端記号を抽出して一覧表示します。

順位種類要素
1固定値'+'
2正規表現"[0-9]+"

言語として有効な終端記号を「字句解析要素」、無効な終端記号を「ダミー要素」として分類します。同じ分類の中では固定値が先に、正規表現が後になるように並べます。同じ種類の中では構文木に出現した順番に並べています。全く同じ要素は1つにまとめられます。

このようにすることで、固定値と正規表現が同じ文字列にマッチしても固定値を優先的に解釈することが可能になります。例えば

Variable ::= "[a-z]+" ;
IfState ::= 'if' Expr 'then' Expr ;
...

という生成規則があった場合、if という文字列は変数としてではなく、if 文のキーワードとして解釈できます。

生成規則

構文木から生成規則を抽出して展開し、一覧表示します。

番号展開後の規則
0#0# ::= Multi ;
1Multi ::= Num #1# ;
2#1# ::= #1# '+' Num ;
3#1# ::= ;
4Num ::= "[0-9]+" ;

入力された最初の開始記号（ここでは Multi）で始まる生成規則は複数ある可能性があります。解析処理を単純にするために、新たな開始記号 #0# を用いた生成規則を先頭に追加しています。

規則の定義は 0 個以上の記号の連結だけとしています。これも後の解析処理を単純にするためです。入力された最初の生成規則

Multi ::= Num ('+' Num)* ;

は、量指定子の部分を別の生成規則として抽出し、ひとまず

Multi ::= Num #1# ;
#1# ::= ('+' Num)* ;

とします。この2番目の生成規則から量指定子を展開すれば

Multi ::= Num #1# ;
#1# ::= #1# '+' Num ;
#1# ::= ;

量指定子も選択もグループ化もなくなり、連結だけになります。

最後にあった

Space ::= "\s+" ;

は、Space が規則の定義に現れない無効な規則なので削除されました。

この先の処理では、入力された3つの生成規則ではなく、ここで示された展開後の5つの生成規則を使用します。規則番号が 0 から始まっている点に注意してください。

生成規則の展開によって追加された非終端記号 #0#、#1#、…は画面上で入力できない（入力してもエラーになる）ため、他の非終端記号と重複することはありません。

クロージャー、状態遷移

初めに生成規則から閉包演算によって LR(0) クロージャーおよびその状態遷移表を作成します。その後 0 番から順に全ての LR(0) アイテムに「次の記号」を付加して LR(1) アイテムに変換し、それをクロージャーとして一覧表示します。

番号アイテム次の記号
0#0# ::= • Multi$
Multi ::= • Num #1#$
Num ::= • "[0-9]+"'+' $
1#0# ::= Multi •$
2Multi ::= Num • #1#$
#1# ::= • #1# '+' Num$ '+'
#1# ::= •$ '+'
3Multi ::= Num #1# •$
#1# ::= #1# • '+' Num $ '+'
4#1# ::= #1# '+' • Num$ '+'
Num ::= • "[0-9]+"$ '+'
5#1# ::= #1# '+' Num •$ '+'
6Num ::= "[0-9]+" •$ '+'

• は解析位置です。$ は文末を表す終端記号ですが、これも入力できないため他の終端記号と重複することはありません。

状態遷移は次の通りです。

遷移元記号遷移先
0Multi1
0Num2
2#1#3
3'+'4
4Num5
4"[0-9]+"6
0"[0-9]+"6

遷移元および遷移先の数字はクロージャー番号です。記号には終端記号も非終端記号もあります。

構文解析表

クロージャーと状態遷移に基づいて構文解析表を作成します。

番号'+'"[0-9]+"$Multi#1#Num
0s6g1g2
1r0
2r3r3g3
3s4r1
4s6g5
5r2r2
6r4r4

番号は状態番号、つまりクロージャー番号です。状態遷移の記号が終端記号の場合、シフトして次の状態に遷移するためアクション記号は s + 遷移先番号となります。状態遷移の記号が非終端記号の場合、単に次の状態に遷移するだけなのでアクション記号は g + 遷移先番号です。

アイテムの解析位置が生成規則の右端にあって状態遷移をしない場合、「次の記号」に対して還元を行ないます。このときのアクション記号は r + 規則番号です。特に r0 の還元が受理を表します。開始状態は 0 です。

JavaScript

これまでの情報を使用して Grammar オブジェクトと Converter オブジェクトを作成します。

// 文法
const Grammar = {

    "flag": "",

    "terminals": [
        "\\+",
        "[0-9]+",
    ],

    "dummies": [
        "\\s+",
    ],

    "rules": [
        "#0#=1",
        "Multi=2",
        "#1#=3",
        "#1#=0",
        "Num=1",
    ],

    "table": [
        [ "", "s6", "", "g1", "", "g2" ],
        [ "", "", "r0", "", "", "" ],
        [ "r3", "", "r3", "", "g3", "" ],
        [ "s4", "", "r1", "", "", "" ],
        [ "", "s6", "", "", "", "g5" ],
        [ "r2", "", "r2", "", "", "" ],
        [ "r4", "", "r4", "", "", "" ],
    ],

}

// 構文変換
const Converter = {

    // Multi ::= Num ('+' Num)* ;
    "Multi": function(tree) {
    },

    // Num ::= "[0-9]+" ;
    "Num": function(tree) {
    },

}

Grammar の flag は「大文字小文字を無視する」場合に i、そうでなければ空文字列となります。terminals は字句解析要素を全て正規表現で表したもので、dummies はダミー要素です。rules は展開後の生成規則ですが、構文解析には規則の定義の数しか使用しないため連結した記号数を出力しています。table は構文解析表です。

Converter には入力された生成規則のうち有効なものを出力しています。自動では関数の枠しか作成されないため、その文法の言語仕様に従って実装する必要があります。例えば次のような処理を行ないます。

// 構文変換
const Converter = {

    // Multi ::= Num ('+' Num)* ;
    "Multi": function(tree) {
        tree.result = tree.children[0].result;
        for (let i = 2; i < tree.children.length; i += 2) {
            tree.result += tree.children[i].result;
        }
    },

    // Num ::= "[0-9]+" ;
    "Num": function(tree) {
        tree.result = parseInt(tree.children[0].text, 10);
    },

}

これらは HABA 自身の構文解析器によって解析可能です。サンプルページで確認してください。