前言：在上一篇博客中，我們已經(jīng)實現(xiàn)了一個計算式的抽象語法樹。這一篇博客主要完成計算式的抽象語法樹的執(zhí)行，達到實現(xiàn)一個計算器的目的
0X00 原理討論
如何執(zhí)行一個計算式的抽象樹？
其實并不難，我們看上面的圖片。只看 + 的那個節(jié)點。左樹只有一個節(jié)點值是 1，右樹是是另外一顆子樹，所以我們要先得到右樹的值，才能計算整個樹的值。
這是什么？先得到所有子樹的值在計算當前節(jié)點的值
這就是簡單的后序遍歷?。?/p>
由于我們已經(jīng)得到了一整顆抽象語法樹，所以實現(xiàn)起來并不是很復(fù)雜。只要根據(jù)表達式，計算子樹就行。
而我們的表達式也只有四種：
- Unary
- Binary
- Group
- Literal
0X01 代碼實現(xiàn)
我們先從簡單的開始寫：
- Literal
這個直接返回表達式的值就好了：
@Override
public Object visitLiteralExpr(Expr.Literal expr) {
return expr.value;
}
- Group
Group 也比較簡單，直接返回他的 expression 的值就好了
@Override
public Object visitGroupingExpr(Expr.Grouping expr) {
// 執(zhí)行表達式
return evaluate(expr.expression);
}
如何得到表達式的值呢？重新 accept 這個表達式：
// 執(zhí)行表達式
private Object evaluate(Expr expr) {
return expr.accept(this);
}
因為 accept 這個表達式就能重新調(diào)用它的訪問者的 visit 函數(shù)得到這個表達式的值。
- 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:
// 不會執(zhí)行到這里
break;
}
// 不會執(zhí)行到這里
return null;
}
解釋一下怎么獲得一元運算的值，首先計算右值，再根據(jù)運算符的 type 計算一元運算的值。
當 operator.type == MINUS 時由于 right 值可能不是數(shù)字，所以要檢查，如果出錯就要扔出「運行時錯誤」
- Binary
最復(fù)雜的來了，由于二元運算的 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;
}
跟之前一樣，要檢查左右值。
但是對于加法來說，我們對 + 號進行了重載，導(dǎo)致我們可以實現(xiàn) string 的加法。
還有如果是 == 或者 != 有一個函數(shù)：isEqual() 來判斷兩者是否相等，具體如何判斷，看我后面分析。
對于真假的判定
在我們的語言中我們規(guī)定：
null、數(shù)字 0、關(guān)鍵字 False 為假，其他全部為真
所以：
private boolean isTruthy(Object obj) {
/**
* 什么時候是假：null、數(shù)字 0、語言本身記錄真假 除此之外全為真
*/
if (obj == null) {
return false;
}
// 由于 obj 是數(shù)字是全部由 Double 代替
if (obj instanceof Double) {
double value = (double) obj;
return (value != 0);
}
if (obj instanceof Boolean)
return (boolean) obj;
return true;
}
判斷相等
由于我們是在 Java 之上封裝的語言，所以可以依靠 Java 對象中的 equal 函數(shù)判讀對象是否相等：
private boolean isEqual(Object a, Object b) {
/**
* 當兩者都為 null 的時候相等 調(diào)用 object equal 會調(diào)用子類重寫的方法 equal
*/
if (a == null && b == null) {
return true;
}
if (a == null) {
return false;
}
return a.equals(b);
}
運行中出錯
除了檢查靜態(tài)語言中的語法，我們還要動態(tài)的檢查語法，比如有些操作數(shù)只能是數(shù)字，不能是字符串、通過計算計算算出要除以 0 等等。
所以我們要在必要的時候檢查錯誤。
而且不能讓 Java 報錯，讓語言使用者看出來。
因此我們定義了：
class RuntimeError extends RuntimeException {
final Token token;
RuntimeError(Token token, String message) {
super(message);
this.token = token;
}
}
用來處理「運行中出錯」。
。。。
就這樣我們實現(xiàn)了一個計算器。。。
