Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Syntax-Directed Translation Schemes
2.1.
Semantic Actions 
3.
Syntax Directed Translation Scheme for Postfix Code
3.1.
Translation for Postfix Notation
4.
Frequently Asked Questions
4.1.
What are the three different types of address codes?
4.2.
What is context-free grammar?
4.3.
What is top-down parsing?
4.4.
What is bottom-up parsing?
4.5.
What is prefix notation?
5.
Conclusion
Last Updated: Mar 27, 2024

Syntax-Directed Translation Schemes

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

Introduction

People often don't know how to make Syntax-Directed Translation Schemes and get confused. Are you also the one? You are in the right place. 

We will first learn about Syntax-Directed Translation Schemes and then their example for better understanding. Furthermore, we will discuss usage of Syntax-Directed Translation Schemes for given data.

Let's dive into the topic now to know more in detail.

Syntax-Directed Translation Schemes

It is context-free grammar, and we use it to evaluate the order of semantic rules. The semantic rules are contained on the right side of the productions in the translation scheme. Braces are used to enclose the position where action has to be taken, which is also written on the right side of the production.

It's a notation in which each context-free Grammar production is linked to a collection of semantic rules or actions. Each grammar symbol is connected to a set of attributes. Syntax-directed definitions are thus formed by combining the language and the collection of semantic actions. 

The generation of intermediate code, adding the information in the symbol table about constructs type, or generation of object code can be the translation. Modern compilers hide extra implementation details to simplify the user's life by using syntax-directed translation and removing the user's need to indicate the order in which semantic rules should be evaluated.

Semantic Actions 

Whenever the parser recognizes the input string generated by a context-free grammar, this action gets executed.

For Example, A → BC {Semantic Action}

Curly braces are used to write semantic action. There's a production attached to it.

Note- 

  • When A is expanded to derive BC, which derives string ‘w’ in the Top-Down Parser, semantic action is taken.
  • When BC is reduced to A in a Bottom-Up Parser, semantic action is generated.
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

Syntax Directed Translation Scheme for Postfix Code

The operators appear after operands in postfix notation. That means we take out operators between operands and put them after operands.

For example,

Consider the grammar

A →  A(1) + A(2)
A →  A(1) ∗ A(2)
A → ( A(1))
A → id

 

The Postfix Translation for the grammar is shown in the table below.

Production Semantic Action
  A → A(1) + A(2) A. CODE =  A(1). CODE| |A(2). CODE | |'+'
  A → A(1) ∗ A(2) A. CODE = A(1). CODE| |A(2). CODE | |'∗'
  A → (A(1)) A. CODE = A(1). CODE
  A → id A. CODE = id

 

Translation for Postfix Notation

‘A.CODE’ denotes property or translation of the grammatical symbol A. It refers to a series of three-address statements that evaluates A. The concatenation (| |) of the translation of the nonterminals on the right followed by the operator is the translation of the nonterminal on the left of each production.

  • The translation value ‘A.CODE’ is the concatenation of two translations ‘A(1). CODE’ & ‘A(2). CODE’ and symbol '+' in the first production, which is A → A(1) + A(2)
  • The translation value ‘A.CODE’ is the concatenation of two translations ‘A(1). CODE’ & ‘A(2). CODE’ and symbol '*' in the first production, which is A → A(1) ∗ A(2)
  • The symbol | | represents the concatenation.
  • The translation of parenthesized expression is the same as that of unparenthesized expression in the third production, A→ (A(1)).
  • The translation of any identifier in the fourth production E → id is the identifier itself.

 

The attributes and translations for the grammatical sign A are listed below.

A. VAL → It tells the value of E.

A. PLACE → It describes the name that will hold the value of the expression.

A. CODE → The sequence of three address statements computing the expression.

A. MODE → It describes the data type of E.

Also see, Syntax Directed Translation Scheme

Frequently Asked Questions

What are the three different types of address codes?

Three-address code is a short, intermediate code to create and convert to machine code. It only uses three locations and one operator to describe an expression, and the value computed at each instruction is saved in a compiler-generated temporary variable.

What is context-free grammar?

A context-free grammar is a type of formal grammar that generates all available strings in a formal language.

G is a context-free grammar defined by four tuples:

G = (V, T, P, S) where G is grammar.

What is top-down parsing?

The top-down parsing technique parses the input and begins building a parse tree from the root node to the leaf nodes.

What is bottom-up parsing?

Bottom-up parsing begins from a tree's leaf nodes and progresses upward until it reaches the root node. We start with a sentence and work backward through the production rules to arrive at the start symbol.

What is prefix notation?

The operators appear before operands in prefix notation. That means we take out operators between operands and put them before operands.

Conclusion

In this article, we have extensively discussed the topic of Syntax-Directed Translation Schemes. 

We hope that this blog has helped you enhance your knowledge regarding encryption 

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Do upvote our blogs to help other ninjas grow. 

Happy Learning!

Previous article
Evaluation Order for SDD's
Next article
Implementing L-Attributed SDD's
Live masterclass