構文解析ツールBison

１．構文解析ツール Bison

上に述べたLR法で特に面倒なのは、構文解析表の生成である。 構文解析ツールBisonは Yacc の後継であり、Windowsパソコンでも使える。 構文規則から構文解析表を自動的に生成し、C言語による 構文解析プログラム(パーサ)を出力する。 構文解析手法としては、SLR法より多くの文脈自由文法を扱える LALR(Lookahead LR)法が使われている。

Bisonによる四則・階乗計算プログラムとその実行例を下に示す。 字句解析には Flexを使っている。

%{
#include <stdio.h>
#include <math.h>
void yyerror(char *s) { printf("%s\n",s); }
int  yywrap(void) { return 1; }
%}

%union {
   float val;
}

%token NUMBER
%token PLUS MINUS MULT DIV EXPON
%token EOL
%token LB RB

%left  MINUS PLUS
%left  MULT DIV
%right EXPON

%type  <val> exp NUMBER

%%
input   :
        | input line
        ;

line    : EOL
        | exp EOL { printf("%g\n",$1);}

exp     : NUMBER                 { $$ = $1;        }
        | exp PLUS  exp          { $$ = $1 + $3;   }
        | exp MINUS exp          { $$ = $1 - $3;   }
        | exp MULT  exp          { $$ = $1 * $3;   }
        | exp DIV   exp          { $$ = $1 / $3;   }
        | MINUS  exp %prec MINUS { $$ = -$2;       }
        | exp EXPON exp          { $$ = pow($1,$3);}
        | LB exp RB              { $$ = $2;        }
        ;
%%

int main() {
  yyparse();
}

%{
#include "y.tab.h"
%}

%%
[0-9]+     { yylval.val = atof(yytext);
             return(NUMBER);
           }
[0-9]+\.[0-9]+ { 
             sscanf(yytext,"%f",&yylval.val);
             return(NUMBER);
           }
"+"        return(PLUS);
"-"        return(MINUS);
"*"        return(MULT);
"/"        return(DIV);
"^"        return(EXPON);
"("        return(LB);
")"        return(RB);
\n         return(EOL);
.          { yyerror("Illegal character"); return(EOL); }
%%

c:\MH>flex calc02.lex
c:\MH>bison -d -y calc02.y
c:\MH>tcc -o calc02.exe y.tab.c lex.yy.c
c:\MH>calc02
10+1*5
15
4.5^2+10
30.25