CSE P 501 Homework 3 - LR Construction & LL Grammars

Due: Monday, Jan. 25 by 11 pm. Please use the dropbox linked from the CSE P 501 homework web page to submit your homework online. You should turn in a single pdf file named hw3_answers.pdf. Scanned copies of hand-written documents are fine if they are legible and easy to read when printed on ordinary size paper, and as long as the total file size is no more than 3 MB or so. Note that a picture of a hand-written solution taken with a phone is very likely to produce a file that is not legible when printed, and unreadable submissions will not be graded. 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) 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 generates.
   
   
   
2. Write a grammar that generates the straight-line code language 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. (moved from HW2). 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?