構文解析ツールbison1†

前回はトークンが正しい順番に並んでいるかのチェックプログラムを作っていました。少し物足りない題材で恐縮だったのですが、この流れはbisonでも同様です。というのも、ツールの理解をを第一の目的にしているので、どうしても実利重視に偏ってしまいます。このコラムの次あたりにtinyBasicにチャレンジする予定ですので、自作言語の構想は当分暖めてといてください。

↑

ところでゴールはいつ？†

言語作りは、大雑把な区分けると以下のようになっています。re2cは終わったので、残り4/3・・・といいたいところですが、実際の難しさの比率は1:4:2:3なので、ここが一番の正念場です。

字句解析（re2c） → 構文解析（bison） → コード生成 → 仮想マシン
↑

bisonとは†

一言でいうとトークンの並びが、構文規則のルールに合っているかチェックをするツールです。構文規則というのはどうにも腑に落ちないですが、後々わかってきますので今は辛抱してください。ちなみにre2cと違うところは、コメントアウト部分に対して生成するのではなく、ルール用のファイル.yを作成し、C言語のファイル（bison.c、bison.h）を生成することです。結果をみると複雑な為、心臓に悪いので見ないほうがいいと思います（汗。ここではブラックボックスということにして、インターフェースに着目してみるところから始めてみましょう。

・コマンド例

bison.exe -l -d -o bison.c bison.y          # bison.c、bison.hが生成されます
cat bison.c
（以下略・・・見ると危険かも）

インストールについてはcygwinを使ってください。bisonと、さらにgcc、makeも用意します。

↑

bisonのインターフェース†

bisonを使うために覚えておきたい関数は３つ（yyparse、yyerror、yylex）です。さっそくyyparseから見てきましょう。この関数自体は、bisonを使って自動生成されますが、具体的な使い方はこんな感じになります。

//---------------------------------------------------------------------------
int main(int argc, char** argv)
{
	char* pBuf = "abc = 123";
	yyin = pBuf;

	if(yyparse() != 0)
	{
		printf("Err\n");
		return -1;
	}

	printf("ok\n");
	return 0;
}

呼び出したい側にとっては文字列が正しいかどうかしか興味がなく、yyparseの戻り値が0なら成功、それ以外は失敗ととらえることが出来ます。中身については触れないことにしますが、基本は（前回作ったRe2cの）yylex関数を逐次呼び出して、トークンの順番が正しいことを確認しています。ちなみにyylex関数を自前に用意しないでコンパイルすると、当然エラーになるので注意してください。 呼び出したい側にとっては文字列が正しいかどうかしか興味がなく、yyparseの戻り値が0なら成功、それ以外は失敗ととらえることが出来ます。中身については触れないことにしますが、基本は（前回作ったRe2cの）yylex関数を逐次呼び出して、トークンの順番が正しいことを確認しています。ちなみにyylex関数を自前に用意しないでコンパイルすると、当然エラーになるので注意してください。

 

最後のyyerrorは、yyparse内でエラーが起こったときに呼び出される関数です。これもyylex同様、自作しなくてはいけないので用意してあげます。引数にはchar*を1つとって、エラーの表示方法はまかせるぞと、開発者の意図が読めてきそうです。

//---------------------------------------------------------------------------
void yyerror(char* str)
{
	printf("!! yyerror !! = %s\n", str);
}
↑

.yファイルの作成†

.yこと、Bison文法ファイル（Bison grammar file）は、主にコードを書くこととは違った考え方が必要です。そもそもツールを使うということは、コードを極力意識しないためにあるのでしょうがないっちゃしょうがないのですけど・・・。ここからは、特にゆっくりペースで話を進めていこうと思います。まず、このファイルの構成は４つに分かれています。

%{
C宣言部（A）
%}

Bison宣言部（B）

%%
文法規則部（C）
%%

追加のCプログラム部（D）

AとDの宣言名からわかるように、もともと.yから.cが生成されるのですから、C言語の自作関数を作ることができます。さっそくDにyyerrorを置いちゃいましょう。Aの部分には、bisonのデバッグフラグやyylex関数のヘッダファイルを付けます。

%{
#include "re2c.h" // yylex関数

#define YYSTYPE char*
#include "bison.h"

//---------------------------------------------------------------------------
// #define YYDEBUG			1
// #define YYERROR_VERBOSE		1
// int yydebug = 1;


//---------------------------------------------------------------------------
void yyerror(char* str);

%}


Bison宣言部（B）


%%
文法規則部（C）
%%


//---------------------------------------------------------------------------
void yyerror(char* str)
{
	printf("!! yyerror !! = %s\n", str);
}

基本はこの形ではないかと勝手に思っています（投げやり。

↑

Bison宣言部（B）†

使用するトークンを宣言しますが、これはbison側から見ると、終端記号という別の名前が与えられています。自分が「チャーハン定食ください」と頼んでも、店員さんからみれば「チャー定だね！」って答えられるようなもんです。立場によって言い方は代わりますが、内容は同じなので気にしないでください。

 

車輪の開発 第一弾。re2cで使った代入文チェックの終端記号（トークン）を以下に表します。

%token TOKEN_NUM
%token TOKEN_VAR
%token TOKEN_STR
%token TOKEN_EQ
%token TOKEN_ERR
↑

文法規則部（C）†

一番理解しずらいところです。ここでは終端記号（トークン）と、非終端記号と呼ばれるものを扱います。

s	: TOKEN_VAR TOKEN_EQ TOKEN_NUM
 	;

日本語通訳しますと「TOKEN_VAR, TOKEN_EQ, TOKEN_NUM の順番に並びを、非終端記号s で構成する」といった意味です。つまりコロンを隔てて

非終端記号 : 構成する要素
           ;

と見ることが出来ます。左側の「非終端記号」には、終端記号（トークン）を書くことはできません。トークンが、トークンによって構成されるってありえませんので。右側には名前の由来どおり、非終端記号（終わらない記号）を書くことも出来ます。ちょっと遊んでみると、こういう書き方もOKです。

s	: s1 s2 s3
 	;

s1	: TOKEN_VAR
 	;

s2	: TOKEN_EQ
 	;

s3	: TOKEN_NUM
 	;
s	: var TOKEN_EQ num
 	;

var	: TOKEN_VAR
 	;

num	: TOKEN_NUM
 	;

双方とも読みにくく普段は使わないと思います（汗。ちょっとダメな例も書いときましょう。s3が定義されてないぞ！とbison先生に怒られます。右側に終端記号を書いたのならば、どこかしらに終端記号の内容を定義しなくてはならないです。

s	: s1 s2 s3
 	;

s1	: TOKEN_VAR
 	;

s2	: TOKEN_EQ
 	;

s4	: TOKEN_NUM
 	;
↑

今までのまとめ†

これからコードが爆発的に増える恐れがあるため、それぞれのファイルに分業します。

・自前準備

%{
#include "re2c.h"	// yylex関数

#define YYSTYPE char*
#include "bison.h"

//---------------------------------------------------------------------------
#define YYDEBUG			1
#define YYERROR_VERBOSE		1
int yydebug = 1;


//---------------------------------------------------------------------------
void yyerror(char* str);


%}


%token TOKEN_NUM
%token TOKEN_VAR
%token TOKEN_STR
%token TOKEN_EQ
%token TOKEN_ERR


%%
s	: TOKEN_VAR TOKEN_EQ TOKEN_NUM
 	;
%%


//---------------------------------------------------------------------------
void yyerror(char* str)
{
	printf("!! yyerror !! = %s\n", str);
}
YACC	:= bison
RE2C	:= re2c
CC	:= gcc
LFLAGS	:= 


test	: main.c re2c.c bison.c
	$(CC) main.c re2c.c bison.c $(LFLAGS) -o test

re2c.c	: re2c.re re2c.h
	$(RE2C) -i -o re2c.c re2c.re

bison.c	: bison.y
	$(YACC) -l -d -o bison.c bison.y


clean	:
	rm bison.c bison.h re2c.c test.exe

・実行

$ make
re2c -i -o re2c.c re2c.re
bison -l -d -o bison.c bison.y
gcc main.c re2c.c bison.c  -o test

・生成ファイル

/* Tokens.  */
#define TOKEN_NUM 258
#define TOKEN_VAR 259
#define TOKEN_STR 260
#define TOKEN_EQ 261
#define TOKEN_ERR 262

以下、bisonのデバッグフラグをオンにした結果を表します。

$ ./test
abc = 123                                  # 入力文字列
Starting parse
Entering state 0
Reading a token: var
Next token is token TOKEN_VAR ()
Shifting token TOKEN_VAR ()
Entering state 1
Reading a token: ws
=
Next token is token TOKEN_EQ ()
Shifting token TOKEN_EQ ()
Entering state 3
Reading a token: ws
digit
Next token is token TOKEN_NUM ()
Shifting token TOKEN_NUM ()
Entering state 5
Reducing stack by rule 1 (line 28):
   $1 = token TOKEN_VAR ()
   $2 = token TOKEN_EQ ()
   $3 = token TOKEN_NUM ()
-> $$ = nterm s ()
Stack now 0
Entering state 2
Reading a token: end
Now at end of input.
Stack now 0 2
Cleanup: popping nterm s ()
ok                                  # 結果
↑

履歴†

トップ   一覧 検索 最終更新   ヘルプ   最終更新のRSS