yacc (yet another compiler compiler) はパーサ（構文解析を行うプログラム）を自動生成するツールです。 構文解析とは、入力された文について正しい文かどうか、どういう構造をした文か、などを分析することです。 lex (lexical analyser generator)はレキシカルアナライザ（字句解析を行うプログラム）を自動生成するツールです。 yacc と lex は UNIX なら標準で付属しています。Windows の場合、GNUプロジェクトが提供している bison と flex を使うことができます。 yacc と lex はそれぞれ別のプログラムですが、一緒に組み合わせて使われることが多いです。 yacc と lex はパーサを C言語のソースプログラムとして生成します。 Java でパーサを作成したい場合は JavaCC を使用します。
英語で例えると、入力された文に I や You などの単語が現れたら主語、run や write が現れたら動詞に分類するのが字句解析です。 そのうえで、S (主語) + V (動詞) + O (目的語) + . (ピリオド) のように英語の語順として正しく並んでいるかどうかを分析するのが構文解析です。
lex
lex 字句解析を行うプログラムを自動生成するツールです。 字句解析プログラムは、入力された文からトークン（文法を構成する意味のある最小単位）を識別します。 字句解析で行う作業は、英文解析の場合で例えると主に次の2つです。
- 単語を取り出して名詞や動詞、形容詞などの品詞に分類する
- vtbgvfujiko のように単語（品詞）としてあり得ないものをエラーとして検出する
字句解析器（レキシカルアナライザ）は上記2つを行ったうえ、それぞれに対して何らかのアクション（動作）を行います。
lex ソースファイル
lex は lex ソースファイルから lex.yy.c を作成します。 lex ソースファイルの特徴を次に示します。
- 拡張子は .l
- 定義部、ルール部、サブルーチン部の3つに分かれている
- 各部分の区切りに %% が使われる
lex ソースファイルの構造を次に示します。
%%
ルール部
%%
ユーザーサブルーチン部
定義部
定義部には、C言語の宣言やlexに与えるオプションを記述します。
%{
#include <stdio.h>
#include "y.tab.h"
%}
ルール部にはスキャナのルールを記述します。
サブルーチン部にはC言語のプログラムを記述します。サブルーチン部は省略することができます。
ルール部
字句解析のルールを記述します。
pattern には識別したいものを記述します。正規表現が使えます。
action には pattern が見つかったときに実行されるC言語の式を記述します。
action に複数の式を記述するには { と } で囲みます。
どのパターンにも当てはまらない場合は、標準入力からの入力をそのまま標準出力に出力します。 たとえば、次の lex プログラムではパターンがひとつも記述されていないため、単に標準入力からの入力をそのまま標準出力に出力します。
%%
「何もしない」アクションを定義したい場合は、セミコロン記号のみ記述します。 例えば、次のプログラムでは、標準入力からの入力に「hello」という単語が現れたら何もしません（標準出力に出力しません）。
%% hello ;
次のプログラムでは、標準入力からの入力に hello という単語が現れたら HELLO に置き換えて標準出力に出力します。
%{
#include <stdio.h>
%}
%%
hello { printf("HELLO"); }
lex の実行
lex ソースファイルをコンパイルすると、lex.yy.c ファイルが生成されます。
lex.yy.c をコンパイルおよびリンクする際は、lex ライブラリとリンク (-ll) します。 lex の代わりに flex を使用している場合は、flex ライブラリとリンク (-lfl) します。
状態
lex は「状態」によって動作を変えることができます。 lex は INITIAL という状態で始まります。 特定の状態のときにのみ適用するルールを記述するには、次のように記述します。
別の状態に変更するには、アクション部分に次のように記述します。
<INITIAL> 以外に独自の「状態」を作ることができます。 独自の「状態」を作るには、定義部に次のように記述します。
次に、コメント内部（'#' から改行まで）以外の lex という文字列を LEX に置き換えるプログラムの例を示します。
%{
#include <stdio.h>
%}
%s comment
%%
<INITIAL># {
printf("#");
BEGIN comment;
}
<INITIAL>lex {
printf("LEX");
}
<comment>\n {
printf("\n");
BEGIN INITIAL;
}
最初は INITIAL 状態です。 INITIAL 状態のときに lex という文字列が現れたら、LEX に置き換えて出力します。 INITIAL 状態のときに '#' という文字が現れたら、comment 状態に遷移します。 comment 状態のときに改行が現れたら、INITIAL 状態に遷移します。
たとえば、入力ファイルが次の内容だとします。
lex # lex lex
このプログラムの実行結果は次のようになります。
% samp1 < inputfile LEX # lex LEX
yacc
yacc は yacc ソースファイルから y.tab.c を生成します。
yacc ソースファイル
yacc ソースファイルの特徴を次に示します。
- 拡張子は .y
- 宣言部、ルール部、プログラム部の3つに分かれている
- 各の部分の区切りに %% が使われる
yacc ソースファイルの構造を次に示します。
%%
ルール部
%%
プログラム部
宣言部
宣言部にはC言語の宣言 (#includeなど) や、yaccの宣言、yaccに与えるオプションを記述します。宣言部は省略することができます。
ルール部
ルール部には構文規則を記述します。
プログラム部
プログラム部にはC言語のプログラムを記述します。プログラム部は省略することができます。
構文規則は次のように記述します。
「symbol が body からできている」という規則が成り立つ場合には、action が実行されます。 action の部分には、C言語の式を記述します。
symbol が body1 または body2 からできている場合には、複数記述することができます。
途中で改行を入れても構いません。上記は次のように記述することもできます。
symbol : body1
{
action1
}
| body2
{
action2
}
;
yacc の実行
yacc で文法ファイルをコンパイルする方法を次に示します。
yacc のオプションを次に示します。
- -d
- yacc またはユーザーが割り当てたトークン番号を、ユーザーが宣言したトークン名に対応させる #define 文を含んだ y.tab.h ファイルを生成します。この対応付けにより、y.tab.c 以外のソースファイルからトークン番号を参照することが可能となります。
yacc で文法ファイルをコンパイルすると、y.tab.c と y.tab.h が生成されます。