It’s equally easy to write a parser for the postfix version. Again we’ll start with a recogniser. The recogniser has a counter initialised to 0. When it reads a module name it increments the counter. When it reads an ∧ or an ∨ it decrements the counter. When it reads a ¬ 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 ∧ Algebra Geometry ∧ ∨” decorated with the values of the counter at each stage:
0 Probability 1 Statistics 2 ∧ 1 Algebra 2 Geometry 3 ∧ 2 ∨ 1Constructing an abstract syntax tree 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, while the parse tree again differs only in the order in which the children of each node are listed.