Due: Monday, February 4 by 11:59 pm. Please use the dropbox linked from the CSE401 homework web page to submit your homework online. Any common format like pdf or doc/docx is fine, or you can submit a scanned copy of your work as long as it is legible. 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. (Aho, Sethi, Ullman, 1st edition) Consider the grammar:
   S ::= aSbS | bSaS | epsilon
   
   1. Show that this grammar is ambiguous by constructing two leftmost derivations for the sentence abab.
   2. Show that this grammar is ambiguous by constructing two rightmost derivations for the sentence abab.
   3. Construct the corresponding parse trees for your derivations.
   
   
2. Given the following grammar:
   
   S ::= ( S ) | [ S ] | x
   
   
   1. Build an LR(0) parser DFA for this grammar. Be sure to show the items for each state of your automaton.
   2. Build the LR(0) parse tables (action and goto) for this grammar.
   3. Show the steps that an LR(0) shift-reduce parser goes through when it parses ([(x)]). That is, show the contents of the stack and remaining input at each step.
   4. Show the steps that an LR(0) shift-reduce parser goes through when it attempts to parse ([x)]. Does it identify an error? When?
   
   
3. 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).
   
   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".)
   
   Hint: See this discussion thread from a couple years ago for some tips.