Post 2: Expression Evaluator - Building an Expression Tree

The Parse function described in the previous posts allows us to specify a ParseEventHandler delegated function which will be called-back by the parser.

We use this function to monitor the parsing of an expression string, and build a corresponding expression tree, which can then be evaluated. This is one of several approaches we could take for the evaluation process - alternatively, we could proceed with the evaluation in-situ, with a makeshift stack. I took this approach because it allows us to re-use the expression strings without having the re-parse - which is something we'll need to support user-defined functions.

The building of the expression tree is straightforward. We require a simple class to keep track of the Root node of the expression, and the Current node - which represents the S-Expression being parsed currently.

We write a simple ParseEventHandler delegate, which hooks the SExprStart state to signify the creation of a sub-tree, and the Atom state to signify leaf nodes of the expression tree. We pass along a ParserContext object to keep a reference to the Root and the Current nodes of the expression tree.

public class ParserContext
{
    public Expression Root { get; private set; }
    public Expression Current { get; set; }

    public ParserContext(Expression Root)
    {
        this.Root = Root;
        this.Current = Root;
    }
}

The ParseEventHandler function is simple and elegant. All we're doing here is listening for three events:

• SExprStart : Signifying a new S-Expression child. Our handler creates a child and sets it as the current parent, so future nodes will get bound to it.
• SExprFinish: Signifying the completion of the current S-Expression. Our handler "pops the stack", as it were, and marks the parent node as the current parent.
• Atom: Signifying a leaf-node child of the current parent. Simply creates and attaches a leaf-node, leaving the current parent intact.

protected static void ParseEventHandler(ParseEventArgs e)
{
    ParserContext pctx = e.ParserContext as ParserContext;
    if (pctx == null) return;

    switch (e.Token)
    {
        case E_TOKEN.SExprStart:
            {
                pctx.Current = new Expression(pctx.Current, ">>", e.State, e.Token);
            }
            return;

        case E_TOKEN.SExprFinish:
            {
                pctx.Current = pctx.Current.Parent;
            }
            return;
    }

    switch (e.State)
    {
        case E_PARSESTATE.Atom:
            {
                Expression exIgnore = pctx.Current.NewChild(e.TokenValue, e.State, e.Token);
            }
            return;

        case E_PARSESTATE.Failure:
            {
                throw new ParseException(String.Format("*** FAILURE {0}] : [ {1} ], {2}, {3}", e.ErrorDescription, e.TokenValue, e.State, e.Token));
            }
    }
}

To actually call the parser, all we do is pass in a reference to the handler and context instance:

Expression Root = new Expression();

Parser.Parse(pszExpression, new ParseEventHandler(ParseEventHandler), new ParserContext(Root));

// ... at this point, Root has been built up, or parsing has failed and thrown an exception

We'll discuss the Expression class in detail in the next post.