antlr/構文木を使った解析
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
[[FrontPage]]
2008/06/26からのアクセス回数 &counter;
#contents
ここでは、[[antlr/ANTLRWorksを使ってみる]]に続いて、例題...
解析に変更して、ANTLRWorksでのデバッグ方法も合わせて紹介...
** 構文木生成 [#y3eb38a0]
例題を四則演算に戻し、変数を導入したのが以下のE3.gです。
#pre{{
grammar E3;
options{
output = AST;
ASTLabelType = CommonTree;
}
tokens{
ASSIGN; ALU_ADD; ALU_SUB; ALU_MUL; ALU_DIV;
}
prog
: (
statement
{ if ($statement.tree != null) System.out.println($stat...
)+
;
statement
: expression NEWLINE!
| IDENTIFIER '=' expression NEWLINE
-> ^(ASSIGN IDENTIFIER expression)
| NEWLINE!
;
expression
: product (aop^ product)*
;
aop
: '+'
-> ALU_ADD
| '-'
-> ALU_SUB
;
product
: factor (pop^ factor)*
;
pop
: '*'
-> ALU_MUL
| '/'
-> ALU_DIV
;
factor
: IDENTIFIER
| CONSTANT
| '('! expression ')'!
;
IDENTIFIER : ('a'..'z'|'A'..'Z')+ ;
CONSTANT : '0'..'9'+ ;
NEWLINE : '\r'? '\n' ;
WS : (' '|'\t')+ {skip();} ;
}}
*** optionsの変更 [#u9fdd2d8]
optionsに
#pre{{
options{
output = AST;
ASTLabelType = CommonTree;
}
}}
とし、出力を構文木、ASTLabelTypeを標準のCommonTreeと宣言...
*** tokenの追加 [#a09717d4]
出力された構文木が言語依存しないようにtokensでオペレータ...
#pre{{
tokens{
ASSIGN; ALU_ADD; ALU_SUB; ALU_MUL; ALU_DIV;
}
}}
ここでは、代入と四則演算を定義しました。
*** 構文木生成オペレータ [#ze05aae2]
構文木を生成する場合に便利なオペレータ！と＾の使い方につ...
構文木は、
#pre{{
^(ルート 要素1 要素2 ...)
}}
のように表現し、ルート要素の子要素として、要素1、要素2が...
構文木生成オペレータは、構文の要素の後に!または、^を続け...
- ^は、指定された要素をルートとするツリーを生成します
- !は、指定された要素を構文木に出力しません
statementを例に説明すると
#pre{{
: expression NEWLINE!
}}
は、NEWLINEを構文木に出力せず、expressionを返す形になりま...
#pre{{
文法定義 -> 構文木置換定義
}}
->オペレータで構文木の置換方法を指定します。
#pre{{
| IDENTIFIER '=' expression NEWLINE
-> ^(ASSIGN IDENTIFIER expression)
}}
は、
^(ASSIGN IDENTIFIER expression)
のように代入トークンの下に識別子とその値（expression）の...
progの定義で
#pre{{
{ if ($statement.tree != null) System.out.println($stat...
}}
の部分で確認のために、生成されたツリーを出力しています。
*** Debuggerで動作を確認 [#q8333fbb]
入力として
#pre{{
a=1
a+2*3
}}
を入力したときのOutputとASTの画面です。
#ref(E3_AST.jpg);
出力は、1行毎の結果で、
#pre{{
(ASSIGN a 1)
(ALU_ADD a (ALU_MUL 2 3))
}}
と期待通りの結果となり、ASTも
#pre{{
^(nil ^(ASSIGN a 1) ^(ALU_ADD a ^(ALUMUL 2 3)))
}}
となっています。
ちなにみ^や!オペレータを使用しない場合には、以下のような...
expression, factorの定義が複雑になっています。
#pre{{
prog
: (
statement
{ if ($statement.tree != null) System.out.println($stat...
)+
;
statement
: expression NEWLINE
-> expression
| IDENTIFIER '=' expression NEWLINE
-> ^(ASSIGN IDENTIFIER expression)
| NEWLINE
->
;
expression
: (product
-> product
)
(aop p=product
-> ^(aop $expression $p)
)*
;
aop
: '+'
-> ALU_ADD
| '-'
-> ALU_SUB
;
product
: (factor
-> factor
)
(pop f=factor
-> ^(pop $product $f)
)*
;
pop
: '*'
-> ALU_MUL
| '/'
-> ALU_DIV
;
factor
: IDENTIFIER
-> IDENTIFIER
| CONSTANT
-> CONSTANT
| '(' expression ')'
-> expression
;
}}
** 構文木解析 [#f182c59a]
構文木解析T1.gは、以下のような定義になります。
#pre{{
tree grammar T1;
options{
tokenVocab=E3;
ASTLabelType = CommonTree;
}
@header {
import java.util.HashMap;
}
@members {
HashMap memory = new HashMap();
}
prog : statement+ ;
statement
: e=expression
{ System.out.println($e.value); }
| ^(ASSIGN id=IDENTIFIER e=expression)
{ memory.put($id.text, new Integer($e.value)); }
;
expression returns [int value]
: ^(ALU_ADD a=expression b=expression)
{$value = $a.value + $b.value;}
| ^(ALU_SUB a=expression b=expression)
{$value = $a.value - $b.value;}
| ^(ALU_MUL a=expression b=expression)
{$value = $a.value * $b.value;}
| ^(ALU_DIV a=expression b=expression)
{$value = $a.value / $b.value;}
| IDENTIFIER
{
Integer v = (Integer)memory.get($IDENTIFIER.text);
if (v != null) $value = v.intValue();
else System.err.println("undefined variable " + $IDENTI...
}
| CONSTANT
{ $value = Integer.parseInt($CONSTANT.text); }
;
}}
*** tree grammar宣言 [#f7156691]
これまでは、grammar宣言を使っていましたが、構文木を扱う文...
tree grammar T1;
のようにtree grammar宣言を使用します。
*** optionsの宣言 [#d52ee497]
optionsでは、
#pre{{
options{
tokenVocab=E3;
ASTLabelType = CommonTree;
}
}}
のように
- tokenVocabで構文木生成に使用したトークンを指定
- ASTLabelTypeを指定
します。
*** header宣言 [#i3accf00]
header宣言では、import文やpackage文等のヘッダ情報を宣言し...
例では、HashMapをインポートしています。
#pre{{
@header {
import java.util.HashMap;
}
}}
*** members宣言 [#h1262612]
members宣言では、構文解析で使用するprivate変数やメソッド...
例では、HashMap型のmemory変数を宣言しています。
#pre{{
@members {
HashMap memory = new HashMap();
}
}}
*** 文法 [#s5cb7e4c]
例題の文法は、
- satement : expressionでは値を出力し、代入ではmomory変数...
- expression : 四則演算結果、変数の値、定数値を返す
''注意すべき点は、この処理は最初の文法には依存しない点で...
*** テストプログラム [#u9ceccba]
残念ながらANTLRWorksでは構文木を扱う文法は直接デバッグす...
プログラムを作成します。
TestE.javaは、以下のように作成します。
#pre{{
import org.antlr.runtime.ANTLRInputStream;
import org.antlr.runtime.CommonTokenStream;
import org.antlr.runtime.tree.CommonTree;
import org.antlr.runtime.tree.CommonTreeNodeStream;
public class TestE {
public static void main(String[] args) throws Excepti...
ANTLRInputStream input = new ANTLRInputStream(Sys...
E3Lexer lexer = new E3Lexer(input);
CommonTokenStream tokens = new CommonTokenStream(...
E3Parser parser = new E3Parser(tokens);
E3Parser.prog_return r = parser.prog();
CommonTree t = (CommonTree)r.getTree();
CommonTreeNodeStream nodes = new CommonTreeNodeSt...
T1 walker = new T1(nodes);
walker.prog();
}
}
}}
ここで、T1をwalkerと宣言していますが、構文木解析プログラ...
ビジターパターンを採用しているからです。
*** デバッグオプション付きでコード生成 [#k998dbd0]
T1.gをデバッグオプション付きでコード生成すると
#pre{{
java org.antlr.Tool -g T1.g
}}
ANTWorksのリモートデバッグが可能なコードを生成します。
*** テストプログラムのデバッグ [#r79ae226]
最初にTestEを起動し、以下のような入力データを入れます。
#pre{{
a=1
a+2*3
}}
TestEは、
#pre{{
(ASSIGN a 1)
(ALU_ADD a (ALU_MUL 2 3))
}}
を出力して停止します。
次にANTLRWorksのDebuggerからDebug Remoteメニューを選択し...
#ref(remote_debug.jpg);
のように入力に構文木が表示され、parse Treeで解析の結果が...
コンソールには、計算結果が表示されます。
#pre{{
7
}}
最後に停止ボタンを押すとプログラムは終了します。
このようにANTLRWorksを使って簡単に構文木解析のプログラム...
** コメント [#r3273b40]
この記事は、
#vote(おもしろかった[58],そうでもない[1],わかりずらい[0])
皆様のご意見、ご希望をお待ちしております。
- デバッグオプションは現在-gではなく、-debugになっている...
- 最新の情報ありがとうございます。 -- [[竹本]] &new{2009-...
- テストプログラムを使った構文木解析の不明点のところ、h94...
- 再入力します。不明点は、TestEは、(ASSIGN a 1)(ALU_ADD a...
- 上記のE3.gをテキストエディタで入力した後、Antlrworksで...
- ANTLRで作成した構文木のいじり方を書いていただきたい -- ...
- kappaさん、コメントありがとうございます。構文木は、関数...
#comment_kcaptcha
終了行:
[[FrontPage]]
2008/06/26からのアクセス回数 &counter;
#contents
ここでは、[[antlr/ANTLRWorksを使ってみる]]に続いて、例題...
解析に変更して、ANTLRWorksでのデバッグ方法も合わせて紹介...
** 構文木生成 [#y3eb38a0]
例題を四則演算に戻し、変数を導入したのが以下のE3.gです。
#pre{{
grammar E3;
options{
output = AST;
ASTLabelType = CommonTree;
}
tokens{
ASSIGN; ALU_ADD; ALU_SUB; ALU_MUL; ALU_DIV;
}
prog
: (
statement
{ if ($statement.tree != null) System.out.println($stat...
)+
;
statement
: expression NEWLINE!
| IDENTIFIER '=' expression NEWLINE
-> ^(ASSIGN IDENTIFIER expression)
| NEWLINE!
;
expression
: product (aop^ product)*
;
aop
: '+'
-> ALU_ADD
| '-'
-> ALU_SUB
;
product
: factor (pop^ factor)*
;
pop
: '*'
-> ALU_MUL
| '/'
-> ALU_DIV
;
factor
: IDENTIFIER
| CONSTANT
| '('! expression ')'!
;
IDENTIFIER : ('a'..'z'|'A'..'Z')+ ;
CONSTANT : '0'..'9'+ ;
NEWLINE : '\r'? '\n' ;
WS : (' '|'\t')+ {skip();} ;
}}
*** optionsの変更 [#u9fdd2d8]
optionsに
#pre{{
options{
output = AST;
ASTLabelType = CommonTree;
}
}}
とし、出力を構文木、ASTLabelTypeを標準のCommonTreeと宣言...
*** tokenの追加 [#a09717d4]
出力された構文木が言語依存しないようにtokensでオペレータ...
#pre{{
tokens{
ASSIGN; ALU_ADD; ALU_SUB; ALU_MUL; ALU_DIV;
}
}}
ここでは、代入と四則演算を定義しました。
*** 構文木生成オペレータ [#ze05aae2]
構文木を生成する場合に便利なオペレータ！と＾の使い方につ...
構文木は、
#pre{{
^(ルート 要素1 要素2 ...)
}}
のように表現し、ルート要素の子要素として、要素1、要素2が...
構文木生成オペレータは、構文の要素の後に!または、^を続け...
- ^は、指定された要素をルートとするツリーを生成します
- !は、指定された要素を構文木に出力しません
statementを例に説明すると
#pre{{
: expression NEWLINE!
}}
は、NEWLINEを構文木に出力せず、expressionを返す形になりま...
#pre{{
文法定義 -> 構文木置換定義
}}
->オペレータで構文木の置換方法を指定します。
#pre{{
| IDENTIFIER '=' expression NEWLINE
-> ^(ASSIGN IDENTIFIER expression)
}}
は、
^(ASSIGN IDENTIFIER expression)
のように代入トークンの下に識別子とその値（expression）の...
progの定義で
#pre{{
{ if ($statement.tree != null) System.out.println($stat...
}}
の部分で確認のために、生成されたツリーを出力しています。
*** Debuggerで動作を確認 [#q8333fbb]
入力として
#pre{{
a=1
a+2*3
}}
を入力したときのOutputとASTの画面です。
#ref(E3_AST.jpg);
出力は、1行毎の結果で、
#pre{{
(ASSIGN a 1)
(ALU_ADD a (ALU_MUL 2 3))
}}
と期待通りの結果となり、ASTも
#pre{{
^(nil ^(ASSIGN a 1) ^(ALU_ADD a ^(ALUMUL 2 3)))
}}
となっています。
ちなにみ^や!オペレータを使用しない場合には、以下のような...
expression, factorの定義が複雑になっています。
#pre{{
prog
: (
statement
{ if ($statement.tree != null) System.out.println($stat...
)+
;
statement
: expression NEWLINE
-> expression
| IDENTIFIER '=' expression NEWLINE
-> ^(ASSIGN IDENTIFIER expression)
| NEWLINE
->
;
expression
: (product
-> product
)
(aop p=product
-> ^(aop $expression $p)
)*
;
aop
: '+'
-> ALU_ADD
| '-'
-> ALU_SUB
;
product
: (factor
-> factor
)
(pop f=factor
-> ^(pop $product $f)
)*
;
pop
: '*'
-> ALU_MUL
| '/'
-> ALU_DIV
;
factor
: IDENTIFIER
-> IDENTIFIER
| CONSTANT
-> CONSTANT
| '(' expression ')'
-> expression
;
}}
** 構文木解析 [#f182c59a]
構文木解析T1.gは、以下のような定義になります。
#pre{{
tree grammar T1;
options{
tokenVocab=E3;
ASTLabelType = CommonTree;
}
@header {
import java.util.HashMap;
}
@members {
HashMap memory = new HashMap();
}
prog : statement+ ;
statement
: e=expression
{ System.out.println($e.value); }
| ^(ASSIGN id=IDENTIFIER e=expression)
{ memory.put($id.text, new Integer($e.value)); }
;
expression returns [int value]
: ^(ALU_ADD a=expression b=expression)
{$value = $a.value + $b.value;}
| ^(ALU_SUB a=expression b=expression)
{$value = $a.value - $b.value;}
| ^(ALU_MUL a=expression b=expression)
{$value = $a.value * $b.value;}
| ^(ALU_DIV a=expression b=expression)
{$value = $a.value / $b.value;}
| IDENTIFIER
{
Integer v = (Integer)memory.get($IDENTIFIER.text);
if (v != null) $value = v.intValue();
else System.err.println("undefined variable " + $IDENTI...
}
| CONSTANT
{ $value = Integer.parseInt($CONSTANT.text); }
;
}}
*** tree grammar宣言 [#f7156691]
これまでは、grammar宣言を使っていましたが、構文木を扱う文...
tree grammar T1;
のようにtree grammar宣言を使用します。
*** optionsの宣言 [#d52ee497]
optionsでは、
#pre{{
options{
tokenVocab=E3;
ASTLabelType = CommonTree;
}
}}
のように
- tokenVocabで構文木生成に使用したトークンを指定
- ASTLabelTypeを指定
します。
*** header宣言 [#i3accf00]
header宣言では、import文やpackage文等のヘッダ情報を宣言し...
例では、HashMapをインポートしています。
#pre{{
@header {
import java.util.HashMap;
}
}}
*** members宣言 [#h1262612]
members宣言では、構文解析で使用するprivate変数やメソッド...
例では、HashMap型のmemory変数を宣言しています。
#pre{{
@members {
HashMap memory = new HashMap();
}
}}
*** 文法 [#s5cb7e4c]
例題の文法は、
- satement : expressionでは値を出力し、代入ではmomory変数...
- expression : 四則演算結果、変数の値、定数値を返す
''注意すべき点は、この処理は最初の文法には依存しない点で...
*** テストプログラム [#u9ceccba]
残念ながらANTLRWorksでは構文木を扱う文法は直接デバッグす...
プログラムを作成します。
TestE.javaは、以下のように作成します。
#pre{{
import org.antlr.runtime.ANTLRInputStream;
import org.antlr.runtime.CommonTokenStream;
import org.antlr.runtime.tree.CommonTree;
import org.antlr.runtime.tree.CommonTreeNodeStream;
public class TestE {
public static void main(String[] args) throws Excepti...
ANTLRInputStream input = new ANTLRInputStream(Sys...
E3Lexer lexer = new E3Lexer(input);
CommonTokenStream tokens = new CommonTokenStream(...
E3Parser parser = new E3Parser(tokens);
E3Parser.prog_return r = parser.prog();
CommonTree t = (CommonTree)r.getTree();
CommonTreeNodeStream nodes = new CommonTreeNodeSt...
T1 walker = new T1(nodes);
walker.prog();
}
}
}}
ここで、T1をwalkerと宣言していますが、構文木解析プログラ...
ビジターパターンを採用しているからです。
*** デバッグオプション付きでコード生成 [#k998dbd0]
T1.gをデバッグオプション付きでコード生成すると
#pre{{
java org.antlr.Tool -g T1.g
}}
ANTWorksのリモートデバッグが可能なコードを生成します。
*** テストプログラムのデバッグ [#r79ae226]
最初にTestEを起動し、以下のような入力データを入れます。
#pre{{
a=1
a+2*3
}}
TestEは、
#pre{{
(ASSIGN a 1)
(ALU_ADD a (ALU_MUL 2 3))
}}
を出力して停止します。
次にANTLRWorksのDebuggerからDebug Remoteメニューを選択し...
#ref(remote_debug.jpg);
のように入力に構文木が表示され、parse Treeで解析の結果が...
コンソールには、計算結果が表示されます。
#pre{{
7
}}
最後に停止ボタンを押すとプログラムは終了します。
このようにANTLRWorksを使って簡単に構文木解析のプログラム...
** コメント [#r3273b40]
この記事は、
#vote(おもしろかった[58],そうでもない[1],わかりずらい[0])
皆様のご意見、ご希望をお待ちしております。
- デバッグオプションは現在-gではなく、-debugになっている...
- 最新の情報ありがとうございます。 -- [[竹本]] &new{2009-...
- テストプログラムを使った構文木解析の不明点のところ、h94...
- 再入力します。不明点は、TestEは、(ASSIGN a 1)(ALU_ADD a...
- 上記のE3.gをテキストエディタで入力した後、Antlrworksで...
- ANTLRで作成した構文木のいじり方を書いていただきたい -- ...
- kappaさん、コメントありがとうございます。構文木は、関数...
#comment_kcaptcha
ページ名:
SmartDoc
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
