antlr/構文木を使った解析のバックアップ(No.1)

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

構文木生成
コメント

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

↑

コメント †

この記事は、

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

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