CSE 401 Au11 (Mini)Homework 3 - LL Grammars

Due: Thursday, October 27 by 11 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. (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. Write a grammar that accepts 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