CS 331, Spring 2008


Assignment #4: 10 points

Date Due: Friday, 2/22/08.


Reading Assignment: Sections 3.1-3.3 of Sebesta.


(2)  1. Problem 3.13.  Draw a parse tree for the string aabb, as derived
        from your grammar.


(2)  2.	The "dangling else" ambiguity is illustrated by parsing the following
	sentencial form in Figure 3.5:

	if <logic_expr> then if <logic_expr> then <stmt> else <stmt>

	Show how the dangling else 'if' statement is parsed using the 
	unambiguous grammar on page 131.   Which of the parse trees in Figure 
	3.5 corresponds to the matching of the else clause using the unambiguous
	grammar?

(2)  3. Suppose B is a boolean variable.  In the following C 'if' statement,
	what value is assigned to X when B is: (a) true and (b) false.
	Explain your answers.

	if (B) if (B) X=0; else X=1;

(2)  4. Using the ANSI C grammar, draw a parse tree to show how the following 
	<expression> is evaluated in C.  Show the order of evaluation as
	determined from the parse tree by inserting parentheses in the
	expression.  

		*x*=*x+++*x

	Hint: The lexical analyzer matches lexemes to the longest string 
	which is a valid token.
		
(2)  5.	Using the BNF grammar of Example 3.5, give the parse tree and the
	value of the following expression in which numbers are used in 
	place of ids: 2 ** 3 ** 2  

	Extra Credit:  Take the quiz at: 
	http://www.malevole.com/mv/misc/killerquiz/ and report your score.