Com Sci 221 --- Programming Languages
Assignment #2 --- Autumn 2000
Due Wednesday, 11 October

Make sure to follow the general instructions for performing and submitting homework.

This homework assignment has no programming component. Logistically, the nastiest part is drawing trees. You can do that in plain text, using ASCII symbols such as -, |, /, \ to draw lines. But, this would also be an excellent time to learn some method for producing PostScript documents. Xfig is one possibility.

I recommend that you work all of the problems at the end of Chapter 2 on pp. 49-52 of the text. I have assigned a selection of them:

1. Do problems 2.1, 2.2, and 2.3 on p. 49 of the text, but only parts c, d, and e.
2. Do problem 2.6 parts c, d, and e, and 2.7 part e on p. 49 of the text.
3. Describe, briefly but precisely, the meaning of each of the nonterminals <expression>, <term>, and <factor>. One sentence suffices for each. In this case, ``precisely'' means that your sentence makes it clear exactly which arithmetic expressions are and are not derived from the given nonterminal. But, your description must refer to intuitive concepts about arithmetic expressions, and not to the grammar. The point of the descriptions is to have an independent description of the meanings of the nonterminals, which can serve as a mechanism for understanding the grammar.
4. Do problem 2.12 on p. 51 of the text. Your grammar should assign to each correct C expression a parse tree that corresponds (after removing ``gimmicks'') to the abstract syntax of the expression.
5. Do problem 2.15 on p. 51 of the text.
6. Do problem 2.20 on p. 52 of the text. One or two sentences, plus a short example, should suffice for your answer.