Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
 
3.
What is a Parse Tree?
4.
Parse Tree For SDT in Compiler Design
5.
Application of Syntax Directed Translation in Compiler Design
6.
Advantages of Syntax Directed Translation in Compiler Design
7.
Disadvantages of Syntax Directed Translation in Compiler Design
8.
Frequently Asked Questions
8.1.
Why SDT is used in compiler design?
8.2.
What is compiler design?
8.3.
Explain the three types of compilers.
8.4.
What is the role of syntax-directed translation?
9.
Conclusion
Last Updated: May 28, 2024

Syntax Directed Translation (STD) in Compiler Design

Author Nitika
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Syntax Direct Translation (SDT) method is used in compiler design, associating the translation rules with grammar production. Syntax Directed Translation can identify informal notations, called semantic rules along with the grammar.

In this article, we will learn more about Syntax Directed Translation (SDT) in compiler design, to help you understand what goes around in the world of Compiler Design.

SDT in Compiler Design

 

Parse tree work flow

Syntax Directed Translation in compiler design requires some information to convert the parse tree into a code. This information cannot be represented by the CFG(Context Free Grammar), hence attributes are attached to the variables of CFG.

We can represent it as:

Grammar + semantic rule = SDT

 

Every non-terminal syntax direct translation can get one or more than one attribute depending on its type. The values of these attributes are set by semantic rules associated with the production rule.

The 'val' attribute in the semantic rules may contain strings, numbers, memory location or a complex record. 

The table below shows production and semantic rules.

S.No

Production

Semantic Rules

1.

E → E + T

E.val := E.val + T.val

2.

E → T

E.val := T.val

3.

T → T * F

T.val := T.val * F.val

4.

T → F

T.val := F.val

5.

F → (F)

F.val := F.val

6.

F → num

F.val := num.lexval

 

For an easy understanding, we assume the following to be a production rule.

Example Image 1

The translation or semantic rule is correspondence to the Production rule and is considered to be an attribute for both the non-terminals E & T

Example Image 2

The right side of the translation rule is always in correspondence to the attribute values of the right side of the production rule. From this, we come to the conclusion that SDT in compiler design associates:

  1. A set of attributes to every node in grammar.
  2. A set of translation rules to every production rule with the help of attributes.
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 a Parse Tree?

A parse tree in compiler design is a graphical representation of a symbol which can be terminal or non-terminal. Here, the string is taken using the start symbol, and the parse tree's root is that start symbol.

 

Rules to follow while drawing a Parse Tree:

  1. All leaf nodes need to be terminals.
     
  2. All interior nodes need to be non-terminals.
     
  3. In-order traversal gives the original input string.
     

In A -> xyz, the parse tree will have A as the interior node whose children are x, y and z from left to right.

Parse Tree For SDT in Compiler Design

Parse tree

Must Read Recursive Descent Parser and  cousins of compiler

Application of Syntax Directed Translation in Compiler Design

Here are some applications of SDT in Compiler Design:

  1. Syntax Directed Translation is used for executing arithmetic expressions
     
  2. Conversion from infix to postfix expression
     
  3. Conversion from infix to prefix expression
     
  4. For Binary to decimal conversion
     
  5. Counting the number of Reductions
     
  6. Creating a Syntax Tree
     
  7. Generating intermediate code
     
  8. Storing information into the symbol table
     
  9. Type checking

Advantages of Syntax Directed Translation in Compiler Design

  • SDT in compiler design provides an easy way to specific transitions and grammar rules. It makes an easy method to translate= programming languages.
     
  • SDT maintains the compiler and is easy to modify as it separates the translation process from the parsing method.
     
  • It optimises the translation process making it code-effective.

Disadvantages of Syntax Directed Translation in Compiler Design

  • Other translation methods, like attribute grammar, have increased expressiveness. This decreases the performance of SDT.
     
  • Also, SDT does not perform well when the translations are complex.
     
  • In addition to that, the process of error fixing and error location is not easy in SDT. This happens in the case of complex translations.

Frequently Asked Questions

Why SDT is used in compiler design?

Semantic analysis, often implemented using a Semantic Description Table (SDT), is crucial in compiler design to check the meaning and correctness of code, ensuring it conforms to the language's semantics before generating executable code.

What is compiler design?

Compiler Design is the process of development of software which can read and interpret a source code written by humans into binary codes which are understood by computers. A compiler tool reads source code, checks for mistakes, and finally, outputs the program in machine language.

Explain the three types of compilers.

The three types of compilers are Single Pass, Two Pass and Multipass. Merging all the phases of compiler design in a singular module is a single-pass compiler. A processor that translates twice is a two-pass compiler. And for a multi-pass compiler, the program’s source code is processed multiple times.

What is the role of syntax-directed translation?

Syntax-directed translation plays a vital role in compiler design by associating attributes and actions with grammar rules. It guides the generation of intermediate code or target code from the source code, enabling the transformation and analysis of programming languages during compilation.

Conclusion

In this article, we learned all about SDT in Compiler Design, with its advantages and disadvantages.

Hope this article helped you in your learning journey.

Recommended Readings:

Check out some of the amazing Guided Paths on topics such as Data Structure and AlgorithmsCompetitive ProgrammingBasics of C, Basics of JavaOperating SystemsComputer Networks, etc., along with some Contests and Test Series only on Coding Ninjas StudioEnrol in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations. 

Happy Learning!!

Previous article
Best 5 Online MySQL Compiler
Next article
Best 5 Online Kotlin Compiler
Live masterclass