D.3 Problems for Chapter 6: Type Checking

D.3.1 Type as Attribute

In Pascal language, a programmer can declare two integer variables a and b with the syntax

var a,b: int

This declaration might be described with the following grammar:

decl   –> var idlist : typeid
idlist –> idlist , ID
idlist –> ID

Write an attribute grammar that assigns the correct data type to each declared variable. (You may have to rewrite the grammar.) Determine an evaluation order of the attributes irrespective of the way the parse tree is constructed. Can this translation be performed in a single pass over the parse tree as it is created?

Solution: The grammar would require an inherited attribute for passing the type of the identifier to the top of the parse tree where the idlist non-terminal is rooted. This inherited attribute causes all sort of problems, the important one being that it would preclude the evaluation in a single pass if the tree were created using a bottom-up and left-to-right parsing approach.

The best way would be to change the grammar as indicated below, where all the attributes would be synthesized and hence allow the evaluation of the attribute in a single pass using the bottom-up left-to-right parsing approach.

decl  –> var ID list            ID.type    = list.type
list0 –> , ID list1             ID.type    = list0.type
                                list1.type = list0.type
list0 –> : typeid               list0.type = typeid.value