Syntax-directed translation

In this tutorial we are going to cover one of the most essential topics, syntax directed translation while covering the most important questions including;

• What is defined as syntax directed translation?

• What are its attributes and its usage in compiler design?

• What are the applications of this concept

And much more!

This concept is defined as a compiler implementation method wherein the source language is driven by the parser. The vital application of SDT is in the construction of varied syntax trees.

There are certain compilers that use syntax trees for its intermediate representation, the main purpose is to turn the required input string in the form of a tree.

Learn in-depth about this concept while we unfold some of its interesting details!

Let’s get started by uncovering this crucial computer science topic!

What do you know about syntax directed translation?

SDT or syntax directed translation is basically used for constructing the parse tree with semantic and grammatical actions. In grammar, there is a need to decide which one has high priority and which action needs to be done first. Though, in case of the semantic actions , there is a need to determine what grammatically action has to be done at first.

Semantic rule + grammar = SDT

Here, we can say that:

• In SDT, all the non-terminal will get one or more attributes. Though, sometimes they will also get 0 attributes. The value can be determined by the semantic rules which are connected with the other production rules

• In case of semantic rules, VAL will be the attribute that can hold a string or a number or a memory location

• In SDT, whenever there is need to construct the programming language in order to translate as per the semantic rules which defines the programming languages

Applications of Syntax Directed Translations

We use SDT for a variety of applications including:

• Executing all the arithmetic operations

• Conversion from the infix to the postfix expressions

• Conversions from the infix to the prefix expressions

• Creating a proven syntax tree

• From binary to the decimal conversion

• Counting all the number of reductions

• Storing all the information in your symbol table

• Doing type checking

Types of attributes for SDT

There are mainly two types of attributes that every programmer should know:

Synthesised Attributes: These attributes are defined as the non-terminal attributes which will be on the left side of your production. These are the attributes that will mainly depend on the values of all the children nodes. If all the related semantic attributes are synthesised in the augmented grammar, the depth-first traversal in this case will be aligned in any order which will be related to your semantic analysis phase.

Inherited Attributes: These attributes are touted as the non-terminal attributes which are on the right side of the attribute production. The dependency of these attributes is generally based on the parents attributes or the children's attributes. The same productive symbols are initially annotated equally between the parent nodes and the children nodes. So, you can make an ideal analysis of this whole statement.

Working of SDT

SDT has certain attributes or augmented grammar rules that help in doing the semantic analysis. It involves passing the information from bottom-up and the top-down to a parse tree in the form of certain attributes which are attached with the nodes.

In syntax directed translation, we generally consider the rules of nodes lexical values, its constants and the attributes that are associated with the non-terminals inside of the definition.

Here, the general approach would be to SDT for constructing a parse tree or computing the values of all attributes for the nodes of the tree either by visiting them in a certain order. In certain cases, the translation can either be done by doing parsing without the building of an explicit tree.

For example;

When you are given with a grammar where you have to validate the expression in the form of addition or multiplication. In order to conduct any kind of semantic analysis, you will first augment the rules of SDT, to pass some sort of information

Here, we will put our main focus on the evaluation of any given expression while checking for the semantic assertions. The translation rules in this set will be considered when; we will see the nodes of grammar while comparing the set of translation rules with certain types of production rules while looking at the attributes, its lexical values and other constants.

In order to evaluate the set of translation rules you can also follow the approach of depth-first traversal on a parse tree. This can be possible when the SDT rules will not impose any kind of evaluation until the children's attributes will be computed before the parents' attributes to check for its grammar rules.

For better understanding, we can move from the bottom-up approach from left to right to check its correctness.

Postfix translation scheme

You can also make use of this scheme in a way as each of the semantic actions will be executed at the end of its production. This execution will take place alongside the reduction of that production to the head. Hee, we will refer to the SDT which will be having all the semantic actions on the right end in your production rules.

Use of SDT in the compiler design

SDT in compiler design plays a crucial role as it allows a designer to clearly specify all kinds of generation of the intermediate code that will directly go in terms of their semantic structures from the source language. This will then be divided into the form of synthesised or the attributes of the inherited grammar. Hence, in the compiler design you can make apt usage of this concept while looking at its broader applications on creating various types of designs.

Wrapping Up

Take this guide into consideration to know in-depth about the concept of syntax directed translation. The concept is widely asked in computer programming and plays a crucial role in interviews.

Happy Learning!