bison/flexに関する極々個人的メモ。

私自身のためのメモであり、解説等になっていたり、ましてやこれを読めばbisonとflexがばりばり使えるようになるなどと思ってはなりません。ちなみに私はbisonとflexは勉強しはじめたばかりであり、ここに書いてあることが間違っていたらごめんなさい。

bison/flexとは。

bison及びflexは、多少の相違はあるものの、それぞれyaccとlexのGNU版らしいです、簡単に言うと。で、bisonは構文解析ルーチン生成ツールであり、flexは字句解析ルーチン生成ツールです。これを駆使すればコンパイラとかも作れちゃいますね。

flexのメモ

先程も書いた通り、字句解析ルーチン生成ツールです。多少の違いはあるものの、基本的にlexの上位互換となっており、正規表現で字句のパターンを記述する。

flexのプログラム構成は以下のようになる。

[定義部]
%%
[ルール部]
%%
[ユーザ定義サブルーチン部]

定義部

宣言部と説明している書籍もある模様。ここでは初期設定等を行うCのコードを記述し、このコードはflexによりプログラムにそのままコピーされる。flexにプログラムにコピーさせたいコードはこの定義部内で%{と%}の間に記述する。また、%{と%}の間の外には開始状態を示すコードを書いてみたりトークンの宣言を書いてみたりするようだ。

ルール部

ここでは、探すパターンと探すパターンがあった場合にどのような処理を行うのかを記述する。パターンは正規表現の拡張版と言えるようなものになっている。

・パターン記述方法（flex版拡張正規表現）

*

直前の正規表現の０個以上の繰り返しにマッチ

+

直前の正規表現の１回以上の繰り返しにマッチ

?

直前の正規表現の0回もしくは1回の繰り返しにマッチ。繰り返しって言うのか？？

.

改行を除く任意の１文字にマッチ

^

正規表現の先頭にある場合は行の先頭にマッチする。ただし[と]の間にある場合に関しては[]の説明を参照のこと

$

正規表現の最後にある場合は行の最後にマッチする。

\

メタ文字のエスケープに使用

|

直前の正規表現もしくは直後の正規表現にマッチ。すなわちor。

/

/の直後の正規表現にマッチする文字列の直前に/の前にある正規表現がマッチする場合に、/の前にある正規表現だけにマッチする。

""

C言語のエスケープシーケンスを除き"と"の間の文字そのものにマッチする。これすなわちC言語のエスケープシーケンス以外のメタ文字が特殊な意味を失い、その文字そのものとなる。

()

(と)の間にある一連の正規表現をグループ化する。

[]

[と]に囲まれた文字のうちどれか一文字にマッチする。ただし[の直後が^の場合は[と]に含まれない一文字にマッチする。また[の直後と]の直前以外で-が記述された場合、それはその-をはさむ文字の範囲にマッチする(0-9とあれば0123456789にマッチする)。

{}

(1) 括弧内に１つか２つの数字を記述すると、直前のパターンが何回繰り返して出現した場合にマッチするかを表す。数字が１つの場合はその回数出現した場合、数字が２つの場合ははじめの数字からふたつめの数字の間の回数の繰り返しに対しマッチする。
(2) {と}の間に名前が指定されている場合、その名前が意味する正規表現に置き換えられる。こいつは定義部で宣言することができる。

・アクション記述方法

パターンを行頭から記述し、同じ行にそのパターンにマッチした場合の処理を記述し、間にひとつ以上の空白文字（タブもしくは半角スペース）を置く。アクションの記述方法も説明しなきゃいけない。基本的にはC言語そのもの。後に説明するbisonに値を渡すには、そのマッチした値をyylvalに代入し、型を表す値(トークン型)をreturnする。

ユーザ定義サブルーチン部

単にサブルーチン部と呼んでいる書籍もあるようだ。input()、unput()、output()、yywrap()を再定義する場合には、ここに新しい定義のそれら関数と、それら新たな関数に必要となる関数を記述するのが一般的。

bisonのメモ

bisonの文法ファイルを書いて、それをbisonに渡すとその文法に則って構文の解析をするためのC言語のソースファイルが出力される。このソースファイル、というか、関数なんですけど、その関数の名前はyyparseという。なので、yyparseを呼びたい場所で呼べばよい。プログラムが始まったらいきなり解析したかったらmainの中の頭で呼び出す。構文の解析がうまくいかない場合にはyyerror関数が呼び出される。また字句解析関数としてyylexを用いるのでflexで生成するか、自分で気合で書いてもよい。このyylexからなにを受け取るかというと、トークン型(token type)と意味値(semantic value)である。たとえば100という文字があったとしたら、トークン型はINTEGER、意味値は100みたいな感じになる。トークン型がyylexの返り値となり、意味値はyylexにより大域変数となるyylvalに代入される。トークンは通常複数の型（たとえば数値だったり文字列だったり）となるであろうから、yylvalも複数の型を許容しなくてはならない。これを実現するため、後に説明する宣言部でどのような型を許容するのかを%unionというキーワードに続けて記述する。

bisonのプログラム構成は以下のようになる。flexとよく似ております。lexがyaccの構成をパクったからです。

[宣言部]
%%
[ルール部]
%%
[プログラム部]

宣言部には～を、ルール部には～を、プログラム部には～を記述する。宣言部とプログラム部は省略可能。なお、コメントはC同様/* ～ */で記述できる。

宣言部

宣言したってください。

ルール部

ここで構文がツリー構造になるように記述する。ツリーだから、すなわち、ルートがある。ルールをいろいろ書いていくんだけども、最終的にはひとつのルールに収束するってこと。よく使いそうなルールを書いてみると、a:b|a b;でaはひとつ以上のbという意味で、a: | a b;でaはゼロ以上のbという意味。

プログラム部

C言語でプログラムを書いてやってください。

bisonのコマンドラインオプション

bison実行時に適用できるさまざまなオプションの中でも使いそうな気がするものをいくつか。

-d

ヘッダを生成します。

組み合わせて使おう

ここまででそれぞれのツールの使い方をわかった上で、どうやって組み合わせて使うかを簡単に説明できたらいいなーと思います。が、どうなることやら。

最後に、、

ここで超単純サンプルコードを出したいと思っています。