FrontPage

2008/07/07からのアクセス回数 6179

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

SampleC構文解析

SampleCは、Cのサブセットで

  • 型はintのスカラーのみ
  • フロー制御は、if文、while文のみ をサポートしています。

最初に、sample.yをベースに以下の処理をします。

  • 左再帰をEBNFに変更
  • 優先順位を明示的に記述
  • エラー処理を外す

生成する構文木の形

入力として以下のデータを入力すると

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ノードを持つツリーが作成されます。

func_tree.jpg

1個目のFUNCノードは、

func_tree1.jpg

2個目のFUNCノードは、

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

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;
        }
}

各変数は、次のようにメモリに割り当てられます。

variable_region.jpg

実際に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を作成します。

  • 関数を管理するfunctions
  • 変数は、リストscopesを使って関数呼び出し、複合文に合わせてパラメータ、ローカル変数マップを管理
  • scopesの0番目には広域変数を管理するglobalsマップがあり、1番目には関数のパラメータを管理する paramsマップがあります。
  • 変数名をscopesの最後から順に検索し、メモリ割り当て領域を求めます。

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のコンパイラができたことは、驚異のツールと言って過言ではないと 思います。

コメント

この記事は、

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

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

  • インタプリタの作成できづいたEXPRの導入とmain関数呼び出しを追加 -- 竹本 浩? 2008-07-11 (金) 11:11:06
  • 非常に遅くなりましたが…例を作ってくださってありがとうございます。参考にさせていただきます。 -- kappa? 2010-08-27 (金) 16:14:04

(Input image string)


添付ファイル: filefunc_tree.jpg 812件 [詳細] filevariable_region.jpg 618件 [詳細] filefunc_tree2.jpg 697件 [詳細] filefunc_tree1.jpg 621件 [詳細]

トップ   編集 凍結解除 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2015-07-06 (月) 20:45:14 (628d)
SmartDoc