It’s equally easy to write a parser for the postfix version. Again we’ll start with a checker. The checker has a counter initialised to 0. When it reads a module name it increments the counter. When it reads an “and” or an “or” it decrements the counter. When it reads a “not” it does nothing. If the counter remains positive until the end of the input, and is equal to 1 there, then the input is grammatically correct. Otherwise it is not.
Here is the input “Probability Statistics and Algebra Geometry and or” decorated with the values of the counter at each stage:
0 Probability 1 Statistics 2 and 1 Algebra 2 Geometry 3 and 2 or 1Constructing an abstract syntax tree from the checker is similar to the case of the prefix language. The nodes correspond to sequences of tokens where the value of the counter is 1 higher at the end than the start and is always higher in between than at the start, and we label each node with its final token. The abstract syntax tree for the input above is the same as for the corresponding input for the prefix parser, assuming we’re using the version where each node is labelled with a single token rather than the whole phrase.