Irony

[アーティクル]
10/31/2009

(Ironically, this post is not about irony in it's traditional sense )

Irony (https://irony.codeplex.com) is an open-source .NET compiler construction framework written by Roman Ivantsov. It is a ".NET Language Implementation Toolkit". The language grammar is described in C# (or any other .NET language).

So instead of generating the scanner and the parser from a grammar description written in an external DSL, Irony uses a .NET object graph to host the grammar description (internal DSL), and it uses this in-memory grammar description to drive the scanner and the parser at runtime.

One huge advantage of this approach is that the language description becomes orthogonal to the scanner and parser implementation. Writing and maintaining a language becomes easier. See an example of grammar definition further down in this post.

Arithmetic expression evaluation

The reason I'm talking about all this is that I was looking around for an expression parser for Live Geometry. I was able to compile expressions earlier using DLR, but there were two issues with that.

First, DLR has quite a footprint – adding a dependency on DLR to a Silverlight binary can grow the size of the .xap file from 400 KB to 1400 KB – and that's not good.
Second, DLR didn't seem to expose the parse trees easily – and I do need the access to the parse trees for inspection and manipulation, such as calculating dependencies between formulas.

So I started looking around. There are really a lot of related projects out there, I'll just mention the ones on CodePlex:

There might be more. My requirements were for the tool to output a parse tree and give me full access to it. Another requirement is that the grammar description has to be as simple as possible and as flexible and extensible as possible (because I planned to extend the language with custom elements such as method calls and property access). However full blown C# and LINQ parsers were an overkill. Other good projects were really fast, but didn't give me the parse tree.

So I settled on Irony, and so far I'm pretty happy that I did. It didn't provide the Silverlight version out of the box, but I'm talking with Roman about Silverlight support. For now, it took me an hour to make the Irony sources build for Silverlight and I built a nice little Irony.Silverlight.dll for my own project.

Expression parser in Irony

Here's how I declared the grammar for the language that I need:

 // This grammar is based on the ExpressionEvaluatorGrammar from Irony.Samples
// Copyright (c) Roman Ivantsov
// Details at https://irony.codeplex.com
[Language("Expression", "1.0", "Dynamic geometry expression evaluator")]
public class ExpressionGrammar : Irony.Parsing.Grammar
{
    public ExpressionGrammar()
    {
        this.GrammarComments = @"Arithmetical expressions for dynamic geometry.";

        // 1. Terminals
        var number = new NumberLiteral("number");
        var identifier = new IdentifierTerminal("identifier");

        // 2. Non-terminals
        var Expr = new NonTerminal("Expr");
        var Term = new NonTerminal("Term");
        var BinExpr = new NonTerminal("BinExpr");
        var ParExpr = new NonTerminal("ParExpr");
        var UnExpr = new NonTerminal("UnExpr");
        var UnOp = new NonTerminal("UnOp");
        var BinOp = new NonTerminal("BinOp", "operator");
        var PostFixExpr = new NonTerminal("PostFixExpr");
        var PostFixOp = new NonTerminal("PostFixOp");
        var AssignmentStmt = new NonTerminal("AssignmentStmt");
        var AssignmentOp = new NonTerminal("AssignmentOp");
        var PropertyAccess = new NonTerminal("PropertyAccess");
        var FunctionCall = new NonTerminal("FunctionCall");

        // 3. BNF rules
        Expr.Rule = Term | UnExpr | FunctionCall | PropertyAccess | BinExpr;
        Term.Rule = number | ParExpr | identifier;
        ParExpr.Rule = "(" + Expr + ")";
        UnExpr.Rule = UnOp + Term;
        UnOp.Rule = ToTerm("+") | "-" | "++" | "--";
        BinExpr.Rule = Expr + BinOp + Expr;
        BinOp.Rule = ToTerm("+") | "-" | "*" | "/" | "^";
        PropertyAccess.Rule = identifier + "." + identifier;
        FunctionCall.Rule = identifier + ParExpr;
        this.Root = Expr;

        // 4. Operators precedence
        RegisterOperators(1, "+", "-");
        RegisterOperators(2, "*", "/");
        RegisterOperators(3, Associativity.Right, "^");

        RegisterPunctuation("(", ")", ".");
        MarkTransient(Term, Expr, BinOp, UnOp, AssignmentOp, ParExpr);
    }
}

That's it! Note how Irony uses operator overloading for | and + to build rules. We need ToTerm("+") call on any of the operands to give the C# compiler a hint about the types so the operator overloading can succeed. This is a good example of an internal DSL hosted in C#.

Consuming the parse tree

Now, here's how to use the ExpressionGrammar class to create and use a parser:

 Grammar grammar = new ExpressionGrammar();
Parser parser = new Parser(grammar);
ParseTree parseTree = parser.Parse("sin(2 * x) + 1");

Producing a LINQ Expression Tree from a parse tree

Now, given the parse tree from the previous step, I just quickly wrote an ExpressionTreeBuilder that produces a bound expression tree out of it, and a Binder that helps resolve names. The Compiler class is a façade for the whole thing:

 public class Compiler
{
    public static Func<double, double> CompileFunction(string functionText)
    {
        ParseTree ast = ParserInstance.Parse(functionText);
        ExpressionTreeBuilder builder = new ExpressionTreeBuilder();
        Expression<Func<double, double>> expression = builder.CreateFunction(ast.Root);
        Func<double, double> function = expression.Compile();
        return function;
    }

    static Parser ParserInstance = new Parser(ExpressionGrammar.Instance);
}



public class Binder
{
    public void RegisterParameter(ParameterExpression parameter)
    {
        parameters.Add(parameter.Name, parameter);
    }

    ParameterExpression ResolveParameter(string parameterName)
    {
        ParameterExpression parameter;
        if (parameters.TryGetValue(parameterName, out parameter))
        {
            return parameter;
        }
        return null;
    }

    Dictionary<string, ParameterExpression> parameters = new Dictionary<string, ParameterExpression>();

    public Expression Resolve(string identifier)
    {
        return ResolveParameter(identifier);
    }

    public MethodInfo ResolveMethod(string functionName)
    {
        foreach (var methodInfo in typeof(System.Math).GetMethods())
        {
            if (methodInfo.Name.Equals(functionName, StringComparison.InvariantCultureIgnoreCase))
            {
                return methodInfo;
            }
        }
        return null;
    }
}

 public class ExpressionTreeBuilder
{
    public ExpressionTreeBuilder()
    {
        Binder = new Binder();
    }

    public Binder Binder { get; set; }

    public Expression<Func<double, double>> CreateFunction(ParseTreeNode root)
    {
        ParameterExpression parameter = Expression.Parameter(typeof(double), "x");
        Binder.RegisterParameter(parameter);
        Expression body = CreateExpression(root);
        var result = Expression.Lambda<Func<double, double>>(body, parameter);
        return result;
    }

    Expression CreateExpression(ParseTreeNode root)
    {
        if (root.Term.Name == "BinExpr")
        {
            return CreateBinaryExpression(root);
        }

        if (root.Term.Name == "identifier")
        {
            return Binder.Resolve(root.Token.Text);
        }

        if (root.Term.Name == "number")
        {
            return CreateLiteralExpression(Convert.ToDouble(root.Token.Value));
        }

        if (root.Term.Name == "FunctionCall")
        {
            return CreateCallExpression(root);
        }

        return null;
    }

    Expression CreateCallExpression(ParseTreeNode root)
    {
        string functionName = root.ChildNodes[0].Token.Text;
        Expression argument = CreateExpression(root.ChildNodes[1]);
        MethodInfo method = Binder.ResolveMethod(functionName);
        return Expression.Call(method, argument);
    }

    Expression CreateLiteralExpression(double arg)
    {
        return Expression.Constant(arg);
    }

    Expression CreateBinaryExpression(ParseTreeNode node)
    {
        Expression left = CreateExpression(node.ChildNodes[0]);
        Expression right = CreateExpression(node.ChildNodes[2]);

        switch (node.ChildNodes[1].Term.Name)
        {
            case "+":
                return Expression.Add(left, right);
            case "-":
                return Expression.Subtract(left, right);
            case "*":
                return Expression.Multiply(left, right);
            case "/":
                return Expression.Divide(left, right);
            case "^":
                return Expression.Power(left, right);
        }
        return null;
    }
}

This just demonstrates the principle. One could easily extend this to write a full blown expression compiler, but this is good enough for my purposes for now. Live Geometry now uses this to evaluate math expressions and plot function graphs. As always, you can get the source from here.

Comments

Anonymous
October 31, 2009
The interesting thing is that you do not actually need an expression tree transformer (ExpressionTreeBuilder), if you use the AstNodeCreator delegate in NonTerminals (I do not remember, but I think there is a constructor overload for that).
Anonymous
November 01, 2009
Yes, I need to learn more about ASTs in Irony. And it seems like I'm not the only one who's using Irony for this purpose: http://intellect.dk/post/Writing-a-calculator-in-C-using-Irony.aspx I should have done a websearch before writing this article :)
Anonymous
November 11, 2009
Using NCalc which is in your tools list, you can access the AST and modify it, even provide your own one, define custom methods and variables. If you need more help then contact me.
Anonymous
November 25, 2009
Thanks Sébastien! There are several good frameworks out there. I liked NCalc a lot. It's just I needed to settle down on one :)
Anonymous
November 30, 2010
By the irony, I had written ab LL(1) parser & AST compiler which is usable as much as like Irony does. Kirill, I can try to rewrite the sample you provided using expressions compiler. What do you think?
Anonymous
December 01, 2010
Of course Artur, you're welcome to do so! It'll be interesting to see your approach.
Anonymous
April 30, 2013
It seems quite good. I will forget boost.spirit for a meanwhile and try this firstly. I need a things can easily work soon, but I also hope it can be run quickly and stable and scalable.

次の方法で共有