JavaCC,ANTLR,パーサコンビネータを触ってみた
某場所にて以下のような課題が出た。
- いわゆるΣ計算の構文を解析するParserと解析結果にあわせた処理を行うVisitorの作成
- 書式は sum i : NUMBER .. NUMBER of expression
- 変数はiで固定、iを1つ目のNUMBERから2つ目のNUMBERまで変化させながらexpressionを計算
- expressionは四則演算を行う。括弧を使用できること。
- jjtreeを用いて実装せよ
たとえば"sum i : 3 .. 5 of 1 + 2 * i"が27になる、みたいな形ですね。
でまぁ、jjtreeというかJavaCCだけだと
戦略というか方向性というか
- 時間短縮のため変数iはキーワードとしておく
- 変数が1つしかない仕様なので記号表は作らない
- Visitorのフィールドでiの当該値を記憶する
あとはその場の勢いで追加実装したりしています。
JavaCC,jjtreeで
コードは諸事情のため略。自分で書いたコードは170行くらい。
12月31日と1月1日で3時間ずつほど消費。割と問題が起こりそうにないところではまったり、typoしてジェネレートやり直しなどで時間をとられた気がする。
ANTLRで
年末から↓の本を読みはじめていたので、軽い気持ちで作ることに。
言語実装パターン ―コンパイラ技術によるテキスト処理から言語実装まで
- 作者: Terence Parr,中田育男,伊藤真浩
- 出版社/メーカー: オライリージャパン
- 発売日: 2011/12/24
- メディア: 大型本
- 購入: 5人 クリック: 333回
- この商品を含むブログ (13件) を見る
コードは次のようになりました。
動かすのに必要なものは
- antlr-3.4.jar
Visitorではなく、tree grammarを使って木構文解析器をジェネレートする形にしました。行数は102行。
tree grammarの書き方がわからずに四苦八苦していたら1月2日が終わっていました…
JParsecで
そういえば、この課題が出た当初にこんなやり取りがあったことを思い出す。
@pocketberserker よし、JParsecを使いましょう!(マテ
2011-12-06 16:56:18 via Tween to @pocketberserker
思い出してしまったらやるしかないですよね。
動かすのに必要なものは
- jparsec-2.0.jar
- cglib-nodep-2.2.2.jar
JParsecで作ったやつだけ追加実装で乗算記号"*"を省略しても乗算が計算できるようにしてあります。320行。
ANTLRのときとは別の意味で書き方がわからず、チュートリアルやサンプルコード読んでいたら1月3日が通り過ぎていました…
おもったこと
言語は異なるものの、id:bleis-tiftさんが下記資料にかかれていること(83ページあたり以降)を実感しました。
- パーサジェネレータはホスト言語とはジェネレータ用の言語を覚える必要がある
- パーサジェネレータだと生成してコンパイルしなければならない
- パーサジェネレータで生成したコードは
- JParsecのコードを読むのはつらい(というか読める気がしない…)
- コード量が膨らむ
あと、パーサジェネレータは内部でホスト言語のコードも書かなければならなくなる場合も多いのでなんだかなぁと思ったりしますね。
JParsecを使ったコードは、今回実装したものが四則演算レベルなのでなんとか読めるレベルで収まっていますが、もっと複雑なことをしようとしたらわけがわからなくなると思われます。GroovyからJParsecを使えば読みやすさは多少改善できるかもしれませんが、パターンマッチやcase classがないのでデータ構造に関しては楽できないと思います。
あと、パーサコンビネータは小さいパーサを組み合わせて大きなパーサを作るので、部分部分のテストもしやすいです。
コードの解説は?
心に余裕ができたら書きます…