Yacc

Yacc（Yet Another Compiler Compiler）とは

Yacc（ヤック）は、パーサジェネレータの一種で、与えられた文法規則に基づいて構文解析器を自動的に生成するツールです。1970年代にAT&Tでスティーヴン・カーティス・ジョンソンによってUNIX用に開発されました。

名称の由来

Yaccは、"Yet Another Compiler Compiler"（また別のコンパイラコンパイラ）の略称です。コンピュータ黎明期には、コンパイラを生成するコンパイラである「コンパイラコンパイラ」の研究が盛んに行われており、その中でYaccが誕生しました。

用途

コンパイラは、ソースコードを中間表現や機械語に変換する際、字句解析と構文解析という処理を行います。字句解析では、ソースコードをトークンと呼ばれる意味のある単位に分割し、構文解析では、それらのトークンが文法規則に従って正しく並んでいるかを検証します。Yaccは、この構文解析器を自動生成する役割を担います。

コンパイラ
　├構文解析部(A)
　│　├字句解析器(A-1)　←〔ソースコード〕（文字列）
　│　│　　　↓
　│　│　　〔トークン列〕
　│　│　　　↓
　│　└構文解析器(A-2)
　│　　　　　↓
　│　　〔構文木〕
　│　　　　　↓
　└コード生成部(B)　　　→〔目的コード〕

構文解析器は、手で記述することも可能ですが、特にボトムアップ構文解析では複雑になりがちです。そこで、Yaccのようなパーサジェネレータが役立ちます。Yaccは、与えられた構文規則に基づいて、LALR（Look-Ahead LR）という方式の構文解析器を生成します。

〔構文規則〕
　　↓
パーサジェネレータ（Yaccなど）
　　↓
〔構文解析器〕

Yaccの機能概要

Yaccは、BNF（バッカス・ナウア記法）に似た形式で記述された構文規則を入力として受け取り、それに基づいて構文解析器を生成します。生成される構文解析器は、解析テーブルとそれを用いるプログラムで構成され、LALR法に基づいて動作します。

LALR法とは

LALR法は、ボトムアップ構文解析の一種で、強力なLR法に制限を加えたものです。LALR法では、先読みするトークンの数を制限することで、解析テーブルのサイズを小さくすることができます。これにより、C言語やJavaなど、多くのプログラミング言語の構文解析器を効率的に実装することが可能です。

字句解析器との連携

Yacc自身は字句解析の機能を持たないため、トークンを生成する字句解析器との連携が必要です。Yaccは、字句解析器の関数である `yylex` を呼び出してトークンを取得します。字句解析器は、入力文字列をトークンに分割し、トークンの種類と意味値をYaccに返します。

字句解析器を自動生成するツールとしては、LexやFlexなどがあります。これらのツールを利用することで、効率的に字句解析器を開発できます。

字句解析器ジェネレータ(Lex,Flex)
↓
字句解析器（yylex関数）
↓
Yacc
↓
構文解析器

Yaccの配布と派生

Yaccは、古典的なコンパイラコンパイラでありながら、現在でも広く利用されています。コンパイラ開発だけでなく、設定ファイルの解析やプログラミング言語コンバータの開発など、様々な用途で活用されています。

Yaccの派生版としては、GNUプロジェクトのBisonがよく知られています。BisonはYaccと上位互換であり、多くのUNIXシステムでデフォルトのパーサジェネレータとして利用可能です。他にも、Berkeley Yacc（byacc）、BYACC/J、MKS Yacc、Abraxas pcyaccなど、様々な派生版が存在します。

また、YaccはJava、Ratfor、EFL、ML、Ada、Limboなどの言語を生成する版としても移植されています。Java向けのパーサジェネレータとしては、jacc、CUP (JavaCUP)、SableCC、jayなどがあります。

Yaccの基本構成

Yaccの文法ファイルは、以下の4つの部分から構成されます。

1. C宣言部：C言語のコードを記述する部分です。ヘッダファイルのインクルードや変数の定義などを行います。
2. Yacc宣言部：トークンの定義や優先順位の指定など、Yaccに関する設定を記述する部分です。
3. 文法規則部：構文規則を記述する部分です。BNFのような形式で、トークンや非終端記号を使って文法を定義します。
4. 追加Cプログラム部：字句解析器やエラー処理関数など、C言語のコードを記述する部分です。

%{
（Ｃ宣言部：ヘッダファイルのインクルードなどC言語の初期設定）
%}
（Yacc宣言部：トークンおよび優先順序の定義など）
%union {
（トークンやグループとその意味値の型の定義）
}
%%
（文法規則部：構文規則）
%%
（追加Ｃプログラム部：以下はそのままプログラムに出力される）

コマンド例

Yaccの文法ファイル（例えば `wiki_samp1.y`）から構文解析器を生成するには、以下のコマンドを実行します。

bash
yacc [-dlrtv ] [-b prefix] fileName

このコマンドにより、C言語のソースコードファイル（通常 `y.tab.c`）が生成されます。このファイルには、LALR解析テーブルとドライバルーチンが含まれており、構文解析を実行する関数 `yyparse()` が定義されています。

`-d` オプションを指定すると、ヘッダファイル `y.tab.h` が生成されます。このファイルには、トークンの定義が含まれており、Lexなどの字句解析器と連携する際に利用します。

`-v` オプションを指定すると、解析テーブル情報がテキストファイル `y.output` に出力されます。この情報は、構文解析器の動作を理解するのに役立ちます。

`-t` オプションを指定すると、構文解析器の実行時に、状態番号やスタックの状態などが標準エラー出力に表示され、デバッグに役立ちます。

電卓プログラムの例

Yaccを使って簡単な電卓プログラムを作成する例を見てみましょう。この電卓は、整数と演算子、カッコなどからなる式を入力すると、その計算結果を出力します。

Yacc構文定義ファイル（前半）

c
%{

include

void prompt();
%}
%start dialogue
%union {
long double ldval;
}
%token NUM EOL
%token '+' '-' '' '/' '%' '(' ')' ''
%left '+' '-'
%left '' '/' '%'
%right '*'
%%
dialogue:
| dialogue qa EOL
{ printf(" Ans = %Lg", $2); prompt(); }
qa:
expr { $$ = $1; }
;
expr:
NUM
| '(' expr ')' { $$ = $2; }
| expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
| expr '' expr { $$ = $1 $3; }
| expr '/' expr { $$ = $1 / $3; }
| expr '%' expr { $$ = fmodl($1, $3); }
| expr '' expr { $$ = powl($1, $3); }
| '-' expr %prec '' { $$ = -$2; }
;
%%

Yacc構文定義ファイル（後半）

c
void prompt() {
printf("?\> ");
}

void yyerror(char s) {
extern int yylineno;
fprintf(stderr, "Syntax error on line %d: %s
", yylineno, s);
fprintf(stderr, " Please input again.
");
}

int yylex() {
int c;
static char p;
static int first = 1;
if (first) {
first = 0;
printf(" Calculator start.
");
prompt();
p = NULL;
}
if (p == NULL || p == '\0') {
static char buff[2000];
if (fgets(buff, sizeof(buff), stdin) == NULL) {
return 0;
}
p = buff;
yylineno++;
}
while ((c = p++) != '\0') {
if (c >= '0' && c <= '9') {
yylval.ldval = strtold(p - 1, &p);
return NUM;
}
if (c == '+' || c == '-' || c == '' || c == '/' || c == '(' || c == ')' || c == '%' ) {
return c;
} else if ( c == '') {
if (p == '') {
p++;
return '**';
}
return c;
} else if (c == '
' ) {
return EOL;
} else if ( c == ' ') {
continue;
} else {
return c;
}
}
return 0;
}

int main() {
return yyparse();
}

動作原理

Yaccが生成する構文解析器は、内部にスタックを持つ有限状態機械です。入力トークンを読み込みながら、解析テーブルを参照して、シフト、還元、遷移などのアクションを実行します。構文解析器は、入力されたトークン列が文法規則に合致するかどうかを検証し、合致すれば、定義されたアクションを実行します。

コンパイラの場合の違い

電卓のように計算結果をその場で求めるだけでなく、コンパイラを開発する場合は、抽象[[構文木]]（AST）を構築する必要があります。ASTは、ソースコードの構造を表現するデータ構造であり、コード生成部の入力として利用されます。

曖昧な文法への対処

同じ入力に対して複数の解釈が可能な文法を「曖昧な文法」といいます。Yaccは、曖昧な文法を検出した場合、警告を発します。曖昧性を解消するためには、文法規則を修正したり、演算子の優先順位を指定したりする必要があります。

まとめ

Yaccは、構文解析器を自動生成する強力なツールです。コンパイラ開発や各種言語処理系開発において、その力を発揮します。この記事では、Yaccの基本的な使い方から、動作原理、構文規則の書き方、エラー処理、曖昧な文法への対処法まで解説しました。Yaccを使いこなすことで、より高度なプログラミングが可能になります。

もう一度検索