Yacc
Yacc(英: yet another compiler compiler、ヤック)はパーサジェネレータの一つである。1970年代にAT&TでUNIX用にスティーヴン・カーティス・ジョンソンが開発した。
Yacc文法ファイルwiki_samp1.y(後述)から構文解析実行プログラムwiki1.exeを実行するまでの実際のコマンド例(Windows Cygwin環境)を示す。
GNUコマンドプログラムbison はYacc上位互換であって、オプション -y によりYacc互換の処理をしてくれる。 解析させるファイルindata.txtの中には、たとえばテスト用の文字列「10+20*30-40《改行》」を入れておく。もちろん「 < indata.txt」を除いて対話的に手入力してもよい。
Yaccが生成する構文解析器は、内部にスタックをもっている有限状態機械である。次のトークンを1個読み(先読みトークン;look-ahead token)変数yycharに入れるが、すぐにスタックにシフトするわけではない。構文解析器はその前に、マッチする規則があるかどうか、構文解析器の現在の状態番号(0,1,...)(これは常にスタックの最新=右端のものである)のもとでYaccが生成しておいた解析テーブルを検索して調べる。スタックの右端と各規則を合わせてみて解析する(右端導出)。
構文解析器は終了条件まで以下を繰り返す処理である:
現在の状態で先読み(lookahead)トークンが必要で現在それがセットされていなければ、yylex()を呼んで先読みトークンをもらう。 そして現在の状態と先読みトークンによって決まるアクションを実行する。
Yaccにより解析テーブルに展開されるこの機械のアクションの種類は、
シフト(shift)先読みトークンが必要で、それをスタックに(右から新しいものを押し込むイメージで)1個追加(プッシュ)する。先読みトークンは消費される。
還元(reduce)n番めの規則の右辺にある記号群から左辺のグループ(非終端記号)への置き換えを適用して、右辺に対応した数のスタック要素をポップアップ(右に出して消すイメージ)する。スタックのサイズは縮む(まさにreduceする)。そして、左辺であるグループ(非終端記号)を1個プッシュしなおす。このグループに意味値があれば、戻り値からセットされる(電卓の例でいえば中間計算結果)。同時に、状態は(現在の状態ではなく)スタックのトップ(最も右)にある状態番号にされる。