コンパイラの技術と関数電卓プログラム(2)

前半では、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;
    }
%%

yacc or bison

yacc ( Yet Another Compiler Compiler ) もしくはその改良版の bison は、構文解析の処理を行ってくれる。 構文をバッカス記法で記載すると、構文のパターンの状態遷移に応じた遷移テーブルを自動生成し、 その遷移テーブルを用いた処理のプログラムをC言語で出力してくれる。

トークンが出力するデータは、様々なデータが考えられるので、 その型を "%union" の中に記載する。 "%%"〜"%%" の間には、BNF記法と、それに対応する処理を記載する。

(( 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 ) ;
        }
}

make と Makefile

これらのプログラムでは、字句解析を行う mycalc.l , 構文解析を行う mycalc.y を 作ったが、これを組合せて1つの実行ファイルにコンパイルする。 これらの手順は煩雑なので、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
	gcc -c lex.yy.c

clean:; rm mycalc y.tab.c y.tab.h lex.yy.c *.o
 

2016年11月

    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30      

アーカイブ

Google

このブログ記事について

このページは、T-Saitohが2016年11月 9日 14:07に書いたブログ記事です。

ひとつ前のブログ記事は「コンパイラの技術と関数電卓プログラム」です。

次のブログ記事は「倍精度で精度が足りない...」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。