前の記事(プログラミング言語を作る前知識)でプログラミング言語少し作れる気がしてきたので、lexとyaccに軽く触れてみた。
実際はflexとbisonを使っている。
lexの書き方
lexのファイルには3つのブロックがあって、%%で区切って記述します。
-------------------------------------------------------
| 定義部
| オプションやincludeや変数宣言、マクロなどを記述します。
| includeや変数宣言は%{...%}で囲って書きます。
| yaccと組み合わせて使う場合、生成されるCソースを
| インクルードすることがあるので、ここに記載します。
| オプションは%ではじめます。
| %noyywrap
| これは入力が1ファイルであることを示していて、よく使われます。
| マクロは、「マクロ名 正規表現」で書きます。
-------------------------------------------------------
%%
-------------------------------------------------------
| ルール部
| 「正規表現 対応するCコード」という記述方法でルールを書きます。
| +や*などは正規表現の特殊文字なので、文字として使いたい場合は
| \でエスケープしたり、""で囲んで明示的に文字列として書きます。
| 定義部で宣言したマクロは{}で囲うことで使えます。
-------------------------------------------------------
%%
-------------------------------------------------------
| ユーザーサブルーチン部
| C言語のmain関数などを書きます。
| yaccと組み合わせて使う場合は、main関数はyacc側に書くため
| この部分はあまり書かないかもしれません。
-------------------------------------------------------
lexで使える正規表現情報です。
lexのファイルは*.lという名前で作成し、lex(flex)コマンドでCソースを生成します。
// lexの場合
$ lex sample.l
// flexの場合
$ flex sample.l
lex.yy.cというファイルが出力されていればok。
yaccの書き方
基本構造はlexと同じです。
-------------------------------------------------------
| 定義部
| includeや%union, %token, %typeなどを定義します。
| includeはlexと同様に%{...%}で記述します。
| %unionは、型定義に使います。
| %tokenは、単にトークンを定義します。
| %typeは、ルール部で使用する変数名を定義します。
| <>で囲んでuniconの変数名を参照して記述することもできます。
-------------------------------------------------------
%%
-------------------------------------------------------
| ルール部
| ルール定義のブロックは以下のよな構成になります。
| 変換結果: 構成要素1 構成要素2 ...
| | (他の構成内容)
| { (マッチした際に実行されるCコード) }
| ;
| ;は省略可能で、{}は構成内容につきそれぞれ定義できます。
-------------------------------------------------------
%%
-------------------------------------------------------
| ユーザーサブルーチン部
| C言語のmain関数などを書きます。
| 実際に入力を解析したりするのに使います。
| 構文解析関数はyyparseです。
| yyparse関数を使う際、yacc単体で利用するときは
| 字句解析器としてyylex関数の実装が必要になります。
-------------------------------------------------------
yaccファイルは、*.yという名前で作成し、yacc(bison)コマンドでCソースを生成します。
// yaccの場合
$ yacc -d sample.y
// bisonの場合
$ bison -d sample.y
sample.tab.hとsample.tab.cというファイルが出力されていればok。
lexとyaccを組み合わせて使う
yyparseが、yylexを必要としているように、lexとyaccは組み合わせ使うと便利です。
大域変数の利用パターン(変数)
intやdoubleなどの変数を扱う場合に、lexとyaccの間で大域変数を使用して、lexの正規表現にマッチした変数を、yaccのunionと紐付けておくことができます。
yaccでuniconで定義した変数は、lexで、yylval.変数名で参照できます。
double型の足し算をするだけの単純な例です。
lexファイル(sample.l)
%{
#include <stdio.h>
#include <stdlib.h>
#include "sample.tab.h"
%}
%%
[0-9]+\.[0-9]* {
yylval.double_value = atof(yytext);
return DOUBLE;
}
"+" { return ADD; }
%%
yaccファイル(sample.y)
%{
#include <stdio.h>
#include <stdlib.h>
%}
%union {
double double_value;
}
%token <double_value> DOUBLE
%type <double_value> factor expr
%left ADD
%%
input :
| input line
line : CR
| expr CR { printf(">> %f\n", $1); }
expr : factor { $$ = $1; }
| expr ADD expr { $$ = $1 + $3; }
factor: DOUBLE
%%
int yyerror(char const *str)
{
fprintf(stderr, "%s\n", str);
return 0;
}
int main(void)
{
yyparse();
return 0;
}
double_valをいうyaccで定義した型を、lexファイルでyylvalを介して参照しています。
yaccファイルでは、%tokenを使ってDOUBLEとunionの変数を紐付けることで、自動的に型をつけるように指定しています。
簡単な計算機を作る
計算機なので計算順序を正しく定義してあげるのが大事だと思います。計算順序を決めるのに、yaccの%left、%rightが役に立ちそうです。
%leftは左結合規則を定義、%rightは右結合規則を定義できます。
身近なところだと、足し算などは左結合、代入などは右結合です。
%left,%rightは定義した順番(上から下)に優先順位がつきます。
"+-*/%^()"と数字(小数点)をlexで定義します。
%option noyywrap
%{
#include <stdio.h>
#include <stdlib.h>
#include "cal.tab.h"
%}
%%
[0-9][0-9]* {
yylval.value = atof(yytext);
return VALUE;
}
[0-9]+\.[0-9]* {
yylval.value = atof(yytext);
return VALUE;
}
"+" { return ADD; }
"-" { return SUB; }
"*" { return MUL; }
"/" { return DIV; }
"%" { return REM; }
"^" { return POW; }
"\n" { return CR; }
"(" { return LP; }
")" { return RP; }
%%
yaccで構文規則を書いていきます、今から作る計算機は"^"だけ右結合です。
%{
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
%}
%union {
double value;
}
%token <value> VALUE
%token ADD SUB MUL DIV REM POW CR LP RP
%type <value> factor expr
%left ADD SUB
%left MUL DIV REM
%left NEG POS
%right POW
%%
input :
| input line
line : CR
| expr CR { printf(">> %f\n", $1); }
| error CR { yyerrok; yyclearin; }
expr : factor
| ADD expr %prec POS { $$ = $2; }
| SUB expr %prec NEG { $$ = -$2; }
| expr ADD expr { $$ = $1 + $3; }
| expr SUB expr { $$ = $1 - $3; }
| expr MUL expr { $$ = $1 * $3; }
| expr DIV expr { $$ = $1 / $3; }
| expr REM expr { $$ = fmod($1, $3); }
| expr POW expr { $$ = pow($1, $3); }
| LP expr RP { $$ = $2; }
factor: VALUE
%%
int yyerror(char const *str)
{
extern char *yytext;
fprintf(stderr, "%s\n--> %s\n", str, yytext);
return 0;
}
int main(void)
{
yyparse();
}
コンパイルして実行します。
$ flex cal.l
$ bison -d cal.y
$ gcc cal.tab.c lex.yy.c -lm -o cal
$ ./cal
2+4*4
>> 18.000000
(2+4)*4
>> 24.000000
60/5*2
>> 24.000000
(9-2*3)^3
>> 27.000000
おぉ、ちゃんと動いてる風だ。
計算機の例が書いてあって参考にした記事
まとめ
lexとyaccの記法について、わかってくれば計算機作れた。
実際に言語を作るときは、yaccで即時評価するのでなく、ASTを作成することになるので、ややこしくなってくる。。
Show comments