使用C#编写一个真正的解释器——基于AST。

Question

我知道有其他关于编译器/解释器技术的问题以及非常好的代码可以学习，例如IronPython和Jurassic。

对我来说，从源代码构建AST（抽象语法树）并编写自上而下的解析器（目前我更喜欢编写而不是使用代码生成工具）是很清楚的。

大多数我正在尝试学习的源都在作为解释器使用时，使用Reflection.Emit之类的API动态编译程序。

现在我想知道构建一个真正的解释器的最佳实践，它不会将源代码编译为.NET VM。

一旦我获得了AST，如何执行代码？我应该使用解释器或访问者设计模式吗？还是做一些不同的事情？什么是最佳或规范的方式？

我知道已经有一个类似的问题，但如果可能的话，我更喜欢更多关于.NET/C#实现的信息。

问候，Giacomo

- gsscoder

---

最佳实践是将编译与解释相结合。AST通常不太适合高效的解释，因此将其降低到一些更简单的表示形式，扩展所有语法糖，在可能的情况下解析标识符（如果您有词法作用域）。只有在这样做之后，您才能开始解释。 下面的“解释器”模式是一个很好的起点，尽管有许多有趣的优化。请参考SISC以获取灵感。 - SK-logic

Answer 1

我应该使用解释器还是访问者设计模式？

我认为名称已经给出了提示;-)

对于AST的通用操作，访问者非常好用，但是对于执行/解释单个功能，你只需要一个方法，因此需要使用解释器模式。

以下是一个非常简单的示例（即使是复杂的解释器，也不会比这更复杂）：

// Holds function scope etc.
class Context {}

abstract class Node {
    public abstract object Execute(Context ctx);
}

class Number : Node {
    private readonly int x;

    public Number(int x) { this.x = x; }

    public override object Execute(Context ctx) { return x; }
}

class Addition : Node {
    private readonly Node left, right;

    public Addition(Node left, Node right) {
        this.left = left;
        this.right = right;
    }

    public override object Execute(Context ctx) {
        // Verification omitted: do the nested expressions evaluate to a number?
        return (int) left.Execute(ctx) + (int) right.Execute(ctx);
    }
}

…就是这样。一个简单的解释器，它知道如何进行加法运算。以下是一个使用示例：

var ast = new Addition(new Number(23), new Number(42));
Console.WriteLine("Result = {0}", ast.Execute(new Context()));

- Konrad Rudolph

---

@gsscoder，正确，你基本上是在Execute方法中实现结构（在for循环的情况下，通过拥有一个for循环；在if语句的情况下，通过拥有一个if语句 - 以此类推）。 - Konrad Rudolph

刚开始...我的新表达式求值器：https://github.com/gsscoder/exprengine :D - gsscoder

@JohnNyingi 谢谢。实际上，这段代码只是一个我没有测试过的快速而简单的示例。我现在已经修复了错误。 - Konrad Rudolph

帮我理解Context类的作用。 - John Nyingi

@JohnNyingi 简短的答案在 Context 类之前的注释中给出；不幸的是，长答案无法放在注释中。它基本上包含了解释器所需的一切，但这些内容并未包含在 AST 中，例如作用域（即变量名到值的映射）等。在上面的简单答案中，显然没有使用。 - Konrad Rudolph