Chapter 4. A Quick Tour

ANTLR Books

ここまでANTLRのインストール方法、キープロセス、専門用語、言語アプリを作成するのに必要の部品の作り方、などを学んだ。この章ではANTLRの能力を説明する幾つかのサンプルを通して、ANTLRを駆け足で見ていく。簡略化のため詳細の多くは軽く扱うが、完全に理解できなくても心配する必要はない。ゴールはANTLRで何ができるかという雰囲気を得ることだから。

ここでは最初にシンプルな数式言語の文法を扱う。それをANTLRのテストツールでテストした後、Sect3.3 Intergrating a Generated into a Java Programで示した構文解析器を起動するメインプログラムについてさらに学ぶ。そして文法を表現するのに重要な構文解析木を見ていく。とても大きな文法を扱うために、imports文法を使って管理可能な大きさの文法の塊へ分割する方法を見る。そしてANTLRが生成した構文解析器が不正な入力にどう反応するか調べる。

4.1 Matching an Arithmetic Expression Language

最初の文法として、簡単な電卓を作成しよう。式で何かをするのは一般的であるため理にかなっている。簡単にするため、基本的な算術演算(四則演算)、()で囲まれた式、整数値、変数だけを許すものとする。また浮動小数点数に代えて整数だけに制限する。以下は、この言語のすべての機能を説明する入力サンプルである。

193
a = 5
b = 6
a+b*2
(1+2)*3

この式言語でのプログラムは、改行で終わる文が連続したもの。文は、式、代入、空行のいずれか。以下のANTLR文法はこれらの文および式を解析するもの。

<snip>tour/Expr.g4</snip>

あまり深入りせず、ANTLR文法のキー要素を見てみる。

  • 文法は言語構文を記述した規則の集合から成り立っている。statやexprのような構文構造、ならびに識別子や整数のような語彙記号(トークン)の規則がある。
  • 小文字で始まる規則は構文解析の規則。
  • 大文字で始まる規則は字句(トークン)解析の規則。
  • 規則の選択肢(構文候補)は | で区切る。また記号を()でまとめて副規則にできる。たとえば、副規則('*'|'/')は乗算記号または除算記号とマッチする。

ANTLR v4の重要な新機能の１つは、(たいていの種類の)左再帰的な規則を扱う能力。左再帰的な規則は、構文候補の最初にそれ自身を起動するもの。たとえば、この文法では、規則exprは左端にexprを再帰的に起動する構文候補を持っている。算術式表記を規定しているこの方法は、典型的なトップダウン構文解析戦略のために必要とするものより劇的に簡単。この戦略では、複数の規則、演算子ごとの優先順位を必要とする。

トークン定義の表記は、正規表現に精通している必要がある。字句(トークン)の規則についてはChapter6 Exploring Some Real Grammarで見る。唯一独特の構文は、WS(WhiteSpace)規則の -> skip 操作である。これは字句解析器にwhitespaceがマッチしても捨てることを指令する(すべての可能な入力文字は、少なくとも一つの字句規則にマッチしなければならない)。字句解析器への読み飛ばし指示を、文法中に埋め込んだコードではなくANTLR表記を使うことで、文法を特定の言語に結びつけることを避ける。

文法をテストする最も簡単な方法はTestRigによるもの。-guiオプションはポップアップウィンドウで構文解析木を表示する。構文解析木は、構文解析器が入力を認識する時たどるであろう関数呼び出し木に類似する(ANTLRは規則ごとに関数を生成する)。

文法の作成、TestRigを使ったテストがOKなので、最後にANTLRが生成した構文解析器をアプリへ統合する。以下に示すmainプログラムは、必要なオブジェクトを全て生成し、規則progから式言語の構文解析器を起動する。

<snip>tour/ExprJoyRide.java</snip>
行*処理内容*
7-11字句解析器用に字の入力ストリームを生成する。
12-14字句解析器、構文解析器オブジェクトを生成し、それらをトークンストリームでつなぐ。
15構文解析器を起動する(規則メソッドの呼び出しは、規則の起動に似ている。必要であれば、任意の構文解析器の規則を呼び出せる)
16規則メソッドprog()が返した構文解析木をテキスト形式でプリントアウトする。

テストプログラムのビルドとt.exprを入力とした実行は以下のようになる。

$ javac ExprJoyRide.java Expr*.java
$ java ExprJoyRide t.expr
(prog 
    (stat (expr 193) \n) 
    (stat a = (expr 5) \n) 
    (stat b = (expr 6) \n) 
    (stat (expr (expr a) + (expr (expr b) * (expr 2))) \n)
    (stat (expr (expr ( (expr (expr 1) + (expr 2)) )) * (expr 3)) \n)
)

テキストで表現する構文解析木はビジュアルなものより読みにくいが、機能的なテストには便利である。

この式文法はとても小さいが、文法は数千行になることができる。次のセクションでは、そんな大きな文法を管理可能にする方法を学ぶ。

Importing Grammars

ソフトウェアで行うように、とても大きな文法を論理的な固まりに分割するのは良い考え。その１つの方法は、文法を構文解析器と字句解析器に分割すること。異なる言語間には驚く量の字句的な重複があるから、これは悪い考えではない。たとえば識別子と数値は通常、言語をまたいで同じ。字句解析規則を「モジュール」へ分解することは、それを異なる構文解析で使えることを意味する。以下は字句解析規則を全て含む字句解析文法。

<snip>tour/CommonLexerRules.g4</snip>

このように分割した字句解析規則は、import文で取り込むことができる。この場合のコンパイルとテストの手順は、import文がない場合と同じである。

<snip>tour/LibExpr.g4</snip>

今までは、私たちは正しい入力を仮定してきた、しかすべての言語アプリでエラーハンドリングは重要な部分の大半を占める。ANTLRが誤った入力をどうするか見てみよう。

Handring Erroneous Input

ANTLRの構文解析器は構文エラーの報告、回復を自動的に行う。たとえば式の ) を忘れたとする。構文解析器は自動的にエラーメッセージを発生させる。ここで同様に重要なのは、構文解析器は２つ目の式(3)に正しくマッチするためリカバーすること。-guiを使うと構文解析器のダイアログは、自動的にエラーノードを赤反転する。

<snip>fig.recover from error in the first expression.</snip>

ANTLRは最初の式のエラーからリカバーし、２つ目に適切にマッチしている。

ANTLRのエラーメカニズムはとても柔軟性がある。私たちはエラーメッセージ、認識例外の補足、エラーハンドリングの戦略原理ですら変更することができる。→Chap9

from The Definitive ANTLR4 Reference by Terence Parr