antlr/ANTLRWorksを使ってみるのバックアップ(No.117)

expression
         : expression '+' product
	 | expression '-' product
	 | product

product
         : product '*' factor
	 | product '/' factor
	 | factor

factor
         : IDENTIFIER
	 | CONSTANT
	 | '(' expressoin ')'

をどのようにANTLRで記述するかを紹介します。

↑

左再帰が使えないことへの対応 †

上記のルールをANTLRWorksで入力すると

のように波下線のある expression, productで Rule "expression" is left-recursive のエラーメッセージが表示されます。

左再帰（left-recursive）を避けるために、文法を以下のように変更します。

expression
	: product ('+' product)*
	| product ('-' product)*
	;

product
	: factor ('*' factor)*
	| factor ('/' factor)*
	;

ここで＊は、カッコで括った部分が0回以上繰り返されることを意味します。

これでエラーは無くなりましたが、expression, productで8個の警告が出力されます。そこで、

expression
	: product ('+' product | '-' product)*
	;

product
	: factor ('*' factor | '/' factor)*
	;

に変更します。

文法が正しいかどうかexpressionのSyntax Diagramを見てみましょう。

これは、productが1個あり、その後に+または-に続きproductが繰り返されることを表現しています。

expressionのシンタックス・グラフ

とは形は異なりますが、同じ処理をすることが読み取れます。

↑

演算の優先順位の対応 †

演算の優先順位は、明示的に文法に記述する必要があります。

上記の例では、

和（+）、差（-）
積（*）、商（/）
カッコ、識別子、定数

のように下に行くほど優先順位が高くなります。これをそれぞれ

pxpression
product
factor

と明示的に定義します。

では、Interpreterで優先順位が正しく処理されているか見てみましょう。

1との和（expression）を行う前に、2と3の積の処理（product）が行われるのが分かります。

↑

右結合演算子の対応 †

累乗（power）のように右結合演算子（right-associative）の処理は、次のように記述します。

expression
	: product ('+' product | '-' product)*
	;

product
	: power ('*' power | '/' power)*
	;
power
	: factor ('^' power)?
	;
factor
	: IDENTIFIER
	| CONSTANT
	| '(' expression ')'
	;

ここで、powerは、右再帰となっています。

1+2^3^4*3

を入力としたときの構文木は、

のようになり、

1 + ((2^(3^4)) * 5)

の計算順序を正しく処理しているのが分かります。

↑

アクションの追加 †

ANTLRでも、yaccのように文法の中にアクションを記述することができます。先の、例題にアクションを追加すると次のようになります。フォーマットはSampleCに合わせて文法はタブ1個の後、アクションはタブ2個の後に記述することにします。

grammar E1;

prog
	: e=expression NEWLINE
		{ System.out.println($e.value);}
	| NEWLINE
	;
expression returns [int value]
	: e=product 
		{$value = $e.value;}
	( '+' e=product 
		{$value += $e.value;}
	| '-' e=product
		{$value -= $e.value;}
	)*
	;
product returns [int value]
	: e=power 
		{$value = $e.value;} 
	( '*' e=power 
		{$value *= $e.value;}
	| '/' e=power
		{$value /= $e.value;}
	)*
	;
power returns [int value]
	: b=factor 
		{ $value = $b.value;}
	( '^' e=power
		{ double v = Math.pow($b.value, $e.value);
		  $value = (int)v;
		}		 
	)?
	;
factor returns [int value]
	: IDENTIFIER
		{$value = 0;}
	| CONSTANT
		{$value = Integer.parseInt($CONSTANT.text);}
	| '(' expression ')'
		{$value = $expression.value;}
	;

IDENTIFIER	:   ('a'..'z'|'A'..'Z')+ ;
CONSTANT	:   '0'..'9'+ ;
NEWLINE		:   '\r'? '\n' ;
WS		:   (' '|'\t')+ {skip();} ;

改行で計算をするようにprogを追加しました。

ノンターミナル（expression, product等）の後に

returns [int value]

を追加することで、戻り値の型と値を保持する変数を定義します。

e=product

のようにノンターミナルの前にラベル=を追加することで、ノンターミナルへの参照をラベルで代用することができます。

例えば、power項では、

power returns [int value]
	: b=factor 
		{ $value = $b.value;}
	( '^' e=power
		{ double v = Math.pow($b.value, $e.value);
		  $value = (int)v;
		}	
	)?
	;

とありますが、ここでb=factor, e=powerを使って

double v = Math.pow($b.value, $e.value);

累乗の計算をしています。

↑

デバッガの起動 †

ANTLRWorksでは、テストプログラムを作成しなくても、文法を実行し、デバッグすることができます。

メニューのDebuggerからDebug... を選択すると自動的にコード生成、コンパイルを実行した後
テストデータを入力する「Input Text」ダイアログが表示します。
右向き▲のStep forwardボタンを押すと、入力テキストが文法のどの部分にマッチしていくかが分かります
Outputボタンを選択すると計算結果や途中のSystem.out.printlnの値を見ることができます。

↑

コメント †

この記事は、

皆様のご意見、ご希望をお待ちしております。

yaccは、LR(1)ではなく、LALR(1)でした。訂正し、お詫びします。 -- 竹本　浩? 2009-08-11 (火) 22:38:45

選択肢	投票
おもしろかった	226
そうでもない	1
わかりずらい	4

antlr/ANTLRWorksを使ってみる のバックアップ(No.117)

ANTLR、ANTLRWorksとは何か †

ANTLRとは何か †

ANTWorksとは何か †

ANTLRWorksのインストール †

ANTLRWorksの起動 †