calculator1.pl - Operator Precedence Climbing

Our first example calculator uses what is known as the Operator Precedence Climbing method. See: <http://en.wikipedia.org/wiki/Operator-precedence_parser#Precedence_climbing_method>.

This is basically a clever technique of specifying our grammar rules such that they imply precedence. Here's the pegex grammar from the code:

    expr: add-sub
    add-sub: mul-div+ % /- ( [ '+-' ])/
    mul-div: power+ % /- ([ '*/' ])/
    power: token+ % /- '^' /
    token: /- '(' -/ expr /- ')'/ | number
    number: /- ( '-'? DIGIT+ )/

It's a little bit wonky but it works. It says that any expression is an add/subtract and that an add/subtract is really a multiply/divide etc. Finally after the last operator comes the number token and the parens.

It feels a bit backwards. One of the biggest drawbacks of PCM is that it becomes less and less efficient with more and more operators. It needs to go through the whole tree, just to find each number.

But it works and the code is minimal. The receiver class gets the numbers in the correct order, immediately evaluates the answer and returns the answer for each level. Whatever the return value of the final operation is, becomes the result of the parse. Here's the receiver class:

    {
        package Calculator;
        use base 'Pegex::Tree';

        sub gotrule {
            my ($self, $list) = @_;
            return $list unless ref $list;

            # Right associative:
            if ($self->rule eq 'power') {
                while (@$list > 1) {
                    my ($a, $b) = splice(@$list, -2, 2);
                    push @$list, $a ** $b;
                }
            }
            # Left associative:
            else {
                while (@$list > 1) {
                    my ($a, $op, $b) = splice(@$list, 0, 3);
                    unshift @$list,
                        ($op eq '+') ? ($a + $b) :
                        ($op eq '-') ? ($a - $b) :
                        ($op eq '*') ? ($a * $b) :
                        ($op eq '/') ? ($a / $b) :
                        die;
                }
            }
            return @$list;
        }
    }

As you can see, it has an action method for each level or precedence. It loops over the expression, evaluating it. Whether it loops from left to right or right to left depends on the associativity that we want to use.

Our runner code looks like this:

    while (1) {
        print "\nEnter an equation: ";
        my $expr = <> || '';
        chomp $expr;
        last unless length $expr;
        calc($expr);
    }

    sub calc {
        my ($expr) = @_;
        my $result = pegex($grammar, 'Calculator')->parse($expr);
        if ($@) {
            warn $@;
            return;
        }
        print "$expr = $result\n";
    }

And that's the whole thing. We have a working calculator as specced!

However the real point of this is to explore good parsing techniques, and the PCM leaves us wanting to try something more efficient. Let's try another approach...

calculator2.pl - Shunting Yard Algorithm

For example:

    1 / 2 - ( -3 * 4 )

becomes:

    1, 2, /, -3, 4, *, -

To evaluate an RPN you pop off an operator and then attempt to pop off and operand. If the operand is another operator you recurse. When you have 2 operands you do the operation and put the result back on the stack. When there is only 1 element on the stack, you are done. That's your result.

Let's look at our new grammar in "calculator2.pl":

    expr: operand (operator operand)*
    operator: /- (['+-*/^'])/
    operand: num | /- '('/ expr /- ')'/
    num: /- ('-'? DIGIT+)/

This is much easier to understand. We are just parsing out the tokens. In a (very real) sense, we are using Pegex as a lexer.

Now let's look at the receiver class:

    {
        package Calculator;
        use base 'Pegex::Tree', 'Precedence';

        my $operator_precedence_table = {
            '+' => {p => 1, a => 'l'},
            '-' => {p => 1, a => 'l'},
            '*' => {p => 2, a => 'l'},
            '/' => {p => 2, a => 'l'},
            '^' => {p => 3, a => 'r'},
        };

        sub got_expr {
            my ($self, $expr) = @_;
            $self->precedence_rpn($expr, $operator_precedence_table);
        }
    }

This is also much simpler. There's only one method. What's going on? Well the secret is that I put the code to turn the tokens into RPN in a separate base class called "lib/Precedence.pm" in example.

This is an implementation of Edsger Dijkstra's famous Shunting-yard Algorithm from 1961! It's only 20 lines of Perl. I won't include it inline here, but have a look at it for yourself. <https://github.com/ingydotnet/pegex-pm/blob/master/eg/calculator/lib/Precedence.pm>

The Shunting-yard algorithm simply takes a list of expression tokens and transforms them into an RPN stack. It uses information from a precedence/associativity table like the one above.

Unlike calculator1.pl where we evaluated as we parsed, calculator2.pl creates an RPN which is akin to an AST. In other words, it's more like something an actually language compiler would do.

But we are writing a calculator and we still need to evaluate this puppy. I changed the runner code to look like this:

    sub calc {
        my $expr = shift;
        my $calculator = pegex($grammar, 'Calculator');
        my $rpn = eval { $calculator->parse($expr) };
        my $result = RPN::evaluate($rpn);
        print $@ || "$expr = $result\n";
    }

So overall, this second solution was a bit more code, but also feels more solid on several levels.