Yacc
Yacc は yet another compiler compiler(またひとつのコンパイラコンパイラ)に由来する。コンピュータ黎明期には「自動プログラミング」と呼ばれたプログラミング言語処理系の技術の進展の方向として、当時、機械語プログラムを生成するコンパイラの次はコンパイラを生成するコンパイラコンパイラであろう、ということで盛んに研究がされており、そのためコンパイラコンパイラを名乗る研究が他にもあれこれ存在した。
パーサはコンパイラの全てではないので、コンパイラコンパイラと呼ぶには Yacc のようなパーサジェネレータは不足と言えなくもないが、特段意識されることは少ない。
そして規則9は「expr '+' exprという並びもexprである」という意味で自分expを記述しているから、再帰的な定義である。すると、規則は繰り返して適用できるから、
など1個以上のNUMの加算式が、わずか2個の規則だけで表現できる。構文解析器実行時にこのうちのどれがやってきてもexprにマッチすると認識できることになる。
トークン値は実際にはASCIIコードと重ならない256以上の整数であるが、Yacc文法記述者はその値を知らなくてよく、NUM, EOLといった通常大文字で記述する記号で宣言と規則で統一的に記載すればよい。
トークンの意味値が伴う種類のトークンは、とりうる型は"%union"によって列挙して定義しておく。そして"%token"で"<ldval>"のように共用体のどのメンバーであるかを明示できる。アクション中で"$$"と書かれた意味値はC言語になったとき"lval.ldval"のように共用体中の要素を指すように自動変換される。このように意味値が伝わっていく。
課題プログラムのYacc構文定義は以下のように作ることができる。これをたとえば、ファイル "wiki_sample.y" に入れ、Lex出力ソースに代えて後述の「後半」内容をつないで作成し、上記#コマンド例のように実行すればよい。