crafting a real interpreter using c# from AST

I know that there are other question about compiler/interpreter technology and also very good code to study like IronPython to Jurassic. To me is quite clear how to build an AST (Abstract Syntax Tree) from source, writing a top-descent parser (for the moment I prefer writing than using code-generation tool).

Most sources I'm trying to study when used as interpreters compile the program on fly using API like Reflection.Emit. Now I'd like to know best practices to build a real interpreter that doesn't compile to .NET VM the source.

Once I got the AST how can I execute the code? Should I use interpreter or visitor design patterns? Or doing something different? What's the best or canonical way?

I know that there's already a question like this but I like more information and more specific to a .NET/C# implementation, if possible.

Regards, Giacomo

Solution

Should I use interpreter or visitor design patterns?

I think the names give a hint ;-)

Visitors are good for general operations on ASTs but for performing a singular function (execution / interpretation) you just need one method, hence the interpreter pattern.

Here’s a very simple example (but it really doesn’t get much more complicated than that, even for complex interpreters):

// 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);
    }
}

… and there you have it. A simple interpreter that knows addition. And here’s an example of usage:

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