2013/07/10

カテゴリー : , ,

HaskellのパーサコンビネータParsecを使ってみた

※注意: この記事は古い記事です。import周り等、最新versionのparsecライブラリにし追随ていません。一応、2013年(7月10日)当時はこうだったという形で記録として残してあります。(追記: 2017/7/17)

Haskellの勉強がてらParsecを使ってみました。

　コードを眺めただけだと、再帰的下向き構文解析を手で書いているのとあまり変わらないように見えますが、実際に書いてみると非常に簡単ですね。モナド使ってるっていうのが、気に入りませんが。構文解析のコードしか書いてないのに、字句解析器もやってくれます。

　次の文法をS式に書き直すパーサを書いてみました。中置記法を前置記法に変換します。LLパーサなので、左再帰しないように気を使います。
Infix  → Exp
Exp    → Term "+" Exp | Term "-" Exp | Term
Term   → Factor "*" Term | Factor "/" Term | Factor
Factor → ident | number | "(" Exp ")"

さらに、これを変換して、
Infix  → Exp
Exp    → Term Exp*
Exp*   → "+" Term Exp* | "-" Term Exp* | ε
Term   → Factor Term*
Term*  → "*" Factor Term* | "/" Factor Term* | ε
Factor → ident | number | "(" Exp ")"

を構文解析させます。変換したのは、演算子の適用順序を正しくするためです。εは、空を表します。

以下が、コードと実行結果。実行環境はghci 7.4.2。

　Parsecは、ひたすら読めるまで読み続けて、パターンにマッチしない文字列が来たら、エラーを出さずに、マッチした部分の文字列の実行結果を返して、終了するようです。文字列を最後まで読み込み、エラーを出す為には、文法にEOF記号を混ぜる必要がありそうですね。Infix → Exp '$'、みたいな書き方にすればよかったってことでしょうか。

参考文献


0 件のコメント :

コメントを投稿