yacc
yacc（Yet Another Compiler-Compiler、ヤック）は構文解析器生成系（パーサジェネレータ）の一つでありUNIXの基本的なツールとして用いられている。1970年代にAT&Tでスティーブ・ジョンソンが開発した。
目次 |
[編集] 概要
yaccはYet Another Compiler-Compiler（もう一つのコンパイラコンパイラ）の略である。この名前の由来は当時同様の機能を持つツールが多かったため皮肉でつけられた名前と言われている。yaccはBNFに似た構文規則に基づいてパーサ（ソースコードの構文解析を行うコンパイラの一部分）を生成する。
仕様としては構文規則を定義したファイル（伝統的に拡張子は.yがつけられる）を読み込むとFILEポインタyyinが指し示すファイル内の文字列を構文解析するyyparse()という名前のC言語の関数を生成する。生成した関数はデフォルトでは"y.tab.c"というファイルに出力される。
yaccが行うのは構文解析のみであり、字句解析に関してはlexやFlexのような字句解析ツールを別途に用意するか、あるいは自分で作成しなければならない。このためyaccの解説はしばしばlexとセットで行われることが多い。lexとyaccの機能はIEEE POSIX P1003.2で標準化されている。
yaccはほとんどのUNIXシステムでデフォルトのパーサジェネレーターとして利用可能だった。yaccと上位互換を持つソフトとしてBarkeley Yacc、GNU bison、MKS yacc、Abraxas pcyaccがある。いずれの派生版も改良されてはいるが基本的な部分は変わらない。またyaccはRatfor、EFL、ML、Ada、Java、Limboなどの言語にも移植されている。オリジナルのyaccはサンマイクロシステムズのOpenSolarisの一部として更新されており、オープンソース化されている。ソースコードはPlan 9やOpenSolarisの標準的なディストリビューションに含まれる。
[編集] 基本構成
yaccの構成は以下の通り、
%{
（ヘッダファイルのインクルードなどC言語の初期設定）
%}
%union {
（トークンなどが返す型はここで定義する）
}
（トークンおよび優先順序の定義など）
%%
（構文規則の定義）
%%
（ここから下はそのまま出力される、C言語の関数などを記述）
例を以下に示す。
%{
#include <stdio.h>
%}
%union {
double val;
}
%token <val> NUM
%type <val> expr
%%
expr: NUM
| expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
| expr '*' expr { $$ = $1 * $3; }
| expr '/' expr { $$ = $1 / $3; }
;
%%
これは一つのトークン（NUM）と一つの構文規則（expr）からなっている。 トークンの定義は
%token <型> トークン名
の形で定義する、<型>を省略すれば何も返さない（void型を返す）ものとして扱う。 また構文規則も構文を認識した後に値を返す場合は規則の記述前に
%type <型> 構文規則名
と宣言する。上記の例では expr は val（%union よりC言語のdouble型）を値で返すことを意味している。
次に構文規則を解説する、構文規則はBNF記法に似た形で
(構文規則名) : (構文規則あるいはトークン1){ そのとき必要な処理（省略可）}
| (構文規則あるいはトークン2){（〃）}
・・・
;
のように表す、規則は再帰的に用いることが出来る。 さきほどの例、
expr: NUM
| expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
| expr '*' expr { $$ = $1 * $3; }
| expr '/' expr { $$ = $1 / $3; }
;
ではまず、最初の行は「NUMはexprである」という事を表している（{ }は省略した）。 次の行は「expr '+' exprと並んでいる物もexprである」という規則で、これを認識すると{～}内のプログラムを実行する。このとき $$ は認識されたexprが返す値、$1と$3は1番目の要素と3番目の要素（この場合は$1 = 左のexpr、$2='+'、 $3 = 右のexpr）の返す値である。
例えば、この構文規則により
NUM '+' NUM '*' NUM '-' NUM
という文字列を読むと、左から（優先順序を指定しない場合yaccは文字列の左から優先的に解析する）規則1（exprはNUMである）以外は全て再帰的なので規則1のみが適用されるこのとき文字列は
expr '+' expr '*' expr '-' expr
と認識する、すると今度は左から規則2が適用され
expr '*' expr '-' expr
さらに規則4が適用され
expr '-' expr
最後に規則3が適用され
expr
よって、この文字列はexprと認識される。
すなわち
NUM NUM '+' NUM NUM '*' NUM '-' NUM '/' NUM
というふうに並んでいる文字列はexprと認識するということを表しており、上の例では省略したが返す値の計算も同時に行うことができる。
しかし、トークンNUMが何の文字列を持ってそう認識するかは定義されていない。その部分はyylex()という関数で定義する。この関数はyaccが生成する関数yyparse()が構文規則を解析する度に呼ぶ関数でありyaccは字句解析を全てこの関数に任せている、ただしyaccはこの関数に関しての生成は一切行わない。そのためyylex()に関しては自分でプログラミングするかlexなどの字句解析ツールを使って作成する必要がある（yaccから見た場合lexは関数yylex()を自動で作るツールである）。
