Yacc
Yacc には構文解析器の機能しかないが、特定の名前の未実装関数 yylex を呼んでトークンを毎度要求する。この字句解析器関数 yylex を作って動的にトークンを生成して、1回呼ばれるごとに1個のトークン種類を戻り値で返してやればよい。さらにそれが数値や文字列のように意味値をもつトークンのときは、意味値も変数 yylval にセットして同時に返す。ユーザはこの字句解析器関数 yylex の処理を実装することになる。
字句解析器(A-1)のほうも、合理的な開発を目的とし、Yacc に似た規則定義を与えれば字句解析器を自動生成してくれる便利な道具として、Lexや Flexなどのレキシカルアナライザジェネレータがある。
そこで Lex などの字句解析器生成ツールを利用するなら、それに字句文法定義を与えて生成させたC言語ソースである字句解析器が yylex 関数を含んでいるので、Cコンパイルで Yacc 出力と一緒にそれをリンクして組み込む。
ユーザは変換仕様をYacc文法ファイルとしてのテキストファイルを作っておく。
yaccコマンド
は、fileName で与えたYacc文法ファイル(たとえば"wiki_samp1.y")(伝統的に拡張子は.yがつけられることが多かった)から構文規則を入力し、それに基づくLALR構文解析器になるC言語のソースプログラム(通常"y.tab.c")を出力する。-rオプションでコード部分だけ"y.code.c"ファイルに独立させることもできる。
このC言語ソースプログラムにはLALR解析テーブルおよびドライバルーチンが含まれる。 特に、構文解析全体を行う関数にはyyparse()という名前がついている。よってこのプログラムにあらかじめ適宜yyparse()を呼び出すmain()関数を加えておくなどして(それはYacc文法ファイル中の「追加Cプログラム部」での記述でも可能)、ほしい変換プログラムを完成することができる。
-dオプションで生成するヘッダファイル"y.tab.h"は、Lexがトークン処理を行うときに、Yaccが割り当てたトークン値(256~)を正しく使うよう、Lex実行時に与える。
-vオプションにより、生成パーサの文法、終端記号、非終端記号、状態の種類とそれぞれの判定パターンおよびそのシフト、還元等の措置や状態遷移先といった解析テーブル情報が、人に分かりやすい形でテキストファイル"y.output"に出力される。(この"y.output"リストの見方が分かりにくい。ピリオド「.」(Yaccの種類によっては下線「_」)は現在のカーソル位置であることなどは知らないと分からないであろう。
実際にはこの課題プログラムに
を与えたとして値も追跡したい。この場合「後半」のyylex()プログラムは構文解析器実行時に、次のトークン群、およびあれば以下でカッコ《》内に付記している意味値を、要求するたびに1個ずつ構文解析器関数yyparser()に返してくるはずである。
最初に、スタックが空
の状態で内部にもつ状態番号を0にして%startで示されているdialogueが調べられる。適用できる規則は右辺が空の規則1なのでこれが適用される。状態スタックにはその0がはいる。このスタック状態を次のように図示できる。
そして状態番号は1に行く。yylex()の中で初回だけ、
と出し、prompt()というユーザ定義関数によって、
と表示する。電卓ユーザまたはファイルから、
が入力されると、yylex()関数はトークン1個ずつyyparser()に返していく。
まずNUM《10》が読まれ,状態1での適用規則が探される。還元できる規則とはスタック右端がマッチしないので、ありえる記号としてそのテーブルに登録されている「NUM」に対する操作が行われる。すなわち、スタックにはじめてそれが1個シフトで入れられ状態5になる.
規則6
(単独のNUMはexpr)だけがマッチするからこれが適用され、
に還元されてスタック内容が入れ替わる。
(この規則6にアクションは書いてなかったが、戻り値がないのではなく、Yaccの空でない規則に対するデフォルトアクション