2010年10月8日金曜日

ANTLR

参考:antlr/ANTLRWorksを使ってみる

任意の言語の字句解析(LEX)と構文解析(PARSER)による構文木(AST)変換をするツール。
構文木を最適化して変換ルールをかませることでコンパイラやインタプリタを作成できる。
yaccではLALR(1)を使って構文解析を行うのに対し、ANTLRはLL(*)を使って構文解析を行う。

yacc,lexとの違いは以下のもの、
 左再帰が使用不可
 演算優先順序は明示する必要あり
 右結合演算子に対応

出てきた用語の概要 : 構文解析 (プログラミング)

LALR
LALR法(英: LALR parser)は、構文解析手法の一種であり、Lookahead(先読み)LR法の略である。単純LR法(SLR法)の構文解析器よりも多くの文脈自由文法を扱うことができる。構文解析表の大きさがあまり大きくなく、多くの文法を扱えることから、最も一般的な構文解析器となっている。yacc や GNU bison といったコンパイラコンパイラの多くもこの種の構文解析器を生成する。

LL
LL法またはLL構文解析とは、文脈自由文法のサブセットのためのトップダウン構文解析法の一種である。入力文字列を左 (Left) から構文解析していき、左端導出 (Leftmost Derivation) を行う(このため、LL法と呼ぶ。LR法も参照されたい)。この方式で構文解析可能な文法のクラスを LL文法 と呼ぶ