crafting a real interpreter using c# from AST

Question

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

Best practice is to combine compilation with interpretation. AST is normally not very suitable for an efficient interpretation, so it makes sense to lower it down to some simpler representation, expand all the syntax sugar, resolve identifiers where possible (if you've got lexical scoping). Then and only then you can start interpreting. An "interpreter" patter in the answer below is a good starting point, although there are many interesting optimisations. See SISC for inspiration. — SK-logic, Dec 22 '12 at 06:37

Konrad Rudolph · Accepted Answer · 2021-08-28T08:28:14.140

5

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()));

edited Aug 28 '21 at 08:28

answered Dec 21 '12 at 11:15

Konrad Rudolph

530,221
131
937
1,214

+1 thank for fast and clear response! just one more thing... when overriding a node that represents structural code like a for clause, I should perform a for cycle and execute all child nodes or there's a better way for implementing structural nodes? thanks again – gsscoder Dec 21 '12 at 11:20
2

@gsscoder Exactly, you basically implement the structure within the `Execute` method (in the case of a `for` clause, by having a `for` loop; in the case of an `if` clause, by having an `if` statement – and so on). – Konrad Rudolph Dec 21 '12 at 11:26
1

just for start... my new expression evaluator: https://github.com/gsscoder/exprengine :D – gsscoder Dec 28 '12 at 15:40
I am getting cannot convert Number to Node? can this answer be made testable? – John Nyingi Aug 28 '21 at 06:38
1

@JohnNyingi Thanks. Indeed, the code is just a quick & dirty example that I hadn’t tested. I’ve fixed the errors now. – Konrad Rudolph Aug 28 '21 at 08:29
Help me understand the role of the `Context` class – John Nyingi Aug 29 '21 at 06:30
1

@JohnNyingi The short answer is given in the comment before the `Context` class; the long answer unfortunately doesn’t fit a comment. It basically carries everything that your interpreter needs, but which isn’t contained in the AST. Such as scope (i.e. mappings of variable names to values) etc. In the simple answer above, it’s obviously unused. – Konrad Rudolph Aug 31 '21 at 08:43

crafting a real interpreter using c# from AST

1 Answers1