yacc (yet another compiler compiler)はパーサ（構文解析を行うプログラム）を自動生成するツールです。 構文解析とは、入力された文について正しい文かどうか、どういう構造をした文か、などを分析することです。 lex (lexical analyser generator)はレキシカルアナライザ（字句解析を行うプログラム）を自動生成するツールです。
英語で例えると、入力された文に You や She などの単語が現れたら主語、run や write が現れたら動詞に分類するのが字句解析です。 そのうえで、S (主語) + V (動詞) + O (目的語) + . (ピリオド) のように英語の語順として正しく並んでいるかどうかを分析するのが構文解析です。
つまり、まず字句解析（lex 又は flex）をしたうえで、次に構文解析（yacc 又は bison）を行うことになります。
yacc と lex は Linux なら標準で付属しています。Windows の場合、GNUプロジェクトが提供している bison と flex を使うことができます。 yacc と lex はそれぞれ別のプログラムですが、一緒に組み合わせて使われることが多いです。 yacc と lex はパーサを C言語のソースプログラムとして生成します。
lex 字句解析を行うプログラムを自動生成するツールです。 字句解析プログラムは、入力された文からトークン（文法を構成する意味のある最小単位）を識別します。 字句解析で行う作業は、英文解析の場合で例えると主に次の2つです。
字句解析器（レキシカルアナライザ）は上記2つを行ったうえ、それぞれに対して何らかのアクション（動作）を行います。
lex は lex ソースファイルから lex.yy.c を作成します。 lex ソースファイルの特徴を次に示します。
lex ソースファイルの構造を次に示します。
定義部
%%
ルール部
%%
ユーザーサブルーチン部定義部には、C言語の宣言やlexに与えるオプションを記述します。
%{
#include <stdio.h>
#include "y.tab.h"
%}ルール部にはスキャナのルールを記述します。
サブルーチン部にはC言語のプログラムを記述します。サブルーチン部は省略することができます。
字句解析のルールを記述します。
pattern actionpattern には識別したいものを記述します。正規表現が使えます。
action
には
pattern
が見つかったときに実行されるC言語の式を記述します。
action
に複数の式を記述するには
{
と
}
で囲みます。
pattern { 式1; 式2; }どのパターンにも当てはまらない場合は、標準入力からの入力をそのまま標準出力に出力します。 たとえば、次の lex プログラムではパターンがひとつも記述されていないため、単に標準入力からの入力をそのまま標準出力に出力します。
%%
「何もしない」アクションを定義したい場合は、セミコロン記号のみ記述します。 例えば、次のプログラムでは、標準入力からの入力に「hello」という単語が現れたら何もしません（標準出力に出力しません）。
%%
hello ;次のプログラムでは、標準入力からの入力に hello という単語が現れたら HELLO に置き換えて標準出力に出力します。
%{
#include <stdio.h>
%}
%%
hello { printf("HELLO"); }lex example.llex ソースファイルをコンパイルすると、lex.yy.c ファイルが生成されます。
lex.yy.c をコンパイルおよびリンクする際は、lex ライブラリとリンク (-ll) します。 lex の代わりに flex を使用している場合は、flex ライブラリとリンク (-lfl) します。
cc lex.yy.c -o example -lllex は「状態」によって動作を変えることができます。 lex は INITIAL という状態で始まります。 特定の状態のときにのみ適用するルールを記述するには、次のように記述します。
<状態>パターン アクション別の状態に変更するには、アクション部分に次のように記述します。
BEGIN 状態 ;<INITIAL> 以外に独自の「状態」を作ることができます。 独自の「状態」を作るには、定義部に次のように記述します。
%s 状態次に、コメント内部（'#' から改行まで）以外の 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
LEXyacc は yacc ソースファイルから y.tab.c を生成します。
yacc ソースファイルの特徴を次に示します。
yacc ソースファイルの構造を次に示します。
宣言部
%%
ルール部
%%
プログラム部宣言部にはC言語の宣言 (#includeなど) や、yaccの宣言、yaccに与えるオプションを記述します。宣言部は省略することができます。
ルール部には構文規則を記述します。
プログラム部にはC言語のプログラムを記述します。プログラム部は省略することができます。
構文規則は次のように記述します。
symbol : body { action } ;「 symbol が body からできている」という規則が成り立つ場合には、 action が実行されます。 action の部分には、C言語の式を記述します。
symbol が body1 または body2 からできている場合には、複数記述することができます。
symbol : body1 { action1 } | body2 { action2 } ;
途中で改行を入れても構いません。上記は次のように記述することもできます。
symbol :
body1 {
action1
}
| body2 {
action2
};yacc で文法ファイルをコンパイルする方法を次に示します。
yacc -d example.yyacc のオプションを次に示します。
yacc で文法ファイルをコンパイルすると、y.tab.c と y.tab.h が生成されます。
cc lex.yy.c y.tab.c -o exampleflexはGNUが開発した字句解析器であり、いわばGNU版lexである。
flex [options] [file]...以下に示すオプションを flex コマンドに指定できる。
大抵の Linux ディストリビューションであれば、予め flex がインストールされている。また、lex は flex へのリンクであることが多い。
Debian 系の Linux (Ubuntu, Linux Mint, etc.) であれば、 apt コマンドを使って flex をインストールすることができる。
$ sudo apt install flexbisonはGNUが開発した構文解析器であり、いわばGNU版yaccである。
bison [options] [file]以下に示すオプションを bison コマンドに指定できる。
大抵の Linux ディストリビューションであれば、予め bison がインストールされている。また、yacc は bison へのリンクであることが多い。
Debian 系の Linux (Ubuntu, Linux Mint, etc.) であれば、 apt コマンドを使って bisonをインストールすることができる。
$ sudo apt install bison