目次


SDL の使用、第4回: lexおよびyacc

スクリプトおよびGUIデザインのためのパーサーの構築

Comments

Pirates Ho! の設計では、プレイヤーに対してインターフェースとダイアログ・オプションを容易に説明する方法が必要でした。この説明では、簡単で、一貫性があり、かつ柔軟性をもった言語が必要でしたから、われわれはスクリプト言語の構築に役立つツールを探しました。

bison の肉をもう一切れなんて!

"yacc" という言葉が、学生のわたしの心に恐怖を植え付けました。その言葉は、ぼさぼさ頭の、青白い顔色をした学生たちが、コンパイラーや記号テーブルについてぼそぼそつぶやいている姿を思い起こさせました。それでわたしは、コンパイラーのクラスを取らなくて済むように入念に工面しました。しかし、われわれはゲームをいじっているうちに、思いきって yacc と取り組むことにしました。そして、それが少しでもスクリプト記述を容易にしてくれることを祈りました。結局、yacc は、スクリプト記述を容易にしただけでなく、面白くもしました。

基本からのスタート

yacc は、実際にかなり使いやすいものです。文法を記述した規則のリストを yacc に与えると、yacc はトークンを構文解析し、その結果に応じてアクションを取ります。われわれのスクリプト言語の場合、以下のような、単に当初指定しただけの簡単な数とその論理演算から始めたいと思いました。

eval.y
%{
/* This first section contains C code which will be included in the output
   file.
*/
#include <stdlib.h>
#include <stdio.h>
/* Since we are using C++, we need to specify the prototypes for some
   internal yacc functions so that they can be found at link time.
*/
extern int yylex(void);
extern void yyerror(char *msg);
%}
/* This is a union of the different types of values that a token can
   take on.  In our case we'll just handle "numbers", which are of
   C int type.
*/
%union {
	int number;
}
/* These are untyped tokens which are recognized as part of the grammar */
%token AND OR EQUALS
/* Here we are, any NUMBER token is stored in the number member of the
   union above.
*/
%token<number> NUMBER
/* These rules all return a numeric value */
%type<number> expression
%type<number> logical_expression and or equals
%%
/* Our language consists either of a single statement or of a list of statements.
   Notice the recursivity of the rule, this allows us to have any
   number of statements in a statement list.
*/
statement_list: statement | statement_list statement
	;
/* A statement is simply an expression.  When the parser sees an expression
   we print out its value for debugging purposes.  Later on we'll
   have more than just expressions in our statements.
*/
statement: expression
	{ printf("Expression = %d\n", $1); }
	;
/* An expression can be a number or a logical expression. */
expression: NUMBER
	|   logical_expression
	;
/* We have a few different types of logical expressions */
logical_expression: and
	|           or
	|           equals
	;
/* When the parser sees two expressions surrounded by parenthesis and
   connected by the AND token, it will actually perform a C logical
   expression and store the result into $$, which is the "value" of
   this statement.
*/
and: '(' expression AND expression ')'
	{ if ( $2 && $4 ) { $$ = 1; } else { $$ = 0; } }
	;
or: '(' expression OR expression ')'
	{ if ( $2 || $4 ) { $$ = 1; } else { $$ = 0; } }
	;
equals: '(' expression EQUALS expression ')'
	{ if ( $2 == $4 ) { $$ = 1; } else { $$ = 0; } }
	;
%%
/* This is a sample main() function that just parses standard input
   using our yacc grammar.  It allows us to feed sample scripts in
   and see if they are parsed correctly.
*/
int main(int argc, char *argv[])
{
	yyparse();
}
/* This is an error function used by yacc, and must be defined */-
void yyerror(char *message)
{
	fprintf(stderr, "%s\n", message);
}

獣 (bison) に餌を与える方法

トークン列を認識する簡単な文法を作成しましたので、われわれは、パーサーにトークンを与える方法を見つけ出す必要がありました。lex は、入力を受け取り、それをトークンに変え、トークンを yacc に渡すツールです。以下、lex がトークンに変える式を 示します。

eval.l
%{
/* Again, this is C code that is inserted into the beginning of the output */
#include<string.h>
#include "y.tab.h"  /* Include the token definitions generated by yacc */
%}
/* Prevent the need for linking with -lfl */
%option noyywrap
/* This next section is a set of regular expressions that describe input
   tokens that are passed back to yacc.  The tokens are defined in y.tab.h,
   which is generated by yacc.
 */
%%
\/\/.*		/* ignore comments */
-[0-9]+|[0-9]+	{ yylval.number=atoi(yytext); return NUMBER; }
[ \t\n]		/* ignore whitespace */
&&		{ return AND; }
\|\|		{ return OR; }
==		{ return EQUALS; }
.		return yytext[0];
%%

構文解析ソースを現行ディレクトリーに入れましたので、それらを構築するための Makefile が必要になりました。

Makefile
all: eval 
y.tab.c: eval.y
	yacc -d $<
lex.yy.c: eval.l
	lex $<
eval: y.tab.o lex.yy.o
	$(CC) -o $@ $^

デフォルトでは、yacc は y.tab.c に出力し、lex は lex.yy.c に出力します。このため、われわれはこれらの名前をソース・ファイルとして使用しました。Make ファイルには、パーサー記述ファイルからソースを構築する規則が含まれています。この作業が終わったら、"make" と入力して、パーサーを構築することができます。このパーサーは、実行することもできるし、スクリプトを入力してわれわれのロジックを調べさせこともできます。

shift/reduce conflicts
shift/reduce conflicts は、yacc が、トークン・セットの構文解析を続行するか、またはそれを規則にして解決するか、のいずれかを選択しなければならなくなった場合に起こります。たとえば、以下の式で構成される文法を作成する場合は、
expression: NUMBER | plus
	;
plus: expression '+' expression
	;

yacc パーサーは、数字を見ても、それをすぐに式に解決するのか、または "X + Y" を待つのか判別できません。この場合、yacc は shift/reduce conflicts について警告を出し、デフォルトで、フル "X + Y" 式を待ちます。GNU bison に '-v' コマンド行オプションを与えてそれを使用するときは、何が実行されているかを正確に見ることができます。このコマンド行オプションは、規則および発生した矛盾が入っている *.output ファイルを作成します。

このあいまいさを解決するには、次のプラス式を括弧で囲む必要があります。

expression: NUMBER | plus
	;
plus: '(' expression '+' expression ')'
	;

C++ との lex および yacc の使用

C++ とともに lex および yacc を使用する場合は、多少注意が必要になります。lex と yacc は C ファイルに出力しますので、C++ の場合は GNU に対応した flex と bison を使用しました。これらのツールを使用すれば、出力ファイルの名前を指定することができます。われわれは、一般規則も Makefile に追加しましたので、GNU Make は自動的に C++ ソース・ファイルを lex および yacc ソースから作成しました。このため、lex および yacc ソースを それぞれ "lex_eval.l" および "yacc_eval.y" にリネームする必要がありました。その結果、Make は、それぞれ異なる C++ ソース・ファイルを生成しました。われわれは、lex ソースが yacc トークン定義のために組み込んでいるファイルを変更しなければなりませんでした。bison が出力するヘッダー・ファイルは、.h サフィックスを持つ出力ファイルの名前です。したがって、われわれの場合、"yacc_eval.cpp.h" となります。次に、新しい Makefile を示します。

Makefile
all: eval 
%.cpp: %.y
	bison -d -o $@ $<
%.cpp: %.l
	flex -o$@ $<
yacc_eval.o: yacc_eval.cpp
lex_eval.o: lex_eval.cpp
eval: yacc_eval.o lex_eval.o
	$(CXX) -o $@ $^

ストリングからの構文解析

デフォルトの lex コードは、その入力データを標準入力から読み取りますが、われわれのゲームの場合は、メモリー内のストリングを構文解析しよう思いました。これを flex で簡単に行うには、 YY_INPUT マクロを lex ソース・ファイルの先頭に再定義します。

extern int eval_getinput(char *buf, int maxlen);
#undef YY_INPUT
#define YY_INPUT(buf, retval, maxlen)	(retval = eval_getinput(buf, maxlen))

われわれは、eval_getinput() に対する実際のコードを別個のファイルに書き、それをとても柔軟性のあるものにしましたので、入力データをファイル・ポインターまたはメモリー内のストリングから取得することができました。実際のコードを使用するために、われわれはまず、グローバル・データ・ソース変数をセットアップし、次に、yacc 関数 yyparse() を呼び出しました。この関数は、われわれの入力関数を呼び出し、それを構文解析します。

複数パーサーの使用

われわれのゲームでは、スクリプト言語と GUI 記述のための別個のパーサーを持ちたいと思いました。なぜならば、それらは異なる文法規則を使用していたからです。これを行うことは可能ですが、flex と bison で 2 つのトリックを行う必要がありました。まず、名前の衝突を避けるために、パーサーの接頭部を "yy" から何か固有なものに変更しなければなりませんでした。このためにわれわれは、flex と bison に対してコマンド行オプションを使用しました。つまり、flex には -P 、bison には -p です。次に、"yy" 接頭部を使用していたコード内の場所を、われわれが選択した接頭部を使用するように変更しなければなりませんでした。このため、lex ソース内の yylval を参照し、 yyerror() を定義しました。なぜならば、われわれは、最終ゲームのためにそれを別個のファイルに入れていたからです。最終的な Makefile は、次のようになっています。

Makefile
all: eval 
YY_PREFIX = eval_
%.cpp: %.y
	bison -p$(YY_PREFIX) -d -o $@ $<
%.cpp: %.l
	flex -P$(YY_PREFIX) -o$@ $<
yacc_eval.o: yacc_eval.cpp
lex_eval.o: lex_eval.cpp
eval: yacc_eval.o lex_eval.o
	$(CXX) -o $@ $^

われわれのスクリプト言語

われわれは、上記のコード ( 「参考文献」 からダウンロード可能) から始め、機能、変数、簡単なフロー制御などのサポートを追加していき、最後は、かなり完全なゲーム用インタープリット言語を作り上げました。1 つの実行可能なスクリプトのサンプルを示します。

example.txt
{
        if ( $1 == "Blackbeard" ) {
                print("Pouring whitewash on Blackbeard!")
                if ( $rum >= 3 ) {
                        print("Blackbeard doesn't care anymore...")
                        mood = "happy"
                } else {
                        print($1, "says Grr....")
                        mood = "angry"
                        print("Have some more rum?")
                        ++rum
                }
        }
}
pirate = "Blackbeard"
rum = 0
mood = "angry"
print($pirate, "is walking by...")
while ( $mood == "angry" ) {
        whitewash($pirate)
}
return "there was much rejoicing"

yacc による GUI の構築

われわれは、GUI を、属性を基本クラスから継承するウィジェットのセットとして構築しました。これは、yacc がその入力データを構文解析する様子を非常によく示しています。基本クラスの属性に対応する規則のセットを定義した後、ウィジェットのための規則をそれぞれに特有なものとして定義しました。これを、基本クラスの規則についても行いました。パーサーがある規則をウィジェット属性と突き合わせた場合は、ウィジェット・ポインターを適切なクラスに割り当て、希望の属性を設定しても差し支えありません。簡単なボタン・ウィジェットのサンプルを示します。

yacc_gui.y
#include <stdlib.h>
#include <stdio.h>
#include "widget.h"
#include "widget_button.h"
#define PARSE_DEBUG(X)	(printf X)
#define MAX_WIDGET_DEPTH 32
static int widget_depth = -1;
static Widget *widget_stack[MAX_WIDGET_DEPTH];
static Widget *widget;
static void StartWidget(Widget *the_widget)
{
	widget_stack[widget_depth++] = widget = the_widget;
}
static void FinishWidget(void)
{
	Widget *child;
	--widget_depth;
	if ( widget_depth >= 0 ) {
		child = widget;
		widget = widget_stack[widget_depth];
		widget->AddChild(child);
	}
}
%}
[簡単にするために、トークンとタイプは省いてあります]
%%
widget: button
	{ FinishWidget();
	  PARSE_DEBUG(("Completed widget\n")); }
	;
widget_attribute:
	widget_area
	;
/* Widget area: x, y, width, height */
widget_area:
	AREA '{' number ',' number ',' number ',' number '}'
	{ widget->SetArea($3, $5, $7, $9);
	  PARSE_DEBUG(("Area: %dx%d at (%d,%d)\n", $7, $9, $3, $5)); }
	;
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/* The button widget */
button:
	button_tag '{' button_attributes '}'
	{ PARSE_DEBUG(("Completed button\n")); }
	;
button_tag:
	BUTTON name
	{ StartWidget(new WidgetButton($2));
	  PARSE_DEBUG(("Starting a button: %s\n", $2));
	  free($2); }
	;
/* The button widget attributes */
button_attributes:
	button_attribute
|	button_attributes button_attribute
	;
button_attribute:
	widget
|	widget_attribute
|	button_normal_image
|	button_hover_image
	;
button_normal_image:
	IMAGE file
	{ ((WidgetButton *)widget)->LoadNormalImage($2);
	  PARSE_DEBUG(("Button normal image: %s\n", $2));
	  free($2); }
	;
button_hover_image:
	HOVERIMAGE file
	{ ((WidgetButton *)widget)->LoadHoverImage($2);
	  PARSE_DEBUG(("Button hover image: %s\n", $2));
	  free($2); }
	;

サンプル GUI

この技法を使って構築できるような GUI の例として、われわれのメイン・メニューを示します。

main_menu.gui
	image "main_menu"
	button "new_game" {
		area { 32, 80, 370, 64 }
		image "main_menu-new"
		hover_image "main_menu-new_hi"
		#onclick [ new_gui("new_game") ]
		onclick [ new_gui("character_screen") ]
	}
	button "load_game" {
		area { 32, 152, 370, 64 }
		image "main_menu-load"
		hover_image "main_menu-load_hi"
		onclick [ new_gui("load_game") ]
	}
	button "save_game" {
		area { 32, 224, 370, 64 }
		image "main_menu-save"
		hover_image "main_menu-save_hi"
		onclick [ new_gui("save_game") ]
	}
	button "preferences" {
		area { 32, 296, 370, 64 }
		image "main_menu-prefs"
		hover_image "main_menu-prefs_hi"
		onclick [ new_gui("preferences") ]
	}
	button "quit_game" {
		area { 32, 472, 370, 64 }
		image "main_menu-quit"
		hover_image "main_menu-quit_hi"
		onclick [ quit_game() ]
	}
}

この画面の記述では、ウィジェットと属性は GUI パーサーによって構文解析され、ボタン・コールバックがスクリプト・パーサーによってインタープリットされます。new_gui() と quit_game() は、スクリプト・メカニズムにエクスポートされた内部関数です。

メイン・メニュー
スクリーン・ショット
スクリーン・ショット

結論

lex と yacc は、われわれのスクリプト言語や GUI デザイン言語を設計する上で非常に貴重なツールでした。これらは、始めのうちはかなり難しそうに思われましたが、少し使ってみて、快適で、使いやすいものだということが分かりました。来月これを完成しますから、ぜひPirates Ho! の世界に足を踏み入れてください。


ダウンロード可能なリソース


関連トピック


コメント

コメントを登録するにはサインインあるいは登録してください。

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Linux
ArticleID=227108
ArticleTitle=SDL の使用、第4回: lexおよびyacc
publish-date=05012000