1. Given the following grammar, we will build an LR(1) parser.

	D::= 	T L
	L::= 	L, I
	L::=	I
	I::=	*I
	I::=	id
	T::=	int | char

1.a Form the parser graphically as a set of states with goto edges between them.

1.b Fill in a transition table for the LR(1) parser for this language. You should have States in the first column followed by a column each for each terminal symbol: * , char int id $. Then show the three goto columns for T, L, I.

2. The following code fragment shows numbered calls between four procedures including the main program in a block structured language without parameters.

{/* main */
 	... 
	void p(){
		void q(){ ... if () /*3*/ p();...}
		...
		/*2*/ q();
		}
	void r(){
		/*5*/ p();
		...
	}
	/*1*/ p();
	/*4*/ r();
	...
}

2.a Draw the procedure activation tree for this program.

2.b Pictorially show the display and runtime stack as you execute each call and then eventually each return. If values have to be saved in the run-time stack identify where and when this is done.

2.c Give an example of an illegal call in the context of this program.

3. Using the small factorial function in C we showed translated into SPIM as test data, do exercise 6.1.a and 6.2 from your Appel textbook.

Prepared by Barbara Ryder at 6:00pm on April 4, 1999.