Assignment 1 Solution

Q1 (5 pts): Consider a slightly generalized version of the attribute grammar for simple expressions, based on the following context-free grammar.

hS i ::= hE i

hE i ::= const j hI i j ( hE i1 + hE i2 ) j let hI i = hE i1 in hE i2 end hI i ::= id

Assume that terminal const represents integer constants and has an attribute lexval of type integer, representing the value of the constant. Similarly to id.lexval, the value of const.lexval is initialized by the lexical analyzer. (The lexical analyzer is also referred to as \scanner".) The evaluation rule for hE i ::= const is as expected: hE i.val := const.lexval. The rest of the attributes and their evaluation rules are as discussed in class.
Consider the following input program:

let x = 3 in let x = ( x + let x = x in x end ) in ( x + x ) end end

Is this a valid string for the attribute grammar? If so, show the parse tree for this string and all attribute values at tree nodes. If not, explain why not.

Q2 (10 pts): Consider a simple language with Java-like labels

hprogrami ::= hci
hci1 ::= hci2 ; hci3 j while hbei do hci2 end j hlabeli : while hbei do hci2 end
• break j break hlabeli hlabeli ::= id

In addition to regular while loops, this language also has labeled while loops. The labels are represented by nonterminal hlabeli. Similarly, the language has break statements with labels. Such a break exits its surrounding loop that has that same label. For example, for

L: while b1 do while b2 do .... break; .... break L; ... end end

the outer loop is labeled with label L and the inner loop is not labeled. The rst break exits the inner loop. The second break exits the outer loop (i.e., the loop with label L).

A break with a label can be nested inside several loops that surround it (e.g., an innermost loop, which itself is nested in an outer loop, which itself is nested in another loop, etc.). Such a break only makes sense if there exists a surrounding loop with the same label. Another correctness condition is the following: for any labeled loop, there should not exist

1

a surrounding labeled loop with the same label. Write an attribute grammar to check these two validity conditions. Include a description of all attributes, evaluation rules for attributes, and conditions. Use Cond in your grammar to perform the necessary checks. Assume that hlabeli has a pre-de ned attribute name giving the label’s string name (e.g., \L" in the example); you do not have to de ne this attribute. Any attributes you de ne should be inherited.

Q3 (10 pts) Consider the following generalization of the type-checking example discussed in class:

hintexpi ::= . . . j hintexpi - hintexpi j hintexpi * hintexpi hboolexpi ::= . . . j hintexpi = hintexpi hstmti ::= . . . j return hintexpi

hformalslisti ::= hformali j hformali , hformalslisti hformali ::= int id j bool id
hactualslisti ::= hactuali j hactuali , hactualslisti hactuali ::= hintexpi j hboolexpi

Here : : : represents production alternatives already discussed in class. In the new grammar we add operators \subtraction", \multiplication", and \equality" for integer expressions, as well as a return statement to return an integer value from a function call. In addition, non-terminals hformalslisti and hactualslisti|which were brie y discussed in class|are precisely de ned.

Part 1 (2 pts): Write the necessary attribute grammar rules (if any) for production alternatives hstmti ::= return hintexpi, hintexpi ::= hintexpi - hintexpi, hintexpi ::= hintexpi * hintexpi, and hboolexpi ::= hintexpi = hintexpi

Part 2 (3 pts): In the lecture notes, there is an informal description of an attribute types for hformalslisti. Write the attribute grammar rules for computing this attribute.
Part 3 (5 pts): In the lecture notes, there is an informal description of an inherited attribute expectedTypes for hactualslisti. At hintexp i ::= id ( hactualslisti ) the value of this attribute for the hactualslisti node is obtained from information about function id, which itself is provided by attribute tbl-stack; helper function paramtypes looks up this information.

Describe informally how attribute expectedTypes should be used to perform type check-ing of the actual parameters at the call site. As discussed in class, the basic idea is to make sure that the expected type of each actual parameter is indeed correct (e.g., if the expected type is INT, the actual parameter should be an hintexpi). Based on your approach, write all evaluation rules for this attribute, as well as for all other attributes of nodes of type hactuali (if necessary). Do not introduce additional attributes for hactualslisti.










2