Chapter 2. The Big Picture^2

2.2 Implementing Parsers

ANTLRは文法規則から再帰的下向き構文解析器(recursive-descent parser)を生成する。再帰的下向き構文解析器は規則に付き１つの再帰メソッドの集合。下向き(descent)という用語は、構文解析が構文解析木の根(ルート；root)から始まり葉(トークン；token)へ向かうことを表している。最初に起動する規則である開始記号は、構文解析木の根になる。それは前のセクションの構文解析木でメソッドstat()の呼び出すことを意味する。この種の構文解析のより一般的な用語は「トップダウン構文解析(top-down parser)」。再帰的下向き構文解析はトップダウン構文解析の実装の一種である。

再帰下降パーサーがどのようなものか理解するために、ANTLRが生成した規則assignのメソッドを見てみる。

//	assign : ID '=' expr ';' ;
void assign () {	// method generated from rule assign
	match(ID);	// compare ID to current input symbol then consume
	match('=');
	expr();		// match an expression by calling expr()
	match(';');
}

再帰的下向き構文解析がcoolなのは、メソッドstat(), assign()を起動することでコールグラフが描かれ、expr()は中間の構文解析木のノードへ反映するところ。match()の呼び出しは構文解析木の葉に対応している。構文解析木を手動で作成するには、各規則メソッドの最初に"add new subtree root"(といった類の)操作を挿入し、match()では"add new leaf node"(といった類の)操作を実行するだろう。

メソッドassign()は必要なトークンがすべて存在し、その順序が正しいことを保証するためチェックをする。構文解析器がassign()に入るとき、構文解析器は複数の構文候補の間で選択する必要がない。構文候補は規則定義の右側の選択肢の１つ。たとえば、assign規則を呼び出すstat規則は、他の種類の文のリストを持つだろう。

/** Match any kind of statement starting at the current input position */
stat : assign		// First alternative ('|' is alternative separator)
     | ifstat		// Second alternative
     | whilestat
    ...
     ;

statの構文解析規則はswitchのように見える。

void stat(){
	switch ( <<current input token>> ){
		CASE ID		: assign(); break;
		CASE IF		: ifstat(); break;	//	IF is token type for keyword 'if'
		CASE WHILE	: whilestat(); break;
		...
		default		: <<raise no viable alternative exception>>
	}
}

メソッドstat()は、次の入力トークンを検査して構文解析の決定または予測をしなければならない。構文解析の決定が予測する構文候補は成功するだろう。この場合、WHILEキーワードを見なすことにより、stat規則の３番目を予測する。よって規則メソッドstat()はwhilestat()を呼び出す。先読みトークン(lookahead token)という用語を聞いたことがあるかもしれないが、これがまさに次の入力トークンである。先読みトークンは、構文解析器がマッチングして消費する前に傍受する任意のトークンである。

しばしば構文解析器は、成功するであろう構文候補を予測するため、多くの先読みトークンを必要とする。もしかすると、現在の位置からファイルの終わりまでの全てのトークンを考慮しなければならないかもしれない！ANTLRはこのすべてを黙って解決するが、意思決定の基礎知識を持つことは、生成された構文解析器のデバッグを楽にするのに役立つ。

構文解析の決定を視覚化するため、１つの入口と１つの出口があって、床に語が書かれた迷路を想像してみよう。入り口から出口への経路に沿ったそれぞれの語の連なりが文を表す。迷路の構造は、定義する言語の文法規則に類似する。言語のメンバーシップをテストするため、文の語と走査する迷路の床の上の語と比較する。もし文の語を追うことで出口に達したらなら、その文は妥当である。

迷路を通り抜けるため、構文解析器が構文候補を選ぶように、分岐ごとに正しい経路を選ばなくてはならない。次の語あるいは文の語と、分岐から出ているそれぞれの経路の語を比較して、どの経路を取るか決定しなければならない。分岐から見える語は、先読みトークンに類似している。それぞれの経路がユニークな語で始まっていれば、決定は非常に簡単。規則statでは、それぞれの構文候補がユニークなトークンで始まっているので、stat()は最初の先読みトークンを見ることで構文候補を区別できる。　

それぞれの経路から始まる語が重なっている場合、構文解析器は構文候補を見分けるため、さらに先を見る必要がある。ANTLRは、それぞれの決定に必要な先読み量を自動的に調整する。もし先読みが同じで、出口(ファイルの終わり)への経路が複数あるなら、現在の入力句に複数の解釈がある。こういった曖昧さの解決が次のトピック。

from The Definitive ANTLR4 Reference by Terence Parr