構文解析における先読み

ウィキペディア小見出し辞書

構文解析における先読み

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/03/13 01:32 UTC 版)

「先読み」の記事における「構文解析における先読み」の解説

先読みは、コンパイラでの構文解析でも重要な概念である。構文解析器が次に適用すべき生成規則を決定する際に入力トークン列を何個か先読みする。 LL法、LR法、LALR法などの構文解析では、後に括弧つきで先読みするトークン数を記することが多い（LALR(1)など）。 多くのプログラミング言語は、限定的な先読み（1個が典型的）で構文解析できるよう設計されている。というのも先読みを制限した方が構文解析器が効率化されるためである。1990年、Terence Parr は博士論文でANTLRを作成し、この傾向に重大な変化をもたらした。ANTLRは、効率的な LL(k) 構文解析器を生成するパーサジェネレータであり、k として任意の固定値が可能である。 構文解析器は、各トークンを参照したときにとりうるアクションが限られている。 shift - トークンをスタックに積み、後で reduce する。 reduce - スタックからトークンを取り出し、生成規則を適用して構文要素を構築する。 end - 構文解析終了（終了トークンを受け取ったとき） error - 構文規則にないトークンの並びが入力された場合 conflict - shift すべきか reduce すべきか判断できない。また、reduce で適用可能な規則が複数あって判断できない場合もある。 先読みには次の2つの利点がある。 conflict 発生時、構文解析器が正しい判断をするのを助ける。例えば if 文 は先読みすることで then 節や else 節が完了したことが容易にわかる。 状態数を大幅に減らすことができる。C言語で先読みしない構文解析器は約10,000の状態があるが、先読みするとこれを約300に減らせる。 例として、"1 + 2 * 3" という式を構文解析する場合を示す。この場合の生成規則（構文規則）は次の通り。 Rule1: E → E + E （式は式と式の加算である） Rule2: E → E * E （式は式と式の乗算である） Rule3: E → number （式は単なる数値である） Rule4: + は * より優先順位が低い。 APLなどの一部の例外を除いて、一般に加算よりも乗算が優先順位が高い。従って、上記の例は (1 + (2*3)) と解釈するのが正しい。上記のRule4は生成規則ではなく、意味論的規則である点に注意されたい。これを生成規則として表すことも可能である。しかし、意味論的規則が全て生成規則に変換できるわけではない。 単純な先読みのない構文解析器は次のように動作する。 reduce - Rule3 に基づき '1' を式 E にする。その E はスタックに置かれる。 shift - 入力 '+' から Rule1 が適用可能となることを予測しつつ、スタックに退避する。 reduce - Rule3 に基づき '2' を式 E にする。 reduce - スタック上の E+ と新たな入力 E に対して Rule1 を適用して E とする。 shift - 入力 '*' から Rule2 が適用可能となることを予測しつつ、スタックに退避する。 reduce - Rule3 に基づき '3' を式 E にする。 reduce - スタック上の E* と新たな入力 E に対して Rule2 を適用して E とする。 これによって生成される構文木とコードは、Rule4 が考慮されていないため正しくない。 先読みなしで正しく構文解析するには、次のような対処法がある。 ユーザーが括弧付きで式を書く。これが不可能なことも多い。 構文解析器にバックトラック機能を追加し、規則違反が発生したときなどに再試行する。同様の手法はLL法で使われている。 reduce 実施を遅延させるような論理を導入し、どちらの規則を先に reduce させるのが適切かを規則に照らして判断する。LR法がこのような手法を採用している。これによって正しい構文解析が可能となるが、状態数が増え、スタックも深くなる。 先読みのある構文解析器では、次のように動作する。 shift - 入力 '1' を Rule3 が適用されることを予想しつつスタックに退避する。即座には reduce しない。 reduce - '+' を先読みして、スタック上の '1' を Rule3 に基づいて E に reduce する。規則上、'+' の前には E しかないため。 shift - 入力 '+' を Rule1 が適用されることを予測しつつスタックに退避する。 shift - 入力 '2' を Rule3 が適用されることを予測しつつスタックに退避する。 reduce - '*' を先読みして、スタック上の '2' を Rule3 に基づいて E に reduce する。規則上、'*' の前には E しかないため。 ここまでで、スタック上には E + E があり、現在の入力は '*' である。従って、Rule1 を適用する reduce を行うという選択肢と、Rule2 に基づいて shift を行うという選択肢がある。Rule4 によれば '*' の方が優先順位が高いので、Rule2 を予測して '*' を shift する。 shift - 入力 '3' を Rule3 が適用されることを予測しつつスタックに退避する。 reduce - 先読みすると入力が終了しているので、スタック上の '3' を Rule3 に基づいて E に reduce する。 reduce - スタック上の E * E を Rule2 に基づき E に reduce reduce - スタック上の E + E を Rule1 に基づき E に reduce これによって生成される構文木は正しく、先読みしない場合よりも効率的に得られる。以上の方式はLALR法に基づいている。