JavaCC,ANTLR,パーサコンビネータを触ってみた

Java Scala

某場所にて以下のような課題が出た。

  • いわゆるΣ計算の構文を解析する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で

年末から↓の本を読みはじめていたので、軽い気持ちで作ることに。

言語実装パターン ―コンパイラ技術によるテキスト処理から言語実装まで

言語実装パターン ―コンパイラ技術によるテキスト処理から言語実装まで

コードは次のようになりました。

ANTLRのtree grammarでΣ演算

動かすのに必要なものは

Visitorではなく、tree grammarを使って木構文解析器をジェネレートする形にしました。行数は102行。
tree grammarの書き方がわからずに四苦八苦していたら1月2日が終わっていました…

JParsecで

そういえば、この課題が出た当初にこんなやり取りがあったことを思い出す。

思い出してしまったらやるしかないですよね。

JParsecでΣ演算

動かすのに必要なものは

  • jparsec-2.0.jar
  • cglib-nodep-2.2.2.jar

JParsecで作ったやつだけ追加実装で乗算記号"*"を省略しても乗算が計算できるようにしてあります。320行。
ANTLRのときとは別の意味で書き方がわからず、チュートリアルやサンプルコード読んでいたら1月3日が通り過ぎていました…

Scalaのパーサコンビネータライブラリで

上記3つでかなり精神的に消耗したため、癒しを求めてScalaでも試すことに。

ScalaのパーサコンビネータでΣ演算

98行。ScalaちゃんマジScala。2時間もかかっていないはず。

おもったこと

言語は異なるものの、id:bleis-tiftさんが下記資料にかかれていること(83ページあたり以降)を実感しました。

仕事で使うF#
View more presentations from bleis tift
  • パーサジェネレータはホスト言語とはジェネレータ用の言語を覚える必要がある
  • パーサジェネレータだと生成してコンパイルしなければならない
  • パーサジェネレータで生成したコードは
  • JParsecのコードを読むのはつらい(というか読める気がしない…)
  • コード量が膨らむ

あと、パーサジェネレータは内部でホスト言語のコードも書かなければならなくなる場合も多いのでなんだかなぁと思ったりしますね。
JParsecを使ったコードは、今回実装したものが四則演算レベルなのでなんとか読めるレベルで収まっていますが、もっと複雑なことをしようとしたらわけがわからなくなると思われます。GroovyからJParsecを使えば読みやすさは多少改善できるかもしれませんが、パターンマッチやcase classがないのでデータ構造に関しては楽できないと思います。
あと、パーサコンビネータは小さいパーサを組み合わせて大きなパーサを作るので、部分部分のテストもしやすいです。

コードの解説は？

心に余裕ができたら書きます…