Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Some Common Terms Used in the Article
2.1.
Siblings
2.2.
Attribute Grammar
2.3.
SDT
2.4.
Parse Tree
2.5.
Synthesized Attribute
3.
What is an Inherited Attribute in Compiler Design?
3.1.
Examples
4.
Difference Between Inherited and Synthesized Attributes
5.
Frequently Asked Questions
5.1.
Which attribute is used in L-attributed SDT?
5.2.
How is a Synthesized attribute different from an Inherited attribute in Compiler Design?
5.3.
What is a compiler?
5.4.
What is top-down parsing?
6.
Conclusion
Last Updated: Mar 27, 2024

Inherited Attribute in Compiler Design

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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.

Inherited Attribute in Compiler Design

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.
Figure 1

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.
Figure 2

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.

It must have a non-terminal in its body.

It must have a non-terminal as its head.

Must Read Recursive Descent Parser and  cousins of compiler

Frequently Asked Questions

Which attribute is used in L-attributed SDT?

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.

To learn more, go through the following articles.

Enhance your skills in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and more with our Coding Ninjas Studio  Guided Path. If you want to sharpen your coding skills for the test, check out the mock test series and enter the contests on Coding Ninjas Studio! 

Check out The Interview guide for Product Based Companies and some of the Popular Interview Problems from Top companies like AmazonAdobeGoogleUberMicrosoft, etc., on Coding Ninjas Studio.

Happy Coding!!

Previous article
First and Follow in Compiler Design
Next article
Parsing in Compiler Design
Live masterclass