CSE 401 15wi (Mini) Homework 3 - LL Grammars & Parsing

Due: Sunday, February 8 by 11 pm. No late assignments accepted, even if you have late days remaining so we can discuss solutions before the midterm on Wednesday, February 9. Please use the dropbox linked from the CSE401 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.

(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.
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
```