Semantic Rules with Controlled Side Effects
Introduction: Translations involve side effects: a desk calculator might print a result; a code generator might enter the type of an identifier into a symbol table. With SDD's, we strike a balance between attribute grammars and translation schemes. Attribute grammars have no side effects and allow any evaluation order consistent with the dependency graph. Translation schemes impose leftto-right evaluation and allow semantic actions to contain any program fragment;
We shall control side effects in SDD's in one of the following ways:
- Permit incidental side effects that do not constrain attribute evaluation. In other words, permit side effects when attribute evaluation based on any topological sort of the dependency graph produces a "correct" translation, where "correct" depends on the application.
- Constrain the allowable evaluation orders, so that the same translation is produced for any allowable order. The constraints can be thought of as implicit edges added to the dependency graph.
As an example of an incidental side effect, let us modify the desk calculator of Example 5.1 to print a result. Instead of the rule L.val = E.val, which saves the result in the synthesized attribute L.val, considers:
1) L E n print (E.val)
Semantic rules that are executed for their side effects, such as print (E.val), will be treated as the definitions of dummy synthesized attributes associated with the head of the production. The modified SDD produces the same translation under any topological sort, since the print statement is executed at the end, after the result is computed into E.val.
Example:The SDD in Fig. 5.8 takes a simple declaration D consisting of a basic type T followed by a list L of identifiers. T can be int or float. For each identifier on the list, the type is entered into the symbol-table entry for the identifier. We assume that entering the type for one identifier does not affect the symbol-table entry for any other identifier. Thus, entries can be updated in any order. This SDD does not check whether an identifier is declared more than once; it can be modified to do so.
Nonterminal D represents a declaration, which, from production 1, consists of a type T followed by a list L of identifiers. T has one attribute, T.type, which is the type in the declaration D. Nonterminal L also has one attribute, which we call ink to emphasize that it is an inherited attribute. The purpose of L.inh is to pass the declared type down the list of identifiers, so that it can be added
to the appropriate symbol-table entries. Productions 2 and 3 each evaluate the synthesized attribute T.type, giving it the appropriate value, integer or float. This type is passed to the attribute L.inh in the rule for production 1. Production 4 passes L.inh down the parse tree. That is, the value L\.inh is computed at a parse-tree node by copying the value of L.inh from the parent of that node; the parent corresponds to the head of the production.
Productions 4 and 5 also have a rule in which a function add Type is called with two arguments:
1. id.entry, a lexical value that points to a symbol-table object, and
2. L.inh,the type being assigned to every identifier on the list.
We suppose that function addType properly installs the type L.inh as the type of the represented identifier.
A dependency graph for the input string float idi , i d2 , i d3 appears in Fig. 5.9. Numbers 1 through 10 represent the nodes of the dependency graph. Nodes 1, 2, and 3 represent the attribute entry associated with each of the leaves labeled id. Nodes 6, 8, and 10 are the dummy attributes that represent the application of the function addType to a type and one of these entry values. Node 4 represents the attribute T.type, and is actually where attribute evaluation begins. This type is then passed to nodes 5, 7, and 9 representing L.inh associated with each of the occurrences of the nonterminal L.