Yacc
Yacc(yet another compiler compiler、ヤック)はパーサジェネレータの一つである。1970年代にAT&TでUNIX用にスティーヴン・カーティス・ジョンソンが開発した。
Yacc は yet another compiler compiler(またひとつのコンパイラコンパイラ)に由来する。コンピュータ黎明期には「自動プログラミング」と呼ばれたプログラミング言語処理系の技術の進展の方向として、当時、機械語プログラムを生成するコンパイラの次はコンパイラを生成するコンパイラコンパイラであろう、ということで盛んに研究がされており、そのためコンパイラコンパイラを名乗る研究が他にもあれこれ存在した。
パーサはコンパイラの全てではないので、コンパイラコンパイラと呼ぶには Yacc のようなパーサジェネレータは不足と言えなくもないが、特段意識されることは少ない。
まず一般的なコンパイラの構成について簡単に説明する。
ソースコードを中間表現あるいは機械語に変換するコンパイラは、ソースコードを入力として受け取り、構文木を構築して出力する構文解析部(A)と、その構文木を入力として受け取り、目的の中間表現ないし機械語のコードを生成して出力するコード生成部(B)からなる。
<pre>
├構文解析部(A)
│ ├字句解析器(A-1) ← [ソースコード] (文字列)
│ │   ↓
│ │   [トークン列]
│ │   ↓
│ └構文解析器(A-2)
│     ↓
│   [構文木]
│     ↓
└コード生成部(B)   → [目的コード]
</pre>
このうち構文解析部(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個のトークン種類を戻り値で返してやればよい。さらにそれが数値や文字列のように意味値をもつトークンのときは、意味値も変数 yylval にセットして同時に返す。ユーザはこの字句解析器関数 yylex の処理を実装することになる。
字句解析器(A-1)のほうも、合理的な開発を目的とし、Yacc に似た規則定義を与えれば字句解析器を自動生成してくれる便利な道具として、Lexや Flexなどのレキシカルアナライザジェネレータがある。
そこで Lex などの字句解析器生成ツールを利用するなら、それに字句文法定義を与えて生成させたC言語ソースである字句解析器が yylex 関数を含んでいるので、Cコンパイルで Yacc 出力と一緒にそれをリンクして組み込む。これにより、ソーステキストの字句解析と構文解析を両方行って、規則のアクション部(あるいはさらにそれに呼ばれるユーザ作成のC言語関数)に書かれた計算の結果や、コンパイルの生成に使われる抽象構文木の構造体データ、あるいは各種表示が出力される、変換プログラムが完成する。GNUプロジェクトでは、Flex という名前で機能を提供している。
ちなみに、Yacc の上位機能をもちやや方式の異なる Java 言語向けジェネレータ JavaCC では、両方の定義・処理機能を併せもっている。Java向けではまた、字句解析器ジェネレータと構文解析器ジェネレータとを組みあわせて用いることも行われている
Yacc と Lex はよく似た文法定義を持つ。組み使い、組で解説することがある。Lex と Yacc の機能は IEEE POSIX 1003.1-2008(かつては1003.2)で標準化している。
Yaccは古典的なコンパイラコンパイラでありながら人気があり、今でもよく産業用や教育用に使われる。コンパイラを開発する目的に限らず、独自の設定ファイルの解析、プログラミング言語コンバータ開発、簡易電卓の例題による学習などに使われている。
YaccはほとんどのUNIXシステムで、デフォルトのパーサジェネレータとして利用可能だった。Yaccと上位互換を持つソフトとして、よく使われているGNUプロジェクトのBisonをはじめ、、、、Abraxas pcyaccがある。いずれの派生版も改良されてはいるが基本的な部分は変わらない。むしろ現在yaccコマンドはbisonコマンドがラップし、-y オプションを付けることでPOSIX Yaccモードに縮小した機能で動くようになっている。
またYaccはJava、Ratfor、EFL、ML、Ada、Limboなどの言語を生成する版としても移植されている。
このうちJava向けには、Yaccと同様のLALR方式の、 (JavaCUP)、、
、またYaccと異なる方式では、LL(k)方式のJavaCCとCoco/R、そしてLL(*)方式のがある
。Bisonのラッパで、アクション部をJava言語で書けてJavaクラスによる構文解析器プログラムを生成できるというものもある。
オリジナルのYaccはOpenSolarisの一部として更新されており、オープンソース化されている。ソースコードはPlan 9やOpenSolarisの標準的なディストリビューションに含まれる。
ユーザは変換仕様をYacc文法ファイルとしてのテキストファイルを作っておく。
yacc [-dlrtv ] [-b prefix] fileName
は、fileName で与えたYacc文法ファイル(たとえば<tt>"wiki_samp1.y"</tt>)(伝統的に拡張子は<tt>.y</tt>がつけられることが多かった)から構文規則を入力し、それに基づくLALR構文解析器になるC言語のソースプログラム(通常<tt>"y.tab.c"</tt>)を出力する。-rオプションでコード部分だけ<tt>"y.code.c"</tt>ファイルに独立させることもできる。
このC言語ソースプログラムにはLALR解析テーブルおよびドライバルーチンが含まれる。
特に、構文解析全体を行う関数にはyyparse()という名前がついている。よってこのプログラムにあらかじめ適宜yyparse()を呼び出すmain()関数を加えておくなどして(それはYacc文法ファイル中の「追加Cプログラム部」での記述でも可能)、ほしい変換プログラムを完成することができる。
-dオプションで生成するヘッダファイル<tt>"y.tab.h"</tt>は、Lexがトークン処理を行うときに、Yaccが割り当てたトークン値(256~)を正しく使うよう、Lex実行時に与える。
-vオプションにより、生成パーサの文法、終端記号、非終端記号、状態の種類とそれぞれの判定パターンおよびそのシフト、還元等の措置や状態遷移先といった解析テーブル情報が、人に分かりやすい形でテキストファイル<tt>"y.output"</tt>に出力される。(この<tt>"y.output"</tt>リストの見方が分かりにくい。ピリオド「.」(Yaccの種類によっては下線「_」)は現在のカーソル位置であることなどは知らないと分からないであろう。説明は日本語文書では良書「Cコンパイラ設計(yacc・lexの応用)
」のほかに見つけにくいが、英語ではいくつかある
)
-tオプションを指定すると、生成パーサが実行されるときに、状態番号、スタック状態、読んだトークン、意味値の演算の様子、変化した状態番号などが、逐一標準エラー出力に表示されるのでデバッグに役立つ(コンパイルオプションも関連)。
次に、Yaccで生成し構文解析器ソースプログラム("y.tab.c")をccコマンドやgccコマンドなどでコンパイルする。このとき、Lexも利用したのであればその出力("lex.yy.c")も並べて指定する。これらに対応するライブラリもコンパイルオプションによってリンクさせる。
コンパイルで作成された変換プログラムを実行すると、標準入力(FILEポインタ<tt>yyin</tt>で変更可能)(yywrap関数で複数ファイルの連結が可能)から変換するファイルを読み込む。これを字句解析器関数yylex()によってトークンにして構文解析が実行される。変換結果やエラーは、Yaccのアクション部や呼ばれる関数で書いた処理によりそれぞれ出力される。syntaxエラーなどは通常標準エラー出力に出るが、形式や出力先をエラー報告関数yyerror()でカスタマイズできる。Yaccのオリジナルなエラーメッセージでは情報が貧弱である。開発・運用で頭を抱えないようにするためには、特に発生場所のファイル名、行番号およびトークン番号などをエラーメッセージに追加するようにyyerror()を作っておくことが望ましい。
Yacc文法ファイルwiki_samp1.y(後述)から構文解析実行プログラムwiki1.exeを実行するまでの実際のコマンド例(Windows Cygwin環境)を示す。
GNUコマンドプログラムbison はYacc上位互換であって、オプション -y によりYacc互換の処理をしてくれる。
解析させるファイルindata.txtの中には、たとえばテスト用の文字列「10+20*30-40《改行》」を入れておく。もちろん「 < indata.txt」を除いて対話的に手入力してもよい。
Yaccの構成は以下のようになっている。
%{
(C宣言部:ヘッダファイルのインクルードなどC言語の初期設定)
%}
(Yacc宣言部:トークンおよび優先順序の定義など)
%union {
(トークンやグループとその意味値の型の定義)
}
%%
(文法規則部:構文規則)
%%
(追加Cプログラム部:以下はそのままプログラムに出力される)
以下に、Wikipedia用に作成した動作確認済サンプルプログラムを示し、その動作を逐次説明していく。
いま作ろうとする電卓は、内部的に64ビット浮動小数点で動作し、整数と演算子、カッコなどからなる式を与えて改行すると計算結果を答えるという会話を繰り返すものである。
Calculator start.
?> 10+20*30-40
Ans = 570
?>   Bye.
小数はサポートしないが、「314/100」のように整数の除算で小数にあたる数を与えることはできる。
「+」、「-」、「*」、「/」、べき乗の「**」、剰余の「%」。
「+」および「-」においては単項と二項の両方。
カッコ「()」で演算順序を明示すること。
課題プログラムのYacc構文定義は以下のように作ることができる。これをたとえば、ファイル "wiki_sample.y" に入れ、Lex出力ソースに代えて後述の「後半」内容をつないで作成し、上記#コマンド例のように実行すればよい。
マクロ定義や文法規則のアクション関数をC言語で記述できるパートである。構文解析器プログラム先頭にそのままコピーされる。
例:
開始記号("%start")、値型の集合("%union")、トークン(終端記号)宣言("%token")、グループ(非終端記号)宣言("%type")、 演算子優先順位指定("%left", "%right", "%nonassoc")などを、必要に応じて記述できるパートである。
例:
Bisonの場合はBison宣言部と呼ぶ。この場合さらに、衝突警告抑制("%expect")、純粋(再入可能)構文解析器指定("%pure_parser")ができる。
変換結果: 構成要素1 構成要素2 …
;
を記述しなければならない。
ここで,変換結果とは、規則が記述する非終端記号。
構成要素とは、この規則がマッチするかを判定するために文法どおりの順に並べられる、0個以上の終端記号や非終端記号の列。
例:
同じ変換結果を生む複数の規則は次のように簡略に連続記述できる。
変換結果: 構成要素11 構成要素12 …
| 構成要素21 構成要素22 …
| 構成要素31 構成要素32 …
;
「;」は省略可能。
見て分かるとおり、構文規則は読み書きしやすいBNF記法になっている。
規則にマッチするたびに行ないたい動作、たとえば変換結果の意味値("$$")をその構成要素の意味値("$1", "$2", …)から計算すること、あるいは値を表示出力などは、C言語命令によるアクションとして「{ }」に囲って、マッチ直前に実行したい構成要素の直前に付して、あるいは規則適用時実行でよければその規則の最後の構成要素のあとに記述する。
例: 上例の「{ printf("  Ans = %Lg", $1); prompt(); }」は
qaがexprにマッチと判定されたとき実行される。
規則は再帰的に定義できる。例で
の規則6は、「NUMと名付けた数値トークンがきたら、それ1個単独でも式exprになる」と宣言している。
そして規則9は「<tt>expr '+' expr</tt>という並びも<tt>expr</tt>である」という意味で自分<tt>exp</tt>を記述しているから、再帰的な定義である。すると、規則は繰り返して適用できるから、
NUM '+' NUM
NUM '+' NUM '+' NUM
:
など1個以上のNUMの加算式が、わずか2個の規則だけで表現できる。構文解析器実行時にこのうちのどれがやってきても<tt>expr</tt>にマッチすると認識できることになる。
トークン値は実際には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により解析テーブルに展開されるこの機械のアクションの種類は、
シフト(shift): 先読みトークンが必要で、それをスタックに(右から新しいものを押し込むイメージで)1個追加(プッシュ)する。先読みトークンは消費される。
還元(reduce) : n番めの規則の右辺にある記号群から左辺のグループ(非終端記号)への置き換えを適用して、右辺に対応した数のスタック要素をポップアップ(右に出して消すイメージ)する。スタックのサイズは縮む(まさにreduceする)。そして、左辺であるグループ(非終端記号)を1個プッシュしなおす。このグループに意味値があれば、戻り値からセットされる(電卓の例でいえば中間計算結果)。同時に、状態は(現在の状態ではなく)スタックのトップ(最も右)にある状態番号にされる。いわばサブルーチンに行って帰って来たような状態である。還元を起動する条件として、解析テーブルに「.」(バージョンによっては「$default」)と書いてあれば無条件に実行されるが、「MINUS」などと先読みトークン値が与えられているときはそれが一致したときに限って実行される。
遷移(goto) : 生成した非終端記号をshiftする。次の終端記号はこのあとのshiftに任される。先読みトークンは消費されない。
受理(accept) : 構文解析の正常終了であり、yyparse()から戻り値0で正常復帰する。この動作はyylex()から0か負が返って次の終端記号が終わりを意味する$endになったとき、規則0「$accept: 全体の非終端記号名 $end」によりスタックが正しく$acceptの1個に還元できたときに行われる。
エラー(error) : 解析表の空欄、すなわち次に現れてはならない終端記号があったときマッチされるべく展開される。すなわち、構文解析器はエラーを検出すると、「error」トークンが正常に合致する規則が見つかるまでスタックをポップアップしながら戻っていく(最後までみつからなければyyparse()から1で異常復帰する)。見つかるとそこに「error」というトークンがあったとみなして、検出される規則のアクションを実行する。そして、先読みトークンはエラーを起こしたトークンに進める(リセット)。Yaccはエラー多発防止のため、トークン3個の読込みおよびシフトが成功するまではこのエラー状態にとどまるが、ユーザがアクションでyyerrok(エラー回復)マクロを実行すればその途中でも正常状態に戻る。
。
可能な還元はそのままいくつか行ったあとはじめて、トークンはシフトされる。
構文解析器は、入力されたトークン列をスタックに入れては次々に上記のように規則適用を試みて、成功するたびに還元していく。そしてテーブルの指定によって状態遷移していく。
入れ子の下位の非終端項目(グループ)が確定すれば、その値がその非終端項目に該当する上位の未確定な右辺の項に代入されて、その左辺のグループがスタックにプッシュされることで、だんだん上位に向かって解決されていく。
トークンを受けた状態番号を状態スタックに出し入れすると完全同期して、(あれば)そのトークンの意味値も意味値スタックに出し入れする。これにより、アクションによる意味値の計算を保証している。
最終目標は、全部読みきったときに、"%start"で指定され解析をスタートした非終端記号(デフォルトは最初に書かれている規則の左辺)が、変換の結果$accept 1個に還元できたかどうか調べることである。
もしそれが(エラー発生がerrorトークンで解決できなかったか、YYABORTマクロを実行されたなどの原因で)できなかったのなら、入力文字列はこの文法に適合しないエラーということが分かる(入力文字列が正しければYacc文法ファイルが間違いということもある)。
もしできたなら、この文法に適合したと判断でき,それに直接あるいは再帰的に入れ子で含まれる全部の要素に該当する入力トークン列が確定する。電卓の計算結果やコンパイラのための抽象構文木といった応用のための)意味値ができていれば、それもアクションで、都度あるいは最後に、表示したりファイルに書き出すことができる。
たとえば、この構文規則から生成した構文解析器が、数値トークンNUM、End Of LineトークンEOLおよび演算子からなるトークン列
NUM '+' NUM '*' NUM '-' NUM EOL
を読むとしよう。
ただこの前半では、トークン<tt>NUM</tt>が何の文字列をもってそう認識するかは定義されていない。Yaccにユーザが与えたYacc文法ファイルには、通常、字句解析をするための文法が存在していないからである(もっとも、無理に字句解析までやらせることは、複雜になるが不可能ではない)。
その代わりトークンの入力は、<tt>yylex()</tt>という決まった名前の関数を呼ぶように展開される。目的の構文解析器の実行時に、Yaccによって生成されている構文解析器関数<tt>yyparse()</tt>は、ひとつひとつトークンを<tt>yylex()</tt>を呼んで要求する。<tt>yylex()</tt>はどこからか文字列を呼んでひとつトークンを返し,あれば変数lval経由でその意味値も同時に返し、ファイルの終端に達したとき(1行ごとにyyparser()から帰ってはまた呼び出す構文解析器を作るにおいては、行末に達したなどそのプログラムが解析のまとまりと認識している区切りに達したとき)はバイナリ0か負数を返して知らせる。
利用者は<tt>yylex()</tt>を自分でプログラミングするか、Lex、Flexなどの字句解析ツールを使って作成する必要がある。つまりLex、FLex、JFLexなどの字句解析器ジェネレータは、Yaccが作ってくれない関数<tt>yylex()</tt>を自動で作ってくれるツールといえる。
10+20*30-40
を与えたとして値も追跡したい。この場合「後半」の<tt>yylex()</tt>プログラムは構文解析器実行時に、次のトークン群、およびあれば以下でカッコ《》内に付記している意味値を、要求するたびに1個ずつ構文解析器関数yyparser()に返してくるはずである。
NUM《10》
'+'
NUM《20》
'*'
NUM《30》
'-'
NUM《40》
0(ファイル終端を表す)
最初に、スタックが空
の状態で内部にもつ状態番号を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》
(単独の<tt>NUM</tt>は<tt>expr</tt>)だけがマッチするからこれが適用され、
0:dialogue  1:expr《10》
に還元されてスタック内容が入れ替わる。
(この規則6にアクションは書いてなかったが、戻り値がないのではなく、Yaccの空でない規則に対するデフォルトアクション
<tt> { $$ = $1; }</tt>
が実行されて10がこの<tt>expr</tt>の値に代入されたのである。)
そしてテーブルに書かれていた状態番号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トークンが
にマッチしていて、次のトークンは'-'であり、今度は遠慮なく還元が実行されてスタックから3個消えて、意味値が600と計算された左辺のグループexprが押し込まれるので、
dialogue  expr《10》  '+'  expr《600》
のように2個分縮むことになる。
次に先読みしていた「-」を読み直す。ここの状態で右端の3トークンが
にマッチしていて、次のトークンは'-'であり、これも還元が実行されてスタックから3個消えて、意味値が10+600=610と計算されたグループexprが押し込まれるので、
dialogue  expr《610》
のようにまた2個分縮む。
(このように、還元が起こるたびに、まるでゲームのテトリスで同じ色のブロックが並んだときのように、スタックが伸びてはストンストンと短くなる。還元が長く起こらないとスタックが長くなって、既定のサイズを超えるとスタックオーバフロー例外で異常終了してしまうのも、ゲームオーバーに似ている。なお、スタックオーバフローを起こさないためには、
<tt>explist:  exp | explist ',' exp</tt>
<tt>explist:  exp | exp ',' explist</tt>