bison/flex(yacc/lex)について

(コンパイラコンパイラ)

始めに

パーサーを自分で作る必要性がでてきたので、 コンパイラコンパイラを利用してみることにしました。 (パーサーとは、文法に基づいて書かれている文章の中身を 解析するソフトのこと)

あまり参考資料がなかったので苦労しました。 苦労したところ、経験して理解したことについてメモしていきます。 基本的な文法については、他のぺーじを見て勉強してください。

ちなみにここでは、linuxにインストールされている、 「bison,flex」を利用しています。(多分、どこでも同じでしょうけど。)

1.コンパイルとファイルの関係について

flexファイル「*.l」と、bisonファイル「*.y」がソースファイルになる。 ここでは、「parse.y」と「parsel.l」を例にとって説明する。

コンパイルの手順

bison -d parse.y (parse.tab.c parse.tab.h を生成)
flex parsel.l (lex.yy.cを生成)
gcc parse.tab.c lex.yy.c -lfl -o parse
bisonとflexのコンパイルの順番は、変わっても問題がない。

parsel.lについて

下の一文を必ず加える。

#include "parse.tab.h"
これによって、指定した%tokenを問題なく使えるようになる。
(parse.tab.hは、bison のコンパイル時に、オプション-dをつけないと 生成されないファイル)

parse.yについて

場合によっては、

#include "lex.yy.c"
を加えなければならないことがあるが、 これがあるためにエラーが起きることもある。 gccでコンパイルする際に、lex.yy.cも同時にコンパイルすれば良いことが多く、 加えない方が良いことが多い。 (これでかなりはまりました)

yylvalを利用する

問題

数値や単語などにマッチしたときに、 その値をbisonファイルに返したい時が多くある。 サンプルプログラムを見ると、 yylvalをintやdoubleなどに指定してそれに代入する方法で値を戻している。

例えば、、

"+" return (ADDOP);
"-" return (SUBOP);
"*" return (MULOP);
"/" return (DIVOP);
"(" return (LP);
")" return (RP);
[0-9]+ { yylval = atoi(yytext); return (NUMBER);}
[ \t] ;
\n return (NL);
というように。

ところが、

[a-zA-Z]+ { yylval = yytext; return (CHAR);}
をこれに加えたいときは、型があわないため、コンパイルできない。

しかし、型変換、なんて荒業は使わなくても良い方法がある。 unionを利用する。

解決

yylvalをunionにし、その中に型の異なる変数を含める。

parse.y

%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
%}
%union{
double n;
char *ch;
}
 /* action */
%token SEE
%token HEAR
etc.

parsel.l 

([0-9]+)|([0-9]+\.[0-9]*) { sscanf (yytext, "%lf", &yylval.n);
                            return (NUMBER); }
[a-zA-Z]+     {yylval.ch = yytext; return (CHAR);}

2.autoconfを利用する

当然利用可能。ただ、落とし穴が多少あるので注意する点を書く。 注意する点は３つ。

Makefile.am、 configure.in

とりあえず「Makefile.am, configure.in」について。 中身を見た方が早い。

configure.in 

AC_INIT(parsel.l)
AM_INIT_AUTOMAKE(calc, 0.1.0)

dnl Checks for programs.
AC_PROG_CC
AC_PROG_YACC
AM_PROG_LEX

dnl Checks for libraries.
dnl Replace `main' with a function in -lfl:
AC_CHECK_LIB(fl, main)

dnl Checks for header files.
AC_HEADER_STDC
AC_CHECK_HEADERS(malloc.h unistd.h)

AC_C_CONST

dnl Checks for library functions.

AC_OUTPUT(Makefile)
AM_PROG_LEXと、AMにするのを間違えないように。ACではない。 そのほかは、autoscanをしたままになっている。

Makefile.am 

noinst_PROGRAMS = parser

parser_SOURCES =  parse.y parsel.l
YFLAGS =  -d
ここで、中間生成ファイル(つまり、parse.tab.cなど)は含めない。 また、bisonファイルを先に、flexファイルを後にしないと、うまくコンパイルで きないことが多い。

#include "parse.tab.h"について

automake, autoconfでは、bisonを実行したあと、 ファイル名を自動的に変更指定しまう。 そのため、インクルードするはずだったファイル名が変わってしまう。 その点に注意する。

具体的には、「parse.y」 →「parse.tab.c 、 parse.tab.h」 → 「parse.c、parse.h」という変更が行われる。 よって、#include "parse.tab.h"ではなく、#include "parse.h" と、ソースファイルに書いておかなければならない。

ファイル名について

上でも書いたが、ファイル名を勝手に書き直してくれてしまう。 ということで、「parse.l」と「parse.y」は、automakeをつかうと、 最終的なファイル名が同じになってしまう。

これではエラーが起きても当然なので、これを避けるために、 異なる名前にする。 (あまり美しい解決方法ではない。 その他の方法を知っている人は、ぜひ教えてください。)

C++を使う

パーサ以外はC++でオブジェクト指向でプログラムしている場合、 当然bisonで生成されるコードでも、せめてクラスくらいは理解して欲しい。 そのためには、C++のコードである必要がある。

automake、autoconfを利用する場合、Parse.y++などという名前にしておくと、 自動的にParse.c++という名前に置き換わる。 同様に、Parse.yyはParse.ccに置き換わる。 この機能を利用すれば、C++のコードとしてコンパイルするので、 クラスなどを理解することができるようになる。

ただこれだと、classの中にパーサを埋め込むことができない。 (もしかしたら必要ないのかも知れないけれど)。 bison++というツールを使うと、もしかしたらできるのかもしれないが、 調べていない。 少なくともそのままでは、automake、autoconfでは対応していない。

(後日談) manによるとbison++とflex++でparserクラスがつくれるらしい． あと，Yet-another Object-Oriented Lex (YooLex)ってのもあるらしい．

参考ページ