6.2 IMPLEMENTATION OF THE TRANSLATIONS SPECIFIED BY SYNTAX-DIRECTED DEFINITIONS
Attributes are associated with the grammar symbols that are the labels of the parse tree nodes. They are thus associated with the construct's parse tree translation specification. Therefore, when a semantic rule is evaluated, the parser computes the value of an attribute at a parse tree node. For example, a semantic rule could specify the computation of the value of an attribute val that is associated with the grammar symbol X (a labeled parse tree node). To refer to the attribute val associated with the grammar symbol X, we use the notation X.val. Therefore, to evaluate the semantic rules and carry out translations, we must traverse the parse tree and get the values of the attributes at the nodes computed. The order in which we traverse the parse tree nodes depends on the dependencies of the attributes at the parse tree nodes. That is, if an attribute val at a parse tree node X depends on the attribute val at the parse tree node Y, as shown in Figure 1, then the val attribute at node X cannot be computed unless the val attribute at Y is also computed.
Hence, carrying out the translation specified by the syntax-directed definitions involves:
-
Generating the parse tree for the input string W,
-
Finding out the traversal order of the parse tree nodes by generating a dependency graph and doing a topological sort of that graph, and
-
Traversing the parse tree in the proper order and getting the semantic rules evaluated.
If the parse tree attribute's dependencies are such that an attribute of node X depends on the attributes of nodes generated before it in the parse tree-construction process, then it is possible to get X's attribute value during the parsing itself; the parser is not required to generate an explicit parse tree, and the translations can be carried out along with the parsing. The attributes associated with a grammar symbol are classified into two categories: the synthesized and the inherited attributes of the grammar symbol.
Synthesized Attributes
An attribute is said to be synthesized if its value at a parse tree node is determined by the attribute values at the child nodes. A synthesized attribute has a desirable property; it can be evaluated during a single bottom-up traversal of the parse tree. Synthesized attributes are, in practice, extensively used. Syntax-directed definitions that only use synthesized attributes are shown below:
These definitions specify the translations that must be carried by the expression evaluator. A parse tree, along with the values of the attributes at the nodes (called an "annotated parse tree"), for an expression 2+3*5 is shown in Figure 2.
Syntax-directed definitions that only use synthesized attributes are known as "S-attributed" definitions. If translations are specified using S-attributed definitions, then the semantic rules can be conveniently evaluated by the LR parser itself during the parsing, thereby making translation more efficient. Therefore, S-attributed definitions constitute a subclass of the syntax-directed definitions that can be implemented using an LR parser.
Inherited Attributes
Inherited attributes are those whose initial value at a node in the parse tree is defined in terms of the attributes of the parent and/or siblings of that node. For example, syntax-directed definitions that use inherited attributes are given below:
A parse tree, along with the attributes' values at the parse tree nodes, for an input string int id1,id2,id3 is shown in Figure 3.
Inherited attributes are convenient for expressing the dependency of a programming language construct on the context in which it appears. When inherited attributes are used, then the interdependencies among the attributes at the nodes of the parse tree must be taken into account when evaluating their semantic rules, and these interdependencies among attributes are depicted by a directed graph called a "dependency graph". For example, if a semantic rule is of the form A.val = f(X.val,Y.val,Z.val)—that is, if A.val is function of X.val, Y.val, and Z.val)-and is associated with a production A → XYZ, then we conclude that A.val depends on X.val, Y.val, and Z.val. Therefore, every semantic rule must adopt the above form (if it hasn't already) by introducing a dummy, synthesized attribute.
Dummy Synthesized Attributes
If the semantic rule is in the form of a procedure call fun(al,a2,a3,…, ak), then we can transform it into the form b = fun(a1,a2,a3,…, ak), where b is a dummy synthesized attribute. The dependency graph has a node for each attribute and an edge from node b to node a if attribute a depends on attribute b. For example, if a production A → XYZ is used in the parse tree, then there will be four nodes in the dependency graph—A.val, X.val, Y.val, and Z.val—with edges from X.val, Y.val, and Z.val to A.val.
The dependency graph for such a parse tree is shown in Figure 4. The ellipses denote the nodes of the dependency graph, and the circles denote the nodes of the parse tree.
This topological sort of a dependency graph results in an order in which the semantic rules can be evaluated. But for reasons of efficiency, it is better to get the semantic rules evaluated (i.e., carry out the translation) during the parsing itself. If the translations are to be carried out during the parsing, then the evaluation order of the semantic rules gets linked to the order in which the parse tree nodes are created, even though the actual parse tree is not required to be generated by the parser. Many top-down as well as bottom-up parsers generate nodes in a depth-first left-to-right order; so the semantic rules must be evaluated in this same order if the translations are to be carried out during the parsing itself. A class of syntax-directed definitions, called "L-attributed" definitions, has attributes that can always be evaluated in depth-first, left-to-right order. Hence, if the translations are specified using L-attributed definitions, then it is possible to carry out translations during the parsing.
|
