We have a fully working ASPL VM now, although its current functionality is rather limited. Right now it is nothing more than a simple arithmetic calculator. Today we’ll start extending its capabilities to work towards a fully capable programming language implementation. We start by adding support for boolean expressions. But before we can do that, we have to revisit ASPL’s grammar rules and make some important changes.

Summary

Let’s examine a bit closer what we are going to do. Supporting boolean expressions. Well, to be precise, we are going to add support for a subset of boolean expressions.

What I mean by that is:

• Introduce two new keywords, true and false
• Add support for equality comparisons: equal and not equal
• Add support for less and less than or equal
• Add support for greater and greater than

Side note: along with true and false keywords we add the nil keyword as well, because it requires no extra work.

Changes in the grammar

Before we jump into coding, let’s examine how this will change the grammar of the language. Remember, the current grammar looks like this:

expression     := addition ;
addition       := multiplication ( ( "+" | "-" ) multiplication )* ;
multiplication := primary ( ( "*" | "/" ) primary )* ;
primary        := literal ;
literal        := integer | floating_point ;
integer        := digit+ ;
floating_point := digit+ ( "." digit+ )? ;
digit          := "0" ... "9" ;

Let’s see what are the changes we need to introduce to support boolean expressions.

First of all, we have to add the new keywords. This is easy because the keywords are terminals, so all we have to do is to add them to the primary rule.

literal        := "true" | "false" | "nil" | integer | floating_point ;

According to our rules of precedence, currently every expression starts with addition because this rule has the lowest precedence (of those we support). This is going to change now. We are introducing two new rules, comparison and equality. Out of these three, equality has the lowest precedence, so from now on, every expression is going to be an equality. Next is the comparison and addition is going to be the third in the new list.

If the equality rule has the lowest precedence, we have to start every expression with it:

expression     := equality ;

All right, but how does the body of the rule look like? Remember, we are building the lower precedence rules out of higher precedence ones, and the next higher precedence rule is going to be comparison, so we will use that to build equality out of.

Also, remember that we have a Pratt parser, which is a recursive-descent parser, and it cannot handle left recursion.

equality       := comparison ( (  "!=" | "==" ) comparison )* ;

This rule means that an equality expression consists of a comparison followed by either != or ==, followed by another comparison (and it can repeat).

So far, so good. Now we need to figure out how the comparison rule is built.

comparison     := addition ( ( "<" | "<=" | ">" | ">=" ) addition )* ;

Again, comparison builds upon the next higher precedence rule, which is addition. A comparison expression consist of an addition followed by either <, <=, >, or >=, followed by another addition (and again, it can repeat).

And that’s it, we are done. These are all the changes in the grammar we need to support boolean expressions.

The complete new look of our grammar looks like this:

expression     := equality ;
equality       := comparison ( (  "!=" | "==" ) comparison )* ;
comparison     := addition ( ( "<" | "<=" | ">" | ">=" ) addition )* ;
addition       := multiplication ( ( "+" | "-" ) multiplication )* ;
multiplication := primary ( ( "*" | "/" ) primary )* ;
primary        := literal ;
literal        := "true" | "false" | "nil" | integer | floating_point ;
integer        := digit+ ;
floating_point := digit+ ( "." digit+ )? ;
digit          := "0" ... "9" ;

Now, that we have our new version of the grammar, we can start implementing the changes in our source code as well. That is what we will do next time.

Stay tuned. I’ll be back.