Due: Monday, April 21 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. You should do this assignment individually.

1. (Cooper & Torczon Sec. 3.3 ex. 5, 2nd ed / ex. 2, 1st ed) Consider the following grammar:

        A ::= B a
        B ::= dab
        B ::= C b
        C ::= c B
        C ::= A c 
   

   Does this grammar satisfy the LL(1) condition? Justify your answer. If it does not, change the grammar to make it LL(1) without changing the language that it describes.
   
   
   
2. This homework question is being postponed for a week. Do not turn it in with this homework assignment
   
   Write a grammar that accepts the language of straight-line code - no IFs or LOOPs - 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
   

3. This is problem 3 from homework 2, which has been postponed.
   
   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?