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

Due: Thursday, April 21 by 11 pm. Submit online via Gradescope (gradescope.com). (Review instructions given in Homework 1, as needed, especially regarding legibility of scanned solutions.)

• 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.
   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. Consider the two-production "if-else" grammar shown on slide D-39 of the LR parsing slides.
   1. Explain why this grammar is not "reduced" in the sense defined on slide C-24 of the Grammars slides.
   2. Adding rules numbered zero and 3:

      0.  S' ::= S$
      3.  S  ::= a

      does result in a reduced grammar (you need not prove it). Complete the LR(0) state machine construction sketched on slide D-39 for this 4-rule grammar.
   3. Build the LR(0) action and goto tables for it, highlighting the shift/reduce conflict. (Grading will be facilitated if everyone numbers their states in the same way. Use 1 and 0 as the numbers for the states containing items S'::= dot S$ and S'::= S dot $, respectively. Number others in the order that they would be reached by following transitions from state 1 on "ifthen S else S" in that order, with remaining states numbered arbitrarily.)
   4. Calculate Nullable, FIRST and FOLLOW for the nonterminals in this grammar.
   5. The SLR action table for this grammar will remove some of the reduce actions from the LR(0) table. Which ones? Does this remove the shift/reduce conflict?


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). 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?