Polish Notation

To try out mpc we’re going to implement a simple grammar that resembles a mathematical subset of our Lisp. It’s called Polish Notation and is a notation for arithmetic where the operator comes before the operands.

For example…

1 + 2 + 6is+ 1 2 6
6 + (2 9)is+ 6 ( 2 9)
(10 2) / (4 + 2)is/ ( 10 2) (+ 4 2)

We need to work out a grammar which describes this notation. We can begin by describing it textually and then later formalise our thoughts.

To start, we observe that in polish notation the operator always comes first in an expression, followed by either numbers or other expressions in parentheses. This means we can say “a program is an operator followed by one or more expressions,” where “an expression is either a number, or, in parentheses, an operator followed by one or more expressions“.

More formally…

Programthe start of input, an Operator, one or more Expression, and the end of input.
Expressioneither a Number or ‘(‘, an Operator, one or more Expression, and an ‘)’.
Operator‘+’, ‘-‘, ‘*’, or ‘/‘.
Numberan optional -, and one or more characters between 0 and 9