CS 3120 Winter 2004 (Yang) Homework 1

due Jan. 14 -- because of the drawings and the start of the quarter, please turn this one in by hand, even if you create your document on the computer.

If you choose to write the assignment by hand, please print neatly. I'm drawing the diagrams using Dia, an open-source product which takes after Microsoft Visio.

1. Using the grammar in Fig. 3.3 of Pratt & Zelkowitz, write a parse tree for the following strings. Follow the example of Fig. 3.4. Make sure you are actually following the grammar -- it is tempting to skip steps. Remember that every node corresponds to one of the grammar rules.
   • i = 0
2. Using the grammar in Fig. 3.3, write the derivation for the following strings -- there is a simple example at the bottom of p. 91. Note that each step replaces exactly one nonterminal, and the derivation is continued until only terminals remain:
   • i = i + 1
3. Draw a syntax chart for the following -- you do not need to draw the charts for the nonterminals contained in the rules for these:
   • < subject > on p. 88
4. Write an EBNF grammar for:
   • an ISBN number for Prentice-Hall. Include the "ISBN" prefix.
   You can find information about the (current) structure of an ISBN here. Prentice-Hall being a US publishing house, its allocated numbers must start with a 0 for its country/area/language age code. Prentice-Hall's publisher code (as you can see on the back cover of your text) is 13.