読者です 読者をやめる 読者になる 読者になる

cloverrose's blog

Python, Machine learning, Emacs, CI/CD, Webアプリなど

ANTLR v4調査

ANTLRv3を使っていましたが、気付けばv4が2013/1/22にリリースされていました。

どんな変更点があるのかWhy do we need ANTLR v4? - ANTLR 4 - ANTLR Projectで調べました。
その中で一般ユーザーに関係ありそうなところを抜き出してメモ。

変更点

文法解析アルゴリズムの変更

version3まではstatic LL(*) grammar analysis algorithmによって文法解析をコンパイル時に行なっていた。
version4ではadaptive LL(*) grammar analysis algorithmによって文法解析を実行時に行うようになった。

この実行時解析はJIT技術の進歩により静的解析よりも強力になった。

左再帰文法に対応

v4 accepts even left recursive grammars, except for indirectly left recursive grammars where x calls y which calls x

yaccみたいに以下の様なLR文法を扱うことができるようになったようです。

e : e '*' e
  | e '+' e
  | INT
  ;

内部的には自分で書いた左再帰の文法をANTLRが左再帰なしの文法に書き換えて、それから今までのようにパーサーを生成しています。

埋め込みアクションからの脱却

ANTLRの文法ファイルに{Javaプログラム断片}みたいなことが今までできていました。
しかし、これは文法ファイルをJavaならJavaに依存したものにしてしまいます。

そこでアクションを文法ファイルに埋め込むのではなく外部のVisitorに書くようにする。

思想の変化

今までは文法ファイルに明示的にASTの作り方を書き、それでできたASTをASTパース用の文法ファイルで定義したTreePaserでパースするという方針だった

それを(明示的にASTの作り方を書かなくても)自動的にTree(≠AST)が出来上がるパーサージェネレータ(ANTLRv4)を提供し、そのTreeを(ANTLRではなくJavaならJavaPythonならPythonといった)普通のコードで(Visitorパターンなどで)Treeを走査する方針に変更。

感想

個人的に明示的にAST作ったり、そのASTをTreeParserでパースするとか、埋め込みアクションとかよく使っていたので、
ANTLRv4に簡単に移行できるかは不安です。

一方、yaccのように左再帰が書けたり、優先順位が付けられたりするのは式部分では記述が簡単になりそうでもある。

おまけ

ANTLR v4 with Terence Parr - YouTubeANTLR v4の講義が見れる
序盤はANTLR v4の変更点について
中盤は使い方(最後にCSVファイルのパーサー例題として)
終盤はAdaptive LL(*)について (ここは見てない)