CS 631, Fall 2009


Assignment #11: 10 points

Date Due: Monday, 12/7/09.


	Read sections 5.1-5.3, 6.1-6.2 & 6.4 of Aho.

(2)  1.	Construct the dependency graph for the annotated parse tree in
	Figure 5.3.  Give a topological sort for the nodes in the dependency
	graph.

(2)  2.	Rewrite the grammar rules for D & L in the SDD of Figure 5.8 as
	follows:
			D -> L id
			L -> L id , | T

	Note that the form of the declaration is the same for the modified
	grammar.  Give the semantic rules for the modified grammar
	and show that the type information in the modified definition can be 
	propagated using only synthesized attributes.  

(2)  3.	Exercise 5.2.3 (b).

(4)  4. Write a YACC/LEX program to implement the expression compiler in 
	Figure 6.20 for integer expressions.  Your program should produce
	three address code in the form of  valid C assignments, which can 
	be compiled and run to evaluate an assignment statement with an 
	integer expression for the right hand side. Add a grammar rule and
	translation scheme for multiplication with normal precedence and
	associativity.  Refer to aho/Fig8_15.gif for the original version
	of this translation scheme from the 1st edition of Aho.

	Use the declarations in aho/postfix/global.h and the code in
	aho/postfix/symbol.c to implement functions lookup() and newtemp()
	in place of the top.get() method and new Temp() constructor.  
	The symbol table defined by these routines is stored in a fixed 
	size array which contains the names of the symbols. (See Ch. 2)  
	The lookup() function returns the index where each identifier or 
	temporary is located.  If an identifier is new, lookup() returns 
	zero and the insert() function must be called to add the identifier 
	to the symbol table.  The attributes addr and lexeme are both
	integers, so yacc's default integer value stack can be used to 
	store the attributes.
	
	The newtemp() function inserts a temporary named $$n, where n 
	is the number of the temporary, into the next free location
	and returns the index for the temporary.  The gen() function
	can be replaced by printf() to output the desired three-address
	code in the form of a C assignment.  (Don't forget the semicolon!)
	The output should be written to a separate file rather than stdout. 
		
	Write a function called yywrap() which prints the contents of the
	symbol table at the end of the program listing.  The output from 
        the table should include the index and name of each entry in the table. 
	yywrap() is called by Lex and should return 1 to indicate the end 
	of input.

	Test your program on the expressions A := -B*(C+D) and also
	X := A*B+C*D-E*F.  Could you compile the resulting C code?
	Why or why not?**


      **For full credit, turn in well commented program listing and
	output from your computer run.