Analysis of Syntax directed definition

RGPV: Compiler Design: Unit 2



   Are a generalizations of context-free grammars in which:

1. Grammar symbols have an associated set of Attributes;

2. Productions are associated with Semantic Rules for computing the values of attributes.


• Such formalism generates Annotated Parse-Trees where each node of the tree is a record with a field for each attribute (e.g.,X.a indicates the attribute a of the grammar symbol X).

• The value of an attribute of a grammar symbol at a given parse-tree node is defined by a semantic rule associated with the production used at that node.


• We distinguish between two kinds of attributes:

1. Synthesized Attributes: They are computed from the values of the attributes of the children nodes.


2. Inherited Attributes: They are computed from the values of the attributes of both the siblings and the parent nodes.

Form of Syntax Directed Definitions


• Each production, A ! α, is associated with a set of semantic rules: b := f(c1, c2, . . . , ck), where f is a function and either.


1. b is a synthesized attribute of A, and c1, c2, . . . , ck are attributes of the grammar symbols of the production, or


2. b is an inherited attribute of a grammar symbol in α, and c1, c2, . . . , ck are attributes of grammar symbols in α or attributes of A.


Syntax Directed Definitions: An Example

Example. Let us consider the Grammar for arithmetic expressions. The Syntax Directed Definition associates to each non terminal a synthesized

attribute called val.

Fig (a):-Example of SDD


S-Attributed Definitions

·         Definition:- An S-Attributed Definition is a Syntax Directed Definition that uses


·         Only synthesized attributes.

o   Evaluation Order. Semantic rules in a S-Attributed Definition can be


·         Evaluated by a bottom-up, or Post Order, traversal of the parse-tree.

o   Example. The above arithmetic grammar is an example of an S-Attributed


·         Definition. The annotated parse-tree for the input 3*5+4n is:




Inherited Attributes

Inherited Attributes are useful for expressing the dependence of a construct On the context in which it appears.


• It is always possible to rewrite a syntax directed definition to use only Synthesized attributes, but it is often more natural to use both synthesized And inherited attributes.


Inherited Attributes: An Example

Example. Let us consider the syntax directed definition with both inherited And synthesized attributes for the grammar for “type declarations”:

The non terminal T has a synthesized attribute, type, determined by the Keyword in the declaration.

• The production D! TL is associated with the semantic rule T.type which set the inherited attribute


• Note: The production L! L1, id distinguishes the two occurrences of L.


Inherited Attributes: An Example (CFG)


• Synthesized attributes can be evaluated by a Post Order traversal.


• Inherited attributes that do not depend from right children can be evaluated by a classical Preorder traversal.


• The annotated parse-tree for the input real id1, id2, id3 is: is then inherited top-down the tree by the other L-nodes.


• At each L-node the procedure add type inserts into the symbol table the type of  the identifier.






Related topics

Professor Jayesh video tutorial

Please use contact page in this website if you find anything incorrect or you want to share more information about the topic discussed above.