CSE 401/M501 18au Homework 3 - LR & LL Grammars & Parsing

Due: Monday, October 29 by 11 pm. You may use at most one (1) late day for this assignment even if you have more late days remaining. This will allow us to hand out sample solutions on Wednesday in class so people can prepare for the midterm exam on Friday.

Please use Gradescope (linked from the CSE 401 web page) to submit your homework online. Gradescope's web site has several instructional videos and help pages to outline the process, and this guide has specific information about scanning and uploading pdf files containing assignments.

Unreadable solutions cannot be graded--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.

Hint: For the last two problems, be sure to read the details of the left-recursion removal algorithms in the textbook before you work on them. Also, for these problems, there may be more than one way to solve the problem, and you will have to decide where (or if) to introduce additional non-terminals and the order in which to process productions.

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