We could emit the postfix string using the following translation scheme from Compilers Principles, Techniques, and Tools:

expr -> expr + term { print('+') }
expr -> expr - term { print('-') }
expr -> term
term -> 0           { print('0') }
term -> 1           { print('1') }
...
term -> 9           { print('9') }

We note in using this technique that the postfix expression is output incrementally. We also note that the semantic action is performed after the left and right subtrees have been visited.

Parsing

parsing - is the process of deciding if a given string is in the language of a given grammar. There are several parsing methods that can be used to determine if a string of tokens can be generated by a grammar. Some parsing methods actually generate a parse tree while others do not.

Parsing methods fall into two basic categories:

top-down - the parse tree is built from the root node and proceeds down.

bottom-up - the parse tree is built starting at the leaves and proceeding up toward the root.

A grammar that generates a subset of Pascal data types (2.8 on p. 41) might look like the following:

type -> simple | ^id | array [simple] of type
simple -> integer | char | num .. num 

Constructing a parse tree using the top-down method is as follows:

Create a node N corresponding with nonterminal A. Construct the children for node N using one of the productions for nonterminal A.

Find the next node at which a subtree needs to be constructed and repeat the process.

P#1: Show the steps in constructing the parse tree for the string array [num .. num] of char.

Note: In some cases the parse tree can be constructed with a simple left to right scan of the input string with a certain number of lookahead symbols. We will get into parsing in greater detail later on in the course.