DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports
Events Video Library
Refcards
Trend Reports

Events

View Events Video Library

Zones

Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks

Last call! Secure your stack and shape the future! Help dev teams across the globe navigate their software supply chain security challenges.

Modernize your data layer. Learn how to design cloud-native database architectures to meet the evolving demands of AI and GenAI workloads.

Releasing software shouldn't be stressful or risky. Learn how to leverage progressive delivery techniques to ensure safer deployments.

Avoid machine learning mistakes and boost model performance! Discover key ML patterns, anti-patterns, data strategies, and more.

Related

  • Building Call Graphs for Code Exploration Using Tree-Sitter
  • Telemetry Pipelines Workshop: Parsing Multiple Events
  • Writing an Interpreter: Implementation
  • On Some Aspects of Big Data Processing in Apache Spark, Part 4: Versatile JSON and YAML Parsers

Trending

  • Integrating Security as Code: A Necessity for DevSecOps
  • Mastering Advanced Traffic Management in Multi-Cloud Kubernetes: Scaling With Multiple Istio Ingress Gateways
  • The Human Side of Logs: What Unstructured Data Is Trying to Tell You
  • How the Go Runtime Preempts Goroutines for Efficient Concurrency
  1. DZone
  2. Coding
  3. Languages
  4. Recursive Descent Parser with C# - Boolean logic expressions

Recursive Descent Parser with C# - Boolean logic expressions

By 
Slobodan Pavkov user avatar
Slobodan Pavkov
·
Dec. 16, 14 · Interview
Likes (0)
Comment
Save
Tweet
Share
12.7K Views

Join the DZone community and get the full member experience.

Join For Free

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.

 

Parser (programming language)

Published at DZone with permission of Slobodan Pavkov, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Related

  • Building Call Graphs for Code Exploration Using Tree-Sitter
  • Telemetry Pipelines Workshop: Parsing Multiple Events
  • Writing an Interpreter: Implementation
  • On Some Aspects of Big Data Processing in Apache Spark, Part 4: Versatile JSON and YAML Parsers

Partner Resources

×

Comments

The likes didn't load as expected. Please refresh the page and try again.

ABOUT US

  • About DZone
  • Support and feedback
  • Community research
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Core Program
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 3343 Perimeter Hill Drive
  • Suite 100
  • Nashville, TN 37211
  • support@dzone.com

Let's be friends: