Syntax Directed Translation (SDT)

In syntax-directed translation, the translation of source language to destination language is completely directed by the parser or the syntax analysis phase. The syntax-directed translation produces an annotated parse tree. Let us learn more about syntax-directed translation.

Content: Syntax Directed Translation (SDT)

1. What Syntax Directed Translation?
2. Syntax Directed Definition
   • Inherited and Synthesized Attribute
   • Evaluating an SDD at Node of Parse Tree
3. SDT Example
4. Evaluation Orders for SDD
5. SDT Scheme
6. Applications of SDT

What is Syntax Directed Translation in Compiler Design?

Syntax directed translation (SDT) add ‘semantics rule’ or actions to productions of CFG. Thus we can refer to the grammar after augmentation as attributed grammar.

The syntax-directed translation interleaves the ‘syntax analysis phase’ with the ‘semantic analysis phase’. In the syntax-directed translation first, you have to construct a ‘parse tree’. Next, apply the semantic rules associated with the production. And evaluate the attribute at the nodes of the parse tree.

We refer to a parse tree with the evaluated attribute value as an annotated parse tree. There are two classes of syntax-directed translation, ‘L-attributed translations’ and ‘S-attributed translations’. We be will be discussing this in the section ahead.

Syntax Directed Definition

The syntax-directed definition (SDD) is a CFG that includes attributes and rules. In an augmented CFG, the attributes are associated with the grammar symbols (i.e. nodes of the parse tree). And the rules are associated with the productions of grammar.

Now the attribute of a grammar symbol can be numbers, types, table references, or a string. Let us further discuss two kinds of attributes:

Synthesized and Inherited Attribute

We can define the value of a synthesized attribute for a non-terminal symbol (node) N:

1. It’s children’s attribute value
2. Total attribute values of N itself.

We can define the value of an inherited attribute for a non-terminal symbol (node) N:

1. The attribute values of N’s parent.
2. Attribute values of N’s Siblings.
3. Total attribute values of N itself.

Evaluating an SDD at Node of Parse Tree

To evaluate the value of attributes at nodes of a parse tree:

1. First, we have to build a parse tree.
2. Then we have to apply SDD rules to evaluate the values of attributes of all the nodes in the parse tree.

This improvised parse tree forms an annotated parse tree.

How to Construct Annotated Parse Tree?

As we say that the annotated parse tree is the one showing the value(s) of all the attribute(s) of node(s). So, before we evaluate the attribute value of a node. We must first evaluate all the attributes upon which its value depends.

• To evaluate the synthesized attribute of a node we have to parse the tree in a bottom-up fashion. As its value depends on the value of the concerned node’s child attributes and the node itself.
• To evaluate the inherited attribute of a node we have to parse the tree in a top-down fashion. As its value depends on the attribute value of its parent, its siblings and the node itself.
• Some nodes in a parse tree may involve both synthesized and inherited attributes. In such a case, we are not sure that there exists even one order in which the attributes at the nodes can be evaluated.

Even a dependency graph can determine the order of evaluation of the attributes.

SDT Example

Consider the SDD provided in the figure below. Here we can see the production rules of grammar along with the semantic actions. And the input string provided by the lexical analyzer is 3 * 5 + 4 n.

To perform SDT the first thing we must do is to create a parse tree with the provided production and lexical input.

The next step is to create an annotated parse tree. So, we will traverse the parse tree from top to bottom. Then add the semantic rule to evaluate the attribute of each node. Thus, you can evaluate the output for the given input string as you can see in the image below.

Evaluation Orders for SDD

There can be two classes of syntax-directed translations S-attributed translation and L-attributed translation.

S-attributed Translation

An SDD is S-attributed if the attributes of the node are synthesized attributes. To evaluate S-attributed SDD we can traverse the nodes of the parse tree in any bottom-up order.

In S-attributed SDD the attributes are evaluated by applying post-order traversal. In postorder traversal, node N is evaluated when the traverser traverses node N for the last time.

L-attributed Translation

An SDD is L-attributed if the attributes of nodes are either synthesized or inherited. Here we can traverse the parse tree strictly from left to right. This is because, in ‘L-attributed translation’, L signifies left-to-right traversing.

The SDD in the figure below is L-attributed:

The Annotated parse tree for the L-attributed SDD above is as follow:

To evaluate the L-attributed SDD, start evaluating the following order:

1. The value of the inherited attribute.
2. Then the value of synthesizing attributes.
   

Syntax Directed Translation Scheme

1. Postfix Translation Scheme

Here, we construct SDT in such as manner that each semantic action is executed at the end of that production. Thus execution of the semantic action takes place along with the reduction of that production to its head.

Thus, we refer to SDT’s with all the semantic actions at the right end of the production rules as postfix SDT’s.

2. Parser-Stack Implementation of Postfix SDT’s

In this scheme, we place the grammar symbol (node) along with its attribute onto the stack. Thus it becomes easy to retrieve attributes and symbols together when the reduction of the corresponding node occurs. As the stack operates in the first-in-last-out mode.

3. SDT’s With Action Inside Productions

In one of the methods, you can even place the semantic action at any position within a production body. The action takes place just after processing all the grammar symbols on the left side of the action.
Such as consider the production B -> X {a} Y;

Here we can perform the semantic action ‘a’ after the processing grammar symbol X (in case X is a terminal).

Or after processing all the symbols derived from X (in case the X is a non-terminal).

4. Eliminating Left Recursion from SDT’s

It is not possible to parse the grammar with left recursion in a top-down fashion. Thus, we must eliminate the left recursion from the grammar.

5. SDT’s for L-Attributed Definition

To translate the L-attributed SDD into the SDT we have to follow:

1. First, perform the semantic action evaluating the value of the inherited attribute.
2. Secondly, perform the semantic action evaluating the value of the synthesized attribute.

We can relate these steps for the SDT with the L-attributed translation.

Applications of Syntax Directed Translation

• SDT is useful in evaluating an arithmetic expression
• It helps in converting infix to postfix or converting infix to prefix.
• The syntax-directed translation is helpful in converting binary to decimal.
• SDT facilitates help in creating the syntax tree.
• The syntax-directed translation can help in generating the intermediate code and even in type checking.
• SDT stores the type info in the symbol table.

So this is all about syntax-directed translation. We have learnt about its implementation with the help of an example. We have also discussed some SDT schemes and their applications. The SDT also helps in type checking and even in generating intermediate code. The translation technique also helps in implementing little languages for some specialized tasks.