CSE 401/M501 22sp (Mini-)Homework 3 - LL Grammars

Due: Wednesday, May 4 by 11 pm. NO late days allowed, so we can make solutions available in time to study for the midterm exam.

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. Consider the following grammar:
   
   A ::= s C n g | ε
   B ::= C r | t
   C ::= B i | t
   
   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