Syntax-Directed Definition and Attribute Grammars
1. Syntax-Directed Definition
The syntax-directed definition is a generalization of a context-free grammar in which each grammar symbol has an associated set of attributes. These attributes are partitioned into two sets: synthesized attributes and inherited attributes.
2. Attribute
An attribute can represent a string, a number, a type, or a memory location. The value of an attribute at a parse tree node is defined by a semantic rule associated with the production used at that node.
3. Synthesized and Inherited Attributes
- Synthesized Attributes: The value of a synthesized attribute at a node is computed from the values of attributes at the children of that node in the parse tree.
- Inherited Attributes: The value of an inherited attribute at a node is computed from the values of attributes at the siblings and parent of that node.
4. Semantic Rules
Semantic rules set up dependencies between attributes that are represented by a graph. From the dependency graph, we derive an evaluation order for the semantic rules. Evaluation of semantic rules defines the values of attributes at the nodes in the parse tree for the input string.
Side Effects of Semantic Rules
- Printing a value
- Updating a global variable
5. Annotated Parse Tree
A parse tree showing the values of attributes at each node is called an annotated parse tree. The process of computing the attribute values at each node is called annotating or decorating the parse tree.
6. Syntax-Directed Definition Example
In a syntax-directed definition, each grammar production ( A \rightarrow \alpha ) has a set of semantic rules of the following form associated with it:
[ b := f(C1, C2, \ldots, Ck) ]
where ( f ) is a function, and either of the following conditions holds for ( b ):
- ( b ) is a synthesized attribute of ( A ), and ( C1, C2, \ldots, Ck ) are attributes belonging to the grammar symbols of the production, OR
- ( b ) is an inherited attribute of the grammar symbols on the right side of the production.
Example: The syntax-directed definition for the grammar:
[ \begin{aligned} E & \rightarrow E + T \mid T \ T & \rightarrow T * F \mid F \ F & \rightarrow (E) \mid id \end{aligned} ]
Synthesized attribute values are associated with each of the non-terminals ( E, T, ) and ( F ). The token digit has a synthesized attribute level whose value is assumed to be supplied by the lexical analyzer.
7. Attribute Grammar
An attribute grammar is a context-free grammar where we define attributes of all symbols in the production group. These attributes can be divided into two types: synthesized attributes and inherited attributes. Evaluation of attributes occurs at the nodes of the abstract syntax tree.
8. Synthesized Attributes
A syntax-directed definition that uses synthesized attributes exclusively is said to be an s-attributed definition. A parse tree for an s-attributed definition can always be annotated by evaluating the semantic rules for the attributes at each node, bottom-up from the leaves to the root.
Example: Consider the expression (3 5 + 4). The annotated parse tree for the input (3 5 + 4).
9. Inherited Attributes
An inherited attribute is one whose value at a node in a parse tree is defined in terms of attributes at the parent and/or siblings of that node. Inherited attributes are convenient for expressing the dependence of a programming language construct on the context in which it appears.
Example: The non-terminal ( T ) has a synthesized attribute type whose value is determined by the keyword in the declaration. The annotated parse tree for the sentence real id1, id2, id3.
10. Dependency Graph
The interdependencies among the inherited and synthesized attributes at the nodes in a parse tree can be depicted by a directed graph called a dependency graph.
Constructing a Dependency Graph
To construct a dependency graph, put each semantic rule into the form ( b = f(C1, C2, \ldots, CK) ) by introducing a dummy synthesized attribute ( b ) for each semantic rule that consists of a procedure call. The graph has a node for each attribute, and if attribute ( b ) depends on attribute ( c ), it has an edge to the node for ( b ) from the node for ( c ).
Algorithm:
- For each node ( n ) in the parse tree, construct a node in the dependency graph for each attribute of the grammar symbol at ( n ).
- For each semantic rule ( b := f(c1, C2, \ldots, CK) ), construct an edge from the node for ( C_i ) to the node for ( b ).
Example: Consider the production ( E \rightarrow E1 + E2 ) and the associated semantic rule ( E.val := E1.val + E2.val ).
Methods for Evaluating Semantic Rules
1. Parse Tree Methods
At compile time, these methods obtain an evaluation order from a topological sort of the dependency graph constructed from the parse tree for each input. These methods fail to find the evaluation order only if the dependency graph has a cycle.
2. Rule-Based Methods
At compiler construction time, the semantic rules associated with productions are analyzed. For each production, the evaluation order is predetermined at compile time.
3. Oblivious Methods
In this method, the evaluation order is chosen without considering the semantic rules. An oblivious evaluation order restricts the class of syntax-directed definitions that can be implemented. Rule-based and oblivious methods do not need to explicitly construct the dependency graph at compile time, making them more efficient in the use of compile time and space.
A syntax-directed definition is said to be circular if the dependency graph for some parse tree generated by its grammar has a cycle.