俺のための yacc 入門

いつか何もかも忘れる自分に向けて。

この文書では、yacc って何？　美味しいの？　みたいなプログラマ、そうオレをターゲットに、 ステップバイステップで yacc の使い方 について学んでいく。

yacc

yacc (yet another compiler compiler) は構文解析器を作るためのツールです。

構文解析器って何よ？

大雑把に言えばプログラミング言語みたいな一定のルールを守った言語のことを 「 形式言語 」と呼びます。 そんな形式言語で書かれた文書を元に、構文木を作るツールが構文解析器です。

一般的に、コンパイラは字句解析器 (lexical analyzer, lexier) が字句解析をし、字句の列を作ります。 次に構文解析器 (parser) が字句の列を元に、構文木を作ります。 そして、最後にその構文木を元に計算を行う奴がいたり、もしくは実行可能なマシン語に変換する奴がいたりします。

yacc はこの構文解析器を作るためのツールになります。

準備

まずは yacc または、bison をインストールしましょう。

インストールされていれば、下記のコマンドでバージョン番号などが確認できるはずです。

$ yacc --version
bison (GNU Bison) 2.3
Written by Robert Corbett and Richard Stallman.

Copyright (C) 2006 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

また、 yacc は定義ファイルを元に C のコードを生成します。 ですので、 C のコンパイラをインストールしておく必要があります。

インストールされていれば、下記のコマンドでバージョン番号などが確認できるはずです。

$ cc --version
Apple LLVM version 8.0.0 (clang-800.0.42.1)
Target: x86_64-apple-darwin15.6.0
Thread model: posix
InstalledDir: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin

あとあと、どうせ使うことになるので lex または flex もインストールしておきます。 lex は字句解析器を作るためのツールとなります。 インストールされていれば、下記のコマンドでバージョン番号などが確認できるはずです。

$ lex --version
flex 2.5.35 Apple(flex-31)

ついでに make もインストールしておくと便利です。 インストールされていれば、下記のコマンドでバージョン番号などが確認できるはずです。

$ make --version
GNU Make 3.81
Copyright (C) 2006  Free Software Foundation, Inc.
This is free software; see the source for copying conditions.
There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A
PARTICULAR PURPOSE.

This program built for i386-apple-darwin11.3.0

初めての(何も起きない)構文解析器 - まずはいつもの Hello,World. から

まずは作業用のディレクトリを作り、そこに移動しましょう。

$ mkdir minimal
$ cd minimal

早速、“Hello, World.” と表示されるだけのプログラムを書いてみましょう。 構文解析器の定義ファイルである minimal.y を次のように書きます。

%{
#include <stdio.h>
int yyerror(const char *s);
int yylex(void);
%}

%%

PROGRAM : ;

%%

int main()
{
  yyparse();
  printf("Hello, World.\n");
  return 0;
}
int yyerror(const char *s) { return 0; }
int yylex(void) { return 0; }

書けたら早速動かしてみましょう。まずは yacc を用いて C のコードを生成します。 この時、何も指定しなければ y.tab.c というファイルが生成されるはずです。 次に、この C のコードをコンパイルして実行可能にします。 コンパイルができたら、動かしてみて、 “Hello,World.” と表示されるのを確認しましょう。

$ yacc minimal.y
$ cc y.tab.c
$ ./a.out
Hello, World.

定義ファイルの構造

yacc で用いる定義ファイルは宣言部、定義部、プログラム部の 3 部で構成され、それぞれ %% で区切られます。

/* 宣言部 */
%%
/* 定義部 */
%%
/* プログラム部 */

このうち、宣言部及びプログラム部は省略が可能です。

宣言部では使用する字句の宣言や全体で使う C の対局変数定義、関数の宣言などを行います。 定義部には構文解析で用いる、構文規則(文法の定義)を、そしてプログラム部では C の関数実装などを行います。

先ほど作った minimal.y を見ていきましょう。

宣言部では、全体で使うために stdio.h のインクルードをしています。 定義部には構文規則が書かれておりますが、今回は特に使わないので意味のない文法が定義されています。 最後にプログラム部ではエントリーポイントである main 関数及び、 yacc が字句解析のために要求する yylex 関数、 そしてエラー処理のために要求する yyerror 関数の実装が書かれています。

定義ファイルの書き方

構文規則

定義部には構文解析に用いる構文規則を書いていきます。 構文規則は以下の形式で定義します。

a : body ;

ここで、 a は文法の名前(非終端記号)で、 body はそれの構成要素です。 具体例として、「日付」の定義を見てみましょう。

date : year '/' month '/' day ;

この構文規則では、次のような書式を「日付」として扱うと定義しています。

「日付」は、まず「年」があり、次に ‘/’ があり、次に「月」があり、次に ‘/’ があり、最後に「日」が書かれている物である

このような構文規則を定義することで、例えば “2017/10/21” のような文字列が「日付」として処理されるようになります。

ところで、上記のような定義を見ると、year とか、 month とかも構文規則が必要になることに気づくかと思います。 その通りで、どんどんどんどん構文規則を定義していくと、最後は「文字」とか、「記号」とかのレベルまで分解可能です。 逆に言えば、「文字」とか「記号」とかは特に定義をする必要がありません。このように、構文規則の右側にのみ現れる記号を 「終端記号」といい、構文規則として定義される記号を「非終端記号」と呼びます。 「日付」の例で言えば、 year や day は非終端記号であり、別に構文規則の定義がされます。 一方、 '/' はスラッシュ記号そのものであり、定義はされません。つまり終端記号です。

構文規則の選択

さて、世の中には同じ記号を複数の構文規則で定義したい場合があります。 例えば、 “2017/10/21” も “2017-10-21” も「日付」として扱いたい場合などです。

この場合、yaccの構文規則では、次のように並べて書くことができます。

date : year '/' month '/' day ;
date : year '-' month '-' day ;

また、バー | を使うことで、より変更しやすく、見やすく書くこともできます。

date : year '/' month '/' day
     | year '-' month '-' day
     ;

再帰的な定義

再帰的に構文規則を定義することで柔軟な文法を定義することができるのも特徴です。 例えば “1,2” も “1,2,3” も「リスト」として扱いたいみたいな場合は、次のように定義します。 (item は [0-9]+ とする)

list : item
     | item list
     ;

この規則 2 である item list がミソです。

まず、規則 1 により、 item は list です。 よって、規則 2 より、item item も list になります。 よって、規則 2 より、item item item も list になります。 と、このように、再帰的に定義が可能となります。

構文規則とアクション

構文規則だけを定義し続けても、「だから？」みたいな気分になること請け合いです。 何らかの処理と関連付けないと意味がありません。 yacc では、構文規則とアクションを関連付けることができます。

アクションは任意の C のコードで、構文規則の次にブレース {} で囲って定義します。

A : '(' B ')'
  { foo(47, "bar") }
  ;

文法に基づいて文を解析しやすくするように、アクション中で次の疑似変数を使うことができます。

アクション中で値を返すためには $$ を使います。

{ $$ = 47; }

構成要素から値を取得するためには $1, $2, ... を使います。

{ printf("%d\n", $1); }

例を見てみましょう。

A : B C
  { printf("%d\n", ($1 + $2)); }
  ;
B : ','
  { $$ = 3 }
  ;
C : '.'
  { $$ = 5 }
  ;

こちらの定義では、 B が 3 を返し、C が 5 を返します。 返した値は、その定義を使う A で利用でき、A のアクション内では、 $1, $2, ... から使うことができます。 この $ の次につく数値は、構文定義の構成要素として現れる順に振られます。 ですので、上記の例では $1 が 3 に、 $2 が 5 になります。

これを用いたサンプルを最後に一つお見せしましょう。

expression : '(' expression ')'
           { $$ = $2 }

この定義は次のようになります。

「式」は ‘()’ でくくっても、「式」

字句解析の定義

最初の方にも書きましたが、一般的なコンパイラでは字句解析器が字句解析をし、 それによって得られた字句の集合を元に構文解析器が構文解析をします。 そして、yacc は構文解析器を作るツールです。

ですので、yacc は字句解器をする関数 int yylex(void); という関数の実装を要求します。

int yylex(void); はユーザからの入力を字句(token)に分解し、パーサに結果を渡す関数です。 この関数は字句の種類を表す字句番号を整数でで返し、トークンに関連付けられた値がある場合は外部変数の yylval に割り当てます。

さて、この int yylex(void); は自作可能ですが、少なくとも入門者が自作するのは無謀なので、 字句解析器を作るためのツールである lex を使います。

字句解析器の生成ツール lex との連携

直前にも書きましたが、yacc は字句解器をする関数 int yylex(void); という関数の実装を要求します。 そして、その関数は自作可能ですが、入門者ならば lex を使い自動生成した方が簡単です。

lex は字句解析器を作るためのツールです。

lex も yacc と似ており、字句解析器の定義ファイルを lex に渡してやることで、 字句解析器の C ソースファイル(デフォルトでは lex.yy.c )が作成されます。

$ ls
minimal.l
$ lex minimal.l
$ ls
minimal.l lex.yy.c

また、定義ファイルの構成も似ており、宣言部、定義部、プログラム部の 3 部で構成され、それぞれ %% で区切られます。

/* 宣言部 */
%%
/* 定義部 */
%%
/* プログラム部 */

lex で定義するのは字句解析器向けのルールになるので、定義部は yacc で用いる定義ファイルと異なります。 lex で定義する字句解析ルールの書き方は簡単で、まずマッチさせるための正規表現を書き、次にアクションを書くだけです。 アクションは C のプログラムコードで書き、1文ならそのまま、2文以上なら {} で囲んで書きます。

サンプルとして、単語数を数える字句解析器のコードを見ながら説明しましょう。

%option noyywrap
%{
  int num_lines = 0, num_words = 0, num_chars = 0;
%}
%%

\n { ++num_lines; }
[a-zA-Z0-9]* { ++num_words; }
. { ++num_chars; }

%%

int main(void) {
  yylex();
  printf("# of lines = %d, # of words = %d # of chars = %d\n", num_lines, num_words, num_chars);
}

この定義ファイルを元に字句解析器を作り、動かしてみると(精度はイマイチですが)きちんと動くのがわかるかと思います。

$ lex mywc.l
$ cc lex.yy.c
$ cat mywc.l | ./a.out
# of lines = 17, # of words = 42 # of chars = 133

さて、この lex を使って yacc 向けの int yylex(void); 関数を実装するわけですが、 この時、上記に示した lex 単体で動くプログラム、 mywc.l と次の3点を変える必要があります。

  1. lex 向けのオプション noyywrap を消す (要調査)
  2. lex のアクションで字句名を返すようにする
  3. lex と yacc で同じ字句名を使えるように、 lex 側で y.tab.h (yacc の生成するヘッダ) を読み込む

サンプルとして、入力中から日付だけを抜き出すプログラムを作ってみましょう。

まずは作業用ディレクトリを用意します。

$ mkdir datefinder
$ cd datefinder

次に、字句解析器の定義を作っていきます。 字句解析器は、与えられた文字列を、字句ごとにバラバラにするのが目的です。 今回は、与えられた文字列を、「年」「月」「日」「それ以外」に分解していきましょう。

なお、簡単にするために「月」は英語の省略形 (例えば ‘Jan’) のみを認めることにします。

%%



%%

もう少しマシな解析器 - 加算器

yacc の詳細を探りながら、次の話に進みましょう。

加算・減算器の実装

lex との連携