Syntax Directed Definitions Synthesized Attributes and Inherited Attributes

Syntax Directed Definitions

1. Sanjivani Rural Education Society’s
Sanjivani College of Engineering, Kopargaon-423 603
(An Autonomous Institute, Affiliated to Savitribai Phule Pune University, Pune)
NACC ‘A’ Grade Accredited, ISO 9001:2015 Certified
Department of Computer Engineering
(NBA Accredited)
Dr. S. N. Gunjal
Assistant Professor
E-mail : [email protected]
Contact No: 91301 91301 Ext :145, 9503916876
Course-System Software
(CO313)
Unit-III Syntax Directed Definitions
Dr. S.N Gunjal

2. A SDD is a context free grammar with attributes and rules
Attributes are associated with grammar symbols and rules with productions
Attributes may be of many kinds: numbers, types, table references, strings, etc
Semantic rules are fragments of code which are embedded usually at the end of production and
enclosed in curly braces ({ }).
E --> E1 + T { E.val= E1.val + T.val}
Types of attributes –There are two types of attributes:
1. Synthesized Attributes–These are those attributes which derive their values from their children
nodes i.e. value of synthesized attribute at node is computed from the values of attributes at
children nodes in parse tree.
Syntax Directed Definitions

3. Example:
E->E1+T{E.val=E1.val+T.val}
Inthis,E.valderiveitsvaluesfromE1.valandT.val
ComputationofSynthesizedAttributes–
WritetheSDDusingappropriatesemanticrulesforeachproductioningivengrammar.
Theannotatedparsetreeisgeneratedandattributevaluesarecomputedinbottomup
manner.
Thevalueobtainedatrootnodeisthefinaloutput.

4. Example: Consider the following grammar :
S --> E
E --> E1 + T
E --> T
T --> T * F
T --> F
F --> digit
1. The SDD for the above grammar can be
written as follow

5. Example:Letusassumeaninputstring4*5+6
forcomputingsynthesizedattributes.The
annotatedparsetreefortheinputstringis

6. 2. Inherited Attributes –
These are the attributes which derive their values from their parent or sibling
nodes i.e. value of inherited attributes are computed by value of parent or sibling
nodes.
Example:
A --> BCD { C.in = A.in, C.type = B.type }

7. Computation of Inherited Attributes –
Construct the SDD using semantic actions.
The annotated parse tree is generated and attribute values are computed in top down
manner.

8. Example: Consider the
following grammar
S --> T L
T --> int
T --> float
T --> double
L --> L, id
L --> id
The SDD for the e grammar can be written as follow

9. Let us assume an input string int a,
cfor computing inherited
attributes. The annotated parse tree
for the input string is

10. Key Components of SDD:
Grammar: A context-free grammar (CFG) that describes the language's syntax.
Attributes:
Synthesized Attributes: Calculated from the attributes of child nodes in the parse tree (bottom-up).
Inherited Attributes: Calculated from the attributes of parent or sibling nodes (top-down or sideways).
Semantic Rules: Define how attributes are computed. These are functions or assignments that
determine attribute values based on other attributes.
Annotated Parse Tree: A parse tree where each node is annotated with the attribute values, determined
by applying the semantic rules.
Syntax Directed Definitions

11. References
1. Compilers : Principles, Techniques, & Tools 2nd Edition" by Alfred V Aho and
Ravi Sethi