#freeze
[[FrontPage]]
2008/06/18からのアクセス回数 &counter;
#contents
** ANTLR、ANTLRWorksとは何か [#pdd09b01]
*** ANTLRとは何か [#y7ebd92e]
ANTLRは、yacc, lexと同じコンパイラー・コンパイラーです。
ANTRLを使うことで、
- 言語のコンパイラ、
- 言語のインタプリタ
- 他の言語への変換ツール
を容易に作成することができます。
一時期よりも話題にならなかったコンパイラー技術もGWTがjavaからjavascriptへの変換を
使ったことにより、その価値が見直されているのではないかと思います。
特にANTRLは、
+ 入力プログラムをASTと呼ばれる構文木に変換し
+ ASTから変数テーブル、関数テーブル、構文チェック、コンパイラー、インタプリタ
を生成するため、数テーブル、関数テーブル、構文チェック、コンパイラー、インタプリタが
再利用できる点が優れています。
*** ANTWorksとは何か [#rcaf5b10]
ANTWorksは、ANTLRの文法を作成、チェックするためのワークベンチです。
- ルールの編集
- インタプリタの提供（テストデータがどのように解析されるか構文ツリーで表示）
- デバッガの提供（どのルールでどのように構文解析されたかを確認できる）
- ルールからパーザーの生成
ができます。
** ANTLRWorksのインストール [#yed4e973]
ANTLRWorksは、以下のURLからマシン環境に合ったファイルをダウンローしてください。
http://www.antlr.org/works/index.html
私は、MacOSXを使用しているので、ANTRLWOrks 1.1.7のBundole for Mac OS Xをダウンロードしました。
*** ANTLRWorksの起動 [#rb0c99a9]
ANTLRWorksの使い方は、http://www.antlr.org/works/help/tutorial/calculator.html を参照してください。
画面の表示例を以下に示します。
#ref(layout.jpg);
** yacc, lexとの違い [#a8b100a4]
[[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章 言語の定義]]の例題の文法
#pre{{
expression
: expression '+' product
| expression '-' product
| product
product
: product '*' factor
| product '/' factor
| factor
factor
: IDENTIFIER
| CONSTANT
| '(' expressoin ')'
}}
をどのようにANTLRで記述するかを紹介します。
*** 左再帰が使えないことへの対応 [#ia95e5a2]
上記のルールをANTLRWorksで入力すると
#ref(E1_error.jpg);
のように波下線のある expression, productで Rule "expression" is left-recursive のエラーメッセージ
が表示されます。
左再帰（left-recursive）を避けるために、文法を以下のように変更します。
#pre{{
expression
: product ('+' product)*
| product ('-' product)*
;
product
: factor ('*' factor)*
| factor ('/' factor)*
;
}}
ここで＊は、カッコで括った部分が0回以上繰り返されることを意味します。
これでエラーは無くなりましたが、expression, productで8個の警告が出力されます。
そこで、
#pre{{
expression
: product ('+' product | '-' product)*
;
product
: factor ('*' factor | '/' factor)*
;
}}
に変更します。
文法が正しいかどうかexpressionのSyntax Diagramを見てみましょう。
#ref(E1_diagram.jpg);
これは、productが1個あり、その後に+または-に続きproductが繰り返されることを表現しています。
expressionのシンタックス・グラフ
#ref(expression.jpg);
とは形は異なりますが、同じ処理をすることが読み取れます。
*** 演算の優先順位の対応 [#y5ae9a6b]
演算の優先順位は、明示的に文法に記述する必要があります。
上記の例では、
+ 和（+）、差（-）
+ 積（*）、商（/）
+ カッコ、識別子、定数
のように下に行くほど優先順位が高くなります。これをそれぞれ
+ pxpression
+ product
+ factor
と明示的に定義します。
では、Interpreterで優先順位が正しく処理されているか見てみましょう。
#ref(E1_interpret.jpg);
1との和（expression）を行う前に、2と3の積の処理（product）が行われるのが分かります。
*** 右結合演算子の対応 [#yf4a865d]
累乗（power）のように右結合演算子（right-associative）の処理は、次のように記述します。
#pre{{
expression
: product ('+' product | '-' product)*
;
product
: power ('*' power | '/' power)*
;
power
: factor ('^' power)?
;
factor
: IDENTIFIER
| CONSTANT
| '(' expression ')'
;
}}
ここで、powerは、右再帰となっています。
1+2^3^4*3
を入力としたときの構文木は、
#ref(power_tree.jpg);
のようになり、
1 + ((2^(3^4)) * 5)
の計算順序を正しく処理しているのが分かります。
** アクションの追加 [#s53db36c]
ANTLRでも、yaccのように文法の中にアクションを記述することができます。
先の、例題にアクションを追加すると次のようになります。フォーマットはSampleCに合わせて
文法はタブ1個の後、アクションはタブ2個の後に記述することにします。
#pre{{
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項では、
#pre{{
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);
累乗の計算をしています。
*** デバッガの起動 [#we8246df]
ANTLRWorksでは、テストプログラムを作成しなくても、文法を実行し、デバッグすることができます。
- メニューのDebuggerからDebug... を選択すると自動的にコード生成、コンパイルを実行した後
- テストデータを入力する「Input Text」ダイアログが表示します。
#ref(input_text.jpg);
- 右向き▲のStep forwardボタンを押すと、入力テキストが文法のどの部分にマッチしていくかが分かります
- Outputボタンを選択すると計算結果や途中のSystem.out.printlnの値を見ることができます。
#ref(debugger.jpg);
-
** コメント [#v9b1b96c]
この記事は、
#vote(おもしろかった[229],そうでもない[1],わかりずらい[5])
#vote(おもしろかった[230],そうでもない[1],わかりずらい[5])
皆様のご意見、ご希望をお待ちしております。
- yaccは、LR(1)ではなく、LALR(1)でした。訂正し、お詫びします。 -- [[竹本 浩]] &new{2009-08-11 (火) 22:38:45};
#comment_kcaptcha
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
