Implementing L-Attributed SDD\'s
Introduction: Since many translation applications can be addressed using L-attributed definitions, we shall consider their implementation in more detail in this section.
The following methods do translation by traversing a parse tree:
1. Build the parse tree and annotate. This method works for any noncircular SDD whatsoever. We introduced annotated parse trees in Section 5.1.2.
2. Build the parse tree, add actions, and execute the actions in preorder. This approach works for any L-attributed definition. We discussed how to turn an L-attributed SDD into an SDT in Section 5.4.5; in particular, we discussed how to embed actions into productions based on the semantic rules of such an SDD.
In this section, we discuss the following methods for translation during parsing:
3. Use a recursive-descent parser with one function for each nonterminal. The function for nonterminal A receives the inherited attributes of A as arguments and returns the synthesized attributes of A.
4. Generate code on the fly, using a recursive-descent parser.
5. Implement an SDT in conjunction with an LL-parser. The attributes are kept on the parsing stack, and the rules fetch the needed attributes from known locations on the stack.
6. Implement an SDT in conjunction with an LR-parser. This method may be surprising, since the SDT for an L-attributed SDD typically has actions in the middle of productions, and we cannot be sure during an LR parse that we are even in that production until its entire body has been constructed. We shall see, however, that if the underlying grammar is LL, we can always handle both the parsing and translation bottom-up.
Translation during Recursive-Descent Parsing:
A recursive-descent parser has a function A for each nonterminal A, as discussed in Section 4.4.1. We can extend the parser into a translator as follows:
a) The arguments of function A are the inherited attributes of nonterminal A.
b) The return-value of function A is the collection of synthesized attributes of nonterminal A.
In the body of function A, we need to both parse and handle attributes:
1. Decide upon the production used to expand A.
2. Check that each terminal appears on the input when it is required. We shall assume that no backtracking is needed, but the extension to recursive- descent parsing with backtracking can be done by restoring the input position upon failure, as discussed in Section 4.4.1.
3. Preserve, in local variables, the values of all attributes needed to compute inherited attributes for nonterminals in the body or synthesized attributes for the head nonterminal.
4. Call functions corresponding to nonterminals in the body of the selected production, providing them with the proper arguments. Since the underlying SDD is L-attributed, we have already computed these attributes and stored them in local variables.