Recursive Descent Parser with C# - Boolean logic expressions

In previous post we gave brief introduction on Recursive Descent Parsers and we implemented parser that was able to parse and calculate simple arithmetic expressions with addition and subtraction.

To be (True) or !(To be True)?

This time we will try to tackle little bit more complex example that will parse and evaluate Boolean logic expressions that will include negation and parenthesis.

Examples of expressions we want to be able to parse and evaluate are:

• True And True And False
• True
• !False
• (!(False)) and (!(True) etc

Let’s assemble a EBNF grammar for this type of expressions:

Expression      := [ "!" ] <Boolean> { BooleanOperator Boolean }
Boolean         := BooleanConstant | Expression | "(" <Expression> ")"
BooleanOperator := "And" | "Or" 
BooleanConstant := "True" | "False"

You can see that our Terminal Symbols are “And”, “Or” (BooleanOperator) and “True”, “False” (BooleanConstant) and off course  “!” and parenthesis.

Expression can have optional negation symbol “!” and then Boolean (which can be BooleanConstant or Expression or Expression in parenthesis).

Every next Boolean expression is optional but if its there, it must be preceded by BooleanOperator so that we can parse the final value by combining it with previous Boolean value. Obviously we will have some recursion there, but more on that later when we start implementing the parser.

Always Tokenize everything!

Before looking into the parser, we have to implement the Tokenizer class that will parse the raw text of the expression, tokenize it and return IEnumerable<Token> so that our parser can have less to worry about.

Here is the Tokenizer class:

public class Tokenizer
{
    private readonly StringReader _reader;
    private string _text;

    public Tokenizer(string text)
    {
        _text = text;
        _reader = new StringReader(text);
    }

    public IEnumerable<Token> Tokenize()
    {
        var tokens = new List<Token>();
        while (_reader.Peek() != -1)
        {
            while (Char.IsWhiteSpace((char) _reader.Peek()))
            {
                _reader.Read();
            }

            if (_reader.Peek() == -1)
                break;

            var c = (char) _reader.Peek();
            switch (c)
            {
                case '!':
                    tokens.Add(new NegationToken());
                    _reader.Read();
                    break;
                case '(':
                    tokens.Add(new OpenParenthesisToken());
                    _reader.Read();
                    break;
                case ')':
                    tokens.Add(new ClosedParenthesisToken());
                    _reader.Read();
                    break;
                default:
                    if (Char.IsLetter(c))
                    {
                        var token = ParseKeyword();
                        tokens.Add(token);
                    }
                    else
                    {
                        var remainingText = _reader.ReadToEnd() ?? string.Empty;
                        throw new Exception(string.Format("Unknown grammar found at position {0} : '{1}'", _text.Length - remainingText.Length, remainingText));
                    }
                    break;
            }
        }
        return tokens;
    }

    private Token ParseKeyword()
    {
        var text = new StringBuilder();
        while (Char.IsLetter((char) _reader.Peek()))
        {
            text.Append((char) _reader.Read());
        }

        var potentialKeyword = text.ToString().ToLower();

        switch (potentialKeyword)
        {
            case "true":
                return new TrueToken();
            case "false":
                return new FalseToken();
            case "and":
                return new AndToken();
            case "or":
                return new OrToken();
            default:
                throw new Exception("Expected keyword (True, False, And, Or) but found "+ potentialKeyword);
        }
    }
}

Not much happening there really, we just go through the characters of the expression, and if its negation or parenthesis we return proper sub classes of Token and if we detect letters we try to parse one of our keywords (“True”, “False”, “And”, “Or”).
If we encounter unknown keyword we throw exception to be on the safe side. I deliberately did not do much validation of the expression in this class since this is done later in the Parser – but nothing would stop us from doing it here also – i will leave that exercise to the reader.

The Parser

Inside of our parser we have main Parse method that will start the process of parsing the tokens, handle the negation, and continue parsing sub-expressions while it encounters one of the OperandTokens (AndToken or OrToken).

public bool Parse()
{
    while (_tokens.Current != null)
    {
        var isNegated = _tokens.Current is NegationToken;
        if (isNegated)
            _tokens.MoveNext();

        var boolean = ParseBoolean();
        if (isNegated)
            boolean = !boolean;

        while (_tokens.Current is OperandToken)
        {
            var operand = _tokens.Current;
            if (!_tokens.MoveNext())
            {
                throw new Exception("Missing expression after operand");
            }
            var nextBoolean = ParseBoolean();

            if (operand is AndToken)
                boolean = boolean && nextBoolean;
            else
                boolean = boolean || nextBoolean;

        }

        return boolean;
    }

    throw new Exception("Empty expression");
}

Parsing of the sub-expressions is handled in the ParseBoolean method:

private bool ParseBoolean()
 {
     if (_tokens.Current is BooleanValueToken)
     {
         var current = _tokens.Current;
         _tokens.MoveNext();

         if (current is TrueToken)
             return true;

         return false;
     }
     if (_tokens.Current is OpenParenthesisToken)
     {
         _tokens.MoveNext();

         var expInPars = Parse();

         if (!(_tokens.Current is ClosedParenthesisToken))
             throw new Exception("Expecting Closing Parenthesis");

         _tokens.MoveNext(); 

         return expInPars;
     }
     if (_tokens.Current is ClosedParenthesisToken)
         throw new Exception("Unexpected Closed Parenthesis");

     // since its not a BooleanConstant or Expression in parenthesis, it must be a expression again
     var val = Parse();
     return val;
 }

This method tries to parse the simplest BooleanValueToken, then if it encounter OpenParenthesisToken it handles the Expressions in parenthesis by skipping the OpenParenthesisToken and then calling back the Parse to get the value of expressions and then again skipping the ClosedParenthesisToken once parsing of inner expression is done.

If it does not find BooleanValueToken or OpenParenthesisToken – method simply assumes that what follows is again an expression so it calls back Parse method to start the process of parsing again.

To be logical is to be simple

As you see, we implemented the parser in less then 90 lines of C# code. Maybe this code is not particularity useful but its good exercise on how to build parsing logic recursively.

It could be further improved by adding more logic to throw exceptions when unexpected Tokens are encountered but again – i leave that to the reader (for example expression like “true)” should throw exception, but in this version of code it will not do that, it will still parse the expression correctly by ignoring the closing parenthesis).

Tests

Here are some of the Unit Tests i built to test the parser:

[TestCase("true", ExpectedResult = true)]
[TestCase(")", ExpectedException = (typeof(Exception)))]
[TestCase("az", ExpectedException = (typeof(Exception)))]
[TestCase("", ExpectedException = (typeof(Exception)))]
[TestCase("()", ExpectedException = typeof(Exception))]
[TestCase("true and", ExpectedException = typeof(Exception))]
[TestCase("false", ExpectedResult = false)]
[TestCase("true ", ExpectedResult = true)]
[TestCase("false ", ExpectedResult = false)]
[TestCase(" true", ExpectedResult = true)]
[TestCase(" false", ExpectedResult = false)]
[TestCase(" true ", ExpectedResult = true)]
[TestCase(" false ", ExpectedResult = false)]
[TestCase("(false)", ExpectedResult = false)]
[TestCase("(true)", ExpectedResult = true)]
[TestCase("true and false", ExpectedResult = false)]
[TestCase("false and true", ExpectedResult = false)]
[TestCase("false and false", ExpectedResult = false)]
[TestCase("true and true", ExpectedResult = true)]
[TestCase("!true", ExpectedResult = false)]
[TestCase("!(true)", ExpectedResult = false)]
[TestCase("!(true", ExpectedException = typeof(Exception))]
[TestCase("!(!(true))", ExpectedResult = true)]
[TestCase("!false", ExpectedResult = true)]
[TestCase("!(false)", ExpectedResult = true)]
[TestCase("(!(false)) and (!(true))", ExpectedResult = false)]
[TestCase("!((!(false)) and (!(true)))", ExpectedResult = true)]
[TestCase("!false and !true", ExpectedResult = false)]
[TestCase("false and true and true", ExpectedResult = false)]
[TestCase("false or true or false", ExpectedResult = true)]
public bool CanParseSingleToken(string expression)
{
    var tokens = new Tokenizer(expression).Tokenize();
    var parser = new Parser(tokens);
    return parser.Parse();
}

Full source code of the whole solution is available at my BooleanLogicExpressionParser GitHub repo.

Stay tuned because next time we will implement parser for more complex arithmetical expressions.