DEV Community

loading...
Cover image for Advent of Code 2020: Day 18 finally using PEG grammar in Python in the way it's supposed to

Advent of Code 2020: Day 18 finally using PEG grammar in Python in the way it's supposed to

meseta profile image Yuan Gao Updated on ・5 min read

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

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))
Enter fullscreen mode Exit fullscreen mode

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 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"
Enter fullscreen mode Exit fullscreen mode

Next, our operators look like this:

    OPERATION = NUMBER (OP NUMBER)+
Enter fullscreen mode Exit fullscreen mode

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]]
Enter fullscreen mode Exit fullscreen mode

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:

from parsimonious.grammar import Grammar

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

When we test it on the expression 1 + (2 * 3) we get:

print(grammar.parse("""1 + (2 * 3)"""))
Enter fullscreen mode Exit fullscreen mode

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 ")">

Enter fullscreen mode Exit fullscreen mode

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.

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
Enter fullscreen mode Exit fullscreen mode

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:

    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
Enter fullscreen mode Exit fullscreen mode

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]]
Enter fullscreen mode Exit fullscreen mode

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:

print("sum", sum(ev.parse(line.strip()) for line in open("input.txt").readlines()))
Enter fullscreen mode Exit fullscreen mode

The output is the answer the challenge is looking for. The full code is:

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()))
Enter fullscreen mode Exit fullscreen mode

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:

    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)
Enter fullscreen mode Exit fullscreen mode

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:

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()))
Enter fullscreen mode Exit fullscreen mode

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

Onwards!

Discussion (0)

pic
Editor guide