構文木を作る

Parsec で構文解析して構文木を作る

構文木を作る手順

Parsec を利用してプログラムをパースして構文木を作る手順については、次のようにまとめることができるだろう。

１．プログラム言語の文法（BNF記法など）を元に、構文木のノードとなる代数的データ型を定義する。

　＊　定型的に Term, Expr, Stmt 型を考えるとよいようだ。

２．字句解析パーサを作る。 　 　＊　makeTokenParser （Text.Parsec.Token モジュール）を使う。設定レコードは Text.Parsec.Lnguage モジュールのemptyDef などをカスタマイズして使う。

３．字句解析パーサを元に項 term 解析パーサを作る。このときパーサの戻り値は対応する代数的データ型とする（Expr 型）。

４．項 term 解析パーサ以外に、演算定義のテーブル table を作る。さらに term パーサと演算テーブル table を元に式 expression パーサを作る。パーサの戻り値は Expr 型にする。

　＊　buildExpressionParser （Text.Parsec.Expr モジュール）を使う。

５．expression パーサを元に文 statement パーサを作る。パーサの戻り値は Stmt 型。

　＊　パーサの解析方法を再帰下降型にすることにより、特に構文木のマージなどを意識しなくても自然に構文木が形成される。

プログラムのソースから構文木を作成するまでの手順は、Parsec を使うと定型的にできるような気がする。あとは、どういう構文木を設計するかという問題だけが残る。

色々なデータの処理プログラムを作っても、実際にはそれらを組み合わせて使いたい場合が多い。自分用のプログラム言語とまではいかなくても、コンソールから処理の組み合わせを指示できたら便利だ。構文解析のプログラムを収集して習熟すれば、役立つ領域は広いだろう。構文解析のアルゴリズム自体は定型的なようで、後は、実験を繰り返して慣れることが必要だ。