授業でコンパイラの勉強をしたので試しにコンパイラ生成系(Compiler Compiler)を使ってみようと思います。
yaccとlexを使いたかったのですが、私のマシンがwindowsだったので同じようなものにbisonとflex
があることが分かったので使ってみます。yaccがbisonでlexがflexのようです。
yaccとlexとは
yaccは構文解析器を作るためのプログラムです。例えば、掛け算の式とは<数>'*'<数>はこんな形だと教えると解釈してくれるようなプログラムを作ってくれます。ずいぶん昔からあるようですが、いまでもRubyの処理系などで現役で活躍しているようです。
lexはyaccよりももっと低レベルな部分について解析する字句解析器を作ってくれるプログラムです。例えば、数は0-9の数字がいくつか並んだものであるとか、識別子は先頭がアルファベットで2文字目以降は数字かアルファベットと教えるとそのようになっている適当な塊で切ってくれます。
yaccとlexを組み合わせると自己流の定義ファイルや言語の解釈をしてくれるプログラムが作れるのです。
bisonとflexのインストール
http://www2.kuma.u-tokai.ac.jp/~kfuji/cygwin/cygwin.htm
こちらのサイトを参考にまずはcygwinをインストールします。
インストーラを起動してインストールプログラムの一覧が表示されたらgccやg++と一緒にbisonとflexもインストールします。
すべてインストールもできますが固定回線でも2,3時間かかりそうなくらいあります。
必要なものだけのほうがよさそうです。
ミニ言語を作ってみよう
ミニ言語というよりは電卓ですがテストの意味もかねて作ってみます。
申し訳程度にif式も作ってみました。
flexを使ってみる
とりあえず簡単に
%{
#include "mini-lang.tab.h"
#include <string.h>
%}
white [ \t]
floating [0-9]+\.[0-9]+
integer [0-9]+
symbol [=+\-\^*/();\n]
letter [a-zA-Z]
other .
%%
{white}+
{symbol} { return(yytext[0]); }
{integer} { sscanf(yytext, "%d", &yylval.ival);
return(INTNUM); }
{floating} { sscanf(yytext, "%lf", &yylval.dval);
return(DOUBLENUM); }
{letter} { yylval.cval = yytext[0];
return(IDENTIFIER); }
for { return(FOR); }
in { return(IN); }
to { return(TO); }
step { return(STEP); }
if { return(IF); }
then { return(THEN); }
else { return(ELSE); }
end { return(END); }
exit { return(EXIT); }
{other} { fprintf(stderr, "Illegal charcter %c, ignored\n", yytext[0]); }
%%
実際forとかは使ってないですがいづれ拡張するかもしれないことを見越してとりあえず入れときました。
ヘッダファイルのインクルードしているmini-lang.tab.hはbisonが吐き出すヘッダを使うためです。
bisonを使ってみる
構文定義です。代入と四則演算は定義しました。
%{
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <string.h>
#define outofrange(n) fprintf(stderr, "memory #%d out of range\n", (n));
#define IDENTSIZE 16
typedef struct _identmap{
char name;
double value;
} identmap;
identmap imap[IDENTSIZE];
double getvalue(char name);
int identregister(char name,double value);
double it;
%}
%union {
int ival;
double dval;
char cval;
}
%token <ival> INTNUM MEMLOAD MEMSTORE FOR IN TO STEP IF THEN ELSE END EXIT
%token <dval> DOUBLENUM
%token <cval> IDENTIFIER
%type <dval> program block expr term factor ifstmt
%start program
%%
program : { $$ = it; }
| block ';' { $$ = it = $1; printf("program return = %lf\n", it); }
| block '\n' { $$ = it = $1; printf("program return = %lf\n", it); }
| program block '\n' { $$ = it = $2; printf("program return = %lf\n", it); }
| program EXIT '\n' { $$ = it; printf("program return = %lf\n", it); return 0; }
;
block : expr { $$ = $1; }
| ifstmt { $$ = $1; }
ifstmt : IF expr THEN expr END { if ( $2 == 1.0) $$ = $4;
else $$ = -1; }
;
expr : term { $$ = $1; }
| IDENTIFIER '=' expr { identregister($1, $3);
$$ = $3; }
| expr '+' term { $$ = $1 + $3; }
| expr '-' term { $$ = $1 - $3; }
;
term : factor { $$ = $1; }
| term '*' factor { $$ = $1 * $3; }
| term '/' factor { $$ = $1 / $3; }
| factor '^' term { $$ = pow($1, $3); }
;
factor : INTNUM { $$ = (double) $1; }
| DOUBLENUM { $$ = $1; }
| IDENTIFIER { $$ = getvalue($1); }
| factor IDENTIFIER { $$ = (double) $1 * getvalue($2); }
| '(' expr ')' { $$ = $2; }
;
%%
int main(void)
{
yyparse();
printf("See you!!");
return 0;
}
int yyerror(char *msg)
{
fprintf(stderr, "mini-lang: %s\n", msg);
return 0;
}
int indexident(char name){
int i;
for( i = 0; i < IDENTSIZE; i++){
if( imap[i].name == name )
return i;
}
return -1;
}
int identregister(char name,double value){
int i = indexident(name);
if ( i == -1){
static int usedi = 0;
imap[usedi].name = name;
imap[usedi].value = value;
usedi++;
}else{
imap[i].value = value;
}
return 0;
}
double getvalue(char name){
int i = indexident(name);
if (i != -1)
return imap[i].value;
else
printf("mini-lang: \'%c\' is not defined\n",name);
return 0.0;
}
コンパイルしてみよう
$ flex mini-lang.l
$ bison -d mini-lang.y
mini-lang.y: warning: 9 shift/reduce conflicts [-Wconflicts-sr]
$ gcc -O2 -o mini-lang mini-lang.tab.c lex.yy.c -lfl -ly
mini-lang.tab.c: In function 'yyparse':
mini-lang.tab.c:1179:16: warning: implicit declaration of function 'yylex' [-Wimplicit-function-declaration]
yychar = yylex ();
^
mini-lang.tab.c:1436:7: warning: implicit declaration of function 'yyerror' [-Wimplicit-function-declaration]
yyerror (YY_("syntax error"));
シフト還元競合など置きますがとりあえずいいことにして動かしてみましょう。
$ mini-lang.exe
2+3
program return = 5.000000
4*5
program return = 20.000000
a = 5
program return = 5.000000
a * 4
program return = 20.000000
a = a + 6
program return = 11.000000
exit
program return = 11.000000
See you!!
どうやらちゃんと動いたようです。頑張るといろいろ面白そうなことができそうです。
今回は中身については触れていませんが今度は中身も詳しくみていこうと思います。
関連記事
言語を作る！(JavaCCの環境構築編)
言語を作る！(シンプルな電卓を作る編①)
言語を作る！(シンプルな電卓を作る編②)