Yacc
のような左再帰の形で定義することである。規模が大きくなる場合はスタックサイズの定義マクロYYMAXDEPTHの値を大きく指定する.)
またまた先読みしていた「-」を読み直す。今度はさすがに適用できる規則がなくシフトされる。
dialogue  expr《610》  '-'
次にNUM《40》が読まれてもシフトするしかない。
dialogue  expr《610》  '-'  NUM《40》
この状態で先読みトークンに、電卓ユーザが押した改行EOLがくる。
dialogue  expr《610》  '-'  NUM《40》  (←次にEOLが来る予定)
この状態において、演算子優先度が関係ない先読みEOLに遠慮する必要がないので、
がマッチとして還元が実行されて、スタックから3個消える。その代わり、意味値が610-40=570と計算されたグループexprが押し込まれるので、
dialogue  expr《570》
のようにまた2個分縮む。
先読みしていたEOLを読み直す。すると、この状態でexprには、
しかマッチせず、アクションのprintf関数が実行されて,
?>   Ans = 570
?>
という計算結果と次のプロンプトが標準出力に見事に出てくる。スタックは、
dialogue  qa
になった。
またまたEOLを読んで今度はシフトする。
dialogue  qa  EOL
の3個のトークンとマッチするので、還元が実行されてスタックから3個消えて左辺のグループdialogueが押し込まれ、
だけになる。
このあと入力ファイルにまだ演算させたい式を書いた行が書かれていれば、上と同様に計算され結果が表示されるであろう。が、いまの場合はファイル終端になってyylex()が
<tt>  Bye.</tt>
と表示して0を返す。すると内部的には$endという特殊トークンがシフトされ
dialogue  $end
となるが、これが暗黙に定義されている規則0
とマッチするので、パーサは$accept(受理)を得て目的を成功裏に果たしたということでスタックをすべてクリーンアップして,yyparse()呼出元に制御を返す。
このようにYaccの作るパーサは、解析した文字列が最後に%startの記号(デフォルトは最初に書いた規則の左辺)に見事にマッチし文法に合格したと判断されたとき正常に戻り値0でyyparser呼出元に帰る。また、YYACCEPTマクロを実行すれば即正常で帰る。
構文解析エラーが起これば異常(戻り値1)でyyparser呼出元に帰る。また、YYABORTマクロを実行すれば即異常(戻り値1)で帰る。
途中、意味値をユーザ定義のアクションや関数で出力すれば、計算の目的が果たせたことになる。
上記 wiki_sample.y 前半に引き続き後半として記述すべき追加Cプログラム例は、以下のとおりである(ここではユーザがyylex()関数を手で書いているが、同じ機能のプログラムは、FLexに字句規則を与えて自動生成させた方がスマートであろう)。
上の例では電卓のようにその場で値を求めることはできる。しかしYaccを利用してコンパイラを開発する場合は、このあとのコード生成部(2)に渡す抽象構文木(abstract syntax tree、AST)というデータの構造を構築していかなければならない。たとえばアクションでユーザ定義関数を呼び出し、
のように左辺と右辺を「+」で結合してそのポインタを返すような操作を行わせることで可能である。すると、構文解析が末端から順次還元を行って根まで統合されて停止したとき、同じ構造の抽象構文木が根まで完成して得られることになる。
このように葉から順に根に至る構文解析法をボトムアップ構文解析という(ここでは木を上下逆さまにして根は一点にしたイメージなので“ボトムアップ"という)。
この方式では、次の有名な例のように、同じ入力を同じ構文規則で複数の解釈ができてしまう曖昧性が避けられない。
Yaccではyaccコマンド実行時に解釈が複数生じる曖昧なケースを発見した場合に「還元/還元衝突警告」または「シフト/還元衝突警告」を出す。これによって、文法を作成中なら文法を、そうでなければ構文規則を改良するきっかけが得られる。
まず「還元/還元衝突警告」が出た場合であるが、パーサが正しい処理をできない構文要素が生じてしまうので、文法、または構文規則のYacc定義を直した方がよい。
ある非終端記号から別の非終端記号に至る呼び出しパスが複数あれば、それは間違いなので直す。
しかし元の言語が複雜すぎてうまく直せない場合は、片方を実体は同じでも別の名前を付けるトークン由来で構成するようにし、Lex側がどちらのトークンをYaccパーサに出すかは状態に応じて変えるようにコーディングしておく方法がある:
状態がトークン列だけから一意に決められるならLex単独で処理できる。しかし、Yaccが実行時にあるルールのマッチを検出したときにはじめて状態を変えたいという複雜なケースでは、次のようにする。LexとYaccで共通の状態変数を設けておき、Yaccの{ }内に記述するアクションで、区別したい何かのフェーズなどの状態に応じて状態変数値を変えてやる。そうすればLexの生成したレキシカルアナライザは、実行時にまさに読んでいる入力トークン列による状態変数値に応じて、ある入側トークンを別々のトークンに動的に変換し分けてYaccの生成したパーサに渡す、という方法である。非常にダイナミックな技である。
次に「シフト/還元衝突」であるが、このときYaccは標準で、(特に演算子優先規則で指定されていないかぎり)シフトを選ぶようにできている。たとえば上記の例ではexpr2不成立のときにstmt2を実行するようにパーサのテーブルが作られる。このように距離の近い記号の関係を優先するよう動作するのは、多くのプログラミング言語のコンパイラに向いているといわれているが、後述のように注意が必要である。
構文上期待外のトークンがくるとアクションが見つからないので、パーサは、状態を戻して、errorという特定トークンのアクションがその状態に定義されているかどうか調べ、あれば実行する。最大3回まで戻しても見つからないときには入力テキストが途中でもそこでパースを打ち切ってしまう。これを利用してたとえば命令リストにerrorトークンのみの右辺をOR(|)結合しておけば、ある命令に属するオペランドに期待外トークンがあっても、そこで警告を出して次の命令以降のパースを続行してくれる、使いやすいコンパイラを作ることができる。ただ最大3回固定なので、深さの差3以内の上位にerrorを処理する構文を書いておかなければ利用できない。またはy.tab.cファイルの変数yyerrstatusの初期値を10などと増やしてやる必要がある。
Yacc実行時に報告されるシフト/還元衝突は、シフトが選ばれるだけで十分と確信できるケース以外は、実は本来0件にしておくべきである。なぜならパーサ実行時にシフトが選ばれて動作することにより、入力されたトークン列によっては行き止まりになる。すなわち期待外のトークンとされ、上記のエラー処理に飛んでしまうからである。Yaccは衝突に対応する枝分かれをすべてバックトラックでたどって解空間を全探索するようにはできていないのである。このため、衝突を残しておくとパーサを当然通ると思った入力が通らず苦労することになる。
Yacc実行時になんらかの衝突が報告されるとき、および、上記パーサ実行時に正しいはずの入力がsyntax errorとなるときの主な対処方法には、次のようなものがある。
syntax error発生時に少なくともそのときのトークン値、状態スタック中の状態番号列およびソースファイル上の行番号・文字番号を出力するように作っておくことで、正確な調査を可能にする。
ある非終端記号から別の非終端記号に至る呼び出しパスが複数あれば、それは間違いなので直す(前述)。
「トークンまたは空である」といった非終端記号をひとつの構文右辺の中に複数並べることによって、衝突が生じていることがある。ひとつの右辺の中には省略のないトークンだけを使うようにする。そして、省略する、しないのすべての組合せは、右辺の種類として列挙してOR(|)結合する形に変更する。人間には等価ないし汚くなるように思えても、Yaccにとっては明瞭化になる。
リストのリストは、繰り返し要素にinなどの接頭辞的なトークンが伴わない定義などでは、要素がどの段階のリストに属するのかという曖昧性を生じる。この場合、リストの段階数を減らすように工夫して明瞭化する。
問題の非終端記号を使う場面ごとに、元が同じ文字列でも別のトークンから構成するように、定義を変更して明瞭化する。そのためにそのトークンを上述のようにLex段階で、場面に応じて変換し分ける。
パーサ実行時の期待外トークンで、あるトークンが複数の場面でどう絡んでいるかを調べるには、y.outputファイルでその状態番号を見つけて熟読し、その状態番号へ飛んでくる状態を1, 2段階さかのぼってたどってみると見えてくるものである。y.outputにはまた、状態番号に対して衝突種類、トークンに対して実行されないアクションを囲むカッコ「[ ]」が出力されているので、場所や影響が分かる。
原因調査が難航している場合は、問題のある文法要素の周辺の定義だけを抽出した“ミニ文法"をYacc定義し、障害がぎりぎり再現する境目を探しすことで切り分けるアプローチもある。
混乱を招いているトークンを含む連続した2個以上のトークンを、Lex段階で1個の別トークンにまとめて明瞭化する。
上記場面がパーサのシフトや還元の状態だけでは記述しきれないとき、Lex段階でその場面を識別するための内部状態をもち、はいってくるトークンを見ながら状態遷移することで問題の箇所を検出する。そして、検出時には別のトークンに変更して出したり、特別なトークンを挿入することで明瞭化する。
上記明瞭化の努力によって、Bison実行で報告される衝突数が減少した場合は、効果が出ている場合が多いが、減少しなくても、特定の入力に対しての処理がエラーから正常に変わって改善している場合もある。増加した場合は逆効果として調べる必要がある。
入力言語があまりに複雜な場合、またはプリプロセッサ命令を含んでいる場合、パースを2段階の直列構成にするという大胆な解決策もある。すなわち、1段階めの前処理Yaccパーサは曖昧性を解決するだけのための簡単な文法で動く。その出力の曖昧性を解決したトークン列を2段階めの本処理Yaccパーサに渡す。3段以上にすることが有効な場合もあろう。文法の性格によっては、この構成にすることで、むしろそれぞれをすっきりさせることができる(エラー位置の表示処理は複雜になる)。