用 C# 开发一个解释器语言——基于《Crafting Interpreters》的实战系列（三）表达式求值

表达式求值

在之前的文章中，我们已经实现了词法分析器（Scanner）和表达式解析器（Parser），成功将源代码字符串转换成了抽象语法树（AST）。但这只是第一步——我们得到了一颗"结构化的树"，但它还不会"动"。

表达式求值（Expression Evaluation）就是让这颗树"活"起来，真正计算出表达式的结果。这是解释器的核心功能之一。

什么是表达式求值？

表达式求值的过程可以简单理解为：

源代码 "1 + 2 * 3"
    ↓ Scanner (词法分析)
Token 序列 [NUMBER(1), PLUS, NUMBER(2), STAR, NUMBER(3)]
    ↓ Parser (语法分析)
AST 结构 Binary(+, Literal(1), Binary(*, Literal(2), Literal(3)))
    ↓ Interpreter (求值) ← 我们这次要实现的部分
最终结果 7

解释器会遍历 AST，根据每个节点的类型执行相应的操作，最终计算出结果。

访问者模式（Visitor Pattern）

在实现表达式求值之前，我们需要理解一个重要的设计模式——访问者模式。

为什么需要访问者模式？

AST 中的节点类型有很多种（Binary、Grouping、Literal、Unary），我们需要针对每种节点执行不同的求值逻辑。如果使用传统的继承方式，会带来两个问题：

1. 添加新操作困难：如果以后想添加"类型检查"、"代码优化"等新功能，需要修改每个节点类
2. 逻辑分散：相关逻辑分散在不同的类中，难以维护

访问者模式解决了这些问题：将数据结构（AST 节点）与操作（求值逻辑）分离。

访问者模式的核心思想

// 每个节点类都实现 Accept 方法
public abstract class Expr
{
    public abstract T Accept<T>(Visitor<T> visitor);
}

public class Binary : Expr
{
    public override T Accept<T>(Visitor<T> visitor)
    {
        return visitor.VisitBinaryExpr(this);  // 双重分发
    }
}

// 访问者接口定义了针对每种节点的操作
public interface Visitor<T>
{
    T VisitBinaryExpr(Binary expr);
    T VisitGroupingExpr(Grouping expr);
    T VisitLiteralExpr(Literal expr);
    T VisitUnaryExpr(Unary expr);
}

// 解释器实现了访问者接口
public class Interpreter : Expr.Visitor<object>
{
    public object VisitBinaryExpr(Binary expr) { /* 求值逻辑 */ }
    public object VisitGroupingExpr(Grouping expr) { /* 求值逻辑 */ }
    public object VisitLiteralExpr(Literal expr) { /* 求值逻辑 */ }
    public object VisitUnaryExpr(Unary expr) { /* 求值逻辑 */ }
}

关键点：

• 每个节点调用 Accept(visitor)，将自己"传给"访问者
• 访问者调用对应的 VisitXxxExpr(node) 方法，执行具体操作
• 这就是双重分发（Double Dispatch）

运行时错误处理

在求值过程中，可能会发生运行时错误（比如对字符串使用减法运算符）。我们需要定义专门的异常类型：

/// <summary>
/// 运行时错误异常
/// 在表达式求值过程中抛出
/// </summary>
public class RuntimeError : Exception
{
    public Token Token { get; }

    public RuntimeError(Token token, string message) : base(message)
    {
        Token = token;
    }
}

与语法错误不同，运行时错误需要携带发生错误的 Token，以便显示错误位置。

我们在 ErrorReporter 中添加运行时错误处理方法：

public static void RuntimeError(RuntimeError error)
{
    Console.Error.WriteLine($"{error.Message}\n[line {error.Token.Line}]");
    HadError = true;
}

解释器实现

1. 解释器基本结构

/// <summary>
/// 表达式解释器
/// 实现访问者模式，遍历 AST 并计算表达式值
/// </summary>
public class Interpreter : Expr.Visitor<object>
{
    /// <summary>
    /// 解释表达式的入口方法
    /// </summary>
    public object Interpret(Expr expression)
    {
        try
        {
            return expression.Accept(this);
        }
        catch (RuntimeError error)
        {
            ErrorReporter.RuntimeError(error);
            return null;
        }
    }
}

2. 字面量求值

最简单的节点类型，直接返回字面量的值：

public object VisitLiteralExpr(Expr.Literal expr)
{
    return expr.Value;
}

3. 分组表达式求值

括号表达式的求值，只需递归求值内部表达式：

public object VisitGroupingExpr(Expr.Grouping expr)
{
    return Evaluate(expr.Expression);
}

private object Evaluate(Expr expr)
{
    return expr.Accept(this);
}

4. 一元表达式求值

一元运算符有两种：

• ! (逻辑非)：对操作数求布尔值后取反
• - (负号)：对数值取负

public object VisitUnaryExpr(Expr.Unary expr)
{
    object right = Evaluate(expr.Right);

    switch (expr.Operator.Type)
    {
        case TokenType.BANG:
            return !IsTruthy(right);
        case TokenType.MINUS:
            CheckNumberOperand(expr.Operator, right);
            return -(double)right;
    }

    return null;
}

类型检查是关键：

private void CheckNumberOperand(Token op, object operand)
{
    if (operand is double) return;
    throw new RuntimeError(op, "Operand must be a number.");
}

如果操作数不是数字，抛出运行时错误。

5. 二元表达式求值

这是最复杂的部分，需要处理多种运算：

5.1 算术运算

case TokenType.MINUS:
    CheckNumberOperands(expr.Operator, left, right);
    return (double)left - (double)right;

case TokenType.SLASH:
    CheckNumberOperands(expr.Operator, left, right);
    return (double)left / (double)right;

case TokenType.STAR:
    CheckNumberOperands(expr.Operator, left, right);
    return (double)left * (double)right;

5.2 加法运算（支持数字和字符串）

case TokenType.PLUS:
    if (left is double leftNum && right is double rightNum)
    {
        return leftNum + rightNum;
    }
    if (left is string leftStr || right is string rightStr)
    {
        return Stringify(left) + Stringify(right);
    }
    throw new RuntimeError(expr.Operator,
        "Operands must be two numbers or two strings.");

5.3 比较运算

case TokenType.GREATER:
    CheckNumberOperands(expr.Operator, left, right);
    return (double)left > (double)right;

case TokenType.GREATER_EQUAL:
    CheckNumberOperands(expr.Operator, left, right);
    return (double)left >= (double)right;
// ... LESS, LESS_EQUAL 类似

5.4 相等性比较

case TokenType.BANG_EQUAL:
    return !IsEqual(left, right);

case TokenType.EQUAL_EQUAL:
    return IsEqual(left, right);

IsEqual 方法处理各种类型的比较：

private bool IsEqual(object a, object b)
{
    if (a == null && b == null) return true;
    if (a == null) return false;
    return a.Equals(b);
}

6. 真值判断

Lox 语言中，只有 false 和 nil 是假值，其他都是真值：

private bool IsTruthy(object value)
{
    if (value == null) return false;
    if (value is bool b) return b;
    return true;
}

这意味着 0、""（空字符串）都是真值，与 JavaScript 不同。

7. 结果字符串化

为了正确显示结果，我们需要将 C# 对象转换为 Lox 风格的字符串：

private string Stringify(object value)
{
    if (value == null) return "nil";

    if (value is double d)
    {
        // 处理小数部分为整数的情况
        if (d == (int)d)
        {
            return d.ToString("F0");
        }
        return d.ToString();
    }

    return value.ToString();
}

这样 123.0 会显示为 123，123.5 显示为 123.5。

测试示例

我们编写一个测试方法，验证各种表达式的求值：

static void TestInterpreter()
{
    string[] testCases = {
        "1 + 2",                    // 简单加法: 3
        "1 + 2 * 3",                // 运算优先级: 7
        "(1 + 2) * 3",              // 括号: 9
        "-123",                     // 负数: -123
        "!true",                    // 逻辑非: false
        "5 > 3",                    // 大于: true
        "5 < 3",                    // 小于: false
        "1 == 1",                   // 相等: true
        "1 == 2",                   // 不等: false
        "\"hello\" + \" world\"",   // 字符串连接: "hello world"
        "nil == nil"                // nil 比较: true
    };

    foreach (string source in testCases)
    {
        Scanner scanner = new Scanner(source);
        List<Token> tokens = scanner.ScanTokens();
        Parser parser = new Parser(tokens);
        Expr expression = parser.Parse();
        Interpreter interpreter = new Interpreter();
        object result = interpreter.Interpret(expression);
        Console.WriteLine($"{source} => {StringifyResult(result)}");
    }
}

运行结果：

表达式: 1 + 2
结果: 3

表达式: 1 + 2 * 3
结果: 7

表达式: (1 + 2) * 3
结果: 9

表达式: -123
结果: -123

表达式: !true
结果: False

表达式: 5 > 3
结果: True

表达式: 5 < 3
结果: False

表达式: 1 == 1
结果: True

表达式: 1 == 2
结果: False

表达式: "hello" + " world"
结果: hello world

表达式: nil == nil
结果: True

核心知识点总结

1. 访问者模式的优势

• 分离关注点：AST 结构定义与操作逻辑解耦
• 易于扩展：添加新操作只需新建访问者类，无需修改节点类
• 代码集中：相关逻辑集中在一个类中，便于维护

2. 动态类型处理

C# 是静态类型语言，但解释器需要处理动态类型：

// 使用 is 模式匹配检查类型
if (left is double leftNum && right is double rightNum)

// 使用 as 或显式转换进行类型转换
return -(double)right;

3. 错误处理策略

• 语法错误：在 Parser 中检测，使用 ParseError 异常
• 运行时错误：在 Interpreter 中检测，使用 RuntimeError 异常
• 类型检查：在运算前检查操作数类型，不符合则抛出错误

4. 递归求值

表达式求值本质上是递归过程：

// 求值二元表达式
object left = Evaluate(expr.Left);   // 递归求值左操作数
object right = Evaluate(expr.Right); // 递归求值右操作数
return 运算结果;

项目进度

• ✅ 词法分析器（Scanner）- 将源码拆解为 Token
• ✅ 抽象语法树（Expr）- 定义表达式节点结构
• ✅ 表达式解析器（Parser）- 将 Token 序列转换为 AST
• ✅ 表达式求值（Interpreter）- 遍历 AST 并计算结果 ← 本次完成
• ⏳ 语句解析（Statements）- var、if、while 等语句
• ⏳ 语句执行（Statement Execution）- 执行语句
• ⏳ 环境管理（Environment）- 变量作用域

下一步计划

现在我们已经实现了完整的表达式求值功能，可以计算各种算术、比较和逻辑表达式的值。下一步我们将实现语句解析和执行，包括：

• 变量声明语句（var x = 1;）
• 打印语句（print x;）
• 条件语句（if ... else）
• 循环语句（while）

这样我们的解释器就能执行完整的程序，而不仅仅是单个表达式了！

参考资料

• 《Crafting Interpreters》第 6 章: Evaluating Expressions
• https://craftinginterpreters.com/evaluating-expressions.html

---