Advent of Code 2020: Day 18 finally using PEG grammar in Python in the way it's supposed to
Tags: adventofcode, python
Published: 2020-12-19 22:08:09

Another quick one for today. The challenge is actually about parsing expressions. So I pull out the Parsimonious library again, and this time use it for its intended use, rather than all the times I used it on previous challenges (Day 07 and Day 04)

# The Challenge Part 1
[Link to challenge on Advent of Code 2020 website](https://adventofcode.com/2020/day/18)

The challenge is to implement a simple math expression parser, but with some unconventional operator precedence rules. An example of an expression is given as:

```
1 + (2 * 3) + (4 * (5 + 6))
```

The parser must solve a big file of these, but one in which operators are evaluated left-to-right rather than multiplication before addition, so `1 + 2 * 3 + 4 * 5 + 6` equals 71 rather than the usual 33

## PEG Grammar
Finally, we get to use [Parsimonious](https://github.com/erikrose/parsimonious) for its intended purpose. We'll write a PEG grammar to deal with these expressions. I'm going to skip over the explanation pretty quickly, more details for how this works can be found in my Day 04 and Day 07 solution posts.

The first thing I note is that the formatting is very consistent, and expressions are always NUMBER SPACE OPERATOR SPACE NUMBER. So we go ahead and define these:

```
    OP = " " ("+" / "*") " "
    NUMBER    = ~r"\d"
```

Next, our operators look like this:
```
    OPERATION = NUMBER (OP NUMBER)+
```
Which is saying that the operation consists of an expression followed by one or more pairs of OP NUMBER. E.g. `1 + 2 * 3 + 4` would give us the following parts:
```
[1, [["+", 2], ["*", 3], ["+", 4]]
```

Finally, we realize that we can't just deal with NUMBER, and sometimes we have to deal with BRACKETS first, so we replace it with an EXPR which can itself be either NUMBER or BRACKETS. This gives us the whole PEG expression:

```py
from parsimonious.grammar import Grammar

grammar = Grammar(r"""
    OPERATION = EXPR (OP EXPR)+
    EXPR = (NUMBER / BRACKETS)
    BRACKETS = "(" OPERATION ")"
    OP = " " ("+" / "*") " "
    NUMBER    = ~r"\d"
""")
```

When we test it on the expression `1 + (2 * 3)` we get:
```py
print(grammar.parse("""1 + (2 * 3)"""))
```
Output
```
<Node called "OPERATION" matching "1 + (2 * 3)">
    <Node called "EXPR" matching "1">
        <RegexNode called "NUMBER" matching "1">
    <Node matching " + (2 * 3)">
        <Node matching " + (2 * 3)">
            <Node called "OP" matching " + ">
                <Node matching " ">
                <Node matching "+">
                    <Node matching "+">
                <Node matching " ">
            <Node called "EXPR" matching "(2 * 3)">
                <Node called "BRACKETS" matching "(2 * 3)">
                    <Node matching "(">
                    <Node called "OPERATION" matching "2 * 3">
                        <Node called "EXPR" matching "2">
                            <RegexNode called "NUMBER" matching "2">
                        <Node matching " * 3">
                            <Node matching " * 3">
                                <Node called "OP" matching " * ">
                                    <Node matching " ">
                                    <Node matching "*">
                                        <Node matching "*">
                                    <Node matching " ">
                                <Node called "EXPR" matching "3">
                                    <RegexNode called "NUMBER" matching "3">
                    <Node matching ")">

```
This looks really long, but when you strip out all the extra bits, you can see that it contains the structure we want.

Next, we implement a node visitor to execute the parsed syntax tree.

```py
class ExprVisitor(NodeVisitor):
    def visit_OPERATION(self, node, visited_children):
        left = visited_children[0]
        for op, value in visited_children[1]:
            if op == "+":
                left += value
            if op == "*":
                left *= value
        return left
    
    def visit_EXPR(self, node, visited_children):
        return visited_children[0]

    def visit_BRACKETS(self, node, visited_children):
        return visited_children[1]
    
    def visit_OP(self, node, visited_children):
        return visited_children[1][0].text

    def visit_NUMBER(self, node, visited_children):
        return int(node.text)

    def generic_visit(self, node, visited_children):
        return visited_children or node

ev = ExprVisitor()
ev.grammar = grammar
```
Most of the lower nodes deal with formatting the nodes so that higher up nodes have clean data to work with. The main part of this that implements the challenge rules is the `visit_OPERATION()` function:

```py
    def visit_OPERATION(self, node, visited_children):
        left = visited_children[0]
        for op, value in visited_children[1]:
            if op == "+":
                left += value
            if op == "*":
                left *= value
        return left
```
This function will have all the EXPR children evaluated to values already (which means BRACKETS will have been resolved recursively to their values). Recall the earlier example of `1 + 2 * 3 + 4`, when it gets to this function, `visited_children` would be
```
[1, [["+", 2], ["*", 3], ["+", 4]]
```
So it can be seen that `left` is set to `1` and then for each pair of operator and value, it'll add or multiply the value onto the running total depending on the operator. The way this is written, the operators will evaluate left to right, as required by the challenge.

Finally, we run the lines of the input through the parser, which returns the evaluated value:

```py
print("sum", sum(ev.parse(line.strip()) for line in open("input.txt").readlines()))
```
The output is the answer the challenge is looking for. The full code is:

```py
from parsimonious.grammar import Grammar, NodeVisitor
grammar = Grammar(r"""
    OPERATION = EXPR (OP EXPR)+
    EXPR = (NUMBER / BRACKETS)
    BRACKETS = "(" OPERATION ")"
    OP = " " ("+" / "*") " "
    NUMBER    = ~r"\d"
""")

class ExprVisitor(NodeVisitor):
    def visit_OPERATION(self, node, visited_children):
        left = visited_children[0]
        for op, value in visited_children[1]:
            if op == "+":
                left += value
            if op == "*":
                left *= value
        return left
    
    def visit_EXPR(self, node, visited_children):
        return visited_children[0]

    def visit_BRACKETS(self, node, visited_children):
        return visited_children[1]
    
    def visit_OP(self, node, visited_children):
        return visited_children[1][0].text

    def visit_NUMBER(self, node, visited_children):
        return int(node.text)

    def generic_visit(self, node, visited_children):
        return visited_children or node

ev = ExprVisitor()
ev.grammar = grammar

print("sum", sum(ev.parse(line.strip()) for line in open("input.txt").readlines()))
```

# The Challenge Part 2
In the second part of the challenge, the precedence is switched. Now instead of evaluating left to right, additions are evaluated first.

We can use the same code as before, we just have to change the `visit_OPERATION()` function to evaluate the additions before multiplications. It ends up looking like this:

```py
    def visit_OPERATION(self, node, visited_children):
        parts = [visited_children[0]]
        for op, value in visited_children[1]:
            if op == "+":
                parts[-1] += value
            if op == "*":
                parts.append(value)
        return math.prod(parts)
```
Instead of keeping a running total onto which each new value is added or multiplied, here, we store a list of values, and for every addition operation we see, immediately add that to the last entry on the list. If we see a multiply, append to the list. This way, all the addition operations happen as we go, leaving only values to multiply in the list to the end, when they're all multiplied together, fulfilling the rules of the challenge.

The full code is, mostly the same as before:
```py
from parsimonious.grammar import Grammar, NodeVisitor
import math

grammar = Grammar(r"""
    OPERATION = EXPR (OP EXPR)+
    EXPR = (NUMBER / BRACKETS)
    BRACKETS = "(" OPERATION ")"
    OP = " " ("+" / "*") " "
    NUMBER    = ~r"\d"
""")

class ExprVisitor(NodeVisitor):
    def visit_OPERATION(self, node, visited_children):
        parts = [visited_children[0]]
        for op, value in visited_children[1]:
            if op == "+":
                parts[-1] += value
            if op == "*":
                parts.append(value)
        return math.prod(parts)
    
    def visit_EXPR(self, node, visited_children):
        return visited_children[0]

    def visit_BRACKETS(self, node, visited_children):
        return visited_children[1]
    
    def visit_OP(self, node, visited_children):
        return visited_children[1][0].text

    def visit_NUMBER(self, node, visited_children):
        return int(node.text)

    def generic_visit(self, node, visited_children):
        return visited_children or node

ev = ExprVisitor()
ev.grammar = grammar
print("sum", sum(ev.parse(line.strip()) for line in open("input.txt").readlines()))
```

That's all! Parsimonious is a fun library to play with for any parsing jobs. I can highly recommend it

Onwards!