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

Recursive descent parser (en.wikipedia.org/wiki/Recursive_descent_parser) can be easily expanded to evaluate the expression while parsing — Zruty
– Zruty, Commented Nov 19, 2013 at 5:59
What's the problem with generating code? You can execute the generated code straight away, it's much easier than an ad hoc interpretation. — SK-logic
– SK-logic, Commented Nov 19, 2013 at 11:45

Zruty · Accepted Answer · 2013-11-19 06:36:00Z

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

greenoldman · Accepted Answer · 2013-11-19 07:44:04Z

0

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.

answered Nov 19, 2013 at 7:44

greenoldman

21.3k31 gold badges143 silver badges239 bronze badges

2 Comments

David Colwell Over a year ago

Thanks, will have a go at implementing tomorow

David Colwell Over a year ago

This solution is quite elegant, however the other integrated with my project better. Thanks for the answer!

Collectives™ on Stack Overflow

Executing a simple Domain Specific Language in .NET

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related