Course Homepage

HW16

Define a grammar for arithmetic expressions given in reverse Polish notation, that preserves its syntactic structure, i.e., syntax trees will capture the order of operations when walking the tree.

• Terminals: + - * / 0 1 2 3 4 5 6 7 8 9
• You can use N -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Answer these questions:

1. What are the nonterminals?
2. What are the productions?
3. What is the starting nonterminal?
4. Does this grammar have ambiguity?