Correctness requires more than avoiding ambiguity
Correctness requires more than avoiding ambiguity 
Assignment #2, due 11 October (Mike O'Donnell)
Assignment #2: questions (Michael C. Brizic)
question about the expression grammar (Michael C. Brizic)
|
In addition to writing out the expression grammar, do we actually need to draw a parse tree for each expression or are we using the idea of being able to match the parse tree to the abstract syntax tree to make sure our grammar is unambiguous?I think that you're asking about problem 2.12 on p. 51 of the text. But in that case, I can't make sense of your question about drawing ``a parse tree for each expression,'' since there is an infinite number of different possible expressions. Notice that 2.13 is not assigned. In any case, 2.12 calls for a grammar, and not for parse trees. If you make the grammar clearly correct, there's no need for any supporting material. If you like, you may illustrate the use of the grammar on a small number of key examples. If you're at all unsure, then it's certainly a good idea to do some examples on your own, but you probably don't need to include them in your submission.
Although you don't need to submit parse trees, you certainly need to understand how particular grammars produce particular parse trees which enforce particular precedence and associativity rules. There's much more to it than making sure the grammar is unambiguous. ``Unambiguous'' just means that it produces a unique parse for each correct expression. Your grammar must produce a correct parse for each correct expression, reflecting the precedence and associativity rules given in Figure 2.9. If this puzzles you, then look back at the grammar for expressions in Figure 2.6 on p. 42, and work out (through examples of parse trees) how it enforces precedence for * and / over + and -, as well as left-associativity for all the operators. Mike O'D. |
to: