Help us understand the problem. What is going on with this article?

言語を作る!bisonとflexを使ってみた

More than 1 year has passed since last update.

 授業でコンパイラの勉強をしたので試しにコンパイラ生成系(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を使ってみる

とりあえず簡単に

mini-lang.l
%{
#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を使ってみる

構文定義です。代入と四則演算は定義しました。

mini-lang.y
%{
#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の環境構築編)
言語を作る!(シンプルな電卓を作る編①)
言語を作る!(シンプルな電卓を作る編②)

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away