![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
|
2008/06/26からのアクセス回数 22310 ここでは、antlr/ANTLRWorksを使ってみるに続いて、例題を構文木を使った 解析に変更して、ANTLRWorksでのデバッグ方法も合わせて紹介する。 構文木生成 †例題を四則演算に戻し、変数を導入したのが以下のE3.gです。 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($statement.tree.toStringTree());}
)+
;
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の変更 †optionsに options{
output = AST;
ASTLabelType = CommonTree;
}
とし、出力を構文木、ASTLabelTypeを標準のCommonTreeと宣言します。 tokenの追加 †出力された構文木が言語依存しないようにtokensでオペレータのトークンを宣言します。 tokens{
ASSIGN; ALU_ADD; ALU_SUB; ALU_MUL; ALU_DIV;
}
ここでは、代入と四則演算を定義しました。 構文木生成オペレータ †構文木を生成する場合に便利なオペレータ！と＾の使い方について説明します。 構文木は、 ^(ルート 要素1 要素2 ...) のように表現し、ルート要素の子要素として、要素1、要素2が生成されることを表します。 構文木生成オペレータは、構文の要素の後に!または、^を続けて付けて使用します。
statementを例に説明すると : expression NEWLINE! は、NEWLINEを構文木に出力せず、expressionを返す形になります。 文法定義 -> 構文木置換定義
| IDENTIFIER '=' expression NEWLINE -> ^(ASSIGN IDENTIFIER expression) は、 ^(ASSIGN IDENTIFIER expression) のように代入トークンの下に識別子とその値（expression）の構文木を生成するように指定します。 progの定義で { if ($statement.tree != null) System.out.println($statement.tree.toStringTree());}
の部分で確認のために、生成されたツリーを出力しています。 Debuggerで動作を確認 †入力として a=1 a+2*3 を入力したときのOutputとASTの画面です。  出力は、1行毎の結果で、 (ASSIGN a 1) (ALU_ADD a (ALU_MUL 2 3)) と期待通りの結果となり、ASTも ^(nil ^(ASSIGN a 1) ^(ALU_ADD a ^(ALUMUL 2 3))) となっています。 ちなにみ^や!オペレータを使用しない場合には、以下のような定義になります（構文のみ抜粋）。 expression, factorの定義が複雑になっています。 prog
: (
statement
{ if ($statement.tree != null) System.out.println($statement.tree.toStringTree());}
)+
;
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
;
構文木解析 †構文木解析T1.gは、以下のような定義になります。 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 " + $IDENTIFIER.text);
}
| CONSTANT
{ $value = Integer.parseInt($CONSTANT.text); }
;
tree grammar宣言 †これまでは、grammar宣言を使っていましたが、構文木を扱う文法では、 tree grammar T1; のようにtree grammar宣言を使用します。 optionsの宣言 †optionsでは、 options{
tokenVocab=E3;
ASTLabelType = CommonTree;
}
のように
します。 header宣言 †header宣言では、import文やpackage文等のヘッダ情報を宣言します。 例では、HashMapをインポートしています。 @header {
import java.util.HashMap;
}
members宣言 †members宣言では、構文解析で使用するprivate変数やメソッドを定義します。 例では、HashMap型のmemory変数を宣言しています。 @members {
HashMap memory = new HashMap();
}
文法 †例題の文法は、
注意すべき点は、この処理は最初の文法には依存しない点です テストプログラム †残念ながらANTLRWorksでは構文木を扱う文法は直接デバッグすることはできないので、テスト プログラムを作成します。 TestE.javaは、以下のように作成します。 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 Exception {
ANTLRInputStream input = new ANTLRInputStream(System.in);
E3Lexer lexer = new E3Lexer(input);
CommonTokenStream tokens = new CommonTokenStream(lexer);
E3Parser parser = new E3Parser(tokens);
E3Parser.prog_return r = parser.prog();
CommonTree t = (CommonTree)r.getTree();
CommonTreeNodeStream nodes = new CommonTreeNodeStream(t);
T1 walker = new T1(nodes);
walker.prog();
}
}
ここで、T1をwalkerと宣言していますが、構文木解析プログラムがデザインパターンの ビジターパターンを採用しているからです。 デバッグオプション付きでコード生成 †T1.gをデバッグオプション付きでコード生成すると java org.antlr.Tool -g T1.g ANTWorksのリモートデバッグが可能なコードを生成します。 テストプログラムのデバッグ †最初にTestEを起動し、以下のような入力データを入れます。 a=1 a+2*3 TestEは、 (ASSIGN a 1) (ALU_ADD a (ALU_MUL 2 3)) を出力して停止します。 次にANTLRWorksのDebuggerからDebug Remoteメニューを選択します。  のように入力に構文木が表示され、parse Treeで解析の結果が表示されます。 コンソールには、計算結果が表示されます。 7 最後に停止ボタンを押すとプログラムは終了します。 このようにANTLRWorksを使って簡単に構文木解析のプログラムもデバッグできます。 コメント †この記事は、 皆様のご意見、ご希望をお待ちしております。
Tweet |
remote_debug.jpg
E3_AST.jpg
