最近ちまちまとyacc/lex(実際はbison/flex)を触っているのですが、やたらと苦労しています。真面目に学校に行ってなかったのが悔やまれますが、愚痴っていても仕方が無いのでメモ書きです。
ここでは以下の様なTinyCモドキのコードをyaccとlexで扱ってみます。
main() { var i; var s; s = 0; i = 0; while(i < 10){ s = s + i; i = i + 1; } println("s = %d",s); }
TinyCについてはコチラのページを参考にさせて頂きました。何故モドキかと言うと、僕にはTinyCですら複雑だったので、TinyCを更に小さくしたモドキをパースする事にしました。ヘタレですいません。
まずはlexで字句解析をします。ここでは各ルールにマッチした文字をそのまま出力させています。ルールに対応する処理内では、yytextでマッチした文字列、yylinenoで行番号を取得しています。
/* * tinyc.l */ /* 準備 */ %{ #include "stdio.h" %} /* 規則 */ %% [ \t] { /* Skip white space */ } [\n] { yylineno++; } "while" { printf("%d: WHILE\n", yylineno); } "var" { printf("%d: VAR\n", yylineno); } "for" { printf("%d: FOR\n", yylineno); } [0-9][0-9]* { printf("%d: CONSTANT %d\n", yylineno, atoi(yytext)); } \"[^\"]*\" { printf("%d: LITERAL %s\n", yylineno, yytext); } [a-zA-Z][0-9a-zA-Z]* { printf("%d: IDENTIFIER %s\n", yylineno, yytext); } . { /* Skip other characters */ } %% /* ユーザ関数 */ int main() { yylex(); }
特に難しいところは有りませんね。以下のように実行します。ビルド時にlibflをリンクしている事に注意しましょう。
$ flex tinyc.l $ gcc lex.yy.c -o tinyc_scan -lfl $ ./tinyc_scan < test.c 1: IDENTIFIER main 3: VAR 3: IDENTIFIER i 4: VAR 4: IDENTIFIER s 5: IDENTIFIER s 5: CONSTANT 0 6: IDENTIFIER i 6: CONSTANT 0 7: WHILE 7: IDENTIFIER i 7: CONSTANT 10 8: IDENTIFIER s 8: IDENTIFIER s 8: IDENTIFIER i 9: IDENTIFIER i 9: IDENTIFIER i 9: CONSTANT 1 11: IDENTIFIER println 11: LITERAL "s = %d" 11: IDENTIFIER s
無事に字句解析に成功していますね。これで与えられた文字列を分解して特定の塊ごとに処理できるようになりましたが、それだけではあまり役に立ちません。実際は塊の並びに基づいた処理をしたいことが多いです。例えば変数の宣言だけ抜き出したいとか、関数の呼出し部分だけ変更を加えたい等が考えられますが、自前で実装となると結構大変なのでyaccを使って必要なパーサを自動的に生成するというのが話の流れです。
早速先ほどの字句解析に対応するyaccファイルを実装したいところですが、その前に字句解析側をyaccに対応するように修正する必要があります。具体的にはyaccの入力に必要なトークン列を字句解析側で準備します。先ほどはルール部の核処理で、マッチした文字列をそのまま出力していましたが、今回は各ルールに対応したトークンを返却するようにしています。
また、これらのトークンはyacc側で定義されていることが期待されていて、その為にtinyc.tab.hというファイルをincludeしています。またyylvalという変数にトークンの実際の内容を代入しています。これでyaccはlexが返した各トークンを並べたトークン列を元に処理でき、必要に応じてトークンの内容も参照できるようになります。
/* * tinyc.l yacc向けに修正 */ /* 準備 */ %{ #include "stdio.h" #include "tinyc.tab.h" %} /* 規則 */ %% [ \t] { /* Skip white space */ } [\n] { yylineno++; } "+" { return '+'; } "-" { return '-'; } "*" { return '*'; } "/" { return '/'; } "{" { return '{'; } "}" { return '}'; } "(" { return '('; } ")" { return ')'; } "while" { return WHILE; } "var" { return VAR; } "for" { return FOR; } [0-9][0-9]* { yylval = atoi(yytext); return CONSTANT; } \"[^\"]*\" { yylval = (int)strdup(yytext); return LITERAL; } [a-zA-Z][0-9a-zA-Z]* { yylval = (int)strdup(yytext); return IDENTIFIER; } . { return yytext[0]; } %% /* ユーザ関数 */ /* mainは.yに移動 */
いよいよyaccファイルを実装します。ここではトークン列を解析して「変数の宣言」と「関数の呼出し」を判別して出力してみます。頑張って短くしたつもりですが、それでも結構複雑ですね。雰囲気はlexによく似ていて、大きくはトークンの定義と構文の定義に別れています。トークン定義は簡単なのでスキップします。注意点としては下に行くほど優先順位の高いトークンになります。なので+は*よりも上に定義しないと駄目ですね。なお、ここで書いた定義が先ほどのtinyc.tab.hに反映されて、それをlex側からも参照する形になります。
さて問題は構文定義です。最初から自力で書くのは結構難しいと思うので、ノリとしては必要なBNFを探すなり書くなりして準備して、それをyaccに置き換えるという感じでしょうか。注意点はyaccで直接表現できない繰り返しの定義を再帰を使って置き換えないといけない事です。この例で言うとparamtersやstatementsなどです。慣れの問題かもしれませんが、僕は好きになれません。yaccのEBNF対応を願うばかりです。(自分でやる程、力も熱意もないであります。)
/* * tinyc.y */ /* 準備 */ %{ #include <stdio .h> %} /* トークン定義 */ %token CONSTANT LITERAL IDENTIFIER %token VAR TYPE WHILE FOR IF %left ';' ',' %left '< ' '>' %right '=' %left '+' '-' %left '*' %token '(' ')' '{' '}' %start program /* 構文定義 */ %% program : external_definitions external_definitions: external_definitions external_definition | external_definition external_definition: IDENTIFIER '(' parameters ')' block | VAR IDENTIFIER '=' expr ';' parameters: parameters ',' parameter | parameter parameter: /* empty */ | TYPE IDENTIFIER block: '{' statements '}' statements : statements statement | statement statement : block | expr ';' | IF '(' expr ')' statement | WHILE '(' expr ')' statement | FOR '(' expr ';' expr ';' expr ')' statement | VAR IDENTIFIER ';' { printf("@ variable declaration %s @\n", $2); } exprs: exprs ',' expr | expr expr: primary_expr | IDENTIFIER '=' expr | expr '+' expr | expr '-' expr | expr '*' expr | expr '< ' expr | expr '>' expr primary_expr: IDENTIFIER | CONSTANT | LITERAL | '(' expr ')' | IDENTIFIER '(' exprs ')' { printf("@ function call %s @\n", $1); } %% /* ユーザ関数 */ int yydebug; int main() { // yydebug = 1; yyparse(); } </stdio>
早速実行してみます。リンク時にlibflに加えてlibyの指定も必要なので注意しましょう。うまく実行されていますね！
$ bison -d tinyc.y -v $ flex tinyc.l $ cc -c lex.yy.c -DYYDEBUG $ cc -c tinyc.tab.c -DYYDEBUG $ gcc lex.yy.o tinyc.tab.o -o tinyc_parser -lfl -ly $ ./tinyc_parser < test.c @ variable declaration i @ @ variable declaration s @ @ function call println @
大抵の情報源だと当然ながらうまく行った場合しか紹介されていませんが、残念ながらyaccファイルは複雑なので一発で正しく動かす事は期待できません。なので地道にデバッグする必要があります。僕が理解している限りだと、基本的には以下のようにデバッグします。
- コンフリクト
bison(yacc)を実行した時に以下の様な警告が出る事があります。$ bison -d tinyc.y -v tinyc.y: conflicts: 18 shift/reduce
その場合は-v(verbose)を付けて再度実行します。そうすると.outputというファイルにパーサー内部の状態マシンの情報が詳しく出力されます。出力されたファイルとにらめっこしてconflictをやっつけます。
- syntax error
生成されたパーサがパース処理に失敗するとこのエラーがでます。このままでは辛いので、上記のmain関数内にコメントアウトしているyydebugを有効にします。そうするとパース処理中の状態遷移が詳しく出力されるので、出力されたメッセージとにらめっこしてパーサのデバッグを行います。
これで漸くyacc & lexが少しは使えるようになりました。コンパイラ・コンパイラは使えると強力な武器になりそうなので、ちょっとずつ肉付けしていこうと思います。最後にこの例の場合の処理の流れを図にしてみました。言うほど複雑じゃないですけど、すぐ忘れるので念のため。
