Implement each of your SDD”s of Exercise 5.4.4 with an LL parser in the style of Section 5.5.3, with code generated “on the fly.”
Exercise 5.4.4 : Write L-attributed SDD”s analogous to that of Example 5.19 for the following productions, each of which represents a familiar flow-of-control construct, as in the programming language C. You may need to generate a three-address statement to jump to a particular label L, in which case you should generate goto L.
Note that any statement in the list can have a jump from its middle to the next statement, so it is not sufficient simply to generate code for each statement in order.
5.5.3 L-Attributed SDD”s and LL Parsing
Suppose that an L-attributed SDD is based on an LL-grammar and that we have converted it to an SDT with actions embedded in the productions, as described in Section 5.4.5. We can then perform the translation during LL parsing by extending the parser stack to hold actions and certain data items needed for attribute evaluation. Typically, the data items are copies of attributes. In addition to records representing terminals and non-terminals, the parser
stack will hold action-records representing actions to be executed and synthesize- records to hold the synthesized attributes for non-terminals. We use the following two principles to manage attributes on the stack:
1. The inherited attributes of a nonterminal A are placed in the stack record that represents that nonterminal. The code to evaluate these attributes will usually be represented by an action-record immediately above the stack record for A; in fact, the conversion of L-attributed SDD”s to SDT”s ensures that the action-record will be immediately above A.
2. The synthesized attributes for a nonterminal A are placed in a separate synthesize-record that is immediately below the record for A on the stack.
This strategy places records of several types on the parsing stack, trusting that these variant record types can be managed properly as subclasses of a “stack-record” class. In practice, we might combine several records into one, but the ideas are perhaps best explained by separating data used for different purposes into different records.
Action-records contain pointers to code to be executed. Actions may also appear in synthesize-records; these actions typically place copies of the synthesized attribute(s) in other records further down the stack, where the value of that attribute will be needed after the synthesize-record and its attributes are popped off the stack.
Let us take a brief look at LL parsing to see the need to make temporary copies of attributes. From Section 4.4.4, a table-driven LL parser mimics a leftmost derivation. If w is the input that has been matched so far, then the
stack holds a sequence of grammar symbols a such that where S lm is the start symbol. When the parser expands by a production A -+ B C, it replaces A on top of the stack by B C. Suppose nonterminal C has an inherited attribute C. i. With A -+ B C, the inherited attribute C. i may depend not only on the inherited attributes of A, but
on all the attributes of B. Thus, we may need to process B completely before C. i can be evaluated. We therefore save temporary copies of all the attributes needed to evaluate C. i in the action-record that evaluates C. i. Otherwise, when the parser replaces A on top of the stack by B C, the inherited attributes of A will have disappeared, along with its stack record. Since the underlying SDD is L-attributed, we can be sure that the values
of the inherited attributes of A are available when A rises to the top of the stack. The values will therefore be available in time to be copied into the action-record that evaluates the inherited attributes of C. Furthermore, space for the synthesized attributes of A is not a problem, since the space is in the synthesize-record for A, which remains on the stack, below B and C, when the parser expands by A → B C. As B is processed, we can perform actions (through a record just above B on the stack) that copy its inherited attributes for use by C, as needed, and after B is processed, the synthesize-record for B can copy its synthesized attributes for use by C, if needed. Likewise, synthesized attributes of A may need temporaries to help compute their value, and these can be copied to the synthesize-record for A as B and then C are processed. The principle that makes all this copying of attributes work is: All copying takes place among the records that are created during one expansion of one nonterminal. Thus, each of these records knows how far below it on the stack each other record is, and can write values into the
records below safely. The next example illustrates the implementation of inherited attributes during LL parsing by diligently copying attribute values. Shortcuts or optimizations are possible, particularly with copy rules, which simply copy the value of one attribute into another. Shortcuts are deferred until Example 5.24,. which also illustrates synthesize-records.