ゴールデンウィークからゲームをやりすぎて食傷気味の今日この頃…。 趣味でプロダクト開発を始めたら、構文解析がしたくなったのでいろいろ調査をしていた。 正規表現を使って頑張るのでもいいのだけど、すでにあるツールを活用したくGNU bisonを使うことにした。
GNU bison
GNU bisonは、構文解析ジェネレータである。
bisonの文法で書かれたファイルを用意してbisonコマンドでコンパイル(トランスパイル？ビルド？)すると、C言語のファイルを吐いてくれるという便利なしろもの。
出力された、C言語のファイルには yyparse という関数が定義されているのでこの関数を呼び出せば構文解析できる。
しかしながら、構文解析はできても字句解析ができないのでこれは自作するしかない。
具体的には yylex 関数を作成する必要がある。
そこで登場するのがflexである
flex
flexは字句解析ジェネレータである。
flexの文法で書かれたファイルを用意してflexコマンドでコンパイルすると、C言語ファイルを吐いてくれる。
出力されたファイルには yylex 関数が定義されているので、GNU bisonで組み合わせるといい感じに字句解析＋構文解析ができるという寸法である*1。
便利〜〜
単純な計算機を作ってみた
実際に作ってみた。コードはGitHubにアップロードしてある。
READMEに書かれている通りに実行すると、最終的に calc という実行ファイルができる、
ここに計算式を入力すると計算結果が返ってくる。
$ echo "1+1" | ./calc 2 $ echo "2*(3+4)" | ./calc 14
なお、実装の都合上、四則演算とカッコしか使えず、また小数点も使えない*2。
解説
字句解析部分
字句解析(flex)はcalc.lに定義されている。
WHITESPACE [ \t] INTEGER [0-9]+ SYMBOL [+\-*/()] LF "\n" %% {WHITESPACE} {INTEGER} { yylval = atoi(yytext); return(INTEGER); } {SYMBOL} { return(yytext[0]); } {LF} { return(LF); } . %%
flexファイルは %% で区切られており各セクションで、それぞれ定義する。
最初のセクションは定義部で、各パターンと名前を定義している。
これは必須ではなく、次のルールセクションでパターンを書いても良い。
わかりやすくするためにパターンに名前を付けている。
次のセクションはルール定義部。
ここではパターンにマッチした部分をどう処理するかを定義する。
書式は パターン { アクション } のように書く。
パターンには正規表現が利用できる。また、定義部で定義したパターンを利用することもできる。
アクションはC言語で書く必要がある。
returnでは、このパターンにマッチしたトークンの識別子を任意の数値で返す必要がある((yylexの戻り値はint型 int yylex(void)))。
しかし、数値だと可読性が悪いのでわかりやすい定数にしておくとよいっぽい。
この定数は、bisonで定義する。
yytextはパターンにマッチした文字列が入っている。
この例では、 {SYMBOL} でマッチングした文字をそのままトークンの識別子にするために使っている。
また、yylvalにはbisonで処理するときに使用する値を格納する。
通常はマッチングした文字列をそのまま使用しているが、この例では {INTEGER} はint型にしておいた方が便利なのでatoiで数値に変換している。
アクションを省略した場合は読み飛ばされる。
この例では {WHITESPACE} にマッチした場合と、 . の場合に読み飛ばしている。
最後のセクションはユーザコード部になっている。 ここに書いたコードは、flexが生成したコードの末尾に追記される。 この例では使用していないために空になっている。
なお、ユーザコード部は生成コードの末尾に追加するが逆に先頭に追加したい場合がある。
そういうときは定義部の前に %{ 〜 %} で括ったブロックを定義することで実現可能である。
字句解析のコードができたら以下のコマンドを実行するとコードが生成される。
flex calc.l
コードは lex.yy.c というファイル名で出力される。
構文解析部分
構文解析(bison)はcalc.yで定義されている。
%{
#include <stdio.h>
extern int yylex (void);
extern int yyerror (const char* str);
%}
%token LF
%token INTEGER
%left '+' '-'
%left '*' '/'
%start list
%%
list : /* empty */
| list LF
| list expr LF { printf("%d\n",$2); }
;
expr : INTEGER
| expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
| expr '*' expr { $$ = $1 * $3; }
| expr '/' expr { $$ = $1 / $3; }
| '(' expr ')' { $$ = $2; }
;
%%
#include "lex.yy.c"
int yyerror (const char* str){
fprintf(stderr, "parse error near %s\n", yytext);
return 0;
}
int main() {
yyparse();
return 0;
}
bisonの文法はflexと同じ%%で区切られていて、各セクションごとに別れている。 各セクションの役割もflexと同じである。
今回の例では、 %{ 〜 %} で囲われたC言語宣言部では、include処理やyylex/yyerrorの宣言を行っている。
これは必須ではなく、gccでコンパイルするときに発生するWARNINGメッセージを消すために書いている。
定義部では、トークンに使用する文字の定義( %token) や演算子の優先順位を定義する。
%left は左結合演算子であることを宣言しているのだが、勉強不足でまだ正しく理解していない。。。
%left あとに定義するほど優先度が高くなる。
%start は次のルール定義部での、処理を開始するルールを指定する。
ルール定義部ではBNF記法で定義していく。
アクション部分では、 $1や$2といった変数を使うことができる。
これは、パターンで定義したグループのマッチした値を参照する。
expr '+' expr ~~~ ~~~ $1 $3
最後に、ユーザコード部。 yyerror関数は定義が必須である。 今回はstderrにエラー出力しているが、何も処理をしなくてもよい。 また、ファイルを増やしたくなかったのでmainもここで定義している。
構文解析ファイルを作ったら以下のコマンドでコードを生成できる。
bison calc.y
生成されたファイルは <name>.tab.c というファイル名で生成される。
デフォルトでは標準入力を使う
flexが生成するコードでは、デフォルトで標準入力からテキストを読み込む。 そのため、今回作ったcalc.lとcalc.yだけで処理できる。 標準入力以外から取りたい場合は、yyinにファイルポインタを格納すればよいらしい。 また、ファイル以外から入力したい場合は自分でyyinput関数を定義すればいいらしい。
最後に
GNU bisonとflexを使って簡単な計算機が作れた。 ネットで出てきた情報を眺めていたけど、全くどうなっているか理解できなかったが実際触ってみたら理解できたので手を動かすって重要だなって思った。
まだ触りだして時間が経っていないので、正しく理解していなかったりよりよい書き方があるかもしれないので、そういうのがあったら、コメント等で優しく教えてもらえると幸いです。
