![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
|
2008/07/07からのアクセス回数 9979 antlr/構文木を使った解析では、構文木を使った四則演算プログラムを紹介しましたが、 ここではCコンパイラ設計(yacc・lexの応用)/第7章 コードの生成と同じアセンブラ コードを出力するコンパイラを作成します。 SampleC構文解析 †SampleCは、Cのサブセットで
最初に、sample.yをベースに以下の処理をします。
生成する構文木の形 †入力として以下のデータを入力すると 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ノードの下にPROGRAMノードがあり、その下に2個のFUNCノードとCALLノードを持つツリーが作成されます。  1個目のFUNCノードは、  2個目のFUNCノードは、  のようになります。
また、SampleCの構文木のみの特徴として式の後にセミコロンがきた タイミングでスタックをクリアするためにEXPRとCLEARノードを追加します。 例えば、 1 + 2; は、 ^(EXPR ^(ALU_ADD 1 2) CLEAR) となります。 SampleC.g †SampleC.gは次のようになります。 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; EXPR;
}
program
: (
d=definition
{ if ($d.tree != null) System.out.println($d.tree.toStringTree());}
)+ EOF
-> ^(PROGRAM definition+ ^(CALL {adaptor.create(IDENTIFIER,"main")} ^(ARG)))
;
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 ';'
-> ^(EXPR $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();} ;
メモリ管理 †Cでは、広域変数領域、パラメータ領域、局所領域の変数を管理するため、それぞれオフセットを保持する必要があります。 下記のプログラムの場合、 main(p0, p1)
int p0;
int p1;
{ int main0, main1;
p0, p1, main0,main1;
{ int nest2, next3, nest4;
nest2,next3,nest4;
}
{ int new2;
new2;
{ int inner3;
inner3;
}
{ int inner3, inner4;
inner3,inner4;
}
}
{ int last2;
last2;
}
}
各変数は、次のようにメモリに割り当てられます。  実際にSampleCのgeneratorの出力のloadオペレータの後の、par, lclの後の数値がそれぞれの変数領域 のオフセットを表しています。上記の図と一致していることが分かります。 main entry $$1
load par,0 ; p0
pop ; discard
load par,1 ; p1
pop ; discard
load lcl,0 ; main0
pop ; discard
load lcl,1 ; main1
pop ; clear stack
load lcl,2 ; nest2
pop ; discard
load lcl,3 ; next3
pop ; discard
load lcl,4 ; nest4
pop ; clear stack
load lcl,2 ; new2
pop ; clear stack
load lcl,3 ; inner3
pop ; clear stack
load lcl,3 ; inner3
pop ; discard
load lcl,4 ; inner4
pop ; clear stack
load lcl,2 ; last2
pop ; clear stack
return ; end of function
$$1 equ= 5 ; main
end 1,main
SymbolTable †SampleCに合わせて、関数や変数を管理するSymbolTalbeを作成します。
SymbolTable.javaは、次のようになります。 import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class SymbolTable {
static final int GLOBALS = 0;
static final int PARAMS = 1;
Map functions = new HashMap();
List scopes = new ArrayList();
Map globals = new HashMap();
Map params = new HashMap();
int globalVarNum = 1;
int paramVarNum = 0;
int localVarNum = 0;
int LabelNum = 0;
public SymbolTable() {
scopes.add(globals);
scopes.add(params);
}
public int nextLabelNum() {
return (LabelNum++);
}
public void enterFunction(String name) {
enterBlock();
}
public void exitFunction() {
exitBlock();
params.clear();
}
public void enterBlock() {
scopes.add(new HashMap());
}
public void exitBlock() {
int lastIndex = scopes.size()-1;
if (lastIndex > PARAMS) {
Map scope = (Map)scopes.get(lastIndex);
localVarNum -= scope.size();
scopes.remove(lastIndex);
}
}
public void declareFunction(String name, String returnType) {
functions.put(name, new Function(name, returnType));
}
public void declareGlobalVariable(String name, String type) {
globals.put(name, new Variable(name, type, new Integer(globalVarNum++)));
}
public void declareLocalVariable(String name, String type) {
Map scope = (Map)scopes.get(scopes.size()-1);
scope.put(name, new Variable(name, type, new Integer(localVarNum++)));
}
public void declareParameter(String name, String type) {
params.put(name, new Variable(name, type, new Integer(paramVarNum++)));
}
public boolean isDeclaredVariable(String name) {
return (getVariableModeAndOffset(name) != null);
}
public boolean isDeclaredFunction(String name) {
return (functions.get(name) != null);
}
public String getVariableModeAndOffset(String name) {
for (int i = scopes.size()-1; i >= 0; i--) {
Map vars = (Map)scopes.get(i);
Variable v = (Variable)vars.get(name);
if (v != null) {
if (i == GLOBALS) return ("gbl," + v.offset);
else if (i == PARAMS) return ("par," + v.offset);
else return ("lcl," + v.offset);
}
}
return (null);
}
}
class Variable {
public String name;
public String type;
public Integer offset;
public Variable(String name, String type, Integer offset) {
this.name = name;
this.type = type;
this.offset = offset;
}
}
class Function {
public String name;
public String returnType;
public Function(String name, String returnType) {
this.name = name;
this.returnType = returnType;
}
コード生成コンパイルによって生成されるアセンブラとその関数もSampleCの関数名と同じ名称でGen.javaに定義します。 Gen.javaのソースは以下の通りです。 import java.util.Stack;
public class Gen {
public static final String OP_ALU = "alu";
public static final String OP_DEC = "dec";
public static final String OP_INC = "inc";
public static final String OP_LOAD = "load";
public static final String OP_STORE = "store";
public static final String OP_POP = "pop";
public static final String OP_JUMPZ = "jumpz";
public static final String OP_JUMP = "jump";
public static final String OP_CALL = "call";
public static final String OP_ENTRY = "entry";
public static final String OP_RETURN = "return";
public static final String MOD_IMMED = "con";
public static final String ALU_ADD = "+";
public static final String ALU_SUB = "-";
public static final String ALU_MUL = "*";
public static final String ALU_DIV = "/";
public static final String ALU_MOD = "%";
public static final String ALU_LT = "<";
public static final String ALU_GT = ">";
public static final String ALU_LE = "<=";
public static final String ALU_GE = ">=";
public static final String ALU_EQ = "==";
public static final String ALU_NE = "!=";
public static final String ALU_AND = "&";
public static final String ALU_OR = "|";
public static final String ALU_XOR = "^";
private Stack b_stack = new Stack();
private Stack c_stack = new Stack();
private String c_top = null;
private String b_top = null;
private int new_label = 0;
public String new_label() {
return ("$$" + (++new_label));
}
public void gen_alu(String mod, String comment) {
System.out.println("\t" + OP_ALU + "\t" + mod + "\t\t; " + comment);
}
public void gen_li(String constant) {
System.out.println("\t" + OP_LOAD + "\t" + MOD_IMMED + "," + constant);
}
public void gen(String op, String modAndOffset, String comment) {
System.out.println("\t" + op + "\t" + modAndOffset + "\t\t; " + comment);
}
public void gen_pr(String op, String comment) {
System.out.println("\t" + op + "\t\t\t; " + comment);
}
public String gen_jump(String op, String label, String comment) {
System.out.println("\t" + op + "\t" + label + "\t\t; " + comment);
return label;
}
public String gen_label(String label) {
System.out.println(label + "\tequ\t*");
return label;
}
public void gen_break() {
gen_jump(OP_JUMP, b_top, "BREAK");
}
public void gen_continue() {
gen_jump(OP_JUMP, b_top, "CONTINUE");
}
public void gen_call(String name, int count) {
System.out.println("\t" + OP_CALL + "\t" + count + "," + name);
for (int i = 0; i < count; i++)
gen_pr(OP_POP, "pop argument");
gen(OP_LOAD, "gbl,0", "push result");
}
public String gen_entry(String name) {
String label = new_label();
System.out.println(name + "\t" + OP_ENTRY + "\t" + label);
return label;
}
public void fix_entry(String name, String label) {
System.out.println(label + "\tequ=\tx\t\t; " + name);
}
public void end_program() {
System.out.println("\tend,x\tmain");
}
public void push_break(String label) {
b_stack.push(label);
}
public void push_continue(String label) {
c_stack.push(label);
}
public void pop_break() {
b_top = (String)b_stack.pop();
}
public void pop_continue() {
c_top = (String)c_stack.pop();
}
}
構文木ツリーからのコンパイル †次に、SampleC.gによって生成された構文木からアセンブラを生成するCompiler.gを作成 します。 ANTLRでは、テンプレート機能を使ってコード生成をすることができますが、 SampleC.yと比較できるように、ここではMain.genにセットされているGenクラスの メソッド呼び出しでアセンブラを出力します。 SampleC.gの以下のようになります。 tree grammar Compiler;
options{
tokenVocab = SampleC;
ASTLabelType = CommonTree;
}
program
@after{
Main.gen.end_program();
}
: ^(PROGRAM definition+ call) EOF
;
definition
: functionDefintion
| ^(VARDEF INT i=IDENTIFIER)
{ Main.symtab.declareGlobalVariable($i.text, "int"); }
;
functionDefintion
scope {
String label;
}
@after{
Main.symtab.exitFunction();
}
: ^(FUNC INT i=IDENTIFIER ^(FUNCPAR parameterList) parameterDeclarations
{ Main.symtab.declareFunction($i.text, "int");
Main.symtab.enterFunction($i.text);
$functionDefintion::label = Main.gen.gen_entry($i.text);
}
compoundStatement
{ Main.gen.gen_pr(Gen.OP_RETURN, "end of function");
Main.gen.fix_entry($i.text, $functionDefintion::label);
}
)
;
parameterList
: IDENTIFIER*
;
parameterDeclarations
: ^(PARDEF parameterDeclaration*)
;
parameterDeclaration
: ^(VARDEF INT i=IDENTIFIER
{ Main.symtab.declareParameter($i.text, "int"); }
)
;
compoundStatement
@init{
Main.symtab.enterBlock();
}
@after{
Main.symtab.exitBlock();
}
: ^(BLOCK declarations statements)
;
declarations
: declaration*
;
declaration
: ^(VARDEF INT i=IDENTIFIER
{ Main.symtab.declareLocalVariable($i.text, "int"); }
)
;
statements
: statement*
;
statement
scope {
String label1;
String label2;
}
: e=expression
| ^(EXPR expression CLEAR)
| NOP
| CLEAR
{ Main.gen.gen_pr(Gen.OP_POP, "clear stack"); }
| BREAK
{ Main.gen.gen_break(); }
| CONTINUE
{ Main.gen.gen_continue(); }
| RETURN
{ Main.gen.gen_pr(Gen.OP_RETURN, "RETURN"); }
| ^(RETURN e=expression)
{ Main.gen.gen(Gen.OP_STORE, "gbl,0", "save result");
Main.gen.gen_pr(Gen.OP_RETURN, "RETURN");
}
| c=compoundStatement
| ^(IF
e=expression
{ $statement::label1 = Main.gen.gen_jump(Gen.OP_JUMPZ, Main.gen.new_label(), "IF");
}
s1=statement
{ $statement::label2 = Main.gen.gen_jump(Gen.OP_JUMP, Main.gen.new_label(), "past ELSE");
Main.gen.gen_label($statement::label1);
}
s2=statement
{ Main.gen.gen_label($statement::label2); }
)
| ^(WHILE
{ $statement::label1 = Main.gen.gen_label($statement::label1);
Main.gen.push_continue($statement::label1);
}
e=expression
{ $statement::label2 = Main.gen.gen_jump(Gen.OP_JUMPZ, Main.gen.new_label(), "WHILE");
Main.gen.push_break($statement::label2);
}
s=statement
{ Main.gen.gen_jump(Gen.OP_JUMP, $statement::label1, "repeat WHILE");
Main.gen.gen_label($statement::label2);
Main.gen.pop_break();
Main.gen.pop_continue();
}
)
;
expression
: ^(ALU_EQ e1=expression e2=expression)
{ Main.gen.gen_alu(Gen.ALU_EQ, "=="); }
| ^(ALU_NE e1=expression e2=expression)
{ Main.gen.gen_alu(Gen.ALU_NE, "!="); }
| ^(ALU_GT e1=expression e2=expression)
{ Main.gen.gen_alu(Gen.ALU_GT, ">"); }
| ^(ALU_LT e1=expression e2=expression)
{ Main.gen.gen_alu(Gen.ALU_LT, "<"); }
| ^(ALU_LE e1=expression e2=expression)
{ Main.gen.gen_alu(Gen.ALU_LE, "<="); }
| ^(ALU_GE e1=expression e2=expression)
{ Main.gen.gen_alu(Gen.ALU_GE, ">="); }
| ^(ALU_ADD e1=expression e2=expression)
{ Main.gen.gen_alu(Gen.ALU_ADD, "+"); }
| ^(ALU_SUB e1=expression e2=expression)
{ Main.gen.gen_alu(Gen.ALU_SUB, "-"); }
| ^(ALU_MUL e1=expression e2=expression)
{ Main.gen.gen_alu(Gen.ALU_MUL, "*"); }
| ^(ALU_DIV e1=expression e2=expression)
{ Main.gen.gen_alu(Gen.ALU_DIV, "/"); }
| ^(ALU_AND e1=expression e2=expression)
{ Main.gen.gen_alu(Gen.ALU_AND, "&"); }
| ^(ALU_OR e1=expression e2=expression)
{ Main.gen.gen_alu(Gen.ALU_OR, "|"); }
| ^(ALU_XOR e1=expression e2=expression)
{ Main.gen.gen_alu(Gen.ALU_XOR, "^"); }
| ^(NOT e1=expression)
{ Main.gen.gen_alu(Gen.ALU_EQ, "=="); }
| ^(NEGATE e1=expression)
{ Main.gen.gen_alu(Gen.ALU_EQ, "=="); }
| ^(ASSIGN i=IDENTIFIER e=expression)
{ Main.gen.gen(Gen.OP_STORE, Main.symtab.getVariableModeAndOffset($i.text), $i.text); }
| ^(PREFIX i=IDENTIFIER PP)
{ Main.gen.gen(Gen.OP_INC, Main.symtab.getVariableModeAndOffset($i.text), $i.text); }
| ^(PREFIX i=IDENTIFIER MM)
{ Main.gen.gen(Gen.OP_DEC, Main.symtab.getVariableModeAndOffset($i.text), $i.text); }
| call
| i=IDENTIFIER
{ Main.gen.gen(Gen.OP_LOAD, Main.symtab.getVariableModeAndOffset($i.text), $i.text); }
| c=CONSTANT
{ Main.gen.gen_li($c.text); }
;
call
@init {
int argCnt = 0;
}
: ^(CALL i=IDENTIFIER
{ argCnt = 0; }
^(ARG (e=expression
{ argCnt++; }
)*)
{ Main.gen.gen_call($i.text, argCnt); }
)
;
例 †Main関数は、以下のように定義します。 import org.antlr.runtime.ANTLRInputStream;
import org.antlr.runtime.CommonTokenStream;
import org.antlr.runtime.tree.CommonTree;
import org.antlr.runtime.tree.CommonTreeNodeStream;
public class Main {
public static SymbolTable symtab = new SymbolTable();
public static Gen gen = new Gen();
public static void main(String[] args) throws Exception {
ANTLRInputStream input = new ANTLRInputStream(System.in);
SampleCLexer lexer = new SampleCLexer(input);
CommonTokenStream tokens = new CommonTokenStream(lexer);
SampleCParser parser = new SampleCParser(tokens);
SampleCParser.program_return r = parser.program();
CommonTree t = (CommonTree)r.getTree();
CommonTreeNodeStream nodes = new CommonTreeNodeStream(t);
Compiler walker = new Compiler(nodes);
walker.program();
}
}
テストラン †プログラムは、変数や関数のチェックもありませんが、SampleCの例と同じ、以下の入力データを与えると 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);
}
以下のように結果を出力しました（BLOCKを見やすく手で修正してあります）。 (FUNC INT main FUNCPAR PARDEF (BLOCK (EXPR (CALL gcd (ARG 36 54)) CLEAR)))
(FUNC INT gcd (FUNCPAR a b) (PARDEF (VARDEF INT a) (VARDEF INT b))
(BLOCK
(IF (ALU_EQ a b)
(return a)
(IF (ALU_GT a b)
(return (CALL gcd (ARG (ALU_SUB a b) b)))
(return (CALL gcd (ARG a (ALU_SUB b a))))))))
main entry $$1
load con,36
load con,54
call 2,gcd
pop ; pop argument
pop ; pop argument
load gbl,0 ; push result
return ; end of function
$$1 equ= x ; main
gcd entry $$2
load par,0 ; a
load par,1 ; b
alu == ; ==
jumpz $$3 ; IF
load par,0 ; a
store gbl,0 ; save result
return ; RETURN
jump $$4 ; past ELSE
$$3 equ *
load par,0 ; a
load par,1 ; b
alu > ; >
jumpz $$5 ; IF
load par,0 ; a
load par,1 ; b
alu - ; -
load par,1 ; b
call 2,gcd
pop ; pop argument
pop ; pop argument
load gbl,0 ; push result
store gbl,0 ; save result
return ; RETURN
jump $$6 ; past ELSE
$$5 equ *
load par,0 ; a
load par,1 ; b
load par,0 ; a
alu - ; -
call 2,gcd
pop ; pop argument
pop ; pop argument
load gbl,0 ; push result
store gbl,0 ; save result
return ; RETURN
$$6 equ *
$$4 equ *
return ; end of function
$$2 equ= x ; gcd
call 0,main
load gbl,0 ; push result
end,x main
感想 †SampleCコンパイラの移植を通じてANTLRとANTLRWorksの完成度の高さに感動しました。 わずか1日で、SampleCのコンパイラができたことは、驚異のツールと言って過言ではないと 思います。 コメント †この記事は、 皆様のご意見、ご希望をお待ちしております。
Tweet |
func_tree.jpg 1888件
[詳細]
variable_region.jpg 1742件
[詳細]
func_tree2.jpg 1688件
[詳細]
func_tree1.jpg 1640件
[詳細]
