antlr/antlrを使ったSampleCコンパイラのバックアップ差分(No.2)

追加された行はこの色です。
削除された行はこの色です。
[[FrontPage]]

2008/07/07からのアクセス回数 &counter;

#contents

[[antlr/構文木を使った解析]]では、構文木を使った四則演算プログラムを紹介しましたが、
ここでは[[Cコンパイラ設計(yacc・lexの応用)/第7章　コードの生成]]と同じアセンブラ
コードを出力するコンパイラを作成します。

** SampleC構文解析 [#f916548a]
SampleCは、Cのサブセットで
- 型はintのスカラーのみ
- フロー制御は、if文、while文のみ
をサポートしています。

最初に、sample.yをベースに以下の処理をします。
- 左再帰をEBNFに変更
- 優先順位を明示的に記述
- エラー処理を外す

*** 生成する構文木の形 [#zca43761]
入力として以下のデータを入力すると
#pre{{
main()
{	
	gcd(36,54);
}

gcd(a,b)
int a;
int b;
{
	if (a == b)
		return a;
	else if (a > b)
		return gcd(a-b, b);
	else
		return gcd(a, b-a);
}
}}

nilノードに2個のFUNCノードを持つツリーが作成されます。
1個目のFUNCノードは、
#ref(func_tree1.jpg);

2個目のFUNCノードは、
#ref(func_tree2.jpg);
のようになります。

- FUNCノードには、以下のノードが付いています。
-- 関数の型
-- 関数名
-- 関数パラメータのFUNCPARノード
-- パラメータの型定義のPARDEFノード
-- 関数本体のBLOCKノード


- 関数呼び出しCALLノードには、以下のノードが付いています。
-- 関数名
-- 引数リストのARGノード

- IF文のIFノードには、以下のノードが付いています。
-- 条件文
-- 条件がTRUEの時の処理ノード
-- 条件がFALSEの時の処理ノード

また、SampleCの構文木のみの特徴として式の後にセミコロンがきた
タイミングでスタックをクリアするためにCLEARノードを追加します。

*** SampleC.g [#zb4c1cd3]
SampleC.gは次のようになります。

#pre{{
grammar SampleC;

options{
	output = AST;
	ASTLabelType = CommonTree;
}

tokens{
	PROGRAM; FUNC; FUNCPAR; PARDEF; VARDEF; BLOCK; ASSIGN;  
	CALL; NOT; NEGATE; ARG; NUM; VAR; PREFIX; NOP; CLEAR;
	ALU_ADD; ALU_SUB; ALU_MUL; ALU_DIV; ALU_LT; 
	ALU_GT; ALU_LE; ALU_GE; ALU_EQ; ALU_NE; 
	ALU_AND; ALU_OR; ALU_XOR;
	INT; VOID; IF; WHILE;
}

program
	: (
	  d=definition
	  	{ if ($d.tree != null) System.out.println($d.tree.toStringTree());}
	  )+
	  	-> ^(PROGRAM definition+)
	;
definition
	: functionDefintion
		-> functionDefintion
	| declaration
		-> declaration
	;
functionDefintion
	: funcType IDENTIFIER '(' parameterList ')' parameterDeclarations compoundStatement
		-> ^(FUNC funcType IDENTIFIER ^(FUNCPAR parameterList) parameterDeclarations compoundStatement)
	;
funcType
	: type
		-> type
	|	-> INT
	;
parameterList
	: (IDENTIFIER (',' IDENTIFIER)*)?
		-> IDENTIFIER*
	;
parameterDeclarations
	: parameterDeclaration*
		-> ^(PARDEF parameterDeclaration*)
	;
parameterDeclaration
	: (t=type id=IDENTIFIER
		-> ^(VARDEF $t $id)
	  )
	  (',' (id=IDENTIFIER)
	  	-> $parameterDeclaration ^(VARDEF $t $id)
	  )* ';'
	;
compoundStatement
	: '{' declarations statements '}'
		-> ^(BLOCK declarations statements)
	;
declarations
	: declaration*
	;
declaration
	: (t=type id=IDENTIFIER
		-> ^(VARDEF $t $id)
	  )
	  (',' (id=IDENTIFIER)
	  	-> $declaration ^(VARDEF $t $id)
	  )* ';'
	;
statements
	: statement*
	;
statement
options {
	backtrack=true;
}
	: e=expression ';'
		-> $e CLEAR
	| ';'
		-> NOP
	| BREAK 
		-> BREAK
	| CONTINUE
		-> CONTINUE
	| RETURN ';'
		-> RETURN
	| RETURN e=expression ';'
		-> ^(RETURN $e)
	| c=compoundStatement
		-> $c
	| ifstm
		-> ifstm
	| 'while' '(' e=expression ')' s=statement
		-> ^(WHILE $e $s)
	;
ifstm
options{
	backtrack=true;
}
	: 'if' '(' e=expression ')' s1=statement ELSE s2=statement
		-> ^(IF $e $s1 $s2)
	| 'if' '(' e=expression ')' s1=statement
		-> ^(IF $e $s1 NOP)
	;
expression 
	: binary
		-> binary
	;
binary
	: i=IDENTIFIER '=' e=expression
		-> ^(ASSIGN $i $e)
	| IDENTIFIER PE e=expression
		-> ^(ASSIGN IDENTIFIER ^(ALU_ADD IDENTIFIER $e))
	| IDENTIFIER ME e=expression
		-> ^(ASSIGN IDENTIFIER ^(ALU_SUB IDENTIFIER $e))
	| IDENTIFIER TE e=expression
		-> ^(ASSIGN IDENTIFIER ^(ALU_MUL IDENTIFIER $e))
	| IDENTIFIER DE e=expression
		-> ^(ASSIGN IDENTIFIER ^(ALU_DIV IDENTIFIER $e))
	| equalityExpr
		-> equalityExpr
	;
equalityExpr
	: comparisonExpr (eqOp^ comparisonExpr)*
	;
eqOp
	: '==' 
		-> ALU_EQ
	| ('!=' | '<>')
		-> ALU_NE
	;
comparisonExpr
	: additiveExpr (compOp^ additiveExpr)*
	;
compOp
	: '>'
		-> ALU_GT
	| '<'
		-> ALU_LT
	| '<='
		-> ALU_LE
	| '>='
		-> ALU_GE
	;
additiveExpr
	: multiplicativeExpr (addOp^ multiplicativeExpr)*
	;
addOp
	: '+'
		-> ALU_ADD
	| '-'
		-> ALU_SUB
	;
multiplicativeExpr
	: bitExpr (mulOp^ bitExpr)*
	;	
mulOp	
	: '*'
		-> ALU_MUL
	| '/'
		-> ALU_DIV
	;
bitExpr
	: notExpr (bitOp^ notExpr)*
	;
bitOp
	: '&'
		-> ALU_AND
	| '|'
		-> ALU_OR
	| '^'
		-> ALU_XOR
	;
notExpr
	: op='!'? negationExpr
		-> {$op != null}? ^(NOT negationExpr)
		-> negationExpr
	;
negationExpr
	: op='-'? primary
		-> {$op != null}? ^(NEGATE primary)
		-> primary
	;
primary
	: atom
	| '('! expression ')'!
	;
atom
	: IDENTIFIER
		-> IDENTIFIER
	| PP IDENTIFIER
		-> ^(PREFIX IDENTIFIER PP)
	| MM IDENTIFIER
		-> ^(PREFIX IDENTIFIER MM)
	| CONSTANT
		-> CONSTANT
	| IDENTIFIER '(' a=argumentList ')'
		-> ^(CALL IDENTIFIER $a)
	;

argumentList
	: (expression (',' expression)*)?
		-> ^(ARG expression*)
	;
type
	: 'int' 
		-> INT
	;
	
BREAK		: 'break' ;
CONTINUE	: 'continue' ;
RETURN		: 'return' ;
ELSE		: 'else' ;
PP		: '++' ;
MM		: '--' ;
PE		: '+=' ;
ME		: '-=' ;
TE		: '*=' ;
DE		: '/=' ;	
IDENTIFIER	: ('a'..'z'|'A'..'Z')('a'..'z'|'A'..'Z'|'0'..'9')* ;
CONSTANT	: '0'..'9'+ ;
WS		: (' '|'\t'|'\r'|'\n')+ {skip();} ;
}}


** コメント [#b42076b0]
この記事は、

#vote(おもしろかった,そうでもない,わかりずらい)

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

#comment
antlr/antlrを使ったSampleCコンパイラ のバックアップ差分(No.2)

antlr/antlrを使ったSampleCコンパイラのバックアップ差分(No.2)
