パーサジェネレータを作る

再帰下降構文解析を手で書いていると、面倒くさい & 結構間違える事があったため、パーサジェネレータを作っていました。EBNF でルールを与えると、再帰下降構文解析のパーサのコードを出力してくれる簡単なものですが、試しに作ってみる簡単な言語であれば十分そうです。

なお、前回までは C# でやっていたのですが、今回はテスト実行に CodeMirror を使いたかったため JavaScript を追加いました。

字句解析と EBNF パーサは手書き

構文をパーサジェネレータのクラスに関数呼び出しで与える方法も良かったのですが、せっかく解析法を覚えたので、EBNF の解析くらいは手書きしました。EBNF の正確な文法は知らないですが、多分こんな感じだと思います。

STRING となっているのは、ダブルクオートで囲った文字リテラルを意味しています。また、改行（先頭は必ず "|" に限っています）や空行も許しています。

EBNF からソースコードに変換

以下の手順でやりました。

  1. 非終端記号の関数を作る
  2. 非終端記号の関数内で順番に呼ぶ（list）
  3. {}
    は while 文に展開する（repeat）
  4. []
    は if 文で 1 トークン目を確認する（option）
  5. |
    は if 文で分岐する（rule）

変換先のソースコードは、とりあえず JavaScript にしましたが、後々 C# など別の言語にすることも考えて、一旦、抽象木的なものを組み立てて、その出力実装を入れ替えることで、（ある程度仕様が似ていれば）様々な言語のコードを出力できるようにしました。言語の本を読んだおかけで、こういうことも考えられるようになった気がします。

コード1: ソースコード出力の抽象木組み立て（repeat の出力例）

一番面倒だったのが、

getCondition
のところです。この関数は、与えたルールを解析して、次に来る可能性のあるトークン（終端記号）を列挙し、それらとマッチするかの条件式を返します。最初に来る可能性のあるトークは、
{}
等があるとちょっと厄介で、その場合は 2 番目もチェックするようにしています。このあたりは、どこかに書いてあったわけではなく、自前なのでバグがあるかもしれませんが、今の所、自分としては必要そうな場面があまりないため、ひとまず先の手順で実装を終えています。

演算子順位解析にも対応

簡単な言語を作ると行っても、そこそこ使えるようにするためには、演算子は揃えないといけません。しかしながら、優先順位を考えて EBNF を書くのは大変そうです。そこで、演算子順位解析にも対応しました。

文法定義の前に、二項演算子の定義を書けるようにし、yacc 風に %% で区切って文法定義を書くようにしました。そして、

X { OP X }
（X は記号、OP は演算子）のときだけ、演算子順位解析を行うコードを出力するようにしました。

コード2: こんな感じで定義（四則演算）

ついでに、定義された演算子は字句解析でちゃんとトークンとして返ってくるように設定されるようにしています。

できたもの

EBNF を書いたら、それをもとにパーサを作成し、さらにそれに文章を入力して、生成された AST を確認できるようなプログラムを作りました。

図1: できたプログラム（すみれパーサジェネレータ）

画面左上が EBNF の定義、その下が出力したパーサのソースコードです。画面右上に作成したパーサへのテスト入力を記述でき、それを実行（？）すると、その下に解析結果の抽象木が出力されます。試しに四則演算を入れてみましたが、無事に動作しました。

JavaScript で書いてあるため、こちらに置いておきました。エラー確認等あまりやっていないので、変な入力を入れると、無限ループに陥る可能性がありますので、ご注意ください。

ファイルの保存なども行えるようにしたいため、本当は Electron でデスクトップにしたいです。

まとめ

ここ数日、再帰下降構文解析をメインにしたパーサジェネレータを作っていました。次からは、抽象木の評価関数を作って、プログラムを実行できるようにしようと思います。（それはそれとして、プログラムの実行以外にも、別言語に出力（トランスパイル？）の方が個人的には使い勝手が良さそうな気がしてきました。）

言語づくりは用語自体は諸々知っていたのですが、やはり実際にやってみると新しい可能性が広がりますね。