Logical Expression parser August 13, 2012

Recently we I had a requirement to enhance the rule engine for our system to use a logical expression formulae to calculate result of several rules associated with a validation.

Until that point all rules had to succeed so it was a straight forward AND between all rules, instead of trying to create a complecated user interface we decided to go with a formulae expression. This of course means that we have to validate during setup and ofcourse evaluate the result based on individual rule result at runtime.

Since this was for for a platform closer to .NET and based on my reading of the Programming in Scala, i looked at parser combinators, and it seems that there are some things there for .NET see for example Sprache but finally we decided not to use it becuase we didnt want to use external libraries for this project. I ended up using new System.Data.DataTable().Compute(...) to evaluate the expression and regular expressions to limit the operations and tokens only to the rules defined for the particular validation.

The solution works, but I really enjoyed the trip with parser combinators(Programming in Scala chapter 33), and I do feel that it is a great tool to have, so i decided to see how i could do the same in Scala, so here it goes:

First I got the grammar for the logical expression and then after reading the rules from the Programming in Scala book i ended up with the following class:

I decided to make it a class that takes a Map[String, Boolean], so i can pass it to my expression parser. The additional benefit of this is that it parses expressions only for the variables in the map, anything else will fail during parsing, so you can really make sure your expression is correct according to your validation rules. One can restrict the rule names to propper identifiers or even more strict but that is outside the scope of this exersice. Finally the code that describes the logical expression is not more than 7 lines including parsing and evaluation which is mindblowing concidering that no external libraries are used just the core scala libraries.

So lets have a look at one of the parsers:

here the parser is splited in 2 parts, first the part before the ^^ 

which is the actual parser saying that b_not_factor is an optional "not" followed by a factor.

The next part is the part that is doing the evaluation: