抽象语法树的执行
前言：在上一篇博客中，我们已经实现了一个计算式的抽象语法树。这一篇博客主要完成计算式的抽象语法树的执行，达到实现一个计算器的目的
0X00 原理讨论
如何执行一个计算式的抽象树？
1+2*3
其实并不难，我们看上面的图片。只看 + 的那个节点。左树只有一个节点值是 1，右树是是另外一颗子树，所以我们要先得到右树的值，才能计算整个树的值。
这是什么？先得到所有子树的值在计算当前节点的值
这就是简单的后序遍历啊！
由于我们已经得到了一整颗抽象语法树，所以实现起来并不是很复杂。只要根据表达式，计算子树就行。
而我们的表达式也只有四种：
- Unary
- Binary
- Group
- Literal
0X01 代码实现
我们先从简单的开始写：
- Literal
这个直接返回表达式的值就好了：
@Override
public Object visitLiteralExpr(Expr.Literal expr) {
return expr.value;
}
- Group
Group 也比较简单，直接返回他的 expression 的值就好了
@Override
public Object visitGroupingExpr(Expr.Grouping expr) {
// 执行表达式
return evaluate(expr.expression);
}
如何得到表达式的值呢？重新 accept 这个表达式：
// 执行表达式
private Object evaluate(Expr expr) {
return expr.accept(this);
}
因为 accept 这个表达式就能重新调用它的访问者的 visit 函数得到这个表达式的值。
- Unary
@Override
public Object visitUnaryExpr(Expr.Unary expr) {
Token operator = expr.operator;
Object right = evaluate(expr.right);
switch (operator.type) {
case MINUS:
checkNumberOperands(operator, right);
return -(double) right;
case BANG:
return !isTruthy(right);
default:
// 不会执行到这里
break;
}
// 不会执行到这里
return null;
}
解释一下怎么获得一元运算的值，首先计算右值，再根据运算符的 type 计算一元运算的值。
当 operator.type == MINUS 时由于 right 值可能不是数字，所以要检查，如果出错就要扔出「运行时错误」
- Binary
最复杂的来了，由于二元运算的 operator.type 的值有很多。所以要列出所有的情况：
@Override
public Object visitBinaryExpr(Expr.Binary expr) {
// 计算左右值
Object left = evaluate(expr.left);
Object right = evaluate(expr.right);
switch (expr.operator.type) {
case GREATER:
checkNumberOperands(expr.operator, left, right);
return (double) left > (double) right;
case GREATER_EQUAL:
checkNumberOperands(expr.operator, left, right);
return (double) left >= (double) right;
case LESS:
checkNumberOperands(expr.operator, left, right);
return (double) left < (double) right;
case LESS_EQUAL:
checkNumberOperands(expr.operator, left, right);
return (double) left <= (double) right;
case MINUS:
checkNumberOperands(expr.operator, left, right);
return (double) left - (double) right;
case SLASH:
checkNumberOperands(expr.operator, left, right);
if ((double) right == 0) {
throw new RuntimeError(expr.operator, "divide zero");
}
return (double) left / (double) right;
case STAR:
checkNumberOperands(expr.operator, left, right);
return (double) left * (double) right;
case BANG_EQUAL:
return !isEqual(left, right);
case EQUAL_EQUAL:
return isEqual(left, right);
case PLUS:
if (left instanceof Double && right instanceof Double) {
return (double) left + (double) right;
}
if (left instanceof String && right instanceof String) {
return (String) left + (String) right;
}
throw new RuntimeError(expr.operator, "Operands must be two numbers or two strings.");
default:
break;
}
// Unreachable.
return null;
}
跟之前一样，要检查左右值。
但是对于加法来说，我们对 + 号进行了重载，导致我们可以实现 string 的加法。
还有如果是 == 或者 != 有一个函数：isEqual() 来判断两者是否相等，具体如何判断，看我后面分析。
对于真假的判定
在我们的语言中我们规定：
null、数字 0、关键字 False 为假，其他全部为真
所以：
private boolean isTruthy(Object obj) {
/**
* 什么时候是假：null、数字 0、语言本身记录真假 除此之外全为真
*/
if (obj == null) {
return false;
}
// 由于 obj 是数字是全部由 Double 代替
if (obj instanceof Double) {
double value = (double) obj;
return (value != 0);
}
if (obj instanceof Boolean)
return (boolean) obj;
return true;
}
判断相等
由于我们是在 Java 之上封装的语言，所以可以依靠 Java 对象中的 equal 函数判读对象是否相等：
private boolean isEqual(Object a, Object b) {
/**
* 当两者都为 null 的时候相等 调用 object equal 会调用子类重写的方法 equal
*/
if (a == null && b == null) {
return true;
}
if (a == null) {
return false;
}
return a.equals(b);
}
运行中出错
除了检查静态语言中的语法，我们还要动态的检查语法，比如有些操作数只能是数字，不能是字符串、通过计算计算算出要除以 0 等等。
所以我们要在必要的时候检查错误。
而且不能让 Java 报错，让语言使用者看出来。
因此我们定义了：
class RuntimeError extends RuntimeException {
final Token token;
RuntimeError(Token token, String message) {
super(message);
this.token = token;
}
}
用来处理「运行中出错」。
。。。
就这样我们实现了一个计算器。。。
