プログラミング言語を自作するにあたって，作成するモチベーションが湧かないのが字句解析器・構文解析器です。字句解析や構文解析から作ると，そこのコーディングやデバッグに時間を取られてしまい，オリジナルプログラミング言語の本質的な作業に取りかかるまでに日が暮れてしまいます。いや，日が暮れるまでに実装できればすごいです。字句解析器や構文解析器の実装は，コンパイラやインタープリタがどのように動いているかを学習するには良いですが，オリジナルのプログラミング言語を設計・実装するのに時間を割くほどのものではありません。

この考え方は昔からあり，1964年のSchorreらの論文 "META II a syntax-oriented compiler writing language"でコンパイラの生成を構文定義に従って行うメタコンパイラとして発案されています。この考えをもとに，コンパイラをBackus-Naur form (BNF)やExtended BNF (EBNF)などで定義した構文木と構文に対する実装をコンパイルすることでコンパイラを生成するものがコンパイラコンパイラです。

コンパイラコンパイラで有名なのはyaccがあります。名前はYet Another Compiler-Compilerの略です。yaccと共に用いられるのが字句解析器（生成器）のlexです。yaccが構文解析器と構文実装をコンパイルする機能を提供します。yaccとlexのGNU拡張版がそれぞれbisonとflexで，こちらもよく使われます。

lexは入力ファイルを解析し，lex.yy.cという字句解析器を実装したC言語のファイルを生成します。lex.yy.cはyylex()という字句解析を実行する関数が定義されています。

lexの入力ファイルは，以下のような%%で区切られた構成になっており，「定義（definitions）」，「規則（rules）」，「ユーザコード（user code）」の3つに分けられます。「規則」は省略不可ですが，「ユーザコード」は省略可能です。この場合，2つ目の%%も省略できます。なお，C言語形式のコメントを使用できますが，「規則」の行頭ではパターンと認識されるため使用できません（スペースを入れれば使用できます）。

/* 定義 */
%%
    /* 規則 */
%%
/* ユーザコード */

以下に各部の書き方を例示します。「定義」には規則で繰り返し使うパターン（以下の例ではDIGIT）の定義のほか，%{ と %}で囲んだ領域でlex.yy.c（の先頭部分）に直接出力されるコードを書きます。つまりヘッダファイルのインクルードなどはここに記述します。「規則」には，パターンとそれに対する処理を{}内に書きます。例えば{DIGIT}+は[0-9]+という正規表現を表しており，1文字以上の数字列にマッチします。マッチした字句は，yytextという文字列変数に格納されるので，以下のコードではatoi()を使って整数型に変換し，printf()にて出力をしています。

/*
 * 定義
 */
%{
/* %{ と %} で囲まれた部分は lex.yy.c にそのままコピーされます */
#include <stdio.h>
#include <stdlib.h>

/* 入力（yyin）が更新されていないかを返す関数。入力がend-of-fileに到達した後に呼ばれる。1 (true)であれば字句解析を終了し，0 (false)であれば入力が更新されたとしてyyinを再設定して再度字句解析を行う。 */
int
yywrap(void)
{
    return 1;
}
/* グローバル変数 */
int num_lines;
%}

/* 定義 */
DIGIT   [0-9]

%%
    /*
     * 規則
     */
{DIGIT}+ {
    printf("Integer: %s is parsed as %d\n", yytext, atoi(yytext));
}
{DIGIT}+\.{DIGIT}* {
    printf("Float: %s is parsed as %f\n", yytext, atof(yytext));
}
[A-Za-z\_]+ {
    printf("ID: %s\n", yytext);
}
[ \t]+    ; /* Ignore whitespaces */
\n        num_lines++;
%%
/*
 * ユーザコード
 */
/* main()関数を定義 */
int
main()
{
    printf("Executing lexical analyzer.\n");
    yylex();
    printf("Reached the end-of-file (%d lines).\n", num_lines);
}

上記のコードをファイル（ここではsample.lとします）に書き込み，

$ lex sample.l

を実行するとlex.yy.cが生成されます。以下のようにコンパイル，実行すると上記で定義したユーザコードが実行され，字句解析が実行されます。

$ cc -o sample lex.yy.c
$ echo "abc 123\n1. 3.2\ndef" | ./a.out
Executing lexical analyzer.
ID: abc
Integer: 123 is parsed as 123
Float: 1. is parsed as 1.000000
Float: 3.2 is parsed as 3.200000
ID: def
Reached the end-of-file (3 lines).

yaccは入力ファイルを解析し，y.tab.cという構文解析器を実装したC言語のファイルを生成します。-dオプションを指定した場合はy.tab.hというヘッダファイル（後述する%unionで宣言した部分をコピーしたファイル）を生成します。

lexと同様に，yaccの入力ファイルも以下のように「宣言（declarations）」，「規則（rules）」，「プログラム（programs）」3つの%%で区切られた構成となっています。「プログラム」は省略可能なため，2つ目の%%とともに省略できます。

/* 宣言 */
%%
/* 規則 */
%%
/* プログラム */

yaccではBackus-Naur form (BNF)に似た構文記法に実装をします。BNFは非常に単純で，以下の構文のように::=の左辺に非終端記号（nonterminal; 置換可能な記号），右辺に1つ以上の記号列からなる式を置きます。式に複数の選択肢がある場合は|で区切ります。右辺は終端記号（terminal）も含みます。

<symbol> ::= __expression__

例えば，整数四則演算式は以下のようになります。

; 式
expr ::=
        a_expr

; 加減算
a_expr ::=
       m_expr ( ("+" | "-") m_expr )*

; 剰余算
m_expr ::=
        u_expr ( ("*" | "/") u_expr )*

; 単項演算
u_expr ::=
        atom | "-" atom

; リテラル
atom ::=
        integer

; 整数
integer ::=
        nonzerodigit digit*

; ゼロ以外の数字
nonzerodigit ::=
        "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

; 数字
digit ::=
        "0" | nonzerodigit

yaccは，通常lexと共に使用します。なので，ここではyacc単体の例ではなく，lexと組み合わせて簡単な整数四則演算電卓を実装してみます。ここではsample.yに構文解析器を実装し，sample.lに字句解析器を実装します。実際にコンパイラの場合は構文解析後にアセンブリやバイトコードを出力する機能を実装しますが，ここでは簡単のためインタプリタのように構文解析器の中に実行機を実装します。

上記のBNFの例では数字列のリテラルも構文解析の一部として定義しましたが，この例では数字列から整数値への変換は字句解析器に実装します。

まず，字句解析器を実装します。上で例示したlexのサンプルプログラムは，main()関数から一度だけyylex()を呼んでおり，これで入力全体をパースしていました。yaccからも同様にyylex()を呼ぶことで字句解析の結果を構文解析に使うのですが，yylex()でひとつずつ字句を取り出すために，lexの規則でreturnにより字句のタイプを表す整数値を返します。この字句のタイプを表す整数値は後述するsample.yで定義し，yaccにより生成するy.tab.hに定義されています。

整数四則演算の例では，演算子（+，-，*，/）と改行（\n），整数値（(0|[1-9][0-9]*)）を規則に書きます。演算子と改行は字句に対して処理を必要としないため，そのまま字句のタイプ（TOK_ADD，TOK_SUB，TOK_MUL，TOK_DIV，TOK_NEWLINE）を返します。整数値は字句の文字列が格納されている変数yytextからatoi()関数により整数値に変換した後，外部変数yylvalに代入します。外部変数yylvalは後述するsample.yの%union宣言で定義する共用体の型で，変数yylvalにより整数値を構文解析器に渡すためにint型のメンバintvalを定義しています。

なお，空白とCR（[ \t\r]）は無視し，そのまま次の字句を処理するためにreturnで値を返しません。また，上述した文字以外については正規表現.で字句の先頭の文字を返すことで，構文解析器でエラーハンドリングをするのが一般的です。yaccで生成する字句の型は256以上の数字となるように生成されるため，衝突しません。

%{
#include <stdio.h>
#include <stdlib.h>
#include "y.tab.h"
int
yywrap(void)
{
    return 1;
}
%}
%%
"+"     return TOK_ADD;
"-"     return TOK_SUB;
"*"     return TOK_MUL;
"/"     return TOK_DIV;
[ \t\r]   ;
"\n"    return TOK_NEWLINE;
(0|[1-9][0-9]*) {
    int val;
    yylval.intval = atoi(yytext);
    return TOK_INT;
}
.       {
    fprintf(stderr, "Invalid character: %s\n", yytext);
    return yytext[0];
}
%%

次に構文解析器を実装します。

%unionには，字句の値を保持するための共用体を定義します。sample.yの%union定義は以下のように展開されます。

typedef union YYSTYPE
{
    int intval;
}

%tokenには字句のタイプを定義します。

%token TOK_ADD TOK_SUB TOK_MUL TOK_DIV TOK_NEWLINE

は値を持たない字句（ここでは演算子と改行）の型を定義しています。

%token <intval> TOK_INT

は上記共用体のintvalの値を持つ字句の型TOK_INTを定義しています。

%typeは構文規則で定義する非終端記号の型を定義します。ここでは加減算・剰余算を含めたすべての式は整数値を返り値に取るので，以下の通り，メンバの型として定義します。

%type <intval> expr a_expr m_expr u_expr atom

規則部には構文を定義します。yaccでは上述したBNFと似た構文で記述しますが，左辺と右辺は":"で分割します。また，右辺のそれぞれの式（記号列）に対して，構文解析器で実行する機能を実装します。右辺が単一のシンボルから成り，その値をそのまま左辺に渡す場合は実装は省略できます。この実装では$で始まる特殊な変数を使用します。$$は左辺，$n（nは自然数）は右辺のn番目のシンボルを表します。例えば，単項演算のu_exprは以下のように，整数値をそのまま取るか，-の後ろに整数値を取る場合（負の数）があり，負の数については- $2をu_exprの値とします。

u_expr:     atom
        |   TOK_SUB atom
            {
                $$ = - $2;
            }
            ;

プログラム部はエラーハンドラと構文解析器を実行するyyparse()を呼ぶmain()関数を実装しています。

%{
#include <stdio.h>
#include <stdlib.h>    
int yylex();
void yyerror(char const *);
%}
%union {
    int intval;
}
%token <intval> TOK_INT
%token TOK_ADD TOK_SUB TOK_MUL TOK_DIV TOK_NEWLINE
%type <intval> expr a_expr m_expr u_expr atom
%start stmt_list
%%
stmt_list:  stmt
        |   stmt_list stmt
            ;

stmt:       expr TOK_NEWLINE
            {
                printf(">> %d\n", $1);
            }
        |   TOK_NEWLINE
            ;
expr:       a_expr
            ;
a_expr:     a_expr TOK_ADD m_expr
            {
                $$ = $1 + $3;
            }
        |   a_expr TOK_SUB m_expr
            {
                $$ = $1 - $3;
            }
        |   m_expr
            ;
m_expr:     m_expr TOK_MUL u_expr
            {
                $$ = $1 * $3;
            }
        |   m_expr TOK_DIV u_expr
            {
                $$ = $1 / $3;
            }
        |   u_expr
            ;
u_expr:     atom
        |   TOK_SUB atom
            {
                $$ = - $2;
            }
            ;
atom:    TOK_INT
            ;
%%
void
yyerror(char const *s)
{
    fprintf(stderr, "Error: %s\n", s);
}
int
main(int argc, const char *const argv[])
{
    extern int yyparse(void);
    extern FILE *yyin;

    yyin = stdin;
    if ( yyparse() ) {
        fprintf(stderr, "Parse error!\n");
        exit(EXIT_FAILURE);
    }
}

以下のコマンドでコンパイルします。yaccはヘッダファイルy.tab.hを生成するために-dオプションを付けています。

$ lex sample.l
$ yacc -d sample.y
$ cc -o sample y.tab.c lex.yy.c

int yylex();
int yyerror(char const *);

なお，この2行は以下のWarningsを回避するために記述しています。

y.tab.c:1242:16: warning: implicit declaration of function 'yylex' is invalid in C99 [-Wimplicit-function-declaration]
      yychar = YYLEX;
               ^
y.tab.c:598:16: note: expanded from macro 'YYLEX'
      # define YYLEX yylex ()
                     ^
y.tab.c:1397:7: warning: implicit declaration of function 'yyerror' is invalid in C99 [-Wimplicit-function-declaration]
      yyerror (YY_("syntax error"));
      ^
y.tab.c:1543:3: warning: implicit declaration of function 'yyerror' is invalid in C99 [-Wimplicit-function-declaration]
  yyerror (YY_("memory exhausted"));
  ^