前半では、1文字の数字と簡単な演算子で表現される計算式を再帰下降パーサで計算する処理で、 演習を行った。
後半は、さらに実際のコンパイラに近いものとして、 C言語で広く使われている、字句解析(lexical analyzer : lex or flex)ツール、 構文解析(parser : yacc or bison) のツールを使って、 さらに現実的な関数電卓プログラムを作ってみる。
lex or flex による字句解析
lexは、字句解析のプログラムを自動生成するツール。 “%%”行の内側に、正規表現とそのパターンの際の処理を書き並べる。 また、”%{ … %}”の内側に、その処理に必要なC言語のソースを書き、 lex で処理を行うと、lex.yy.c というC言語のソースを出力する。
# flex は、lex の改良版。
(( mycalc.l ))
%{
#include <stdio.h>
// yaccが出力するヘッダファイル
#include "y.tab.h"
int yywrap( void )
{
// 1: スキャナ終了
// 0: yyin を切り替えて継続
return 1 ;
}
%}
%%
"+" return ADD ;
"-" return SUB ;
"*" return MUL ;
"/" return DIV ;
"\n" return CR ;
[0-9][0-9]* {
int temp ;
sscanf( yytext , "%d" , &temp ) ;
yylval.int_value = temp ;
return INT_LITERAL;
}
%%
このプログラムを、lex で処理させると、+ 記号に ADD という定数記号を割り振るとか、数字列をみつけると、文字列から数値を生成(sscanf)して、その場合の記号に INT_LITERAL という定数記号を割り振る…といった処理のプログラムを生成してくれる。
yacc or bison
yacc ( Yet Another Compiler Compiler ) もしくはその改良版の bison は、構文解析の処理を行ってくれる。 構文をバッカス記法で記載すると、構文のパターンの状態遷移に応じた遷移テーブルを自動生成し、 その遷移テーブルを用いた処理のプログラムをC言語で出力してくれる。
トークンが出力するデータは、様々なデータが考えられるので、 その型を “%union” の中に記載する。 “%%”〜”%%” の間には、BNF記法と、それに対応する処理を記載する。
# bison(水牛)は、yacc(山牛)の改良版。
(( mycalc.y ))
%{
#include <stdio.h>
#include <stdlib.h>
// yacc が定義する内部関数のプロトタイプ宣言
#define YYDEBUG 1
extern int yyerror( char const* ) ;
extern char *yytext ;
extern int yyparse( void ) ;
extern FILE *yyin ;
extern int yylex( void ) ;
%}
// 字句(トークン)の定義
%union {
int int_value;
}
%token <int_value> INT_LITERAL
%token ADD SUB MUL DIV CR
%type <int_value> expression term primary_expression
%%
// 構文の定義
line_list : line
| line_list line
;
line : expression CR { printf( ">>%d\n" , $1 ) ; }
;
expression : term
| expression ADD term { $$ = $1 + $3 ; }
| expression SUB term { $$ = $1 - $3 ; }
;
term : primary_expression
| term MUL primary_expression { $$ = $1 * $3 ; }
| term DIV primary_expression { $$ = $1 / $3 ; }
;
primary_expression
: INT_LITERAL
;
%%
// 補助関数の定義
int yyerror( char const* str )
{
fprintf( stderr , "parser error near %s\n" , yytext ) ;
return 0 ;
}
int main( void )
{
yyin = stdin ;
if ( yyparse() ) {
fprintf( stderr , "Error ! Error ! Error !\n" ) ;
exit( 1 ) ;
}
}
このプログラムを、yacc で処理すると、「加算式 + 乗算式」という文になっている部分を見つけると、
「$1(加算式部分の値)と、$3(乗算式の部分)の値を加えて、$$(式の結果)を求める」といった処理を生成してくれる。yyparse() 関数を呼び出すと、構文の一番最上部の line_list に相当する処理が起動される。yyerror()は、構文解析の途中で文法エラーになった時に呼び出される関数。
生成されるパーサの内容に興味があるなら、生成される y.tab.c の内容を読むと良い。
make と Makefile
これらのプログラムでは、字句解析を行う mycalc.l , 構文解析を行う mycalc.y を 作ったが、これを組合せて１つの実行ファイルにコンパイルする。 これらの手順は煩雑なので、make ツールを使う。
make は、 Makefile に記載されている”ターゲット”と、それを作るために必要な”依存ファイル”、 “依存ファイル”から”ターゲット”を生成する処理から構成される。 make は、ターゲットと依存ファイルの更新時間を比較し、 必要最小限の処理を行う。
(( Makefile ))
# 最終ターゲット
mycalc: y.tab.o lex.yy.o
gcc -o mycalc y.tab.o lex.yy.o
# 構文解析処理
y.tab.o: mycalc.y
bison -dy mycalc.y # -dy : yacc互換モード
gcc -c y.tab.c
# 字句解析処理
lex.yy.o: mycalc.l mycalc.y
flex -l mycalc.l # -l : lex互換モード
gcc -c lex.yy.c
clean:; rm mycalc y.tab.c y.tab.h lex.yy.c *.o
((ファイルの依存関係))
mycalc.l mycalc.y
| ＼ |
lex.yy.c y.tab.h y.tab.c
| ＼ |
lex.yy.o y.tab.o
＼ ／
mycalc
この課題にあたり、後半の実験では flex, bison などの unix 系プログラミング環境を利用する。
macOS の利用者であれば MacPorts や、Windows 利用者であれば、wsl(Windows subsystem for Linux) などをインストールし実行すること。
今回の実験であれば、”apt-get install flex bison gcc make” にて、必要なパッケージをインストールして実験を行うこと。