antlr/antlrを使ったSampleCコンパイラ
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
[[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ノードの下にPROGRAMノードがあり、その下に2個のFUNCノー...
#ref(func_tree.jpg);
1個目のFUNCノードは、
#ref(func_tree1.jpg);
2個目のFUNCノードは、
#ref(func_tree2.jpg);
のようになります。
- FUNCノードには、以下のノードが付いています。
-- 関数の型
-- 関数名
-- 関数パラメータのFUNCPARノード
-- パラメータの型定義のPARDEFノード
-- 関数本体のBLOCKノード
- 関数呼び出しCALLノードには、以下のノードが付いています。
-- 関数名
-- 引数リストのARGノード
- IF文のIFノードには、以下のノードが付いています。
-- 条件文
-- 条件がTRUEの時の処理ノード
-- 条件がFALSEの時の処理ノード
また、SampleCの構文木のみの特徴として式の後にセミコロンが...
タイミングでスタックをクリアするためにEXPRとCLEARノードを...
例えば、
1 + 2;
は、
^(EXPR ^(ALU_ADD 1 2) 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; EXPR;
}
program
: (
d=definition
{ if ($d.tree != null) System.out.println($d.tree.toS...
)+ EOF
-> ^(PROGRAM definition+ ^(CALL {adaptor.create(IDENT...
;
definition
: functionDefintion
-> functionDefintion
| declaration
-> declaration
;
functionDefintion
: funcType IDENTIFIER '(' parameterList ')' parameterDec...
-> ^(FUNC funcType IDENTIFIER ^(FUNCPAR parameterList) ...
;
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'..'...
CONSTANT : '0'..'9'+ ;
WS : (' '|'\t'|'\r'|'\n')+ {skip();} ;
}}
** メモリ管理 [#p5f434d2]
Cでは、広域変数領域、パラメータ領域、局所領域の変数を管理...
下記のプログラムの場合、
#pre{{
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;
}
}
}}
各変数は、次のようにメモリに割り当てられます。
#ref(variable_region.jpg);
実際にSampleCのgeneratorの出力のloadオペレータの後の、par...
のオフセットを表しています。上記の図と一致していることが...
#pre{{
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 [#sdad0c03]
SampleCに合わせて、関数や変数を管理するSymbolTalbeを作成...
- 関数を管理するfunctions
- 変数は、リストscopesを使って関数呼び出し、複合文に合わ...
- scopesの0番目には広域変数を管理するglobalsマップがあり...
paramsマップがあります。
- 変数名をscopesの最後から順に検索し、メモリ割り当て領域...
SymbolTable.javaは、次のようになります。
#pre{{
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 returnTy...
functions.put(name, new Function(name, returnType));
}
public void declareGlobalVariable(String name, String ty...
globals.put(name, new Variable(name, type, new Integer(...
}
public void declareLocalVariable(String name, String typ...
Map scope = (Map)scopes.get(scopes.size()-1);
scope.put(name, new Variable(name, type, new Integer(lo...
}
public void declareParameter(String name, String type) {
params.put(name, new Variable(name, type, new Integer(p...
}
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のソースは以下の通りです。
#pre{{
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; ...
}
public void gen_li(String constant) {
System.out.println("\t" + OP_LOAD + "\t" + MOD_IMMED + ...
}
public void gen(String op, String modAndOffset, String c...
System.out.println("\t" + op + "\t" + modAndOffset + "\...
}
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 c...
System.out.println("\t" + op + "\t" + label + "\t\t; " ...
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 + "," ...
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" + labe...
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();
}
}
}}
** 構文木ツリーからのコンパイル [#jcceca76]
次に、SampleC.gによって生成された構文木からアセンブラを生...
します。
ANTLRでは、テンプレート機能を使ってコード生成をすることが...
SampleC.yと比較できるように、ここではMain.genにセットされ...
メソッド呼び出しでアセンブラを出力します。
SampleC.gの以下のようになります。
#pre{{
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) param...
{ Main.symtab.declareFunction($i.text, "int");
Main.symtab.enterFunction($i.text);
$functionDefintion::label = Main.gen.gen_entry($i.tex...
}
compoundStatement
{ Main.gen.gen_pr(Gen.OP_RETURN, "end of function");
Main.gen.fix_entry($i.text, $functionDefintion::lab...
}
)
;
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...
}
s1=statement
{ $statement::label2 = Main.gen.gen_jump(Gen.OP_JUMP,...
Main.gen.gen_label($statement::label1);
}
s2=statement
{ Main.gen.gen_label($statement::label2); }
)
| ^(WHILE
{ $statement::label1 = Main.gen.gen_label($statement::l...
Main.gen.push_continue($statement::label1);
}
e=expression
{ $statement::label2 = Main.gen.gen_jump(Gen.OP_JUM...
Main.gen.push_break($statement::label2);
}
s=statement
{ Main.gen.gen_jump(Gen.OP_JUMP, $statement::label1...
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.getVariableMod...
| ^(PREFIX i=IDENTIFIER PP)
{ Main.gen.gen(Gen.OP_INC, Main.symtab.getVariableModeA...
| ^(PREFIX i=IDENTIFIER MM)
{ Main.gen.gen(Gen.OP_DEC, Main.symtab.getVariableModeA...
| call
| i=IDENTIFIER
{ Main.gen.gen(Gen.OP_LOAD, Main.symtab.getVariableMode...
| 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); }
)
;
}}
** 例 [#jedb0887]
Main関数は、以下のように定義します。
#pre{{
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 Excepti...
ANTLRInputStream input = new ANTLRInputStream(Sys...
SampleCLexer lexer = new SampleCLexer(input);
CommonTokenStream tokens = new CommonTokenStream(...
SampleCParser parser = new SampleCParser(tokens);
SampleCParser.program_return r = parser.program();
CommonTree t = (CommonTree)r.getTree();
CommonTreeNodeStream nodes = new CommonTreeNodeSt...
Compiler walker = new Compiler(nodes);
walker.program();
}
}
}}
*** テストラン [#ub00547c]
プログラムは、変数や関数のチェックもありませんが、SampleC...
#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);
}
}}
以下のように結果を出力しました（BLOCKを見やすく手で修正し...
#pre{{
(FUNC INT main FUNCPAR PARDEF (BLOCK (EXPR (CALL gcd (ARG...
(FUNC INT gcd (FUNCPAR a b) (PARDEF (VARDEF INT a) (VARDE...
(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
}}
*** 感想 [#fecc8129]
SampleCコンパイラの移植を通じてANTLRとANTLRWorksの完成度...
わずか1日で、SampleCのコンパイラができたことは、驚異のツ...
思います。
** コメント [#b42076b0]
この記事は、
#vote(おもしろかった[28],そうでもない[0],わかりずらい[0])
皆様のご意見、ご希望をお待ちしております。
- インタプリタの作成できづいたEXPRの導入とmain関数呼び出...
- 非常に遅くなりましたが…例を作ってくださってありがとうご...
#comment_kcaptcha
終了行:
[[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ノードの下にPROGRAMノードがあり、その下に2個のFUNCノー...
#ref(func_tree.jpg);
1個目のFUNCノードは、
#ref(func_tree1.jpg);
2個目のFUNCノードは、
#ref(func_tree2.jpg);
のようになります。
- FUNCノードには、以下のノードが付いています。
-- 関数の型
-- 関数名
-- 関数パラメータのFUNCPARノード
-- パラメータの型定義のPARDEFノード
-- 関数本体のBLOCKノード
- 関数呼び出しCALLノードには、以下のノードが付いています。
-- 関数名
-- 引数リストのARGノード
- IF文のIFノードには、以下のノードが付いています。
-- 条件文
-- 条件がTRUEの時の処理ノード
-- 条件がFALSEの時の処理ノード
また、SampleCの構文木のみの特徴として式の後にセミコロンが...
タイミングでスタックをクリアするためにEXPRとCLEARノードを...
例えば、
1 + 2;
は、
^(EXPR ^(ALU_ADD 1 2) 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; EXPR;
}
program
: (
d=definition
{ if ($d.tree != null) System.out.println($d.tree.toS...
)+ EOF
-> ^(PROGRAM definition+ ^(CALL {adaptor.create(IDENT...
;
definition
: functionDefintion
-> functionDefintion
| declaration
-> declaration
;
functionDefintion
: funcType IDENTIFIER '(' parameterList ')' parameterDec...
-> ^(FUNC funcType IDENTIFIER ^(FUNCPAR parameterList) ...
;
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'..'...
CONSTANT : '0'..'9'+ ;
WS : (' '|'\t'|'\r'|'\n')+ {skip();} ;
}}
** メモリ管理 [#p5f434d2]
Cでは、広域変数領域、パラメータ領域、局所領域の変数を管理...
下記のプログラムの場合、
#pre{{
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;
}
}
}}
各変数は、次のようにメモリに割り当てられます。
#ref(variable_region.jpg);
実際にSampleCのgeneratorの出力のloadオペレータの後の、par...
のオフセットを表しています。上記の図と一致していることが...
#pre{{
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 [#sdad0c03]
SampleCに合わせて、関数や変数を管理するSymbolTalbeを作成...
- 関数を管理するfunctions
- 変数は、リストscopesを使って関数呼び出し、複合文に合わ...
- scopesの0番目には広域変数を管理するglobalsマップがあり...
paramsマップがあります。
- 変数名をscopesの最後から順に検索し、メモリ割り当て領域...
SymbolTable.javaは、次のようになります。
#pre{{
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 returnTy...
functions.put(name, new Function(name, returnType));
}
public void declareGlobalVariable(String name, String ty...
globals.put(name, new Variable(name, type, new Integer(...
}
public void declareLocalVariable(String name, String typ...
Map scope = (Map)scopes.get(scopes.size()-1);
scope.put(name, new Variable(name, type, new Integer(lo...
}
public void declareParameter(String name, String type) {
params.put(name, new Variable(name, type, new Integer(p...
}
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のソースは以下の通りです。
#pre{{
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; ...
}
public void gen_li(String constant) {
System.out.println("\t" + OP_LOAD + "\t" + MOD_IMMED + ...
}
public void gen(String op, String modAndOffset, String c...
System.out.println("\t" + op + "\t" + modAndOffset + "\...
}
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 c...
System.out.println("\t" + op + "\t" + label + "\t\t; " ...
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 + "," ...
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" + labe...
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();
}
}
}}
** 構文木ツリーからのコンパイル [#jcceca76]
次に、SampleC.gによって生成された構文木からアセンブラを生...
します。
ANTLRでは、テンプレート機能を使ってコード生成をすることが...
SampleC.yと比較できるように、ここではMain.genにセットされ...
メソッド呼び出しでアセンブラを出力します。
SampleC.gの以下のようになります。
#pre{{
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) param...
{ Main.symtab.declareFunction($i.text, "int");
Main.symtab.enterFunction($i.text);
$functionDefintion::label = Main.gen.gen_entry($i.tex...
}
compoundStatement
{ Main.gen.gen_pr(Gen.OP_RETURN, "end of function");
Main.gen.fix_entry($i.text, $functionDefintion::lab...
}
)
;
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...
}
s1=statement
{ $statement::label2 = Main.gen.gen_jump(Gen.OP_JUMP,...
Main.gen.gen_label($statement::label1);
}
s2=statement
{ Main.gen.gen_label($statement::label2); }
)
| ^(WHILE
{ $statement::label1 = Main.gen.gen_label($statement::l...
Main.gen.push_continue($statement::label1);
}
e=expression
{ $statement::label2 = Main.gen.gen_jump(Gen.OP_JUM...
Main.gen.push_break($statement::label2);
}
s=statement
{ Main.gen.gen_jump(Gen.OP_JUMP, $statement::label1...
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.getVariableMod...
| ^(PREFIX i=IDENTIFIER PP)
{ Main.gen.gen(Gen.OP_INC, Main.symtab.getVariableModeA...
| ^(PREFIX i=IDENTIFIER MM)
{ Main.gen.gen(Gen.OP_DEC, Main.symtab.getVariableModeA...
| call
| i=IDENTIFIER
{ Main.gen.gen(Gen.OP_LOAD, Main.symtab.getVariableMode...
| 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); }
)
;
}}
** 例 [#jedb0887]
Main関数は、以下のように定義します。
#pre{{
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 Excepti...
ANTLRInputStream input = new ANTLRInputStream(Sys...
SampleCLexer lexer = new SampleCLexer(input);
CommonTokenStream tokens = new CommonTokenStream(...
SampleCParser parser = new SampleCParser(tokens);
SampleCParser.program_return r = parser.program();
CommonTree t = (CommonTree)r.getTree();
CommonTreeNodeStream nodes = new CommonTreeNodeSt...
Compiler walker = new Compiler(nodes);
walker.program();
}
}
}}
*** テストラン [#ub00547c]
プログラムは、変数や関数のチェックもありませんが、SampleC...
#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);
}
}}
以下のように結果を出力しました（BLOCKを見やすく手で修正し...
#pre{{
(FUNC INT main FUNCPAR PARDEF (BLOCK (EXPR (CALL gcd (ARG...
(FUNC INT gcd (FUNCPAR a b) (PARDEF (VARDEF INT a) (VARDE...
(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
}}
*** 感想 [#fecc8129]
SampleCコンパイラの移植を通じてANTLRとANTLRWorksの完成度...
わずか1日で、SampleCのコンパイラができたことは、驚異のツ...
思います。
** コメント [#b42076b0]
この記事は、
#vote(おもしろかった[28],そうでもない[0],わかりずらい[0])
皆様のご意見、ご希望をお待ちしております。
- インタプリタの作成できづいたEXPRの導入とmain関数呼び出...
- 非常に遅くなりましたが…例を作ってくださってありがとうご...
#comment_kcaptcha
ページ名:
SmartDoc
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
