Yacc（英:yet another compiler compiler、ヤック）はパーサジェネレータの一つである。1970年代にAT&TでUNIX用にスティーヴン・カーティス・ジョンソンが開発した。
Yacc はyet another compiler compiler（またひとつのコンパイラコンパイラ）に由来する。コンピュータ黎明期には「自動プログラミング」と呼ばれたプログラミング言語処理系の技術の進展の方向として、当時、機械語プログラムを生成するコンパイラの次はコンパイラを生成するコンパイラコンパイラであろう、ということで盛んに研究がされており、そのためコンパイラコンパイラを名乗る研究が他にもあれこれ存在した。
パーサはコンパイラの全てではないので、コンパイラコンパイラと呼ぶにはYacc のようなパーサジェネレータは不足と言えなくもないが、特段意識されることは少ない。
まず一般的なコンパイラの構成について簡単に説明する。
ソースコードを中間表現あるいは機械語に変換するコンパイラは、ソースコードを入力として受け取り、構文木を構築して出力する構文解析部(A)と、その構文木を入力として受け取り、目的の中間表現ないし機械語のコードを生成して出力するコード生成部(B)からなる。
コンパイラ ├構文解析部(A) │ ├字句解析器(A-1) ←〔ソースコード〕（文字列） │ │ ↓ │ │ 〔トークン列〕 │ │ ↓ │ └構文解析器(A-2) │ ↓ │ 〔構文木〕 │ ↓ └コード生成部(B) →〔目的コード〕
このうち構文解析部(A)は、文字列からトークンを切り出しトークン列とする字句解析器（レキシカルアナライザ、トークナイザ、スキャナ、図のA-1)と、構文規則に従ってトークン列に対し構文解析をおこない、構文木を出力する（狭義の）構文解析器（パーサ，パーザ、図のA-2)から成る。（必ずしもこのようにする必要はないが、典型的な構成としてはこのようにする）
構文解析器は直接書くこともできるが、煩雑になる部分があり、特にボトムアップ構文解析のプログラムを手で書くのは現実的ではない。そういった構文解析器を、機械可読な構文規則群から自動生成してくれるツールがパーサジェネレータである。YaccはLALR、通常LALR(1)の構文解析器を生成する。
〔構文規則〕 ↓パーサジェネレータ（Yaccなど） ↓〔構文解析器〕
Yacc はBNF（バッカス・ナウア記法）に似た構文規則を入力として受け取り、それに基づいて構文解析器を自動生成する。
Yacc の生成する構文解析器は解析テーブルとそれを用いるプログラムから構成される。構文解析手法はLALRである。
LALR法とは、ボトムアップ構文解析に属する強力なLR法に制限を加えた手法である（Lは入力を左から読むこと、Rは右端導出、その後に付くことのある(1)のような数字は先読みするトークン数（文字数ではない）が1個、を意味する）。コンパクトな解析テーブルでありながらC言語、Javaなど多くのプログラミング言語の構文解析器を実装することができる。アクション内で先読みを行うことでLALR(k)の文法に対応させることも不可能ではないが、普通はLALR(1)の構文解析器を生成する。
構文解析器(A-2)に解析を数字や英字や空白などの1文字単位で行わせると、複雜になりすぎる．しかし、人間が英文から英単語やカッコなどの記号列を、区切り文字（たとえば空白、タブ、改行、コンマ、終止符）やその列を目印に抽出して意味を判断しているのと同様の発想ができる。すなわち、区切り記号列でソースを切っていくと、「print」のような語、「1999」のような10進数、「"Hello, World."」といった文字リテラル、「++」といった演算子、「}」や「;」など意味のある区切り文字など、各種の文字列が取り出せる。これをトークンという。ここまでの下位の文法処理を上記字句解析器(A-1)に行わせ、一方、構文解析器(A-2)はトークンから出発して句、文、ブロック、プログラムなどを認識する上位の文法処理に専念させる。この分業化により、それぞれの定義と処理が簡潔になった。
Yacc には構文解析器の機能しかないが、特定の名前の未実装関数yylex を呼んでトークンを毎度要求する。この字句解析器関数yylex を作って動的にトークンを生成して、1回呼ばれるごとに1個のトークン種類を戻り値で返してやればよい。さらにそれが数値や文字列のように意味値[1]をもつトークンのときは、意味値も変数yylval にセットして同時に返す。ユーザはこの字句解析器関数yylex の処理を実装することになる。
字句解析器(A-1)のほうも、合理的な開発を目的とし、Yacc に似た規則定義を与えれば字句解析器を自動生成してくれる便利な道具として、Lex[2]やFlex[3]などのレキシカルアナライザジェネレータがある。
そこでLex などの字句解析器生成ツールを利用するなら、それに字句文法定義を与えて生成させたC言語ソースである字句解析器がyylex 関数を含んでいるので、CコンパイルでYacc 出力と一緒にそれをリンクして組み込む。これにより、ソーステキストの字句解析と構文解析を両方行って、規則のアクション部（あるいはさらにそれに呼ばれるユーザ作成のC言語関数）に書かれた計算の結果や、コンパイルの生成に使われる抽象構文木の構造体データ、あるいは各種表示が出力される、変換プログラムが完成する。GNUプロジェクトでは、Flex という名前で機能を提供している。
ちなみに、Yacc の上位機能をもちやや方式の異なるJava 言語向けジェネレータJavaCC では、両方の定義・処理機能を併せもっている。Java向けではまた、字句解析器ジェネレータJFlexと構文解析器ジェネレータCUPとを組みあわせて用いることも行われている[4]
Yacc とLex はよく似た文法定義を持つ。組み使い、組で解説することがある。Lex とYacc の機能はIEEEPOSIX 1003.1-2008（かつては1003.2）で標準化している[5]。
Yaccは古典的なコンパイラコンパイラでありながら人気があり、今でもよく産業用や教育用に使われる。コンパイラを開発する目的に限らず、独自の設定ファイルの解析、プログラミング言語コンバータ開発、簡易電卓の例題による学習などに使われている。
YaccはほとんどのUNIXシステムで、デフォルトのパーサジェネレータとして利用可能だった。Yaccと上位互換を持つソフトとして、よく使われているGNUプロジェクトのBisonをはじめ、Barkeley Yacc（byacc）、BYACC/J、MKS Yacc、Abraxas pcyaccがある。いずれの派生版も改良されてはいるが基本的な部分は変わらない。むしろ現在yaccコマンドはbisonコマンドがラップし、-y オプションを付けることでPOSIX Yaccモードに縮小した機能で動くようになっている。
またYaccはJava、Ratfor、EFL、ML、Ada、Limboなどの言語を生成する版としても移植されている。
このうちJava向けには、Yaccと同様のLALR方式のjacc、CUP (JavaCUP)、SableCC、jay、またYaccと異なる方式では、LL(k)方式のJavaCCとCoco/R、そしてLL(*)方式のANTLRがある[6]。Bisonのラッパで、アクション部をJava言語で書けてJavaクラスによる構文解析器プログラムを生成できるJBisonというものもある。
オリジナルのYaccはOpenSolarisの一部として更新されており、オープンソース化されている。ソースコードはPlan 9やOpenSolarisの標準的なディストリビューションに含まれる。
ユーザは変換仕様をYacc文法ファイルとしてのテキストファイルを作っておく。
yaccコマンド
yacc [-dlrtv ] [-bprefix]fileName
は、fileName で与えたYacc文法ファイル（たとえば"wiki_samp1.y"）（伝統的に拡張子は.yがつけられることが多かった）から構文規則を入力し、それに基づくLALR構文解析器になるC言語のソースプログラム（通常"y.tab.c"）を出力する。-rオプションでコード部分だけ"y.code.c"ファイルに独立させることもできる。
このC言語ソースプログラムにはLALR解析テーブルおよびドライバルーチンが含まれる。特に、構文解析全体を行う関数にはyyparse()という名前がついている。よってこのプログラムにあらかじめ適宜yyparse()を呼び出すmain()関数を加えておくなどして（それはYacc文法ファイル中の「追加Ｃプログラム部」での記述でも可能）、ほしい変換プログラムを完成することができる。
-dオプションで生成するヘッダファイル"y.tab.h"は、Lexがトークン処理を行うときに、Yaccが割り当てたトークン値（256～）を正しく使うよう、Lex実行時に与える。
-vオプションにより、生成パーサの文法、終端記号、非終端記号、状態の種類とそれぞれの判定パターンおよびそのシフト、還元等の措置や状態遷移先といった解析テーブル情報が、人に分かりやすい形でテキストファイル"y.output"に出力される。（この"y.output"リストの見方が分かりにくい。ピリオド「.」（Yaccの種類によっては下線「_」）は現在のカーソル位置であることなどは知らないと分からないであろう。説明は日本語文書では良書「Cコンパイラ設計(yacc・lexの応用)[7]」のほかに見つけにくいが、英語ではいくつかある[8][9][10][11]）
-tオプションを指定すると、生成パーサが実行されるときに、状態番号、スタック状態、読んだトークン、意味値の演算の様子、変化した状態番号などが、逐一標準エラー出力に表示されるのでデバッグに役立つ（コンパイルオプションも関連）。
次に、Yaccで生成し構文解析器ソースプログラム（"y.tab.c"）をccコマンドやgccコマンドなどでコンパイルする。このとき、Lexも利用したのであればその出力（"lex.yy.c"）も並べて指定する。これらに対応するライブラリもコンパイルオプションによってリンクさせる。
コンパイルで作成された変換プログラムを実行すると、標準入力（FILEポインタyyinで変更可能）（yywrap関数で複数ファイルの連結が可能）から変換するファイルを読み込む。これを字句解析器関数yylex()によってトークンにして構文解析が実行される。変換結果やエラーは、Yaccのアクション部や呼ばれる関数で書いた処理によりそれぞれ出力される。syntaxエラーなどは通常標準エラー出力に出るが、形式や出力先をエラー報告関数yyerror()でカスタマイズできる。Yaccのオリジナルなエラーメッセージでは情報が貧弱である。開発・運用で頭を抱えないようにするためには、特に発生場所のファイル名、行番号およびトークン番号などをエラーメッセージに追加するようにyyerror()を作っておくことが望ましい。
Yacc文法ファイルwiki_samp1.y（後述）から構文解析実行プログラムwiki1.exeを実行するまでの実際のコマンド例（WindowsCygwin環境）を示す。
>bison-ydv./wiki_samp1.y>gcc-DYYERROR_VERBOSE-DYYDEBUG./y.tab.c-ly-lm-owiki_samp1_parser>wiki_samp1_gcc_outlist.txt>./wiki_samp1_parser.exe<./indata.txt
GNUコマンドプログラムbison はYacc上位互換であって、オプション -y によりYacc互換の処理をしてくれる。解析させるファイルindata.txtの中には、たとえばテスト用の文字列「10+20*30-40《改行》」を入れておく。もちろん「 < indata.txt」を除いて対話的に手入力してもよい。
Yaccの構成は以下のようになっている。
%{ （Ｃ宣言部：ヘッダファイルのインクルードなどC言語の初期設定）%} （Yacc宣言部：トークンおよび優先順序の定義など）%union { （トークンやグループとその意味値の型の定義）}%% （文法規則部：構文規則）%% （追加Ｃプログラム部：以下はそのままプログラムに出力される）以下に、Wikipedia用に作成した動作確認済サンプルプログラムを示し、その動作を逐次説明していく。
いま作ろうとする電卓は、内部的に64ビット浮動小数点で動作し、整数と演算子、カッコなどからなる式を与えて改行すると計算結果を答えるという会話を繰り返すものである。
目的とする出力例
Calculator start. ?> 10+20*30-40 Ans = 570 ?> Bye.
小数はサポートしないが、「314/100」のように整数の除算で小数にあたる数を与えることはできる。
「+」、「-」、「*」、「/」、べき乗の「**」、剰余の「%」。
「+」および「-」においては単項と二項の両方。
カッコ「()」で演算順序を明示すること。
課題プログラムのYacc構文定義は以下のように作ることができる。これをたとえば、ファイル "wiki_sample.y" に入れ、Lex出力ソースに代えて後述の「後半」内容をつないで作成し、上記#コマンド例のように実行すればよい。
%{/*----- 【1】ここからＣ宣言部（C declarations） -----*/#include<stdio.h>#include<ctype.h>#include<math.h>#define YYDEBUG 1%}/*----- 【2】ここからYacc宣言部（Yacc declarations） -----*/%startdialogue;/* 文法規則部で記述する最大の構造の名前 */%union{/* 意味値に可能な値型の集合 */intival;/* 4バイト．*/longdoubleldval;/* 12バイト．*/}%tokenEOL/* トークン （終端記号）の定義．*/%token<ldval>NUM/* トークン （終端記号）とその意味値yylvalの型の定義．*/%type<ldval>expr/* グループ（非終端記号）とその意味値yylvalの型の定義．*/%left'+''-'/* 優先順序等の定義. 優先の低から高に配列する．*//* leftは左結合性．例：1-2-3 は 1-(2-3) ではなく (1-2)-3 */%left'*''/''%'%leftUPLUSUMINUS/* 単項演算子のほうの記号 */%rightEXPONENT;/* べき乗を表す「**」*/%%/*----- 【3】ここから文法規則部（Grammar rules） -----*/dialogue:/* 空 *//* 規則1 0行もOK．*/|dialogueEOL{prompt();}/* 規則2 空行．*/|dialogueqaEOL/* 規則3 Q&A行. */|dialogueerrorEOL{yyerrok;prompt();}/* 規則4 エラー回復処理．*//* 末尾に「;」を書いてもよい．*/qa:expr{printf(" Ans = %Lg",$1);prompt();}/* 規則5 改行で計算，表示．*/expr:NUM/* 規則6 「$$=$1;」は省略可 */|'+'expr%precUPLUS{$$=$2;}/* 規則7 優先順位変更．*/|'-'expr%precUMINUS{$$=-$2;}/* 規則8 優先順位変更．*/|expr'+'expr{$$=$1+$3;}/* 規則9 加算．*/|expr'-'expr{$$=$1-$3;}/* 規則10 減算．*/|expr'*'expr{$$=$1*$3;}/* 規則11 乗算．*/|expr'/'expr{$$=$1/$3;}/* 規則12 除算．*/|expr'%'expr{$$=((int)$1)%((int)$3);}/* 規則13 剰余．*/|exprEXPONENTexpr{$$=powf($1,$3);}/* 規則14 指数．powfはC99規格．*/|'('expr')'{$$=$2;}/* 規則15 カッコ．*/%%/*----- 【4】ここから追加Ｃプログラム部（Additional C code） -----*/《ここに後述の「[[#Yacc構文定義ファイルの内容（後半）|後半]]」を記述する》
マクロ定義や文法規則のアクション関数をC言語で記述できるパートである。構文解析器プログラム先頭にそのままコピーされる。例:
#include<stdio.h>
開始記号（"%start"）、値型の集合（"%union"）、トークン（終端記号）宣言（"%token"）、グループ（非終端記号）宣言（"%type"）、 演算子優先順位指定（"%left", "%right", "%nonassoc"）などを、必要に応じて記述できるパートである。 例:
%token<ldval>NUM/* トークン （終端記号）とその意味値yylvalの型の定義．*/
Bisonの場合はBison宣言部と呼ぶ。この場合さらに、衝突警告抑制（"%expect"）、純粋（再入可能）構文解析器指定（"%pure_parser"）ができる。
文法規則部には1個以上のYacc文法規則
変換結果: 構成要素1 構成要素2 … ;
を記述しなければならない。
ここで，変換結果とは、規則が記述する非終端記号。構成要素とは、この規則がマッチするかを判定するために文法どおりの順に並べられる、0個以上の終端記号や非終端記号の列。例:
qa:expr{printf(" Ans = %Lg",$1);prompt();}/* 規則5 改行で計算，表示．*/
同じ変換結果を生む複数の規則は次のように簡略に連続記述できる。
変換結果: 構成要素11 構成要素12 … | 構成要素21 構成要素22 … | 構成要素31 構成要素32 … ;
「;」は省略可能。
見て分かるとおり、構文規則は読み書きしやすいBNF記法になっている。
規則にマッチするたびに行ないたい動作、たとえば変換結果の意味値（"$$"）をその構成要素の意味値（"$1", "$2", …）から計算すること、あるいは値を表示出力などは、C言語命令によるアクションとして「{ }」に囲って、マッチ直前に実行したい構成要素の直前に付して、あるいは規則適用時実行でよければその規則の最後の構成要素のあとに記述する。
例: 上例の「{ printf(" Ans = %Lg", $1); prompt(); }」はqaがexprにマッチと判定されたとき実行される。規則は再帰的に定義できる。例で
expr:NUM/* 規則6 「$$=$1;」は省略可 */|expr'+'expr{$$=$1+$3;}/* 規則9 加算．*/
の規則6は、「NUMと名付けた数値トークンがきたら、それ1個単独でも式exprになる」と宣言している。
そして規則9は「expr '+' exprという並びもexprである」という意味で自分expを記述しているから、再帰的な定義である。すると、規則は繰り返して適用できるから、
NUMNUM '+' NUMNUM '+' NUM '+' NUM:
など1個以上のNUMの加算式が、わずか2個の規則だけで表現できる。構文解析器実行時にこのうちのどれがやってきてもexprにマッチすると認識できることになる。
トークン値は実際にはASCIIコードと重ならない256以上の整数であるが、Yacc文法記述者はその値を知らなくてよく、NUM, EOLといった通常大文字で記述する記号で宣言と規則で統一的に記載すればよい。
トークンの意味値が伴う種類のトークンは、とりうる型は"%union"によって列挙して定義しておく。そして"%token"で"<ldval>"のように共用体のどのメンバーであるかを明示できる。アクション中で"$$"と書かれた意味値はC言語になったとき"lval.ldval"のように共用体中の要素を指すように自動変換される。このように意味値が伝わっていく。
関数、変数等をC言語で記述できるパートである。構文解析器プログラムでyyparse()関数の展開が終わったあとの末尾に、そのままコピーされる。たとえば字句解析器関数yylex()、エラー報告関数yyerror()、C言語メインプログラムmain()なども、それぞれ必要があればここに記述する。
Yaccが生成する構文解析器は、内部にスタックをもっている有限状態機械である。次のトークンを1個読み（先読みトークン;look-ahead token）変数yycharに入れるが、すぐにスタックにシフトするわけではない。構文解析器はその前に、マッチする規則があるかどうか、構文解析器の現在の状態番号（0,1,…）（これは常にスタックの最新＝右端のものである）のもとでYaccが生成しておいた解析テーブルを検索して調べる。スタックの右端と各規則を合わせてみて解析する（右端導出）。
構文解析器は終了条件まで以下を繰り返す処理である：
現在の状態で先読み（lookahead）トークンが必要で現在それがセットされていなければ、yylex()を呼んで先読みトークンをもらう。そして現在の状態と先読みトークンによって決まるアクションを実行する。
Yaccにより解析テーブルに展開されるこの機械のアクションの種類は、
である[8][9][10]。可能な還元はそのままいくつか行ったあとはじめて、トークンはシフトされる。
構文解析器は、入力されたトークン列をスタックに入れては次々に上記のように規則適用を試みて、成功するたびに還元していく。そしてテーブルの指定によって状態遷移していく。
入れ子の下位の非終端項目（グループ）が確定すれば、その値がその非終端項目に該当する上位の未確定な右辺の項に代入されて、その左辺のグループがスタックにプッシュされることで、だんだん上位に向かって解決されていく。
トークンを受けた状態番号を状態スタックに出し入れすると完全同期して、（あれば）そのトークンの意味値も意味値スタックに出し入れする。これにより、アクションによる意味値の計算を保証している。
最終目標は、全部読みきったときに、"%start"で指定され解析をスタートした非終端記号（デフォルトは最初に書かれている規則の左辺）が、変換の結果$accept 1個に還元できたかどうか調べることである。
もしそれが（エラー発生がerrorトークンで解決できなかったか、YYABORTマクロを実行されたなどの原因で）できなかったのなら、入力文字列はこの文法に適合しないエラーということが分かる（入力文字列が正しければYacc文法ファイルが間違いということもある）。
もしできたなら、この文法に適合したと判断でき，それに直接あるいは再帰的に入れ子で含まれる全部の要素に該当する入力トークン列が確定する。電卓の計算結果やコンパイラのための抽象構文木といった応用のための）意味値ができていれば、それもアクションで、都度あるいは最後に、表示したりファイルに書き出すことができる。
たとえば、この構文規則から生成した構文解析器が、数値トークンNUM、End Of LineトークンEOLおよび演算子からなるトークン列
NUM '+' NUM '*' NUM '-' NUM EOL
を読むとしよう。
ただこの前半では、トークンNUMが何の文字列をもってそう認識するかは定義されていない。Yaccにユーザが与えたYacc文法ファイルには、通常、字句解析をするための文法が存在していないからである（もっとも、無理に字句解析までやらせることは、複雜になるが不可能ではない）。その代わりトークンの入力は、yylex()という決まった名前の関数を呼ぶように展開される。目的の構文解析器の実行時に、Yaccによって生成されている構文解析器関数yyparse()は、ひとつひとつトークンをyylex()を呼んで要求する。yylex()はどこからか文字列を呼んでひとつトークンを返し，あれば変数lval経由でその意味値も同時に返し、ファイルの終端に達したとき（1行ごとにyyparser()から帰ってはまた呼び出す構文解析器を作るにおいては、行末に達したなどそのプログラムが解析のまとまりと認識している区切りに達したとき）はバイナリ0か負数を返して知らせる。
利用者はyylex()を自分でプログラミングするか、Lex、Flexなどの字句解析ツールを使って作成する必要がある。つまりLex、FLex、JFLexなどの字句解析器ジェネレータは、Yaccが作ってくれない関数yylex()を自動で作ってくれるツールといえる。
実際にはこの課題プログラムに
10+20*30-40
を与えたとして値も追跡したい。この場合「後半」のyylex()プログラムは構文解析器実行時に、次のトークン群、およびあれば以下でカッコ《》内に付記している意味値を、要求するたびに1個ずつ構文解析器関数yyparser()に返してくるはずである。
NUM《10》'+'NUM《20》'*'NUM《30》'-'NUM《40》EOL0（ファイル終端を表す）
最初に、スタックが空
の状態で内部にもつ状態番号を0にして%startで示されているdialogueが調べられる。適用できる規則は右辺が空の規則1なのでこれが適用される。状態スタックにはその0がはいる。このスタック状態を次のように図示できる。
0:dialogue
そして状態番号は1に行く。yylex()の中で初回だけ、
Calculator start.
と出し、prompt()というユーザ定義関数によって、
?>
と表示する。電卓ユーザまたはファイルから、
10+20*30-40
が入力されると、yylex()関数はトークン1個ずつyyparser()に返していく。
まずNUM《10》が読まれ，状態1での適用規則が探される。還元できる規則とはスタック右端がマッチしないので、ありえる記号としてそのテーブルに登録されている「NUM」に対する操作が行われる。すなわち、スタックにはじめてそれが1個シフトで入れられ状態5になる．
0:dialogue 1:NUM《10》
規則6
expr:NUM/* 規則6 「$$=$1;」は省略可 */
（単独のNUMはexpr）だけがマッチするからこれが適用され、
0:dialogue 1:expr《10》
に還元されてスタック内容が入れ替わる。
（この規則6にアクションは書いてなかったが、戻り値がないのではなく、Yaccの空でない規則に対するデフォルトアクション
が実行されて10がこのexprの値に代入されたのである。）
そしてテーブルに書かれていた状態番号10になる。
ここで'+'を読んでシフトし、状態16になってNUM《20》までシフトしたとき、
0:dialogue 1:expr《10》 10:'+' 16:NUM《20》
となるから、先と同様に規則6でNUMがexprに還元され
0:dialogue 1:expr《10》 10:'+' 16:expr《20》 （←次に'*'が来る予定）
となる（以下、内部状態番号の変化は省略するが次々と遷移していく）。
ここで現在スタックの右端にある3トークン「expr '+' expr」が規則9（加算式）にマッチして還元が起こりそうに思えるかもしれないが、起こらない。先読みしている次のトークンが現在の「+」よりも優先順位が高い「*」なので還元はせず、シフトを行う（もし演算子優先順位を同列にしていたら還元が起こって先に加算をするであろう）。
dialogue expr《10》 '+' expr《20》 '*'
NUM《30》を読んでシフトし
dialogue expr《10》 '+' expr《20》 '*' NUM《30》
規則6で還元し、
dialogue expr《10》 '+' expr《20》 '*' expr《30》
ここで、右端の3トークンが
|expr'*'expr{$$=$1*$3;}/* 規則11 乗算．*/
にマッチしていて、次のトークンは'-'であり、今度は遠慮なく還元が実行されてスタックから3個消えて、意味値が600と計算された左辺のグループexprが押し込まれるので、
dialogue expr《10》 '+' expr《600》
のように2個分縮むことになる。
次に先読みしていた「-」を読み直す。ここの状態で右端の3トークンが
|expr'+'expr{$$=$1+$3;}/* 規則9 加算．*/
にマッチしていて、次のトークンは'-'であり、これも還元が実行されてスタックから3個消えて、意味値が10+600=610と計算されたグループexprが押し込まれるので、
dialogue expr《610》
のようにまた2個分縮む。
（このように、還元が起こるたびに、まるでゲームのテトリスで同じ色のブロックが並んだときのように、スタックが伸びてはストンストンと短くなる。還元が長く起こらないとスタックが長くなって、既定のサイズを超えるとスタックオーバフロー例外で異常終了してしまうのも、ゲームオーバーに似ている。なお、スタックオーバフローを起こさないためには、
のような右再帰の形を避けて
のような左再帰の形で定義することである。規模が大きくなる場合はスタックサイズの定義マクロYYMAXDEPTHの値を大きく指定する．）
またまた先読みしていた「-」を読み直す。今度はさすがに適用できる規則がなくシフトされる。
dialogue expr《610》 '-'
次にNUM《40》が読まれてもシフトするしかない。
dialogue expr《610》 '-' NUM《40》
この状態で先読みトークンに、電卓ユーザが押した改行EOLがくる。
dialogue expr《610》 '-' NUM《40》 （←次にEOLが来る予定）
この状態において、演算子優先度が関係ない先読みEOLに遠慮する必要がないので、
|expr'-'expr{$$=$1-$3;}/* 規則10 減算．*/
がマッチとして還元が実行されて、スタックから3個消える。その代わり、意味値が610-40=570と計算されたグループexprが押し込まれるので、
dialogue expr《570》
のようにまた2個分縮む。
先読みしていたEOLを読み直す。すると、この状態でexprには、
qa:expr{printf(" Ans = %Lg",$1);prompt();}/* 規則5 改行で計算，表示．*/
しかマッチせず、アクションのprintf関数が実行されて，
?> Ans = 570 ?>
という計算結果と次のプロンプトが標準出力に見事に出てくる。スタックは、
dialogue qa
になった。
またまたEOLを読んで今度はシフトする。
dialogue qa EOL
これはdialogueの再帰的な規則のひとつ
|dialogueqaEOL/* 規則3 Q&A行. */
の3個のトークンとマッチするので、還元が実行されてスタックから3個消えて左辺のグループdialogueが押し込まれ、
dialogue
だけになる。
このあと入力ファイルにまだ演算させたい式を書いた行が書かれていれば、上と同様に計算され結果が表示されるであろう。が、いまの場合はファイル終端になってyylex()が
と表示して0を返す。すると内部的には$endという特殊トークンがシフトされ
dialogue $end
となるが、これが暗黙に定義されている規則0
$accept:dialogue$end
とマッチするので、パーサは$accept（受理）を得て目的を成功裏に果たしたということでスタックをすべてクリーンアップして，yyparse()呼出元に制御を返す。
このようにYaccの作るパーサは、解析した文字列が最後に%startの記号（デフォルトは最初に書いた規則の左辺）に見事にマッチし文法に合格したと判断されたとき正常に戻り値0でyyparser呼出元に帰る。また、YYACCEPTマクロを実行すれば即正常で帰る。
構文解析エラーが起これば異常（戻り値1）でyyparser呼出元に帰る。また、YYABORTマクロを実行すれば即異常（戻り値1）で帰る。
途中、意味値をユーザ定義のアクションや関数で出力すれば、計算の目的が果たせたことになる。
上記 wiki_sample.y 前半に引き続き後半として記述すべき追加Ｃプログラム例は、以下のとおりである（ここではユーザがyylex()関数を手で書いているが、同じ機能のプログラムは、FLexに字句規則を与えて自動生成させた方がスマートであろう）。
intpass=0;/* 通過回数．*/intlineno=1;/* 行番号．*/inttokenno=1;/* 行内トークン番号．*//* 字句解析器 yylex．トークンを要求するときyyparseから呼び出される． ここでは手で書いているが，Lex, Flexなどの字句解析器生成器を使えば自動生成が可能． */intyylex(void){if(pass++==0){printf(" Calculator start.");prompt();}intc;/* 空白やCrを読みとばす．*/while((c=getchar())==' '||c==0x0d||c=='\t'){}if(c==EOF){/* ファイル終端．コマンドプロンプトではCtrl-Dで入力可能. */printf(" Bye.\n");return0;}if(c=='\n'){/* 改行（NL）検出. */lineno++;tokenno=0;returnEOL;}tokenno++;if(isdigit(c)){longlongintval=(c-'0');while(isdigit(c=getchar())){val=val*10+c-'0';}yylval.ldval=(longdouble)val;ungetc(c,stdin);//printf(" 入力整数値 val=%lld, 意味値 yylval=%Lf, トークンコード NUM=%d\n",// val, yylval.ldval, NUM);return(NUM);}/* printf("c=%d\n", c); */if(c=='*'){if((c=getchar())=='*'){returnEXPONENT;/* 指数演算子の「**」だった．*/}ungetc(c,stdin);/* 「**」ではなく乗算演算子の「*」だった．*/c='*';}/* その他のコードはそのまま伝え，'%' など直接文字コードで判定させている．*/return(c);}/* 入力促進文字を表示する．*/intprompt(void){printf("\n ?> ");}/* エラー発生時にyyparseから呼び出される． * 引数: yyparseから渡ってくるエラーメッセージの文字列． */yyerror(char*str){printf(" Error! {%s}\n lineno{%d} near tokenno{%d} yychar{%d}\n",str,lineno,tokenno,yychar);}/** 生成された構文解析器のメインプログラムになる．*/intmain(void){yydebug=0;/* Yacc動作をトレースしたいとき1にする．*/yyparse();/* 生成された構文解析関数を呼ぶ．*/}
上の例では電卓のようにその場で値を求めることはできる。しかしYaccを利用してコンパイラを開発する場合は、このあとのコード生成部(2)に渡す抽象構文木（abstract syntax tree、AST）というデータの構造を構築していかなければならない。たとえばアクションでユーザ定義関数を呼び出し、
{$$=node('+',$1,$3);}
のように左辺と右辺を「+」で結合してそのポインタを返すような操作を行わせることで可能である。すると、構文解析が末端から順次還元を行って根まで統合されて停止したとき、同じ構造の抽象構文木が根まで完成して得られることになる。
このように葉から順に根に至る構文解析法をボトムアップ構文解析という（ここでは木を上下逆さまにして根は一点にしたイメージなので“ボトムアップ”という）。
この方式では、次の有名な例のように、同じ入力を同じ構文規則で複数の解釈ができてしまう曖昧性が避けられない。
/* stmt2って一体どっちのIFが不成立のときに実行したいの？ */IFexpr1IFexpr2stmt1;ELSEstmt2;
Yaccではyaccコマンド実行時に解釈が複数生じる曖昧なケースを発見した場合に「還元／還元衝突警告」または「シフト／還元衝突警告」を出す。これによって、文法を作成中なら文法を、そうでなければ構文規則を改良するきっかけが得られる。
まず「還元／還元衝突警告」が出た場合であるが、パーサが正しい処理をできない構文要素が生じてしまうので、文法、または構文規則のYacc定義を直した方がよい。
ある非終端記号から別の非終端記号に至る呼び出しパスが複数あれば、それは間違いなので直す。
しかし元の言語が複雜すぎてうまく直せない場合は、片方を実体は同じでも別の名前を付けるトークン由来で構成するようにし、Lex側がどちらのトークンをYaccパーサに出すかは状態に応じて変えるようにコーディングしておく方法がある：
状態がトークン列だけから一意に決められるならLex単独で処理できる。しかし、Yaccが実行時にあるルールのマッチを検出したときにはじめて状態を変えたいという複雜なケースでは、次のようにする。LexとYaccで共通の状態変数を設けておき、Yaccの{ }内に記述するアクションで、区別したい何かのフェーズなどの状態に応じて状態変数値を変えてやる。そうすればLexの生成したレキシカルアナライザは、実行時にまさに読んでいる入力トークン列による状態変数値に応じて、ある入側トークンを別々のトークンに動的に変換し分けてYaccの生成したパーサに渡す、という方法である。非常にダイナミックな技である。
次に「シフト／還元衝突」であるが、このときYaccは標準で、（特に演算子優先規則で指定されていないかぎり）シフトを選ぶようにできている。たとえば上記の例ではexpr2不成立のときにstmt2を実行するようにパーサのテーブルが作られる。このように距離の近い記号の関係を優先するよう動作するのは、多くのプログラミング言語のコンパイラに向いているといわれているが、後述のように注意が必要である。
構文上期待外のトークンがくるとアクションが見つからないので、パーサは、状態を戻して、errorという特定トークンのアクションがその状態に定義されているかどうか調べ、あれば実行する。最大3回まで戻しても見つからないときには入力テキストが途中でもそこでパースを打ち切ってしまう。これを利用してたとえば命令リストにerrorトークンのみの右辺をOR（|）結合しておけば、ある命令に属するオペランドに期待外トークンがあっても、そこで警告を出して次の命令以降のパースを続行してくれる、使いやすいコンパイラを作ることができる。ただ最大3回固定なので、深さの差3以内の上位にerrorを処理する構文を書いておかなければ利用できない。またはy.tab.cファイルの変数yyerrstatusの初期値を10などと増やしてやる必要がある。
Yacc実行時に報告されるシフト／還元衝突は、シフトが選ばれるだけで十分と確信できるケース以外は、実は本来0件にしておくべきである。なぜならパーサ実行時にシフトが選ばれて動作することにより、入力されたトークン列によっては行き止まりになる。すなわち期待外のトークンとされ、上記のエラー処理に飛んでしまうからである。Yaccは衝突に対応する枝分かれをすべてバックトラックでたどって解空間を全探索するようにはできていないのである。このため、衝突を残しておくとパーサを当然通ると思った入力が通らず苦労することになる。
Yacc実行時になんらかの衝突が報告されるとき、および、上記パーサ実行時に正しいはずの入力がsyntax errorとなるときの主な対処方法には、次のようなものがある。
典拠管理データベース: 国立図書館 |
|---|