HABA 構文解析器

HABA の文法を解析するための構文解析器は、それが出力した文法の構文解析もできるようになっています。というより、この解析器によって解析可能な JavaScript プログラムを出力しています。

使用方法

構文解析器は parser.js というファイル1つにまとまっているので、これをダウンロードして自分のパソコンやサーバーに設置してください。HTMLから呼び出して使うには <head> ブロックに次の1行を書いてファイルを読み込みます。

<script src="./parser.js"></script>

また、自分で作成した文法プログラム（例えば multi.js）も同様にして読み込みます。

<script src="./multi.js"></script>

文法プログラムには Grammar オブジェクトと Converter オブジェクトが必要です。

そして <script> タグや外部 JavaScript ファイルで Parser オブジェクトにそれらを渡すことで文字列を解析できます。例えば入力文字列 input の字句解析および構文解析をするプログラムは次のようになります。

<script>
const parser = new Parser(Grammar, Converter);
const result = parser.tokenize(input);
const outcome = parser.parse(result.tokens);
</script>

構文解析用オブジェクト

parser.js を読み込むとグローバル名前空間に以下の各オブジェクトが定義されます。外部から使用するのは Parser オブジェクトと Tree オブジェクトで、それ以外は内部的に使用されるだけです。

Parser: 字句解析および構文解析を実行します。
StateStack: 状態と構文木を同時に保持するスタックです。
Token: 字句解析後のトークンを保持します。
Tree: 構文解析後の構文木を保持します。

Parser

コンストラクタにて新しい Parser オブジェクトを生成します。

new Parser(grammar, converter)

grammar: 文法オブジェクトです。flag, terminals, dummies, rules, table の各プロパティが必要です。; 通常は HABA が出力した Grammar オブジェクトをそのまま使用します。
converter: 構文変換オブジェクトです。文法に現れる非終端記号と同じ名前のメソッドが必要です。; 通常は HABA が出力した Converter オブジェクトに処理を記述したものを使用します。

Parser.prototype.parse()

構文解析を行なうインスタンスメソッドです。

parse(tokens)

tokens: トークン一覧です。; 通常は tokenize() メソッドの返値の tokens プロパティをそのまま指定します。

以下のようなプロパティを持ったオブジェクトを返します。

invalid: 解析に失敗した場合に存在し、失敗した箇所以降のトークン文字列が格納されます。
tree: 解析に成功した場合は結果の構文木が、失敗した場合は null が格納されます。
valid: 解析に失敗した場合に存在し、先頭から成功した部分までのトークン文字列が格納されます。

Parser.prototype.tokenize()

字句解析を行なうインスタンスメソッドです。

tokenize(text)

text: 解析すべき入力文字列です。

以下のようなプロパティを持ったオブジェクトを返します。

invalid: 解析に失敗した場合に存在し、失敗した箇所以降の入力文字列が格納されます。
tokens: 解析に成功した場合は結果のトークン一覧が、失敗した場合は null が格納されます。
valid: 解析に失敗した場合に存在し、先頭から成功した部分までのトークン文字列が格納されます。

Tree

構文木を表します。新規に作成するのではなく、parse() メソッドの呼び出し結果として得られたものを利用します。

Tree.prototype.children

この要素の直接の子要素一覧を格納した配列です。子要素は全て Tree オブジェクトです。

Tree.prototype.label

文法上の終端記号、または非終端記号が格納されます。

Tree.prototype.text

label プロパティが終端記号の場合はそれに対する入力文字列が格納されます。label プロパティが非終端記号の場合は空文字列となります。

その他のプロパティ

Converter オブジェクトの実装によって Tree オブジェクトに新たなプロパティが追加されたり、既存のプロパティが変更されたりします。動作説明で示した足し算文法の Converter オブジェクトに含まれる Num メソッドの場合、

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

引数の tree は次のようになります。

tree = {
    children: [
        0: tree = {
            children: [],
            label: "'[0-9]+'",
            text: "1"
        }
    ],
    label: "Num",
    text: ""
}

親の tree は非終端記号 Num を表していて label プロパティは "Num"、text プロパティは空文字列です。children は Num の規則の定義部分で、この場合は終端記号 "[0-9]+" だけが格納されます。その text プロパティの値 "1" が実際に入力された文字列となります。

このうち足し算の処理に必要なのは "1" の部分だけなので、これを数値の 1 に変換して親 tree の result プロパティとして追加します。

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

続いて Multi メソッド

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

の引数の tree は以下のようになります。

tree = {
    children: [
        0: tree = {
            children: [...],
            label: "Num",
            result: 1,
            text: ""
        },
        1: tree = {
            children: [],
            label: "'+'",
            text: "+"
        },
        2: tree = {
            children: [...],
            label: "Num",
            result: 2,
            text: ""
        }
    ],
    label: "Multi",
    text: ""
}

子要素 Num のメソッドが先に呼び出されるため、その tree には既に result が設定されています。

ここでは 1 + 2 の足し算をしています。1 + 2 + 3 のように足し算を続けることもできて、その場合は children 配列の要素が増えていきます。このため children の 0, 2, 4, ... 番目の要素にある result の値を全て足せば全体の結果になります。

// 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;
    }
},

これで parse() メソッドの返値の outcome.tree.result に足し算結果が格納されることになります。