解释器从抽象语法树的根节点开始遍历该树直至叶节点,并计算各节点的内容
eval方法:eval是evaluate(求值)的缩写。eval方法将计算与该节点为根的子树对应的语句、表达式及子表达式,并返回执行结果。
eval方法递归调用子节点的eval方法
不同类型的节点的类,对eval方法有着不同的定义
public Object eval(Environment env){ Object left = left().eval(env); Object right = right().eval(env); return (Integer)letf + (Integer)right; }
public Object eval(Environment env){ return value(); } // value()将返回该对象表示的整型字面量
类似深度优先树节点搜索算法
package chap6; public interface Environment { void put(String name, Object value); Object get(String name); }
package chap6; import java.util.HashMap; public class BasicEnv implements Environment { protected HashMap<String,Object> values; public BasicEnv() { values = new HashMap<String,Object>(); } public void put(String name, Object value) { values.put(name, value); } public Object get(String name) { return values.get(name); } }
package chap6; import stone.StoneException; import stone.Token; import stone.ast.*; import javassist.gluonj.*; import java.util.List; @Reviser public class BasicEvaluator { public static final int TRUE = 1; public static final int FALSE = 0; @Reviser public static abstract class ASTreeEx extends ASTree { public abstract Object eval(Environment env); } @Reviser public static class ASTListEx extends ASTList { public ASTListEx(List<ASTree> c) { super(c); } public Object eval(Environment env) { throw new StoneException("cannot eval: " + toString(), this); } } @Reviser public static class ASTLeafEx extends ASTLeaf { public ASTLeafEx(Token t) { super(t); } public Object eval(Environment env) { throw new StoneException("cannot eval: " + toString(), this); } } @Reviser public static class NumberEx extends NumberLiteral { public NumberEx(Token t) { super(t); } public Object eval(Environment e) { return value(); } } @Reviser public static class StringEx extends StringLiteral { public StringEx(Token t) { super(t); } public Object eval(Environment e) { return value(); } } @Reviser public static class NameEx extends Name { public NameEx(Token t) { super(t); } public Object eval(Environment env) { Object value = env.get(name()); if (value == null) throw new StoneException("undefined name: " + name(), this); else return value; } } @Reviser public static class NegativeEx extends NegativeExpr { public NegativeEx(List<ASTree> c) { super(c); } public Object eval(Environment env) { Object v = ((ASTreeEx)operand()).eval(env); if (v instanceof Integer) return new Integer(-((Integer)v).intValue()); else throw new StoneException("bad type for -", this); } } @Reviser public static class BinaryEx extends BinaryExpr { public BinaryEx(List<ASTree> c) { super(c); } public Object eval(Environment env) { String op = operator(); if ("=".equals(op)) { Object right = ((ASTreeEx)right()).eval(env); return computeAssign(env, right); } else { Object left = ((ASTreeEx)left()).eval(env); Object right = ((ASTreeEx)right()).eval(env); return computeOp(left, op, right); } } protected Object computeAssign(Environment env, Object rvalue) { ASTree l = left(); if (l instanceof Name) { env.put(((Name)l).name(), rvalue); return rvalue; } else throw new StoneException("bad assignment", this); } protected Object computeOp(Object left, String op, Object right) { if (left instanceof Integer && right instanceof Integer) { return computeNumber((Integer)left, op, (Integer)right); } else if (op.equals("+")) return String.valueOf(left) + String.valueOf(right); else if (op.equals("==")) { if (left == null) return right == null ? TRUE : FALSE; else return left.equals(right) ? TRUE : FALSE; } else throw new StoneException("bad type", this); } protected Object computeNumber(Integer left, String op, Integer right) { int a = left.intValue(); int b = right.intValue(); if (op.equals("+")) return a + b; else if (op.equals("-")) return a - b; else if (op.equals("*")) return a * b; else if (op.equals("/")) return a / b; else if (op.equals("%")) return a % b; else if (op.equals("==")) return a == b ? TRUE : FALSE; else if (op.equals(">")) return a > b ? TRUE : FALSE; else if (op.equals("<")) return a < b ? TRUE : FALSE; else throw new StoneException("bad operator", this); } } @Reviser public static class BlockEx extends BlockStmnt { public BlockEx(List<ASTree> c) { super(c); } public Object eval(Environment env) { Object result = 0; for (ASTree t: this) { if (!(t instanceof NullStmnt)) result = ((ASTreeEx)t).eval(env); } return result; } } @Reviser public static class IfEx extends IfStmnt { public IfEx(List<ASTree> c) { super(c); } public Object eval(Environment env) { Object c = ((ASTreeEx)condition()).eval(env); if (c instanceof Integer && ((Integer)c).intValue() != FALSE) return ((ASTreeEx)thenBlock()).eval(env); else { ASTree b = elseBlock(); if (b == null) return 0; else return ((ASTreeEx)b).eval(env); } } } @Reviser public static class WhileEx extends WhileStmnt { public WhileEx(List<ASTree> c) { super(c); } public Object eval(Environment env) { Object result = 0; for (;;) { Object c = ((ASTreeEx)condition()).eval(env); if (c instanceof Integer && ((Integer)c).intValue() == FALSE) return result; else result = ((ASTreeEx)body()).eval(env); } } } }
在GluonJ中,标有@Reviser的类称为修改器(reviser)。修改器看起来和子类很相似,实则不然,它将直接修改(reviser)所继承的类的定义。
eval方法是Stone语言解释器的核心完成了eval方法的实现之后解释器只要读取程序并调用eval方法,就能执行Stone语言程序。
package chap6; import stone.*; import stone.ast.ASTree; import stone.ast.NullStmnt; public class BasicInterpreter { public static void main(String[] args) throws ParseException { run(new BasicParser(), new BasicEnv()); } public static void run(BasicParser bp, Environment env) throws ParseException { Lexer lexer = new Lexer(new CodeDialog()); while (lexer.peek(0) != Token.EOF) { ASTree t = bp.parse(lexer); if (!(t instanceof NullStmnt)) { Object r = ((BasicEvaluator.ASTreeEx)t).eval(env); System.out.println("=> " + r); } } } }