Yacc
ウィキペディアから無料の百科事典
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 の機能は IEEE POSIX 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 ] [-b prefix] 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を実行するまでの実際のコマンド例（Windows Cygwin環境）を示す。
> bison -ydv ./wiki_samp1.y > gcc -DYYERROR_VERBOSE -DYYDEBUG ./y.tab.c -ly -lm -o wiki_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文法ファイルの書き方[編集]
Yaccの構成は以下のようになっている。
%{ （Ｃ宣言部：ヘッダファイルのインクルードなどC言語の初期設定） %} （Yacc宣言部：トークンおよび優先順序の定義など） %union { （トークンやグループとその意味値の型の定義） } %% （文法規則部：構文規則） %% （追加Ｃプログラム部：以下はそのままプログラムに出力される） 電卓プログラム生成例による動作解説[編集]
以下に、Wikipedia用に作成した動作確認済サンプルプログラムを示し、その動作を逐次説明していく。
課題プログラムの仕様[編集]
いま作ろうとする電卓は、内部的に64ビット浮動小数点で動作し、整数と演算子、カッコなどからなる式を与えて改行すると計算結果を答えるという会話を繰り返すものである。
目的とする出力例
Calculator start. ?> 10+20*30-40 Ans = 570 ?> Bye.
小数はサポートしないが、「314/100」のように整数の除算で小数にあたる数を与えることはできる。
サポートすべき演算子[編集]
「+」、「-」、「*」、「/」、べき乗の「**」、剰余の「%」。
「+」および「-」においては単項と二項の両方。
カッコ「()」で演算順序を明示すること。
Yacc構文定義ファイルの内容（前半）[編集]
課題プログラムのYacc構文定義は以下のように作ることができる。これをたとえば、ファイル "wiki_sample.y" に入れ、Lex出力ソースに代えて後述の「後半」内容をつないで作成し、上記#コマンド例のように実行すればよい。
%{ /*----- 【1】ここからＣ宣言部（C declarations） -----*/ #include <stdio.h> #include <ctype.h> #include <math.h> #define YYDEBUG 1 %} /*----- 【2】ここからYacc宣言部（Yacc declarations） -----*/ %start dialogue; /* 文法規則部で記述する最大の構造の名前 */ %union { /* 意味値に可能な値型の集合 */ int ival; /* 4バイト．*/ long double ldval; /* 12バイト．*/ } %token EOL /* トークン （終端記号）の定義．*/ %token <ldval> NUM /* トークン （終端記号）とその意味値yylvalの型の定義．*/ %type <ldval> expr /* グループ（非終端記号）とその意味値yylvalの型の定義．*/ %left '+' '-' /* 優先順序等の定義. 優先の低から高に配列する．*/ /* leftは左結合性．例：1-2-3 は 1-(2-3) ではなく (1-2)-3 */ %left '*' '/' '%' %left UPLUS UMINUS /* 単項演算子のほうの記号 */ %right EXPONENT; /* べき乗を表す「**」*/ %% /*----- 【3】ここから文法規則部（Grammar rules） -----*/ dialogue: /* 空 */ /* 規則1 0行もOK．*/ | dialogue EOL { prompt(); } /* 規則2 空行．*/ | dialogue qa EOL /* 規則3 Q&A行. */ | dialogue error EOL { yyerrok; prompt(); } /* 規則4 エラー回復処理．*/ /* 末尾に「;」を書いてもよい．*/ qa: expr { printf(" Ans = %Lg", $1); prompt(); }/* 規則5 改行で計算，表示．*/ expr: NUM /* 規則6 「$$=$1;」は省略可 */ | '+' expr %prec UPLUS { $$ = $2; } /* 規則7 優先順位変更．*/ | '-' expr %prec UMINUS { $$ = - $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 剰余．*/ | expr EXPONENT expr { $$ = powf($1, $3); } /* 規則14 指数．powfはC99規格．*/ | '(' expr ')' { $$ = $2; } /* 規則15 カッコ．*/ %% /*----- 【4】ここから追加Ｃプログラム部（Additional C code） -----*/ 《ここに後述の「[[#Yacc構文定義ファイルの内容（後半）|後半]]」を記述する》 C宣言部[編集]
マクロ定義や文法規則のアクション関数をC言語で記述できるパートである。構文解析器プログラム先頭にそのままコピーされる。 例:
#include <stdio.h> Yacc宣言部[編集]
開始記号（"%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を記述しているから、再帰的な定義である。すると、規則は繰り返して適用できるから、
NUM NUM '+' NUM NUM '+' 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により解析テーブルに展開されるこの機械のアクションの種類は、
- シフト（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（エラー回復）マクロを実行すればその途中でも正常状態に戻る。
である [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》 EOL 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》
規則6
expr: NUM /* 規則6 「$$=$1;」は省略可 */ （単独のNUMはexpr）だけがマッチするからこれが適用され、
0:dialogue 1:expr《10》
に還元されてスタック内容が入れ替わる。
（この規則6にアクションは書いてなかったが、戻り値がないのではなく、Yaccの空でない規則に対するデフォルトアクション
- {{{1}}}}
が実行されて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個分縮む。
（このように、還元が起こるたびに、まるでゲームのテトリスで同じ色のブロックが並んだときのように、スタックが伸びてはストンストンと短くなる。還元が長く起こらないとスタックが長くなって、既定のサイズを超えるとスタックオーバフロー例外で異常終了してしまうのも、ゲームオーバーに似ている。なお、スタックオーバフローを起こさないためには、
- explist ',' exp
のような右再帰の形を避けて
- exp ',' explist
のような左再帰の形で定義することである。規模が大きくなる場合はスタックサイズの定義マクロ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の再帰的な規則のひとつ
| dialogue qa EOL /* 規則3 Q&A行. */ の3個のトークンとマッチするので、還元が実行されてスタックから3個消えて左辺のグループdialogueが押し込まれ、
dialogue
だけになる。
このあと入力ファイルにまだ演算させたい式を書いた行が書かれていれば、上と同様に計算され結果が表示されるであろう。が、いまの場合はファイル終端になってyylex()が
- Bye.
と表示して0を返す。すると内部的には$endという特殊トークンがシフトされ
dialogue $end
となるが、これが暗黙に定義されている規則0
$accept: dialogue $end とマッチするので、パーサは$accept（受理）を得て目的を成功裏に果たしたということでスタックをすべてクリーンアップして，yyparse()呼出元に制御を返す。
このようにYaccの作るパーサは、解析した文字列が最後に%startの記号（デフォルトは最初に書いた規則の左辺）に見事にマッチし文法に合格したと判断されたとき正常に戻り値0でyyparser呼出元に帰る。また、YYACCEPTマクロを実行すれば即正常で帰る。
構文解析エラーが起これば異常（戻り値1）でyyparser呼出元に帰る。また、YYABORTマクロを実行すれば即異常（戻り値1）で帰る。
途中、意味値をユーザ定義のアクションや関数で出力すれば、計算の目的が果たせたことになる。
Yacc構文定義ファイルの内容（後半）[編集]
上記 wiki_sample.y 前半に引き続き後半として記述すべき追加Ｃプログラム例は、以下のとおりである（ここではユーザがyylex()関数を手で書いているが、同じ機能のプログラムは、FLexに字句規則を与えて自動生成させた方がスマートであろう）。
int pass = 0; /* 通過回数．*/ int lineno = 1; /* 行番号．*/ int tokenno = 1; /* 行内トークン番号．*/ /* 字句解析器 yylex．トークンを要求するときyyparseから呼び出される． ここでは手で書いているが，Lex, Flexなどの字句解析器生成器を使えば自動生成が可能． */ int yylex(void) { if (pass++ == 0) { printf(" Calculator start."); prompt(); } int c; /* 空白やCrを読みとばす．*/ while ( (c = getchar() ) == ' ' || c == 0x0d || c == '\t'){ } if (c == EOF) { /* ファイル終端．コマンドプロンプトではCtrl-Dで入力可能. */ printf(" Bye.\n"); return 0; } if (c == '\n') { /* 改行（NL）検出. */ lineno++; tokenno = 0; return EOL; } tokenno++; if( isdigit(c) ) { long long int val = (c - '0'); while ( isdigit(c = getchar() ) ) { val = val * 10 + c - '0'; } yylval.ldval = (long double)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() ) == '*') { return EXPONENT; /* 指数演算子の「**」だった．*/ } ungetc(c, stdin); /* 「**」ではなく乗算演算子の「*」だった．*/ c = '*'; } /* その他のコードはそのまま伝え，'%' など直接文字コードで判定させている．*/ return(c); } /* 入力促進文字を表示する．*/ int prompt(void) { printf( "\n ?> "); } /* エラー発生時にyyparseから呼び出される． * 引数: yyparseから渡ってくるエラーメッセージの文字列． */ yyerror (char* str) { printf (" Error! {%s}\n lineno{%d} near tokenno{%d} yychar{%d} \n", str, lineno, tokenno, yychar); } /** 生成された構文解析器のメインプログラムになる．*/ int main(void) { yydebug = 0; /* Yacc動作をトレースしたいとき1にする．*/ yyparse(); /* 生成された構文解析関数を呼ぶ．*/ } コンパイラの場合の違い[編集]
上の例では電卓のようにその場で値を求めることはできる。しかしYaccを利用してコンパイラを開発する場合は、このあとのコード生成部(2)に渡す抽象構文木（abstract syntax tree、AST）というデータの構造を構築していかなければならない。たとえばアクションでユーザ定義関数を呼び出し、
{ $$ = node( '+', $1, $3 ); } のように左辺と右辺を「+」で結合してそのポインタを返すような操作を行わせることで可能である。すると、構文解析が末端から順次還元を行って根まで統合されて停止したとき、同じ構造の抽象構文木が根まで完成して得られることになる。
このように葉から順に根に至る構文解析法をボトムアップ構文解析という（ここでは木を上下逆さまにして根は一点にしたイメージなので“ボトムアップ”という）。
曖昧な文法への対処[編集]
この方式では、次の有名な例のように、同じ入力を同じ構文規則で複数の解釈ができてしまう曖昧性が避けられない。
/* stmt2って一体どっちのIFが不成立のときに実行したいの？ */ IF expr1 IF expr2 stmt1; ELSE stmt2; 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となるときの主な対処方法には、次のようなものがある。
- syntax error発生時に少なくともそのときのトークン値、状態スタック中の状態番号列およびソースファイル上の行番号・文字番号を出力するように作っておくことで、正確な調査を可能にする。
- ある非終端記号から別の非終端記号に至る呼び出しパスが複数あれば、それは間違いなので直す（前述）。
- 「トークンまたは空である」といった非終端記号をひとつの構文右辺の中に複数並べることによって、衝突が生じていることがある。ひとつの右辺の中には省略のないトークンだけを使うようにする。そして、省略する、しないのすべての組合せは、右辺の種類として列挙してOR（|）結合する形に変更する。人間には等価ないし汚くなるように思えても、Yaccにとっては明瞭化になる。
- リストのリストは、繰り返し要素にinなどの接頭辞的なトークンが伴わない定義などでは、要素がどの段階のリストに属するのかという曖昧性を生じる。この場合、リストの段階数を減らすように工夫して明瞭化する。
- 問題の非終端記号を使う場面ごとに、元が同じ文字列でも別のトークンから構成するように、定義を変更して明瞭化する。そのためにそのトークンを上述のようにLex段階で、場面に応じて変換し分ける。
- パーサ実行時の期待外トークンで、あるトークンが複数の場面でどう絡んでいるかを調べるには、y.outputファイルでその状態番号を見つけて熟読し、その状態番号へ飛んでくる状態を1, 2段階さかのぼってたどってみると見えてくるものである。y.outputにはまた、状態番号に対して衝突種類、トークンに対して実行されないアクションを囲むカッコ「[ ]」が出力されているので、場所や影響が分かる。
- 原因調査が難航している場合は、問題のある文法要素の周辺の定義だけを抽出した“ミニ文法”をYacc定義し、障害がぎりぎり再現する境目を探しすことで切り分けるアプローチもある。
- 混乱を招いているトークンを含む連続した2個以上のトークンを、Lex段階で1個の別トークンにまとめて明瞭化する。
- 上記場面がパーサのシフトや還元の状態だけでは記述しきれないとき、Lex段階でその場面を識別するための内部状態をもち、はいってくるトークンを見ながら状態遷移することで問題の箇所を検出する。そして、検出時には別のトークンに変更して出したり、特別なトークンを挿入することで明瞭化する。
- 上記明瞭化の努力によって、Bison実行で報告される衝突数が減少した場合は、効果が出ている場合が多いが、減少しなくても、特定の入力に対しての処理がエラーから正常に変わって改善している場合もある。増加した場合は逆効果として調べる必要がある。
- 入力言語があまりに複雜な場合、またはプリプロセッサ命令を含んでいる場合、パースを2段階の直列構成にするという大胆な解決策もある。すなわち、1段階めの前処理Yaccパーサは曖昧性を解決するだけのための簡単な文法で動く。その出力の曖昧性を解決したトークン列を2段階めの本処理Yaccパーサに渡す。3段以上にすることが有効な場合もあろう。文法の性格によっては、この構成にすることで、むしろそれぞれをすっきりさせることができる（エラー位置の表示処理は複雜になる）。
脚注・出典[編集]
- ^ 英: semantic value
- ^ 英: lexical analyzer
- ^ 英: fast lexical analyzer generator
- ^ Theory of Compilation -- JLex, CUP tools --(PDF) - Haifa Univ. Bilal Saleh
- ^ POSIX 1003.1-2008 - IEEE（有料）
- ^ An Overview of Parser Generator Tools for Java
- ^ G・フリードマン著、矢吹道郎ら訳、竹本 浩OCR復刻 Cコンパイラ設計(yacc・lexの応用)
- ^ a b パーサーの操作 - Oracle
- ^ a b A yacc tutorial - Arizona大学 CSc 453: Supporting Documents
- ^ a b Yacc: A Parser Generator(pdf) by Stephen C. Johnson.（Yacc作者）and Ravi Sethi
- ^ Bison 2.7 8.1 Understanding Your Parser
関連項目[編集]
外部リンク[編集]
- Yacc: Yet Another Compiler-Compiler 作者スティーヴン・カーティス・ジョンソンが作成した詳細解説のHTML版（英語）、
- 「yacc - コンパイラコンパイラ」（その日本語訳）（ただし例題に多数翻訳ミスあり．一方「優先度」節（原文のPrecedence節に対応）の後半のように、日本語訳独自の加筆部分が見られる） - Oracle Documentation プログラミングユーティリティ 第3章
- 速習yacc（日本語）- 青木峰郎著 Rubyソースコード完全解説 第9章
- Lex & Yacc Tutorial - Tom Niemann epaperpress.com（英語）
- OS/Programming - 東京工業大学 千葉 滋 教授
- やさしい Java インタプリタ の作り方 - 沖ソフトウェア株式会社
- プログラミング言語処理 講義資料 - 筑波大学 佐藤 三久 教授
- GNU Bison Yacc上位互換ソフトBisonのホームページ
- Bison for Windows Windows版Bisonのダウンロードページ
- Bison 1.28 Bisonの詳しい解説。石川直太氏訳、
- 特に、「Bison構文解析器のアルゴリズム」
- 蔵満 琢麻ほか：ダブル配列によるGLR解析表の実現とSQL構文解析の高速化 （提案方式との対比のためにBison解析器の実装方法を詳説）
- 〔yacc/lex〕yyparse()でsyntax errorと言われたときのデバッグ方法 - 極北データモデリングさん
| 典拠管理データベース: 国立図書館 |
|---|
