antlr/ANTLRWorksを使ってみる
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
[[FrontPage]]
2008/06/18からのアクセス回数 &counter;
#contents
** ANTLR、ANTLRWorksとは何か [#pdd09b01]
*** ANTLRとは何か [#y7ebd92e]
ANTLRは、yacc, lexと同じコンパイラー・コンパイラーです。
ANTRLを使うことで、
- 言語のコンパイラ、
- 言語のインタプリタ
- 他の言語への変換ツール
を容易に作成することができます。
一時期よりも話題にならなかったコンパイラー技術もGWTがjava...
使ったことにより、その価値が見直されているのではないかと...
特にANTRLは、
+ 入力プログラムをASTと呼ばれる構文木に変換し
+ ASTから変数テーブル、関数テーブル、構文チェック、コンパ...
を生成するため、数テーブル、関数テーブル、構文チェック、...
再利用できる点が優れています。
*** ANTWorksとは何か [#rcaf5b10]
ANTWorksは、ANTLRの文法を作成、チェックするためのワークベ...
- ルールの編集
- インタプリタの提供（テストデータがどのように解析される...
- デバッガの提供（どのルールでどのように構文解析されたか...
- ルールからパーザーの生成
ができます。
** ANTLRWorksのインストール [#yed4e973]
ANTLRWorksは、以下のURLからマシン環境に合ったファイルをダ...
http://www.antlr.org/works/index.html
私は、MacOSXを使用しているので、ANTRLWOrks 1.1.7のBundole...
*** ANTLRWorksの起動 [#rb0c99a9]
ANTLRWorksの使い方は、http://www.antlr.org/works/help/tut...
画面の表示例を以下に示します。
#ref(layout.jpg);
** yacc, lexとの違い [#a8b100a4]
[[Cコンパイラ設計(yacc・lexの応用)]] で紹介した
yaccではLALR(1)を使って構文解析を行うのに対し、ANTLRはLL(...
ANTRLの特徴は、
- 字句解析と構文解析を1つのツールで処理する
- 構文解析の結果生成される構文木（AST）を入力して次の段階...
- ANTLRWorksというGUI開発環境を提供し、構文のチェック、入...
- 様々なプラットフォーム、言語に対応している
が挙げられます。
yacc, lexと比較すると
- yaccがLALR(1)を使ったボトムアップの解析をするのに対し、...
- 拡張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 "expressi...
が表示されます。
左再帰（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のように文法の中にアクションを記述すること...
先の、例題にアクションを追加すると次のようになります。フ...
文法はタブ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.prin...
#ref(debugger.jpg);
-
** コメント [#v9b1b96c]
この記事は、
#vote(おもしろかった[230],そうでもない[1],わかりずらい[5])
皆様のご意見、ご希望をお待ちしております。
- yaccは、LR(1)ではなく、LALR(1)でした。訂正し、お詫びし...
#comment_kcaptcha
終了行:
[[FrontPage]]
2008/06/18からのアクセス回数 &counter;
#contents
** ANTLR、ANTLRWorksとは何か [#pdd09b01]
*** ANTLRとは何か [#y7ebd92e]
ANTLRは、yacc, lexと同じコンパイラー・コンパイラーです。
ANTRLを使うことで、
- 言語のコンパイラ、
- 言語のインタプリタ
- 他の言語への変換ツール
を容易に作成することができます。
一時期よりも話題にならなかったコンパイラー技術もGWTがjava...
使ったことにより、その価値が見直されているのではないかと...
特にANTRLは、
+ 入力プログラムをASTと呼ばれる構文木に変換し
+ ASTから変数テーブル、関数テーブル、構文チェック、コンパ...
を生成するため、数テーブル、関数テーブル、構文チェック、...
再利用できる点が優れています。
*** ANTWorksとは何か [#rcaf5b10]
ANTWorksは、ANTLRの文法を作成、チェックするためのワークベ...
- ルールの編集
- インタプリタの提供（テストデータがどのように解析される...
- デバッガの提供（どのルールでどのように構文解析されたか...
- ルールからパーザーの生成
ができます。
** ANTLRWorksのインストール [#yed4e973]
ANTLRWorksは、以下のURLからマシン環境に合ったファイルをダ...
http://www.antlr.org/works/index.html
私は、MacOSXを使用しているので、ANTRLWOrks 1.1.7のBundole...
*** ANTLRWorksの起動 [#rb0c99a9]
ANTLRWorksの使い方は、http://www.antlr.org/works/help/tut...
画面の表示例を以下に示します。
#ref(layout.jpg);
** yacc, lexとの違い [#a8b100a4]
[[Cコンパイラ設計(yacc・lexの応用)]] で紹介した
yaccではLALR(1)を使って構文解析を行うのに対し、ANTLRはLL(...
ANTRLの特徴は、
- 字句解析と構文解析を1つのツールで処理する
- 構文解析の結果生成される構文木（AST）を入力して次の段階...
- ANTLRWorksというGUI開発環境を提供し、構文のチェック、入...
- 様々なプラットフォーム、言語に対応している
が挙げられます。
yacc, lexと比較すると
- yaccがLALR(1)を使ったボトムアップの解析をするのに対し、...
- 拡張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 "expressi...
が表示されます。
左再帰（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のように文法の中にアクションを記述すること...
先の、例題にアクションを追加すると次のようになります。フ...
文法はタブ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.prin...
#ref(debugger.jpg);
-
** コメント [#v9b1b96c]
この記事は、
#vote(おもしろかった[230],そうでもない[1],わかりずらい[5])
皆様のご意見、ご希望をお待ちしております。
- yaccは、LR(1)ではなく、LALR(1)でした。訂正し、お詫びし...
#comment_kcaptcha
ページ名:
SmartDoc
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
