1. Appel, Chapter 8, 8.6,8.7 (you can use the definitions from your notes for this problem and just look at his algorithm on page 191; note the typo that the comment All the successor of b are marked is incorrect so cross it out. )

2. (Sethi-Ullman Algorithm)
2.a. Annotate the tree on the first slide of this file (note: this is slide 22 from the codeGeneration lecture notes) according the Sethi-Ullman algorithm to find the minimum number of registers needed to evaluate an expression.

2.b. Think about how our MIPS machine architecture differs from that explained in the assumptions of the original Sethi-Ullman algorithm. Design a Sethi-Ullman-like algorithm which will work on our MIPS architecture and determine the minimum number of registers needed to evaluate an expression using SPIM instructions.

2.c. Use your algorithm from part 2.b to evaluate the expression trees in the codeGeneration lecture class notes shown here.

3. (Top Down Parsing- taken from Aho,Sethi,Ullman Chap 4 exercises) Given the following grammar

	E::=	S
	S::= 	(L)
	S::= 	a
	L::=	L,S
	L::=	S

3.a. What are the terminals, nonterminal and start symbol of this grammar?

3.b. Show parse trees for the following sentences:

	i. (a,a) ii. (a, (a,a)) iii. (a,((a,a),(a,a)))

3.c. Eliminate left recursion from this grammar.

3.d. Build a predictive parser for this grammar. Show the behavior of the parser on the sentences in part b. (i.e., give the list of states,inpus the recognition computation goes through).

Prepared by Barbara Ryder at 11:16am on April 20, 1999.