compiler、ヤック)はパーサジェネレータの一つである。1970年代にAT&TでUNIX用にスティーヴン・カーティス・ジョンソンが開発した。compiler(またひとつのコンパイラコンパイラ)に由来するである。この命名は一種の韜晦で、コンピュータ黎明期には「自動プログラミング」と呼ばれたプログラミング言語処理系の技術の進展の方向として、当時、機械語プログラムを生成するコンパイラの次はコンパイラを生成するコンパイラコンパイラであろう、ということで盛んに研究がされており、そのためコンパイラコンパイラを名乗る研究が他にもあれこれあったためである。ようなパーサジェネレータは不足と言えなくもないが、特段意識されることは少ない。用途編集まず一般的なコンパイラの構成について簡単に説明する。ソースコードを中間表現あるいは機械語に変換するコンパイラは、ソースコードを入力として受け取り、構文木を構築して出力する構文解析部(A)と、その構文木を入力として受け取り、目的の中間表現ないし機械語のコードを生成して出力するコード生成部(B)からなる。→〔目的コード〕このうち構文解析部(A)は、文字列からトークンを切り出しトークン列とする字句解析器(レキシカルアナライザ、トークナイザ、スキャナ、図のA-1)と、構文規則に従ってトークン列に対し構文解析をおこない、構文木を出力する(狭義の)構文解析器(パーサ,パーザ、図のA-2)から成る。(必ずしもこのようにする必要はないが、典型的な構成としてはこのようにする)構文解析器は直接書くこともできるが、煩雑になる部分があり、特にボトムアップ構文解析のプログラムを手で書くのは現実的ではない。いった構文解析器を、機械可読な構文規則群から自動生成してくれるツールがパーサジェネレータである。YaccはLALR、通常LALR(1)の構文解析器を生成する。BNF(バッカス・ナウア記法)に似た構文規則を入力として受け取り、それに基づいて構文解析器を自動生成する。生成する構文解析器は解析テーブルとそれを用いるプログラムから構成される。構文解析手法はLALRである。LALR法とは、ボトムアップ構文解析に属する強力なLR法に制限を加えた手法である(Lは入力を左から読むこと、Rは右端導出、その後に付くことのある(1)のような数字は先読みするトークン数(文字数ではない)が1個、を意味する)。コンパクトな解析テーブルでありながらC言語、Javaなど多くのプログラミング言語の構文解析器を実装することができる。アクション内で先読みを行うことでLALR(k)の文法に対応させることも不可能ではないが、普通はLALR(1)の構文解析器を生成する。構文解析器(A-2)に解析を数字や英字や空白などの1文字単位で行わせると、複雜になりすぎる.しかし、人間が英文から英単語やカッコなどの記号列を、区切り文字(たとえば空白、タブ、改行、コンマ、終止符)やその列を目印に抽出して意味を判断しているのと同様の発想ができる。World."」といった文字リテラル、「++」といった演算子、「}」や「;」など意味のある区切り文字など、各種の文字列が取り出せる。これをトークンという。(A-2)はトークンから出発して句、文、ブロック、プログラムなどを認識する上位の文法処理に専念させる。この分業化により、それぞれの定義と処理が簡潔になった。呼んでトークンを毎度要求する。作って動的にトークンを生成して、1回呼ばれるごとに1個のトークン種類を戻り値で返してやればよい。セットして同時に返す。処理を実装することになる。Flex[3]などのレキシカルアナライザジェネレータがある。出力と一緒にそれをリンクして組み込む。これにより、ソーステキストの字句解析と構文解析を両方行って、規則のアクション部(あるいはさらにそれに呼ばれるユーザ作成のC言語関数)に書かれた計算の結果や、コンパイルの生成に使われる抽象構文木の構造体データ、あるいは各種表示が出力される、変換プログラムが完成する。いう名前で機能を提供している。両方の定義・処理機能を併せもっている。組み使い、組で解説することがある。1003.1-2008(かつては1003.2)で標準化している[5]。配布と派生編集Yaccは古典的なコンパイラコンパイラでありながら人気があり、今でもよく産業用や教育用に使われる。コンパイラを開発する目的に限らず、独自の設定ファイルの解析、プログラミング言語コンバータ開発、簡易電卓の例題による学習などに使われている。YaccはほとんどのUNIXシステムで、デフォルトのパーサジェネレータとして利用可能だった。いずれの派生版も改良されてはいるが基本的な部分は変わらない。Yaccモードに縮小した機能で動くようになっている。YaccはJava、Ratfor、EFL、ML、Ada、Limboなどの言語を生成する版としても移植されている。Bisonのラッパで、アクション部をJava言語で書けてJavaクラスによる構文解析器プログラムを生成できるJBisonというものもある。オリジナルのYaccはOpenSolarisの一部として更新されており、オープンソース化されている。処理編集ユーザは変換仕様をYacc文法ファイルとしてのテキストファイルを作っておく。与えた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実行時に与える。種類とそれぞれの判定パターンおよびそのシフト、還元等の措置や状態遷移先といった解析テーブル情報が、人に分かりやすい形でテキストファイル"y.output"に出力される。(この"y.output"リストの見方が分かりにくい。ピリオド「.」(Yaccの種類によっては下線「_」)は現在のカーソル位置であることなどは知らないと分からないであろう。)-tオプションを指定すると、生成パーサが実行されるときに、状態番号、スタック状態、読んだトークン、意味値の演算の様子、変化した状態番号などが、逐一標準エラー出力に表示されるのでデバッグに役立つ(コンパイルオプションも関連)。次に、Yaccで生成し構文解析器ソースプログラム("y.tab.c")をccコマンドやgccコマンドなどでコンパイルする。このとき、Lexも利用したのであればその出力("lex.yy.c")も並べて指定する。これらに対応するライブラリもコンパイルオプションによってリンクさせる。コンパイルで作成された変換プログラムを実行すると、標準入力(FILEポインタyyinで変更可能)(yywrap関数で複数ファイルの連結が可能)から変換するファイルを読み込む。これを字句解析器関数yylex()によってトークンにして構文解析が実行される。変換結果やエラーは、Yaccのアクション部や呼ばれる関数で書いた処理によりそれぞれ出力される。syntaxエラーなどは通常標準エラー出力に出るが、形式や出力先をエラー報告関数yyerror()でカスタマイズできる。Yaccのオリジナルなエラーメッセージでは情報が貧弱である。開発・運用で頭を抱えないようにするためには、特に発生場所のファイル名、行番号およびトークン番号などをエラーメッセージに追加するようにyyerror()を作っておくことが望ましい。Cygwin環境)を示す。よりYacc互換の処理をしてくれる。解析させるファイルindata.txtの中には、たとえばテスト用の文字列「10+20*30-40《改行》」を入れておく。indata.txt」を除いて対話的に手入力してもよい。Yacc文法ファイルの書き方編集Yaccの構成は以下のようになっている。以下に、Wikipedia用に作成した動作確認済サンプルプログラムを示し、その動作を逐次説明していく。課題プログラムの仕様編集いま作ろうとする電卓は、内部的に64ビット浮動小数点で動作し、整数と演算子、カッコなどからなる式を与えて改行すると計算結果を答えるという会話を繰り返すものである。Bye.小数はサポートしないが、「314/100」のように整数の除算で小数にあたる数を与えることはできる。「+」、「-」、「*」、「/」、べき乗の「**」、剰余の「%」。「+」および「-」においては単項と二項の両方。カッコ「()」で演算順序を明示すること。課題プログラムのYacc構文定義は以下のように作ることができる。入れ、Lex出力ソースに代えて後述の「後半」内容をつないで作成し、上記#コマンド例のように実行すればよい。《ここに後述の「[[#Yacc構文定義ファイルの内容(後半)|後半]]」を記述する》C宣言部編集マクロ定義や文法規則のアクション関数をC言語で記述できるパートである。構文解析器プログラム先頭にそのままコピーされる。"%nonassoc")などを、必要に応じて記述できるパートである。(終端記号)とその意味値yylvalの型の定義.*/Bisonの場合はBison宣言部と呼ぶ。;を記述しなければならない。ここで,変換結果とは、規則が記述する非終端記号。構成要素とは、この規則がマッチするかを判定するために文法どおりの順に並べられる、0個以上の終端記号や非終端記号の列。改行で計算,表示.*/同じ変換結果を生む複数の規則は次のように簡略に連続記述できる。見て分かるとおり、構文規則は読み書きしやすいBNF記法になっている。}」に囲って、マッチ直前に実行したい構成要素の直前に付して、あるいは規則適用時実行でよければその規則の最後の構成要素のあとに記述する。}」はqaがexprにマッチと判定されたとき実行される。規則は再帰的に定義できる。加算.*/の規則6は、「NUMと名付けた数値トークンがきたら、それ1個単独でも式exprになる」と宣言している。exprという並びもexprである」という意味で自分expを記述しているから、再帰的な定義である。このうちのどれがやってきてもexprにマッチすると認識できることになる。EOLといった通常大文字で記述する記号で宣言と規則で統一的に記載すればよい。トークンの意味値が伴う種類のトークンは、とりうる型は"%union"によって列挙して定義しておく。"%token"で"<ldval>"のように共用体のどのメンバーであるかを明示できる。アクション中で"$$"と書かれた意味値はC言語になったとき"lval.ldval"のように共用体中の要素を指すように自動変換される。このように意味値が伝わっていく。C言語で記述できるパートである。構文解析器プログラムでyyparse()関数の展開が終わったあとの末尾に、そのままコピーされる。字句解析器関数yylex()、エラー報告関数yyerror()、C言語メインプログラムmain()なども、それぞれ必要があればここに記述する。動作原理編集Yaccが生成する構文解析器は、内部にスタックをもっている有限状態機械である。token)変数yycharに入れるが、すぐにスタックにシフトするわけではない。構文解析器はその前に、マッチする規則があるかどうか、構文解析器の現在の状態番号(0,1,...)(これは常にスタックの最新=右端のものである)のもとでYaccが生成しておいた解析テーブルを検索して調べる。スタックの右端と各規則を合わせてみて解析する(右端導出)。構文解析器は終了条件まで以下を繰り返す処理である:現在の状態で先読み(lookahead)トークンが必要で現在それがセットされていなければ、yylex()を呼んで先読みトークンをもらう。現在の状態と先読みトークンによって決まるアクションを実行する。Yaccにより解析テーブルに展開されるこの機械のアクションの種類は、シフト(shift)先読みトークンが必要で、それをスタックに(右から新しいものを押し込むイメージで)1個追加(プッシュ)する。先読みトークンは消費される。還元(reduce)n番めの規則の右辺にある記号群から左辺のグループ(非終端記号)への置き換えを適用して、右辺に対応した数のスタック要素をポップアップ(右に出して消すイメージ)する。スタックのサイズは縮む(まさにreduceする)。左辺であるグループ(非終端記号)を1個プッシュしなおす。このグループに意味値があれば、戻り値からセットされる(電卓の例でいえば中間計算結果)。同時に、状態は(現在の状態ではなく)スタックのトップ(最も右)にある状態番号にされる。サブルーチンに行って帰って来たような状態である。還元を起動する条件として、解析テーブルに「.」(バージョンによっては「$default」)と書いてあれば無条件に実行されるが、「MINUS」などと先読みトークン値が与えられているときはそれが一致したときに限って実行される。遷移(goto)生成した非終端記号をshiftする。次の終端記号はこのあとのshiftに任される。先読みトークンは消費されない。受理(accept)構文解析の正常終了であり、yyparse()から戻り値0で正常復帰する。$end」によりスタックが正しく$acceptの1個に還元できたときに行われる。エラー(error)解析表の空欄、すなわち次に現れてはならない終端記号があったときマッチされるべく展開される。構文解析器はエラーを検出すると、「error」トークンが正常に合致する規則が見つかるまでスタックをポップアップしながら戻っていく(最後までみつからなければyyparse()から1で異常復帰する)。見つかるとそこに「error」というトークンがあったとみなして、検出される規則のアクションを実行する。先読みトークンはエラーを起こしたトークンに進める(リセット)。Yaccはエラー多発防止のため、トークン3個の読込みおよびシフトが成功するまではこのエラー状態にとどまるが、ユーザがアクションでyyerrok(エラー回復)マクロを実行すればその途中でも正常状態に戻る。[8][9][10]。可能な還元はそのままいくつか行ったあとはじめて、トークンはシフトされる。構文解析器は、入力されたトークン列をスタックに入れては次々に上記のように規則適用を試みて、成功するたびに還元していく。テーブルの指定によって状態遷移していく。入れ子の下位の非終端項目(グループ)が確定すれば、その値がその非終端項目に該当する上位の未確定な右辺の項に代入されて、その左辺のグループがスタックにプッシュされることで、だんだん上位に向かって解決されていく。トークンを受けた状態番号を状態スタックに出し入れすると完全同期して、(あれば)そのトークンの意味値も意味値スタックに出し入れする。これにより、アクションによる意味値の計算を保証している。1個に還元できたかどうか調べることである。それが(エラー発生がerrorトークンで解決できなかったか、YYABORTマクロを実行されたなどの原因で)できなかったのなら、入力文字列はこの文法に適合しないエラーということが分かる(入力文字列が正しければYacc文法ファイルが間違いということもある)。できたなら、この文法に適合したと判断でき,それに直接あるいは再帰的に入れ子で含まれる全部の要素に該当する入力トークン列が確定する。電卓の計算結果やコンパイラのための抽象構文木といった応用のための)意味値ができていれば、それもアクションで、都度あるいは最後に、表示したりファイルに書き出すことができる。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()に返してくるはずである。状態で内部にもつ状態番号を0にして%startで示されているdialogueが調べられる。適用できる規則は右辺が空の規則1なのでこれが適用される。状態スタックにはその0がはいる。このスタック状態を次のように図示できる。