FrontPage

2008/06/26からのアクセス回数 14781

ここでは、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の画面です。

E3_AST.jpg

出力は、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;
}

のように

  • tokenVocabで構文木生成に使用したトークンを指定
  • ASTLabelTypeを指定

します。

header宣言

header宣言では、import文やpackage文等のヘッダ情報を宣言します。

例では、HashMapをインポートしています。

@header {
import java.util.HashMap;
}

members宣言

members宣言では、構文解析で使用するprivate変数やメソッドを定義します。

例では、HashMap型のmemory変数を宣言しています。

@members {
HashMap	memory = new HashMap();
}

文法

例題の文法は、

  • satement : expressionでは値を出力し、代入ではmomory変数にセット
  • expression : 四則演算結果、変数の値、定数値を返す

注意すべき点は、この処理は最初の文法には依存しない点です

テストプログラム

残念ながら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メニューを選択します。

remote_debug.jpg

のように入力に構文木が表示され、parse Treeで解析の結果が表示されます。

コンソールには、計算結果が表示されます。

7

最後に停止ボタンを押すとプログラムは終了します。

このようにANTLRWorksを使って簡単に構文木解析のプログラムもデバッグできます。

コメント

この記事は、

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

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

  • デバッグオプションは現在-gではなく、-debugになっているようです。 -- Aobara? 2009-01-06 (火) 16:54:54
  • 最新の情報ありがとうございます。 -- 竹本? 2009-01-06 (火) 18:11:37
  • テストプログラムを使った構文木解析の不明点のところ、h94192@live.jpまでご返事いただければ幸いです。 -- sadie? 2009-07-17 (金) 16:06:40
  • 再入力します。不明点は、TestEは、(ASSIGN a 1)(ALU_ADD a (ALU_MUL 2 3))を出力して停止しません。というところです。 -- sadie? 2009-07-17 (金) 16:12:16
  • 上記のE3.gをテキストエディタで入力した後、Antlrworksで上記の手順で試してみてください。お願いします。 -- 竹本 浩? 2009-07-17 (金) 23:58:26
  • ANTLRで作成した構文木のいじり方を書いていただきたい -- kappa? 2010-06-22 (火) 18:26:50
  • kappaさん、コメントありがとうございます。構文木は、関数テーブル、変数テーブル、コード変換において共有することに価値があるのだと考えています。例題の作成にはすこしお時間をください。 -- 竹本 浩? 2010-06-22 (火) 22:30:11

(Input image string)


添付ファイル: fileremote_debug.jpg 888件 [詳細] fileE3_AST.jpg 871件 [詳細]

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