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,
and**true****false** - Add support for equality comparisons:
and**equal****not equal** - Add support for
and**less****less than or equal** - Add support for
and**greater****greater than**

Side note: along with * true* and

*keywords we add the*

**false***keyword as well, because it requires no extra work.*

**nil**# 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.