Yacc
Yacc はBNF(バッカス・ナウア記法)に似た構文規則を入力として受け取り、それに基づいて構文解析器を自動生成する。
Yacc の生成する構文解析器は解析テーブルとそれを用いるプログラムから構成される。構文解析手法はLALRである。
LALR法とは、ボトムアップ構文解析に属する強力なLR法に制限を加えた手法である(Lは入力を左から読むこと、Rは右端導出、その後に付くことのある(1)のような数字は先読みするトークン数(文字数ではない)が1個、を意味する)。コンパクトな解析テーブルでありながらC言語、Javaなど多くのプログラミング言語の構文解析器を実装することができる。アクション内で先読みを行うことでLALR(k)の文法に対応させることも不可能ではないが、普通はLALR(1)の構文解析器を生成する。
構文解析器(A-2)に解析を数字や英字や空白などの1文字単位で行わせると、複雜になりすぎる.しかし、人間が英文から英単語やカッコなどの記号列を、区切り文字(たとえば空白、タブ、改行、コンマ、終止符)やその列を目印に抽出して意味を判断しているのと同様の発想ができる。すなわち、区切り記号列でソースを切っていくと、「print」のような語、「1999」のような10進数、「"Hello, World."」といった文字リテラル、「++」といった演算子、「}」や「;」など意味のある区切り文字など、各種の文字列が取り出せる。これをトークンという。ここまでの下位の文法処理を上記字句解析器(A-1)に行わせ、一方、構文解析器(A-2)はトークンから出発して句、文、ブロック、プログラムなどを認識する上位の文法処理に専念させる。この分業化により、それぞれの定義と処理が簡潔になった。
いま作ろうとする電卓は、内部的に64ビット浮動小数点で動作し、整数と演算子、カッコなどからなる式を与えて改行すると計算結果を答えるという会話を繰り返すものである。
目的とする出力例
小数はサポートしないが、「314/100」のように整数の除算で小数にあたる数を与えることはできる。
マクロ定義や文法規則のアクション関数をC言語で記述できるパートである。構文解析器プログラム先頭にそのままコピーされる。 例:
という計算結果と次のプロンプトが標準出力に見事に出てくる。スタックは、
になった。
またまたEOLを読んで今度はシフトする。
これはdialogueの再帰的な規則のひとつ
の3個のトークンとマッチするので、還元が実行されてスタックから3個消えて左辺のグループdialogueが押し込まれ、
だけになる。
このあと入力ファイルにまだ演算させたい式を書いた行が書かれていれば、上と同様に計算され結果が表示されるであろう。が、いまの場合はファイル終端になってyylex()が
Bye.
と表示して0を返す。すると内部的には$endという特殊トークンがシフトされ
となるが、これが暗黙に定義されている規則0
とマッチするので、パーサは$accept(受理)を得て目的を成功裏に果たしたということでスタックをすべてクリーンアップして,yyparse()呼出元に制御を返す。
このようにYaccの作るパーサは、解析した文字列が最後に%startの記号(デフォルトは最初に書いた規則の左辺)に見事にマッチし文法に合格したと判断されたとき正常に戻り値0でyyparser呼出元に帰る。また、YYACCEPTマクロを実行すれば即正常で帰る。
構文解析エラーが起これば異常(戻り値1)でyyparser呼出元に帰る。また、YYABORTマクロを実行すれば即異常(戻り値1)で帰る。
途中、意味値をユーザ定義のアクションや関数で出力すれば、計算の目的が果たせたことになる。