Yacc
上の例では電卓のようにその場で値を求めることはできる。しかしYaccを利用してコンパイラを開発する場合は、このあとのコード生成部(2)に渡す抽象構文木(abstract syntax tree、AST)というデータの構造を構築していかなければならない。たとえばアクションでユーザ定義関数を呼び出し、
のように左辺と右辺を「+」で結合してそのポインタを返すような操作を行わせることで可能である。すると、構文解析が末端から順次還元を行って根まで統合されて停止したとき、同じ構造の抽象構文木が根まで完成して得られることになる。
このように葉から順に根に至る構文解析法をボトムアップ構文解析という(ここでは木を上下逆さまにして根は一点にしたイメージなので“ボトムアップ”という)。
である 。 可能な還元はそのままいくつか行ったあとはじめて、トークンはシフトされる。
構文解析器は、入力されたトークン列をスタックに入れては次々に上記のように規則適用を試みて、成功するたびに還元していく。そしてテーブルの指定によって状態遷移していく。
入れ子の下位の非終端項目(グループ)が確定すれば、その値がその非終端項目に該当する上位の未確定な右辺の項に代入されて、その左辺のグループがスタックにプッシュされることで、だんだん上位に向かって解決されていく。
トークンを受けた状態番号を状態スタックに出し入れすると完全同期して、(あれば)そのトークンの意味値も意味値スタックに出し入れする。これにより、アクションによる意味値の計算を保証している。
最終目標は、全部読みきったときに、"%start"で指定され解析をスタートした非終端記号(デフォルトは最初に書かれている規則の左辺)が、変換の結果$accept 1個に還元できたかどうか調べることである。
もしそれが(エラー発生がerrorトークンで解決できなかったか、YYABORTマクロを実行されたなどの原因で)できなかったのなら、入力文字列はこの文法に適合しないエラーということが分かる(入力文字列が正しければYacc文法ファイルが間違いということもある)。
もしできたなら、この文法に適合したと判断でき,それに直接あるいは再帰的に入れ子で含まれる全部の要素に該当する入力トークン列が確定する。電卓の計算結果やコンパイラのための抽象構文木といった応用のための)意味値ができていれば、それもアクションで、都度あるいは最後に、表示したりファイルに書き出すことができる。
説明は日本語文書では良書「Cコンパイラ設計(yacc・lexの応用) 」のほかに見つけにくいが、英語ではいくつかある )
-tオプションを指定すると、生成パーサが実行されるときに、状態番号、スタック状態、読んだトークン、意味値の演算の様子、変化した状態番号などが、逐一標準エラー出力に表示されるのでデバッグに役立つ(コンパイルオプションも関連)。
次に、Yaccで生成し構文解析器ソースプログラム("y.tab.c")をccコマンドやgccコマンドなどでコンパイルする。このとき、Lexも利用したのであればその出力("lex.yy.c")も並べて指定する。これらに対応するライブラリもコンパイルオプションによってリンクさせる。
コンパイルで作成された変換プログラムを実行すると、標準入力(FILEポインタyyinで変更可能)(yywrap関数で複数ファイルの連結が可能)から変換するファイルを読み込む。これを字句解析器関数yylex()によってトークンにして構文解析が実行される。変換結果やエラーは、Yaccのアクション部や呼ばれる関数で書いた処理によりそれぞれ出力される。syntaxエラーなどは通常標準エラー出力に出るが、形式や出力先をエラー報告関数yyerror()でカスタマイズできる。Yaccのオリジナルなエラーメッセージでは情報が貧弱である。開発・運用で頭を抱えないようにするためには、特に発生場所のファイル名、行番号およびトークン番号などをエラーメッセージに追加するようにyyerror()を作っておくことが望ましい。