FrontPage

2008/06/18からのアクセス回数 27644

ANTLR、ANTLRWorksとは何か

ANTLRとは何か

ANTLRは、yacc, lexと同じコンパイラー・コンパイラーです。

ANTRLを使うことで、

  • 言語のコンパイラ、
  • 言語のインタプリタ
  • 他の言語への変換ツール

を容易に作成することができます。

一時期よりも話題にならなかったコンパイラー技術もGWTがjavaからjavascriptへの変換を 使ったことにより、その価値が見直されているのではないかと思います。

特にANTRLは、

  1. 入力プログラムをASTと呼ばれる構文木に変換し
  2. ASTから変数テーブル、関数テーブル、構文チェック、コンパイラー、インタプリタ

を生成するため、数テーブル、関数テーブル、構文チェック、コンパイラー、インタプリタが 再利用できる点が優れています。

ANTWorksとは何か

ANTWorksは、ANTLRの文法を作成、チェックするためのワークベンチです。

  • ルールの編集
  • インタプリタの提供(テストデータがどのように解析されるか構文ツリーで表示)
  • デバッガの提供(どのルールでどのように構文解析されたかを確認できる)
  • ルールからパーザーの生成

ができます。

ANTLRWorksのインストール

ANTLRWorksは、以下のURLからマシン環境に合ったファイルをダウンローしてください。

http://www.antlr.org/works/index.html

私は、MacOSXを使用しているので、ANTRLWOrks 1.1.7のBundole for Mac OS Xをダウンロードしました。

ANTLRWorksの起動

ANTLRWorksの使い方は、http://www.antlr.org/works/help/tutorial/calculator.html を参照してください。

画面の表示例を以下に示します。

layout.jpg

yacc, lexとの違い

Cコンパイラ設計(yacc・lexの応用) で紹介した yaccではLALR(1)を使って構文解析を行うのに対し、ANTLRはLL(*)を使って構文解析を行います。

ANTRLの特徴は、

  • 字句解析と構文解析を1つのツールで処理する
  • 構文解析の結果生成される構文木(AST)を入力して次の段階の構文解析を行うことができる
  • ANTLRWorksというGUI開発環境を提供し、構文のチェック、入力データの構文解析結果の表示、デバッグができる
  • 様々なプラットフォーム、言語に対応している

が挙げられます。

yacc, lexと比較すると

  • yaccがLALR(1)を使ったボトムアップの解析をするのに対し、ANTLRはLL(*)を使ったトップダウン解析をします
  • 拡張BNFで構文を記述できる
  • ANTLRは、左再帰が使えない
  • left, right, noassocが使えないため、文法で明示的に優先順位を指定する必要がある

の違いがあります。

以下では、Cコンパイラ設計(yacc・lexの応用)/第1章 言語の定義の例題の文法

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

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

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

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

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

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

E1_error.jpg

のように波下線のある 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を見てみましょう。

E1_diagram.jpg

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

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

expression.jpg

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

演算の優先順位の対応

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

上記の例では、

  1. 和(+)、差(-)
  2. 積(*)、商(/)
  3. カッコ、識別子、定数

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

  1. pxpression
  2. product
  3. factor

と明示的に定義します。

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

E1_interpret.jpg

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

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

power_tree.jpg

のようになり、

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」ダイアログが表示します。
    input_text.jpg
  • 右向き▲のStep forwardボタンを押すと、入力テキストが文法のどの部分にマッチしていくかが分かります
  • Outputボタンを選択すると計算結果や途中のSystem.out.printlnの値を見ることができます。
    debugger.jpg

コメント

この記事は、

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

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

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

(Input image string)


添付ファイル: filedebugger.jpg 1106件 [詳細] fileinput_text.jpg 506件 [詳細] filepower_tree.jpg 1249件 [詳細] fileexpression.jpg 990件 [詳細] fileE1_diagram.jpg 1075件 [詳細] fileE1_interpret.jpg 1061件 [詳細] fileE1_error.jpg 1119件 [詳細] filelayout.jpg 1218件 [詳細]

トップ   編集 凍結解除 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2017-03-18 (土) 00:11:47 (5d)
SmartDoc