Executing a simple Domain Specific Language in .NET

Question

I have a very simple Domain Specific Language consisting of the following BNF definition

<Statement> ::= <Expression> | <Expression> <BinaryOperator> <Expression>
<Expression> ::= <Field> <Comparer> <Value> | "(" <Expresion> ")"
<Field> ::= "Name" | "Date of Birth" | "Address"
<Comparer> ::= "One Of", "=", "!=", "Not One Of"
<Value> ::= --Any string literal
<BinaryOperator> ::= "OR" | "AND"

I need a simple guide to writing a DSL parser/executor in the .NET framework. I have had a look at Irony, but it seems to generate code instead of executing it with values.

An example is:

(Name = "Dave" AND Address = "150 nosuchstreet, nowhere") OR Date Of Birth != 15/10/1976

It basically just needs to evaluate the statement (after having the values of NAme, Address, and Date of Birth replaced with the actual values) and return a boolean true or false

Answer 1

As an exercise, I've quickly sketched a recursive-descent parser/evaluator for your language. I omitted the most obvious code (like tokenization and field value retrieval) and I didn't pay any attention to efficiency.

In your implementation you might want to consider

• moving away from string literals for field names and operator names, to reduce the number of string comparisons
• modifying GetNextToken() to avoid calls to StartsWith()
• storing the parsed expression tree to reuse for multiple calculations
• support short-circuit evaluation (0 && x == 0, 1 || x == 1)

Code is below

public class Evaluator
{
    public enum TokenType
    {
        Field,
        Comparer,
        Value,
        Operator,
        Parenthesis
    }

    public class Token
    {
        public TokenType TokenType;
        public string Value;
    }

    private string statement;
    private int cursor = 0;
    private Token curToken;
    private object target;

    public Evaluator(string statement, object target)
    {
        this.statement = statement;
    }

    public bool EvaluateStatement()
    {
        GetNextToken();
        bool value = EvaluateExpression();
        if (curToken != null && curToken.TokenType == TokenType.Operator)
        {
            var op = curToken;
            GetNextToken();
            var v2 = EvaluateExpression();
            if (op.Value == "AND")
                return value && v2;
            else
                return value || v2;
        }

        return value;
    }

    private bool EvaluateExpression()
    {
        if (curToken.TokenType == TokenType.Parenthesis)
        {
            GetNextToken();
            bool value = EvaluateExpression();
            GetNextToken(); // skip closing parenthesis
            return value;
        }
        var fieldName = curToken.Value;
        GetNextToken();
        var op = curToken.Value;
        GetNextToken();
        var targetValue = curToken.Value;
        GetNextToken();

        var fieldValue = GetFieldValue(target, fieldName);
        return EvaluateComparer(fieldValue, targetValue, op);
    }

    private bool EvaluateComparer(string left, string right, string op)
    {
        if (op == "=")
        {
            return left == right;
        }
        else if (op == "!=")
        {
            return left != right;
        }
        // add more ops here
        else
        {
            throw new Exception("Invalid op");
        }
    }

    /// <summary>
    /// Get the next token from the input string, put it into 'curToken' and advance 'cursor'.
    /// </summary>
    public void GetNextToken()
    {
        // skip spaces
        while (cursor < statement.Length || Char.IsWhiteSpace(statement[cursor]))
        {
            cursor++;
        }

        if (cursor >= statement.Length)
        {
            curToken = null;
        }

        var remainder = statement.Substring(cursor);
        if (remainder.StartsWith("Name"))
        {
            cursor += "Name".Length;
            curToken = new Token
            {
                TokenType = TokenType.Field,
                Value = "Name"
            };
        }
        else if (remainder.StartsWith("!="))
        {
            cursor += "!=".Length;
            curToken = new Token
            {
                TokenType = TokenType.Field,
                Value = "!="
            };
        }
        // etc.
        else
        {
            throw new Exception("Unexpected token");
        }
    }

    private string GetFieldValue(object target, string fieldName)
    {
        // trivial to implement with fixed set of field names
        throw new NotImplementedException();
    }
}

Answer 2

This is how would you do it in NLT.

scanning

"Name" -> NAME;
"Date of Birth" -> BIRTH;
"Address" -> ADDRESS;
// ... and so on

parsing

S -> s:Statement { s };

Statement -> e:Expression { e }
           | e1:Expression AND e2:Expression { e1 && e2 }
           | e1:Expression OR e2:Expression { e1 || e2 }
           ;

Expression bool -> f:Field c:Comparer v:VALUE { compare(c,f,v) }
                 | LPAREN e:Expresion RPAREN { e }
                 ;

Field string -> f:[NAME BIRTH ADDRESS] { f };

Comparer string -> c:[ONEOF EQ NEQ NONEOF] { c };

All you have to add really is function compare which does the comparison. As the result you will get null (wrong input) or true/false value as evaluation.