CSE 401/M501 24sp Homework 2 - CFGs and LR Parsing

Due: Thursday, April 18 by 11:59 pm. Please use Gradescope (gradescope.com, also linked from the CSE 401/M501 resources web page) to submit your homework online. Gradescope's web site has several instructional videos and help pages to outline the process, and this guide has specific information about scanning and uploading pdf files containing assignments.

• Unreadable solutions cannot be graded--no blurry photos, poor contrast, or illegible handwriting, please.
• Type-written solutions are encouraged but not required.
• If possible, don't split the solution to a problem across a page break.

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) Consider the grammar:
   
   S ::= aSbS | bSaS | ε
   
   
   1. Show that this grammar is ambiguous by showing the steps in two distinct leftmost derivations for the sentence abab.
   2. Show that this grammar is ambiguous by showing the steps in two distinct rightmost derivations for the sentence abab.
   3. Draw the corresponding parse trees for your derivations.
   
   
2. (Aho, Sethi, Ullman) 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 and indicate whether each step is a shift, reduce, or accept action as we did with several shift-reduce parser examples in class. (You do not need to construct the LR parser DFA or tables for this.)
   4. Suppose we replace the left-recursive production L::=L,S with a right-recursive one L::=S,L. What general 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. (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". Your solution should use the English words in some essential way to show the ambiguity, not just something involving punctuation. (Hint: do not go overboard. This is not an exercise in computational linguistics or Natural Language Processing. If you've done "sentence diagrams" in grade school, that's the right level of complexity for the grammar here. If you are not familiar with sentence diagrams, wikipedia has an article that shows what we've got in mind - look at the later half of the article for example trees. Don't try to reproduce diagrams with exactly the same details, but that's the general idea. The idea is to have a bit of fun with grammars and explore ambiguities in the English language.)
   
   
4. 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). Similes 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?