Compiler Design and Construction - Old Questions
9. What is Syntax Directed Definition? Define synthesized and inherited attributes with example.
A syntax-directed definition (SDD) is a context-free grammar together with attributes and rules. Attributes are associated with grammar symbols and rules are associated with productions. For example,
Production | Semantic Rules |
E → E1 + T | E.val = E1.val+T.val |
E → T | E.val = T.val |
Synthesized Attributes
The attribute of node that are derived from its children nodes are called synthesized attributes. Assume the following production:
S → ABC
If S is taking values from its child nodes (A, B, C), then it is said to be a synthesized attribute, as the values of ABC are synthesized to S.
Example for synthesized attribute:
Production | Semantic Rules |
E → E1 * E2 | {E.val = E1.val * E2.val} |
E → E1 + E2 | {E.val = E1.val +E2.val} |
E → int | {E.val = int.val} |
The Syntax Directed Definition associates to each non terminal a synthesized attribute called val.
In synthesized attributes, value owns from child to parent in the parse tree. For example, for string 3*2+5
Inherited Attributes
The attributes of node that are derived from its parent or sibling nodes are called inherited attributes. If the value of the attribute depends upon its parent or siblings then it is inherited attribute. As in the following production,
S → ABC
"A‟ can get values from S, B and C. B can take values from S, A, and C. Likewise, C can take values from S, A, and B.
Example for Inherited Attributes:
Production | Semantic Rules |
D ® TL | L.in = T.type |
T ® int | T.type = integer |
T ® real | T.type = real |
L ® L1, id | L1.in = L.in; addtype(id.entry, L.in) |
L ® id | addtype(id.entry, L.in) |
Symbol T is associated with a synthesized attribute type and symbol L is associated with an inherited attribute in.
In inherited attributes, values flows into a node in the parse tree from parents and/or siblings. For example, for input: int id, id
