198:415 - Compilers
Spring 1999
Professor Barbara G. Ryder

Attribute Grammar Problems


1. Given the following grammar, add attributes and semantic actions so that we can enter each identifier into the symbol table with the appropriate type. If an illegal type is given, use the attributes to reject that statement as syntactically incorrect.

Show decorated parse trees for the following inputs:


	x, y, z: int
	a, b : float

Grammar from class notes:


	D ::= id L
	L ::= , id L | : T
	T := int | char | real | bool

2. Using the example in your class notes as a guide, write a grammar that recognizes arithmetic expressions which can include the operations { * + } with integer constant operands. Your grammar should allow parenthesized expressions as well. Add attributes to your grammar so that at each intermediate node in the parse tree, you can report the number of each operator recognized so far in the part of the input already parsed (i.e., num+ and num* might be good attribute names; for example, after recognition of 1+2 then num+=1 and num*=0).

a. Identify the kind of attributes you have defined.

b. Show a decorated parse tree for the following:


	1 + 2 * (3 + 4)

	1 * 2 * (-3) * 4

	1 - 2	

Prepared by Barbara Ryder at 12:08pm on February 23, 1999.