Do you think IIT Guwahati certified course can help you in your career?
Introduction
In compiler design, Syntax Directed Translation calculates the value of the attribute of the node present in the parsing tree. The Syntax Directed Definition (SDD) uses two types of attributes, which are used to determine the value of the attribute at the node.
These two attributes are Synthesized Attributes and Inherited Attributes.
This article will discuss the Inherited attribute in compiler design used in Syntax Directed Definitions for defining the node's value.
Some Common Terms Used in the Article
Siblings
Nodes with the same parent in a tree are known as siblings. For example, in Fig 1, B is the sibling of C as the parent of both nodes is A.
Attribute Grammar
It is a type of CGF that provides more information about the non-terminals in grammar.
SDT
SDT stands for Syntax Directed Translation which is used for semantic analysis and to create a parse tree or syntax tree. To learn more, you can read the Applications of Syntax Directed Translation.
Parse Tree
The parse tree is a syntactic structure in which the nodes are stored hierarchically according to the grammar. It is condensed to make a syntax tree. Click to learn more about syntax trees.
Synthesized Attribute
It is an attribute in which the value of a node is taken only from the child node, and this can be S-attributed or L-attributed SDT.
What is an Inherited Attribute in Compiler Design?
If the node value of the parse tree is taken by the attribute value of either the parent node or sibling node, then it will be known as an inherited attribute. So, there should be a non-terminal symbol in its body.
As this is an inherited attribute in compiler design, the value of the node should be in terms of itself, the parent or sibling of that node. It only contains non-terminals and uses only L-attributed SDT. L-attribute restrict to inherit from parents or siblings only.
We can follow either the parse tree's sideways or top-down traversal to evaluate the inherited attribute in compiler design.
Examples
Check whether an attribute is inherited or not.
A → BC { B.val = A.val, C.val = B.val} Here, in the case of B.val = A.val, A is the parent of B. So, B is inheriting the attribute from its parent. In C.val = B.val, C is assigned the value of its sibling, i.e., B. So, this is also an inherited attribute.
The curved lines of the above parse tree show the values assigned and are inherited attributes as the value of B is taken from its parent, and C’s value is taken from its sibling.
A → BCD {B.val = A.val, D.val = C.val, A.val = C.val} Here, in the case of B.val = A.val, since A is the parent of B, so its an inherited attribute. In D.val = C.val, since D and C are siblings, so according to the rule of inherited attributes, this is also an inherited attribute. Now, for A.val = C.val, since C is the child of A, its not an inherited attribute.
The above parse tree also shows the values assigned to B and C from parent and sibling, respectively, and the value of A is taken from node C, which is the child of A.
Difference Between Inherited and Synthesized Attributes
Inherited Attributes
Synthesized Attributes
If the value of an attribute at its parent, siblings, or other nodes determines the value of that attribute at that node's parse tree node, that attribute is said to be inherited.
If the value of an attribute at its child nodes determines the value of its parse tree node, the attribute is said to be synthesized.
One can only specify an inherited property at node n in terms of those nodes' siblings, parents, and attribute values.
Only the attribute values at n's children are used to define a synthesized attribute at node n.
A single top-down and sideways parse tree traversal is used to evaluate this attribute.
Single bottom-up traversal of the parse tree is used to evaluate this attribute.
L-attributed SDT uses this attribute.
L-attributed and S-attributed SDT uses this attribute.
L-attribute SDT (Syntax Directed Translation) is used for both Synthesized as well as inherited attributes in compiler design. These attributes are evaluated by traversing the parse tree by depth-first or left to right.
How is a Synthesized attribute different from an Inherited attribute in Compiler Design?
Synthesized attributes are used for the node's value from the child, while inherited attribute provides the node's value from its parent or siblings. S-attributed SDT is used only for synthesized, while L-attributes are used for both attributes.
What is a compiler?
A compiler is a set of programs that converts high-level language to a language understood by a machine and helps learn the programming language quickly and shorten the code. C, C++, or Java are some examples.
What is top-down parsing?
Top-down parsing is to create the parse tree by parsing the input by starting from the root and parsing toward the leaf of the parse tree. It is useful for LL(1) grammar.
Conclusion
In this article, we discussed inherited attributes in compiler design. Along with that, we also learned some of the basic terms which we used while explaining the inherited attribute in compiler design.
We saw some examples to identify whether the attribute is inherited or synthesized.
84+ registered