Syntax-Directed Definations

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 partitioned into two sets, the synthesized attributes and inherited attributes of that grammar.

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

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. 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 will be 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.

Semantic rules may have side effects like 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

In a syntax-directed definition, each grammar production A has a set of semantic rules of the following form associated with it.

b: = f(C1,C2, ……., Ck)

where f is a function, and either of the following conditions holds good for b.

(i) b is a synthesized attribute of A and C1, C2, ……., Ck are attributes belonging to the grammar symbols of the production OR

(ii) b is an inherited attribute of the grammar symbols on the right side of the production.

In both cases, attribute b depends on attributes c1, C2, ……., Ck

Example: The syntax-directed definition given in the Table for the grammar is:

E->E+T|T

TT * F |F

F -> (E) |id

 

Synthesized attribute value is 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. An evaluation of attributes occurs at the nodes of the abstract syntax tree.

8. Synthesized Attributes

• 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.

• The syntax-directed definition given in Table 4.2 is the S-attributed definition for the desk calculator. Consider the expression 3 * 5 + 4 n. 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.

value of L.in at the three L-nodes gives the type of the identifiers id1, id2, and id3.

These values are determined by computing the value of the attribute T.type at the left child of the root, and then evaluating L.in top-down at the three L-nodes in the right subtree of the root.

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.

• To construct a dependency graph, we put each semantic rule into the form b = f( C1, C2, ……., 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 in case attribute b depends on attribute c, it also has an edge to the node for b from the node for c.

Algorithm to Construct Dependency Graph:

for each node n in the parse tree do for each attribute a of the grammar symbol at n do construct a node in the dependency graph for a for each node n in the parse tree do for each semantic rule b .= f(c1.Cz……….CK) associated with the production sedated for i:=1 tok do construct an edge from the node for ct to the node for b;

Example:

Consider that

The production is: E -> E1+E2 and the associated semantic rule is :

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 the compiler construction time, the semantic rules associated with productions are analyzed. For each production, the evaluation order is predetermined at the 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 need not explicitly construct the dependency graph at compile time. Hence, they are 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