CS 3120 Winter 2005 (Yang) Homework 1

due Jan. 12 (10:30am -- collected in class -- no late submissions) -- 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 claims to be similar to 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, but for this question, start with <variable> at the root 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.
  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. [This example is intended to help you understand how grammars handle operator precedence. You may want to separately work out how "x = a + 2 - c" and/or "x = a * 2 + c" would be derived]
  3. Suppose we add a few grammar rules to the grammar in Fig. 3.3:
    <statement> ::= <if_stmt> | <assignment statement>
    <if_stmt> ::=     if ( <boolean expression> ) <statement>
         |     if ( <boolean expression> ) <statement> else <statement>

    Draw a syntax chart for <if_stmt> -- you do not need to draw the charts for the nonterminals contained in the rules for these. In particular, you will not need rules to recognize boolean expressions.

  4. Write additional EBNF rules to enable the grammar at the bottom of p. 88 to accept lists of subjects as subjects. We want to be able to accept as syntactically correct sentences like "The cat, the dog and the mouse ran home" or "Did A policeman and a judge cook dinner?" We keep the book's simplification that nouns come with articles, and in a list of subjects we do insert a comma between the last two subjects, even when there are more than 2 in the list.