Yacc
LexとYaccで共通の状態変数を設けておき、Yaccの{ }内に記述するアクションで、区別したい何かのフェーズなどの状態に応じて状態変数値を変えてやる。そうすればLexの生成したレキシカルアナライザは、実行時にまさに読んでいる入力トークン列による状態変数値に応じて、ある入側トークンを別々のトークンに動的に変換し分けてYaccの生成したパーサに渡す、という方法である。非常にダイナミックな技である。
次に「シフト/還元衝突」であるが、このときYaccは標準で、(特に演算子優先規則で指定されていないかぎり)シフトを選ぶようにできている。たとえば上記の例ではexpr2不成立のときにstmt2を実行するようにパーサのテーブルが作られる。このように距離の近い記号の関係を優先するよう動作するのは、多くのプログラミング言語のコンパイラに向いているといわれているが、後述のように注意が必要である。
構文上期待外のトークンがくるとアクションが見つからないので、パーサは、状態を戻して、errorという特定トークンのアクションがその状態に定義されているかどうか調べ、あれば実行する。
y.outputにはまた、状態番号に対して衝突種類、トークンに対して実行されないアクションを囲むカッコ「[ ]」が出力されているので、場所や影響が分かる。
原因調査が難航している場合は、問題のある文法要素の周辺の定義だけを抽出した“ミニ文法”をYacc定義し、障害がぎりぎり再現する境目を探しすことで切り分けるアプローチもある。
混乱を招いているトークンを含む連続した2個以上のトークンを、Lex段階で1個の別トークンにまとめて明瞭化する。
上記場面がパーサのシフトや還元の状態だけでは記述しきれないとき、Lex段階でその場面を識別するための内部状態をもち、はいってくるトークンを見ながら状態遷移することで問題の箇所を検出する。そして、検出時には別のトークンに変更して出したり、特別なトークンを挿入することで明瞭化する。
上記明瞭化の努力によって、Bison実行で報告される衝突数が減少した場合は、効果が出ている場合が多いが、減少しなくても、特定の入力に対しての処理がエラーから正常に変わって改善している場合もある。増加した場合は逆効果として調べる必要がある。
入力言語があまりに複雜な場合、またはプリプロセッサ命令を含んでいる場合、パースを2段階の直列構成にするという大胆な解決策もある。すなわち、1段階めの前処理Yaccパーサは曖昧性を解決するだけのための簡単な文法で動く。その出力の曖昧性を解決したトークン列を2段階めの本処理Yaccパーサに渡す。3段以上にすることが有効な場合もあろう。文法の性格によっては、この構成にすることで、むしろそれぞれをすっきりさせることができる(エラー位置の表示処理は複雜になる)。
最大3回まで戻しても見つからないときには入力テキストが途中でもそこでパースを打ち切ってしまう。これを利用してたとえば命令リストにerrorトークンのみの右辺をOR(|)結合しておけば、ある命令に属するオペランドに期待外トークンがあっても、そこで警告を出して次の命令以降のパースを続行してくれる、使いやすいコンパイラを作ることができる。ただ最大3回固定なので、深さの差3以内の上位にerrorを処理する構文を書いておかなければ利用できない。またはy.tab.cファイルの変数yyerrstatusの初期値を10などと増やしてやる必要がある。
Yacc実行時に報告されるシフト/還元衝突は、シフトが選ばれるだけで十分と確信できるケース以外は、実は本来0件にしておくべきである。なぜならパーサ実行時にシフトが選ばれて動作することにより、入力されたトークン列によっては行き止まりになる。すなわち期待外のトークンとされ、上記のエラー処理に飛んでしまうからである。Yaccは衝突に対応する枝分かれをすべてバックトラックでたどって解空間を全探索するようにはできていないのである。このため、衝突を残しておくとパーサを当然通ると思った入力が通らず苦労することになる。
文法規則部には1個以上のYacc文法規則
を記述しなければならない。
ここで,変換結果とは、規則が記述する非終端記号。 構成要素とは、この規則がマッチするかを判定するために文法どおりの順に並べられる、0個以上の終端記号や非終端記号の列。 例:
同じ変換結果を生む複数の規則は次のように簡略に連続記述できる。
「;」は省略可能。
見て分かるとおり、構文規則は読み書きしやすいBNF記法になっている。
規則にマッチするたびに行ないたい動作、たとえば変換結果の意味値("$$")をその構成要素の意味値("$1", "$2", ...)から計算すること、あるいは値を表示出力などは、C言語命令によるアクションとして「{ }」に囲って、マッチ直前に実行したい構成要素の直前に付して、あるいは規則適用時実行でよければその規則の最後の構成要素のあとに記述する。
規則は再帰的に定義できる。例で
の規則6は、「NUMと名付けた数値トークンがきたら、それ1個単独でも式exprになる」と宣言している。
いわばサブルーチンに行って帰って来たような状態である。還元を起動する条件として、解析テーブルに「.」(バージョンによっては「$default」)と書いてあれば無条件に実行されるが、「MINUS」などと先読みトークン値が与えられているときはそれが一致したときに限って実行される。
遷移(goto)生成した非終端記号をshiftする。次の終端記号はこのあとのshiftに任される。先読みトークンは消費されない。
受理(accept)構文解析の正常終了であり、yyparse()から戻り値0で正常復帰する。この動作はyylex()から0か負が返って次の終端記号が終わりを意味する$endになったとき、規則0「$accept: 全体の非終端記号名 $end」によりスタックが正しく$acceptの1個に還元できたときに行われる。
エラー(error)解析表の空欄、すなわち次に現れてはならない終端記号があったときマッチされるべく展開される。すなわち、構文解析器はエラーを検出すると、「error」トークンが正常に合致する規則が見つかるまでスタックをポップアップしながら戻っていく(最後までみつからなければyyparse()から1で異常復帰する)。見つかるとそこに「error」というトークンがあったとみなして、検出される規則のアクションを実行する。そして、先読みトークンはエラーを起こしたトークンに進める(リセット)。Yaccはエラー多発防止のため、トークン3個の読込みおよびシフトが成功するまではこのエラー状態にとどまるが、ユーザがアクションでyyerrok(エラー回復)マクロを実行すればその途中でも正常状態に戻る。