CSE 401 - Homework Assignment #2

Due: Friday October 17 (at the beginning of class)

The problems marked (A) are required of All students; those marked (R) are only required for those doing the Reduced (MiniJava--) project.

  1. [10 points] (R) Write an unambiguous grammar for the following language: Balanced parentheses and square brackets. Example:


    One way (but not the only way) of verifying that a grammar is unambiguous is to run it through Yacc, the UNIX parsing tool, and get no conflicts.

  2. [15 points] (A) Write a grammar that accepts the straight line code language given below, but that is suitable for LL(1) parsing. That is, eliminate the ambiguity, eliminate the left recursion, and (if necessary) left-factor.

S ::= S ; S
S ::= id := E
S ::= print( L )
E ::= id
E ::= num
E ::= E + E
E ::= ( S, E)
L ::= E
L ::= L , E

  1. (R) For the grammar

S ::= E $
E ::= id
E ::= ( E )
E ::= E + id

  1. [10 points] Build the LR(0) DFA

  2. [5 points] Show the parse for: ((id+id+(id)))

  1. (Strongly recommended, but not required for anybody, not to be turned in)
    Consider the following MiniJava statement:

while (x < 3+4*5) {
    y = new C().test(a,b,c);

  1. Draw the concrete syntax tree for this statement. Use the MiniJava grammar embedded in the Parser/minijava.cup file.

  2. Draw the abstract syntax tree for this statement, labelling each AST node with the name of an AST node class from the MiniJava compiler and labelling each child edge with the name of an instance variable of the parent node’s class.

Produce a hard-copy of your answers and turn them in by the start of class