Chapter 2. The Big Picture

ANTLR Books

2.1 Let's Meta!

言語を実装するには、文を読んで、そこから見つけた句や入力記号に対して適切に反応するアプリを作る必要がある。もしあるアプリが計算する、あるいは文を「実行する」場合、そのアプリをインタプリタと呼ぶ(例としては、計算機、設定ファイル読み込みプログラム、Pythonインタプリタ、など)。もしある言語から他の言語へ文を変換するなら、そのアプリをトランスレーターと呼ぶ(例としてはJava→C#コンバーター、コンパイラ、など)。

適切に反応するため、インタプリターやトランスレーターは、言語の全ての妥当な文、句、下位句を認識できなければならない。句の認識とは、多様なコンポーネントを識別できて、他の句と区別できる、ということを意味する。例えば、私たちは入力 

sp = 100;

をプログラミング言語の代入文として認識する。これは私たちが sp が代入先で、100 は格納する値、であることを知っていることを意味する。代入文 sp = 100; の認識はまた、言語アプリがそれ他(例えば import文)と明らかに区別していることを意味する。認識後、アプリは

performAssignment("sp", 100)

とか

translateAssignment("sp", 100)

のような、適切なオペレーションを実行するだろう。

言語を認識するプログラムは「パーサー」とか「構文解析器」と呼ばれる。構文は、言語のメンバーシップを管理する規則を表し、これから言語構文を指定するためにANTLR文法を作成しようとしている。文法はまさに規則の集合であり、それぞれが句の構造を表現している。ANTLRは文法を経験豊富なプログラマが作るのと非常に似てた構文解析器へ変換する。文法それ自身は、他の言語を指定するために最適化された言語構文に従っている。(ANTLRは他の言語を記述するための言語、つまりメタ言語)。

構文解析は２つタスク(ステージ)に分割すると理解しやすくなる。２つのステージは私たちの頭脳が英文を読むのとよく似ている。私たちは文を字毎に読まない。代わりに文を語のストリームとして知覚する。人間の脳は無意識のうちに、字の連続を語にまとめ、文法構造を認識する前にそれを辞書と照らし合わせる。このプロセスはモールス符号を読む場合がわかりやすい、メッセージを読む前に「・」と「ー」を字に変換しなければならないので。これはまたHumuhumunukunukuapua'a(フムフムヌクヌクアプアア；ハワイ州の州魚;タスキモンガラ)のような長い語を読むとき理解しやすい。

字をまとめて語・記号(トークン)にするプロセスは「字句解析(lexical analysis)」、あるいは単に「字句抽出(tokenizing)」と呼ばれている。この入力を字句抽出するプログラムを字句解析器(レクサー;lexer;字句解析プログラム)と呼ぶ。字句解析器は関連するトークンをトークンクラス、あるいはトークンタイプ(例. INT, ID, FLOAT)へグループ化できる。字句解析器は、構文解析器が個別の記号でなくタイプにだけ着目するとき語彙記号をタイプにグループ化する。トークンは最低２種類の情報で構成される；トークンタイプ(字句構造の認識)と字句解析器がマッチしたトークンのテキスト。

２つめのステージは実際の構文解析器で、これらのトークンを文構造を認識するため入力する(この場合は代入文)。デフォルトでは、ANTLRが生成した構文解析器は、構文解析器が入力文とその構成する句の構造をどのように認識したか記録した「構文解析木」あるいは「構文木」と呼ばれるデータ構造を作成する。

構文解析木の中間ノードは、グループ化して認識したその子供の句の名前。根ノードは最も抽象的な句の名前で、この場合はstat(statementを省略したもの)。構文解析木の葉は常に入力トークン。構文解析木を作ることで、構文解析器は、記号をどのように句へグループ化したかについて完全な情報を保持する便利なデータ構造を後のアプリに引き渡す。木はその後のステップでの処理が容易で、プログラマーによく知られている。さらに良いことに、構文解析器は構文解析木を自動生成できる。

構文解析木の操作をやめることで、同じ言語を認識する必要のある複数のアプリケーションが１つのパーサーを再利用できる。他の選択肢は、構文解析生成器が伝統的に行っているアプリケーション固有のコードの断片を直接へ文法へ埋め込むもの。ANTLR v4はこれをまだ許しているが、構文解析木はより整然と、より分離したデザインを促進する。

構文解析木はまた(あるステージが前のステージの情報を必要とする計算の依存性により)複数パス(木走査)が要求される変換に役立つ。別の場合では、入力文字を各ステージで構文解析し直すより、構文解析木を複数回走査するほうが効率が良い。

私たちは構文構造を規則の組みで指定するため、構文解析木の部分木の根は文法規則名に対応している。

ダイアグラムのassig部分木の最初のレベルに対応する文法規則は以下の通り。

assign : ID '=' expr ';' // match an assignment statement like "sp = 100; "

ANTLRがそのような規則を人間が読める構文解析コードに変換するかを理解することは、文法を使ったりデバッグするための基本原理である。構文解析がどのように作用するか深く見ていこう。

from The Definitive ANTLR4 Reference by Terence Parr