Due: Monday, April 14 at 11 pm. Please use the dropbox to submit your homework online. Please submit your work as some combination of PDF, plaintext, and PNG files. Please do not submit doc/docx files. You may submit a scanned copy of handwritten work, as long as it is legible and in one of the formats mentioned above. We suggest you show your work to help us award partial credit if appropriate, and for TA sanity.

1. Give an unambiguous grammar for each of the following languages. (Hint: If you're not sure, one way of verifying that a grammar is unambiguous is to run it through a LALR parser generator like Yacc, Bison, or CUP and get no conflicts. You are not required to do this, however.)
   
   
   1. Statement blocks in Pascal or ML where the semicolons separate the statements:
      { statement ; { statement ; statement } ; statement }
   2. Statement blocks in C or Java where the semicolons terminate the statements:
      { expression ; { expression ; expression ; } expression ; }
   3. Balanced parentheses and square brackets. Example:
      ([[](()[()][])])[]
   
   
2. Given the following grammar:
   
   S ::= ( L ) | x
   L ::= L , S | S
   
   1. Give a left-most derivation of (x, (x, x)) .
   2. Give a right-most derivation of (x, (x, x)) .
   3. Show the steps that a shift-reduce parser goes through when it parses (x, x, x). That is, show the contents of the stack and remaining input at each step.
   4. Suppose we replace the left-recursive production L::=L,S with a right-recursive one L::=S,L . What effect does this have on the depth of the stack during a shift-reduce parse? (You might work through the parse of (x, x, x) again to see what changes.)
      
      
3. This problem has been postponed to Homework 3. It remains here for reference, but you do not need to complete it for this homework assignment
   
   The following is a grammar that generates epithets (E). An epithet is a description (D). A description can be either a trait (T) or a simile (S). Similies are of the form "trait like animal" (A).
   (Note: please refer to slides E36 - E43, available here)
   
   E ::= D
   D ::= T | S
   S ::= T like A
   T ::= quick | strong
   A ::= bunny | ox
   
   
   1. Construct the LR(0) state diagram and parse table for this grammar.
   2. Calculate FIRST, FOLLOW, and nullable for each non-terminal.
   3. Construct the SLR parse table.
   4. Is this grammar LR(0)? SLR?
      
      
4. (Appel) Write a grammar for English sentences using the words
   

   time  arrow  banana  flies  like  a  an  the  fruit

   and the semicolon. Be sure to include all the senses (noun, verb, etc.) of each word. Then show that this grammar is ambiguous by exhibiting more than one parse tree for the sentence "time flies like an arrow; fruit flies like a banana".)