flexとbisonを使って簡単な電卓を作る
はじめに
この記事は
の続きになるゾ
前回lexとyaccの記述方法について書いたので、今回はlexとyaccを使ってオレオレ言語電卓を作ります。
さらに前回説明しなかったlexとyaccを使ったプログラムのコンパイル方法とかyaccプログラムの解説とかをしていきます
電卓プログラム
電卓は
lexで字句解析→yaccで構文解析→構文解析した結果に従ってプログラム実行
という感じにしていけばできるはずなので、まずは電卓で使用される文字を識別するためにlexでルールを作ります
今回は簡単な四則演算ができればいいと思うのでこんな感じ
lexプログラム
%%
"+" return(ADD);
"-" return(SUB);
"*" return(MUL);
"/" return(DIV);
"/n" return(LF);
[0-9]+ { yylval = atoi(yytext);
return(NUMBER); }
[ \t]+ ;
. ;
%%
yaccプログラム
%token LF
%token NUMBER
%left ADD SUB
%left MUL DIV
%%
list : /* empty */
| list expr LF { printf("%d\n",$2); }
;
expr : expr ADD expr { $$ = $1 + $3; }
| expr SUB expr { $$ = $1 - $3; }
| expr MUL expr { $$ = $1 * $3; }
| expr DIV expr { $$ = $1 / $3; }
| NUMBER
;
%%
#include "lex.yy.c"
main(){
yyparse();
}
yaccプログラムの解説
宣言部のところ
tokenを宣言することでルール部で使用することができるようになります。
ルール部での符の宣言に%leftや%rightがあり、コンパイラにおけるそれぞれ左結合、右結合なのですがいちおう説明
3+5-4+2と言った式があった場合、左(3+5)から順に計算して欲しいときは左結合、逆に4+2から計算して欲しい場合は右結合になります。
加減乗除は左から計算していくので左結合になります。
乗除は加減よりも先に計算するという優先度があります。
そのため宣言をADDとSUBよりも下に書くことでMULとDIVの処理を先に行うように設定します。
ルール部
大体見た感じで解ると思います。入力におけるルール部の動きを追ったほうが説明しやすいしわかりやすいと思うのでそのように説明します。
まず入力が3 + 4 * 2 - 6 / 3 \nであったとします。
そうすると字句解析の結果NUMBER ADD NUMBER MUL NUMBER SUB NUMBER DIV NUMBER LFとなります。
ルール部にexpr : NUMBERとあるのでexpr ADD expr MUL expr SUB expr DIV exprとなります。
宣言部でMULとDIVは左結合で最優先となるのでexpr MUL exprがルール部のルールとなりexprとなります。またこの値は$1 * $3なので入力と照らし合わせて4 * 2で8になっています。
そんな感じで構文規則の通りに変換するとexpr ADD expr SUB exprとなっています3 + 8 - 2となるわけです。
次はADDとSUBなのでこれも同様にしていくので最後にexprが残ります。（この値は9）
listのところの構文規則ですが最初にlist: /* empty */となっています。これはlist : expr LFと同じ意味である。
なので最後には答えである9が出力されるわけである。
ここでなぜlist : expr LF {}と記述しないのという部分の話だが。これはCtrl-Dを入力として受け付けるためである。
list : /* empty */の規則はトークンを含まない空の入力文字列を受け取るためCtrl-Dが入力として受け付けられプログラムを終了します。
このように入力に合わせて構文規則を作っていく。
プログラム部
main関数をここで呼んでいる。この中でyyparse()を呼び出すことで構文解析が行われる
詳しいところはここで Bison 1.28: 構文解析器のC言語インターフェイス
lexとyaccの連携及びコンパイル
上のlexプログラムをcalc.l、yaccプログラムをcalc.yとする。
また実行ファイルをexecuteとすると、以下のコマンドで実行ファイルができあがる
$ flex calc.l $ bison calc.y $ gcc calc.tab.c -lfl -ly -o ./execute
flex calc.lでyaccプログラム内で呼び出すlex.yy.cファイルが作成され、次のbison calc.yでgccでコンパイルする`calc.tab.cが作られる
後はgccでコンパイルすれば実行ファイルができあがる。実行すると標準入力から受け付けた計算を計算してくれる
終わり
これで簡単な電卓は完成である。後は()を使用できるように改善とかはできますが今回はここまで(続くかどうかは知らない)
参考
前回のも合わせて参考にした記事
