- 追加された行はこの色です。
- 削除された行はこの色です。
#freeze
[[FrontPage]]
2008/07/11からのアクセス回数 &counter;
#contents
SampleCのコンパイラでは、コンパイルされたプログラムの動作をすぐに確認できません。
そこで、生成された構文木をたどって逐次処理を行うインタプリタを作成します。
ANTLRのサンプルページにあるC--のinterpreter
http://www.antlr.org/share/1178224532340/cminus.zip
を参考に実装しました。
** メモリ管理の変更と追加 [#x705820c]
インタプリタでは、関数の本体（blockノード）を使って関数呼び出しを行うため、
SymbolTableのFunctionクラスにparmList, blockNodeを追加し、以下のように変更しました。
#pre{{
class Function {
public String name;
public String returnType;
public List parmList;
public CommonTree blockNode;
public Function(String name, String returnType) {
this(name, returnType, new ArrayList(), null);
}
public Function(String name, String returnType, List parmList, CommonTree blockNode) {
this.name = name;
this.returnType = returnType;
this.parmList = parmList;
this.blockNode = blockNode;
}
}
}}
次に、SymbolTableの
- declareFunction: parmList, blockNodeも登録
- getFunctionParmList: 関数の引数名リストを取得
- getFunctionBlock: 関数のblockノードを取得
- setValue: 変数に値をセット
- getValue: 変数の値を取得
を追加しました。
#pre{{
public void declareFunction(String name, String returnType, List parmList, CommonTree blockNode) {
functions.put(name, new Function(name, returnType, parmList, blockNode));
}
public List getFunctionParmList(String name) {
Function f = (Function)functions.get(name);
return (f != null ? f.parmList : new ArrayList());
}
public CommonTree getFunctionBlock(String name) {
Function f = (Function)functions.get(name);
return (f != null ? f.blockNode : null);
}
public void setValue(String name, int value) {
String key = getVariableModeAndOffset(name);
values.put(key, new Integer(value));
}
public int getValue(String name) {
String key = getVariableModeAndOffset(name);
Integer value = (Integer)values.get(key);
return (value.intValue());
}
}}
** 関数管理 [#s5389cf4]
構文解析木から関数の情報を登録するために、FunctionID.gを作成します。
programの定義を
: ^(PROGRAM definition+ . ) EOF
のようにdefinition+の後にピリオド.を使うことで、任意のノードにマッチすることを表します。
これによって不要な部分（関数本体）の定義を省略できます。
FunctionID.gは以下のようになります。
#pre{{
tree grammar FunctionID;
options{
tokenVocab = SampleC;
ASTLabelType = CommonTree;
}
@header{
import java.util.ArrayList;
import java.util.List;
}
program
: ^(PROGRAM definition+
. // call
) EOF
;
definition
: functionDefintion
| ^(VARDEF INT i=IDENTIFIER)
;
functionDefintion
scope {
String label;
}
@after{
CommonTree blockNode = (CommonTree)$functionDefintion.start.getChild(4);
Engine.symtab.declareFunction($i.text, "int", $p.parmList, blockNode);
}
: ^(FUNC INT i=IDENTIFIER ^(FUNCPAR p=parameterList)
. // parameterDeclarations
. // block
)
;
parameterList returns[List parmList]
@init{
parmList = new ArrayList();
}
: ( i=IDENTIFIER
{parmList.add($i.text);}
)*
;
}}
** SampleC.gの変更 [#af7d375e]
インタプリタでは、すぐに動作するためにどこかでmain関数を呼び出してやらなければ
なりません。
そこで、SampleC.gで呼び出し分を追加することにしました。
#pre{{
program
: (
d=definition
{ if ($d.tree != null) System.out.println($d.tree.toStringTree());}
)+
-> ^(PROGRAM definition+ ^(CALL {adaptor.create(IDENTIFIER,"main")} ^(ARG)))
}}
adaptor.createメソッドでmainという値のIDENTIFIERノードを追加しています。
^(CALL IDENTIFIER ^(ARG))
がmain関数の呼び出しを表します。
** インタプリタの定義 [#k3f7d862]
インタプリタでは、関数定義は必要ないので、
#pre{{
functionDefintion
: ^(FUNC INT i=IDENTIFIER .*)
;
}}
と省略しています。
動作の進捗が分かるようにstatement定義に
#pre{{
statement
@init{
try{
if((! $call::can_run) || $whileStmt::breaked || $whileStmt::continued){
matchAny(input);
return null;
}
}catch(java.util.EmptyStackException ignore){}
CommonTree node=(CommonTree)$statement.start;
System.out.println(node.toStringTree());
}
}}
としています。ここでcan_runは、途中でのreturn文によってその後の式を評価しないようにするため
、$whileStmt::breaked、$whileStmt::continuedは、WHILE文のbreak, continue処理に使用します。
変数のセットに
#pre{{
| ^(ASSIGN i=IDENTIFIER e=expression)
{ Engine.symtab.setValue($i.text, $e.value);
$value = $e.value;
System.out.println("set " + $i.text + "=" + $e.value);
}
}}
関数呼び出しに
#pre{{
System.out.println("enter " + $i.text);
... 途中省略
System.out.println("arg " + parm + "=" + $e.value);
... 途中省略
System.out.println("exit " + $i.text + " return=" + $value);
}}
のチェックプリントをいれました。
構文木の解析順序を変更するには、streamに対して
#pre{{
stream.push(stream.getNodeIndex(blockNode));
compoundStatement();
stream.pop();
}}
のようにノードのpush後に、解析したいメソッドをコールし、popします。
Interpreter.gは、以下のようになります。
#pre{{
tree grammar Interpreter;
options{
tokenVocab = SampleC;
ASTLabelType = CommonTree;
}
@header{
import java.util.List;
import java.util.ArrayList;
}
@members{
CommonTreeNodeStream stream = (CommonTreeNodeStream)input;
}
program
: ^(PROGRAM definition+ call) EOF
;
definition
: functionDefintion
| ^(VARDEF INT i=IDENTIFIER)
;
functionDefintion
: ^(FUNC INT i=IDENTIFIER .*)
;
compoundStatement
@init{
Engine.symtab.enterBlock();
}
@after{
Engine.symtab.exitBlock();
}
: ^(BLOCK declarations statements)
;
declarations
: declaration*
;
declaration
: ^(VARDEF INT i=IDENTIFIER
{ Engine.symtab.declareLocalVariable($i.text, "int"); }
)
;
statements
: statement*
;
statement
@init{
try{
if((! $call::can_run) || $whileStmt::breaked || $whileStmt::continued){
matchAny(input);
return null;
}
}catch(java.util.EmptyStackException ignore){}
CommonTree node=(CommonTree)$statement.start;
System.out.println(node.toStringTree());
}
: expression
| ^(EXPR expression CLEAR)
| NOP
| CLEAR
| BREAK
{ $whileStmt::breaked = true; }
| CONTINUE
{ $whileStmt::continued = true; }
| RETURN
{ $call::can_run = false; }
| ^(RETURN e=expression)
{ $call::return_val = $e.value;
$call::can_run = false;
}
| c=compoundStatement
| ifStmt
| whileStmt
;
whileStmt
scope{
Boolean breaked;
Boolean continued;
}
@after{
CommonTree stmtNode=(CommonTree)$whileStmt.start.getChild(1);
CommonTree exprNode=(CommonTree)$whileStmt.start.getChild(0);
int test;
$whileStmt::breaked=false;
$whileStmt::continued=false;
while($whileStmt::breaked==false){
stream.push(stream.getNodeIndex(exprNode));
test=expression().value;
stream.pop();
if (test==0) break;
stream.push(stream.getNodeIndex(stmtNode));
statement();
stream.pop();
}
}
: ^(WHILE . .)
;
ifStmt
@after{
CommonTree stmtNode;
if ($v.value!=0){
stmtNode = (CommonTree)$ifStmt.start.getChild(1);
}else{
stmtNode = (CommonTree)$ifStmt.start.getChild(2);
}
stream.push(stream.getNodeIndex(stmtNode));
statement();
stream.pop();
}
: ^(IF v=expression . .)
;
expression returns [int value]
@init {
CommonTree node=(CommonTree)$expression.start;
// System.out.println(node.toStringTree());
}
: ^(ALU_EQ e1=expression e2=expression)
{ $value = ($e1.value == $e2.value)? 1 : 0; }
| ^(ALU_NE e1=expression e2=expression)
{ $value = ($e1.value != $e2.value)? 1 : 0; }
| ^(ALU_GT e1=expression e2=expression)
{ $value = ($e1.value > $e2.value)? 1 : 0; }
| ^(ALU_LT e1=expression e2=expression)
{ $value = ($e1.value < $e2.value)? 1 : 0; }
| ^(ALU_LE e1=expression e2=expression)
{ $value = ($e1.value <= $e2.value)? 1 : 0; }
| ^(ALU_GE e1=expression e2=expression)
{ $value = ($e1.value >= $e2.value)? 1 : 0; }
| ^(ALU_ADD e1=expression e2=expression)
{ $value = $e1.value + $e2.value; }
| ^(ALU_SUB e1=expression e2=expression)
{ $value = $e1.value - $e2.value; }
| ^(ALU_MUL e1=expression e2=expression)
{ $value = $e1.value * $e2.value; }
| ^(ALU_DIV e1=expression e2=expression)
{ $value = $e1.value / $e2.value; }
| ^(ALU_AND e1=expression e2=expression)
{ $value = $e1.value & $e2.value; }
| ^(ALU_OR e1=expression e2=expression)
{ $value = $e1.value | $e2.value; }
| ^(ALU_XOR e1=expression e2=expression)
{ $value = $e1.value ^ $e2.value; }
| ^(NOT e1=expression)
{ $value = ($e1.value!=0)? 0 : 1; }
| ^(NEGATE e1=expression)
{ $value = -$e1.value; }
| ^(ASSIGN i=IDENTIFIER e=expression)
{ Engine.symtab.setValue($i.text, $e.value);
$value = $e.value;
System.out.println("set " + $i.text + "=" + $e.value);
}
| ^(PREFIX i=IDENTIFIER PP)
{ int v = Engine.symtab.getValue($i.text);
Engine.symtab.setValue($i.text, ++v);
$value = v;
}
| ^(PREFIX i=IDENTIFIER MM)
{ int v = Engine.symtab.getValue($i.text);
Engine.symtab.setValue($i.text, --v);
$value = v;
}
| call
| i=IDENTIFIER
{ $value = Engine.symtab.getValue($i.text); }
| c=CONSTANT
{ $value = Integer.parseInt($c.text); }
;
call returns [int value]
scope{
int return_val;
Boolean can_run;
}
@init {
int argCnt=0;
List parmList;
String parm;
CommonTree blockNode;
$call::can_run=true;
}
: ^(CALL i=IDENTIFIER
{ argCnt = 0;
parmList = Engine.symtab.getFunctionParmList($i.text);
blockNode = Engine.symtab.getFunctionBlock($i.text);
Engine.symtab.enterFunction($i.text);
System.out.println("enter " + $i.text);
}
^(ARG (e=expression
{ parm = (String)parmList.get(argCnt++);
Engine.symtab.declareParameter(parm, "int");
Engine.symtab.setValue(parm, $e.value);
System.out.println("arg " + parm + "=" + $e.value);
}
)*)
{ stream.push(stream.getNodeIndex(blockNode));
compoundStatement();
stream.pop();
$value = $call::return_val;
Engine.symtab.exitFunction();
System.out.println("exit " + $i.text + " return=" + $value);
}
)
;
}}
** テスト [#ufca8cd4]
インタプリタに以下の入力を与えると、
#pre{{
main()
{ int a,b;
a = 36;
b = 54;
while( a != b)
if (a > b)
a -= b;
else
b -= a;
}
}}
最初に関数の構文木が表示されます。（みやすいように手で加工）
#pre{{
(FUNC INT main FUNCPAR PARDEF
(BLOCK (VARDEF INT a) (VARDEF INT b)
(EXPR (ASSIGN a 36) CLEAR)
(EXPR (ASSIGN b 54) CLEAR)
(WHILE (ALU_NE a b)
(IF (ALU_GT a b)
(EXPR (ASSIGN a (ALU_SUB a b)) CLEAR)
(EXPR (ASSIGN b (ALU_SUB b a)) CLEAR)))))
}}
その後、処理した文のノードと変数セット、関数呼び出しのチェックプリントが順次
出力されます。
これで、インタプリタが正常に動作することが確認できました！
#pre{{
enter main
(EXPR (ASSIGN a 36) CLEAR)
set a=36
(EXPR (ASSIGN b 54) CLEAR)
set b=54
(WHILE (ALU_NE a b) (IF (ALU_GT a b) (EXPR (ASSIGN a (ALU_SUB a b)) CLEAR) (EXPR (ASSIGN b (ALU_SUB b a)) CLEAR)))
(IF (ALU_GT a b) (EXPR (ASSIGN a (ALU_SUB a b)) CLEAR) (EXPR (ASSIGN b (ALU_SUB b a)) CLEAR))
(EXPR (ASSIGN b (ALU_SUB b a)) CLEAR)
set b=18
(IF (ALU_GT a b) (EXPR (ASSIGN a (ALU_SUB a b)) CLEAR) (EXPR (ASSIGN b (ALU_SUB b a)) CLEAR))
(EXPR (ASSIGN a (ALU_SUB a b)) CLEAR)
set a=18
exit main return=0
}}
** ソース [#h3793a37]
完全なソースは、
#ref(SymbolTable.java);
#ref(SampleC.g);
#ref(FunctionID.g);
#ref(Interpreter.g);
#ref(Engine.java);
にあります。
** コメント [#ndc934f1]
この記事は、
#vote(おもしろかった[6],そうでもない[0],わかりずらい[0])
#vote(おもしろかった[10],そうでもない[0],わかりずらい[0])
皆様のご意見、ご希望をお待ちしております。
#comment_kcaptcha
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
