Syntax-Directed Translation

Overview

Having established the grammatical structure of a source program through parsing, we now proceed to the crucial phase of discerning its meaning. This process is systematically guided by the program's syntax, and the formal framework for achieving this is known as Syntax-Directed Translation (SDT). This powerful method involves associating semantic rules, or actions, with the productions of a context-free grammar. By executing these actions during parsing, we can translate a string from the source language into a target representation, which may be an abstract syntax tree, intermediate code, or even executable code itself.

The principles of syntax-directed translation form the theoretical and practical foundation for the semantic analysis phase of a compiler. Through this framework, we can perform a multitude of essential tasks, including the enforcement of type-compatibility rules, the collection of information for symbol tables, and the generation of intermediate representations such as three-address code. In essence, syntax-directed translation serves as the bridge between the structural analysis performed by the front end and the code synthesis conducted by the back end, ensuring that the compiler understands what the program is supposed to do, not just how it is structured.

For the Graduate Aptitude Test in Engineering (GATE), a thorough understanding of this topic is paramount. Questions frequently assess one's ability to work with attribute grammars, differentiate between S-attributed and L-attributed definitions, and trace the evaluation of attributes on a parse tree. Mastery of these concepts is indispensable for solving complex problems involving semantic checking and intermediate code generation, which are recurring and high-value themes in the Compiler Design syllabus.

---

Chapter Contents

| # | Topic | What You'll Learn |
|---|-------|-------------------|
| 1 | Semantic Analysis | Verifying program meaning and language rules. |

---

Learning Objectives

---

We now turn our attention to Semantic Analysis, which constitutes the first and most fundamental application of the syntax-directed framework.
## Part 1: Semantic Analysis

Introduction

Following the parsing phase, a compiler has successfully verified that a source program is syntactically correct according to the rules of a context-free grammar. However, syntactic correctness does not guarantee that the program is meaningful or logically sound. For instance, a program might attempt to add an integer to a string, or use a variable before it has been declared. The detection of such errors falls under the purview of semantic analysis. This phase serves as a critical bridge between the structural analysis of the parser and the generation of machine-level code, ensuring that the program adheres to the language's semantic rules.

The primary framework for performing semantic analysis is Syntax-Directed Translation (SDT). This powerful technique systematically associates semantic rules, or actions, with the productions of a grammar. As the parser constructs the parse tree, these semantic actions are executed to compute attribute values, perform checks, and generate intermediate representations. We can view this process as annotating the parse tree with semantic information that flows up, down, and across its nodes, ultimately determining the overall meaning of the source program. The successful completion of this phase confirms that the program is not only syntactically well-formed but also semantically coherent.

---

Key Concepts

#
## 1. Attributes: Synthesized and Inherited

Attributes are values associated with grammar symbols that carry semantic information. They can be of any type, such as numbers, strings, types, memory locations, or even data structures. We classify attributes into two distinct categories based on how their values are computed.

a) Synthesized Attributes

A synthesized attribute for a non-terminal is computed from the attribute values of its children in the parse tree. This corresponds to a flow of information upwards from the leaves of the tree towards the root. For a production $A \rightarrow \alpha$, a semantic rule computing a synthesized attribute for $A$ will take the form $A.s = f(\text{attributes of symbols in } \alpha)$.

Consider the parse tree for a production $A \rightarrow BCD$. A synthesized attribute $A.s$ is computed using attributes from its children $B$, $C$, and $D$.

Synthesized Attribute Flow



A


B


C


D

A.s = f(B.attr, C.attr, D.attr)

b) Inherited Attributes

An inherited attribute for a non-terminal is computed from the attribute values of its parent and/or its siblings in the parse tree. This corresponds to a flow of information downwards or sideways across the tree. For a production $A \rightarrow BCD$, a semantic rule computing an inherited attribute for child $C$ might take the form $C.i = f(A.i, B.attr)$.

Inherited Attribute Flow



A


B


C


D

C.i = f(A.i, B.attr)

Inherited attributes are particularly useful for propagating contextual information, such as the data type in a declaration, down to the individual identifiers.

---

#
## 2. Classes of Syntax-Directed Definitions

Based on the types of attributes and the structure of semantic rules, we can classify SDDs into two important categories, which have significant implications for parsing and implementation.

a) S-Attributed Definitions

An SDD that uses only synthesized attributes is called an S-attributed definition. These are the simplest form of SDDs and are highly compatible with bottom-up parsing methods, such as LR parsing.

The evaluation of attributes in an S-attributed definition naturally follows a post-order traversal of the parse tree. Since a node's attribute value depends only on its children, we can compute it as soon as the attributes for all its children have been computed. This aligns perfectly with the reduction step in a bottom-up parser.

Worked Example: S-Attributed Expression Evaluator

Problem: Consider the following S-attributed grammar for binary number evaluation. Compute the value of the input string `1011`.

| Production | Semantic Rule |
|-----------------------|---------------------------------|
| $N \rightarrow B$ | $\{ N.val = B.val; \}$ |
| $N \rightarrow N_1 B$ | $\{ N.val = 2 \times N_1.val + B.val; \}$ |
| $B \rightarrow \bf{0}$ | $\{ B.val = 0; \}$ |
| $B \rightarrow \bf{1}$ | $\{ B.val = 1; \}$ |

Solution:

First, we construct the parse tree for the input string `1011`. The grammar is left-recursive, so the parse tree will be left-leaning.

Step 1: Parse the input and build the tree. The string `1011` is parsed as $(( (1) 0 ) 1 ) 1$.

Step 2: Evaluate attributes in a post-order traversal (bottom-up).

• The first `1` is reduced by $N \rightarrow B \rightarrow \bf{1}$. Let's call this $N_a$.

• Next, `10` is parsed. This corresponds to the production $N_b \rightarrow N_a B$.

• Next, `101` is parsed. This corresponds to $N_c \rightarrow N_b B$.

• Finally, `1011` is parsed. This corresponds to $N \rightarrow N_c B$.

Answer: The computed value for the string `1011` is $11$.

b) L-Attributed Definitions

L-attributed definitions are a more general class that allows both synthesized and inherited attributes, but with a key restriction on how inherited attributes are computed. This class is designed to permit attribute evaluation in a single left-to-right, depth-first traversal of the parse tree.

Crucially, an inherited attribute for a symbol $X_j$ cannot depend on any attributes from its right siblings ($X_{j+1}, \dots, X_n$). This "left-to-right" information flow makes L-attributed definitions suitable for top-down parsing methods.

Example Analysis: S-Attributed vs. L-Attributed

Let us consider three different semantic rules.

Rule A: $P \rightarrow QR \quad \{P.s = Q.s + R.s;\}$

This rule only defines a synthesized attribute ($P.s$) based on its children. Thus, it is S-attributed (and therefore also L-attributed).

Rule B: $D \rightarrow \text{type } L \quad \{L.in\_type = \text{type.lexval};\}$

Here, the attribute $L.in\_type$ is an inherited attribute of $L$. It depends on an attribute of its left sibling, `type`. This follows the L-attributed rule. Since it uses an inherited attribute, it is not S-attributed but is L-attributed.

Rule C: $A \rightarrow BC \quad \{B.i = C.s; \quad C.i = A.i;\}$

The rule for $B.i$ requires the synthesized attribute $C.s$ from its right sibling $C$. This violates the L-attributed condition. Therefore, this definition is neither S-attributed nor L-attributed.

---

#
## 3. Application: Type Checking

One of the most important roles of semantic analysis is type checking. SDDs provide a formal mechanism to implement this. We associate a `type` attribute with non-terminals representing expressions and use semantic rules to enforce type compatibility.

Consider a simple language with integer and boolean types.

| Production | Semantic Rule |
|-----------------------------|----------------------------------------------------------------------------------------------------------------|
| $D \rightarrow \text{int id}$ | $\{ \text{add\_type(id.lexeme, INT)}; \}$ |
| $D \rightarrow \text{bool id}$ | $\{ \text{add\_type(id.lexeme, BOOL)}; \}$ |
| $E \rightarrow E_1 + E_2$ | $\{ \text{if } E_1.type == \text{INT and } E_2.type == \text{INT then } E.type = \text{INT else error()}; \}$ |
| $E \rightarrow E_1 \text{ and } E_2$ | $\{ \text{if } E_1.type == \text{BOOL and } E_2.type == \text{BOOL then } E.type = \text{BOOL else error()}; \}$ |
| $E \rightarrow \text{id}$ | $\{ E.type = \text{lookup\_type(id.lexeme)}; \}$ |

Here, the `add_type` function would update the symbol table during a declaration, and `lookup_type` would retrieve the type from the symbol table when an identifier is used in an expression. The rules for expressions check if the operands have the correct types for the given operator. Notice the rule for $E \rightarrow \text{id}$, which correctly looks up the type, avoiding the flaw seen in a similar PYQ where the type was hardcoded.

---

Problem-Solving Strategies

When faced with SDT problems in GATE, a systematic approach is essential.

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="Consider the following syntax-directed definition:
S \rightarrow L = R \quad \{ \text{check_type}(L.type, R.type); \}
$R \rightarrow L \quad \{ R.type = L.type; \}$
$L \rightarrow \text{id} \quad \{ L.type = \text{lookup(id.entry)}; \}$
L \rightarrow L_1 [E] \quad \{ L.type = \text{element_type}(L_1.type); \quad E.type = \text{INT}; \}
Which of the following statements is true?" options=["The SDD is S-attributed.","The SDD is L-attributed but not S-attributed.","The SDD is neither S-attributed nor L-attributed.","The SDD contains a syntax error."] answer="The SDD is S-attributed." hint="Analyze the dependencies for each attribute. Does any attribute for a symbol on the RHS depend on its parent or siblings?" solution="Let's analyze the attributes.

• In $S \rightarrow L=R$, the semantic action is a procedure call, not an attribute assignment. We consider the attributes used. $L.type$ and $R.type$ are synthesized from the children.


• In $R \rightarrow L$, $R.type$ is a synthesized attribute depending on its child $L$.


• In $L \rightarrow \text{id}$, $L.type$ is a synthesized attribute.


• In $L \rightarrow L_1 [E]$, $L.type$ is synthesized from its child $L_1$. The rule also checks that $E.type$ is INT, but it does not define any inherited attributes. All information flows up the parse tree.

Since all attributes are synthesized, the SDD is S-attributed."
:::

:::question type="NAT" question="Consider the following SDD, where `val` is a synthesized attribute.

$S \rightarrow E$ $\{ S.val = E.val; \}$
$E \rightarrow E_1 + T$ $\{ E.val = E_1.val + T.val; \}$
$E \rightarrow T$ $\{ E.val = T.val; \}$
$T \rightarrow T_1 * F$ $\{ T.val = T_1.val \times T.val; \}$ -- Note the typo in the rule
$T \rightarrow F$ $\{ T.val = F.val; \}$
$F \rightarrow (E)$ $\{ F.val = E.val; \}$
$F \rightarrow \text{digit}$ $\{ F.val = \text{digit.lexval}; \}$

There is a deliberate error in one semantic rule. Assuming the parser uses this SDD to evaluate the expression `3 (4 + 2)`. What is the value computed for $S.val$?" answer="18" hint="The rule $T \rightarrow T_1$ F has a typo: $T.val$ depends on itself. This creates an infinite recursion for the attribute calculation. However, for the given expression, this production is used as $T \to F \to (E) \to (E+T) \to ...$ and $T \to T_1$ FT→T1​∗F is not used at the top level for the multiplication. Let's re-read the question. Ah, the typo is $T.val = T_1.val \times T.val$. This is a circular definition. Let's assume the intended rule was $T.val = T_1.val \times F.val$. Let's solve with the intended rule. Wait, the question asks what is computed with the given SDD*. Let's trace it carefully.
The expression is `3 * (4 + 2)`.
The parse tree structure is $S \to E \to T \to T_1 * F$.
$T_1$ derives `3`. $F$ derives `(4 + 2)`.
Let's compute $F.val$ for `(4 + 2)` first.
$F \to (E)$. We need $E.val$ for `4+2`.
$E \to E_1 + T$. $E_1$ derives `4`, $T$ derives `2`.
$E_1 \to T \to F \to \text{digit}$. $E_1.val = 4$.
$T \to F \to \text{digit}$. $T.val = 2$.
So, $E.val = 4 + 2 = 6$.
This means $F.val$ for `(4+2)` is $6$.
Now for the top-level production $T \rightarrow T_1 * F$.
$T_1 \to F \to \text{digit}$. $T_1.val = 3$.
$F.val = 6$.
The rule is $T.val = T_1.val \times T.val$. This is a circular definition. $T.val = 3 \times T.val$. This equation only holds if $T.val = 0$. However, compilers would typically get stuck in a loop or use an uninitialized value. Let's reconsider the question's intent. It's more likely a typo in the question itself and should be $T.val = T_1.val \times F.val$. Let's assume this was the intended rule, as this is a common GATE pattern.
With the corrected rule $T.val = T_1.val \times F.val$:
$T.val = 3 \times 6 = 18$.
$S.val = E.val = T.val = 18$.
Let's assume the question is malicious. If $T.val = 3 \times T.val$, then $2 \times T.val = 0$, which implies $T.val=0$. If the value is 0, the answer is 0. But this is semantically nonsensical. Competitive exam questions usually test understanding, not obscure language-lawyer issues with circular definitions. The most logical interpretation is that the `T.val` on the RHS was a typo for `F.val`.
Let's stick to the most reasonable interpretation.
" solution="
Step 1: Assume the semantic rule for multiplication has a typo and the intended rule is $\{ T.val = T_1.val \times F.val; \}$. A circular definition like $\{ T.val = T_1.val \times T.val; \}$ is not evaluable and would likely be flagged as an error or result in undefined behavior, which is not typically tested via a NAT question seeking a specific value.

Step 2: Construct the parse tree for `3 (4 + 2)`. The top-level production for the expression will be $E \rightarrow T$, and for the term, it will be $T \rightarrow T_1$ F.

• $T_1$ will correspond to the sub-expression `3`.


• $F$ will correspond to the sub-expression `(4 + 2)`.

Step 3: Evaluate the attribute for the sub-expression `3`.
$T_1 \rightarrow F \rightarrow \text{digit}$.

Step 4: Evaluate the attribute for the sub-expression `(4 + 2)`.
This corresponds to the production $F \rightarrow (E)$. We must find the value of $E$ for `4 + 2`.
The production for this is $E \rightarrow E_1 + T$.

• $E_1$ corresponds to `4`. $E_1 \rightarrow T \rightarrow F \rightarrow \text{digit}$. So, $E_1.val = 4$.


• $T$ corresponds to `2`. $T \rightarrow F \rightarrow \text{digit}$. So, $T.val = 2$.

Applying the rule for addition:

Therefore, for the sub-expression `(4 + 2)`, we have:

Step 5: Compute the final value using the top-level production $T \rightarrow T_1 * F$.

Result:
The final value computed for the expression is $18$.
"
:::

:::question type="MSQ" question="Which of the following statements about Syntax-Directed Definitions (SDDs) and their evaluation are correct?" options=["All S-attributed definitions can be evaluated by a bottom-up parser during parsing.","An L-attributed definition can have inherited attributes that depend on attributes of right siblings.","A top-down parser, like a recursive-descent parser, can evaluate any L-attributed definition.","Type checking is an application of synthesized attributes only."] answer="A,C" hint="Evaluate each statement based on the core definitions of S-attributed and L-attributed grammars and their relationship with parsing methods." solution="

• A. All S-attributed definitions can be evaluated by a bottom-up parser during parsing. This is correct. S-attributed definitions use only synthesized attributes. In a bottom-up parser, a reduction occurs only after the entire right-hand side of a production (and its subtrees) have been processed. At this point, the attributes of all children are available on the stack, and the parent's synthesized attribute can be computed.

• B. An L-attributed definition can have inherited attributes that depend on attributes of right siblings. This is incorrect. This is the primary restriction of L-attributed definitions. An inherited attribute of a symbol $X_j$ can only depend on its parent and its left siblings ($X_1, \dots, X_{j-1}$).

• C. A top-down parser, like a recursive-descent parser, can evaluate any L-attributed definition. This is correct. The left-to-right dependency flow in L-attributed definitions is designed to work with the depth-first, left-to-right traversal naturally performed by top-down parsers. Inherited attributes can be passed down as arguments to the parsing functions for non-terminals.

• D. Type checking is an application of synthesized attributes only. This is incorrect. While synthesized attributes are used to pass the type of an expression up the tree (e.g., $E.type = \text{INT}$), inherited attributes are very useful for passing contextual type information down the tree, for example, in declarations like $D \rightarrow \text{type } L$, the type is passed to $L$ via an inherited attribute.

"
:::

---

Summary

---

What's Next?

---

Chapter Summary

---

Chapter Review Questions

:::question type="MCQ" question="Consider the following Syntax-Directed Definition (SDD), where `s` denotes a synthesized attribute and `i` denotes an inherited attribute.
Grammar:
$A \rightarrow B C$
$B \rightarrow b$
$C \rightarrow c$

Semantic Rules:

$B.i = A.i + 2$

$C.i = B.s + 3$

$A.s = C.s - 1$

$B.s = B.i \times 2$

$C.s = C.i$

Which of the following statements is TRUE regarding this SDD?" options=["The SDD is both S-Attributed and L-Attributed.", "The SDD is L-Attributed but not S-Attributed.", "The SDD is S-Attributed but not L-Attributed.", "The SDD is neither S-Attributed nor L-Attributed."] answer="B" hint="Analyze the dependencies for each inherited attribute. Recall the specific constraint for an L-Attributed definition concerning dependencies on siblings." solution="
Let us analyze the given SDD to classify it.

1. Check for S-Attributed property:
An SDD is S-Attributed if it uses only synthesized attributes. The given SDD uses both synthesized attributes (`s`) and inherited attributes (`i`). Therefore, it is not S-Attributed. This immediately eliminates options A and C.

2. Check for L-Attributed property:
An SDD is L-Attributed if, for any production $X \rightarrow Y_1 Y_2 \dots Y_n$, the inherited attributes of $Y_j$ (for $1 \le j \le n$) depend only on:

• The inherited attributes of $X$.


• The attributes (synthesized or inherited) of the symbols $Y_1, Y_2, \dots, Y_{j-1}$ (i.e., symbols to the left of $Y_j$).

Let's examine the rules for the production $A \rightarrow B C$:

• Rule for $B.i$: $B.i = A.i + 2$. The inherited attribute of $B$ depends on the inherited attribute of the parent $A$. This is valid under the L-Attributed definition.


• Rule for $C.i$: $C.i = B.s + 3$. The inherited attribute of $C$ depends on a synthesized attribute of its left sibling, $B$. This is also valid under the L-Attributed definition.

Since all rules adhere to the constraints, the SDD is L-Attributed.

Conclusion:
The SDD is L-Attributed but not S-Attributed. Thus, option B is the correct answer.
"
:::

:::question type="NAT" question="Consider the S-Attributed Definition for evaluating binary numbers, given by the following productions and semantic rules, where `val` is a synthesized attribute.

$N \rightarrow S$ { $N.val = S.val$ }
$S \rightarrow S_1 B$ { $S.val = 2 \times S_1.val + B.val$ }
$S \rightarrow B$ { $S.val = B.val$ }
$B \rightarrow 0$ { $B.val = 0$ }
$B \rightarrow 1$ { $B.val = 1$ }

Using this SDD, compute the value for the input string `1101`." answer="13" hint="Trace the evaluation of the `val` attribute up the parse tree in a bottom-up fashion, corresponding to an LR parse of the string." solution="
We need to evaluate the `val` attribute for the input string `1101`. The evaluation follows the structure of a bottom-up parse. Let's trace the reductions and the corresponding semantic rule applications.

The input string is `1101`.

The first `1` is parsed.

- Reduction: $B \rightarrow 1$. Rule: $B.val = 1$.
- Reduction: $S \rightarrow B$. Rule: $S.val = B.val = 1$.
- The value of the prefix `1` is 1.

The next character `1` is parsed. The current prefix is `11`.

- Reduction: $B \rightarrow 1$. Rule: $B.val = 1$.
- We now have $S_1$ (from prefix `1`) and $B$ (from current `1`).
- Reduction: $S \rightarrow S_1 B$. Rule: $S.val = 2 \times S_1.val + B.val = 2 \times 1 + 1 = 3$.
- The value of the prefix `11` is 3.

The next character `0` is parsed. The current prefix is `110`.

- Reduction: $B \rightarrow 0$. Rule: $B.val = 0$.
- We now have $S_1$ (from prefix `11`) and $B$ (from current `0`).
- Reduction: $S \rightarrow S_1 B$. Rule: $S.val = 2 \times S_1.val + B.val = 2 \times 3 + 0 = 6$.
- The value of the prefix `110` is 6.

The final character `1` is parsed. The full string is `1101`.

- Reduction: $B \rightarrow 1$. Rule: $B.val = 1$.
- We now have $S_1$ (from prefix `110`) and $B$ (from current `1`).
- Reduction: $S \rightarrow S_1 B$. Rule: $S.val = 2 \times S_1.val + B.val = 2 \times 6 + 1 = 13$.
- The value of the string `1101` is 13.

Finally, the start symbol reduction $N \rightarrow S$ sets $N.val = S.val = 13$.

The final computed value is 13.
"
:::

:::question type="MCQ" question="A syntax-directed translation scheme is given for type checking expressions:

$E \rightarrow E_1 + E_2 \quad \{ \text{if } E_1.type = \text{int and } E_2.type = \text{int then } E.type = \text{int else } E.type = \text{error} \}$
$E \rightarrow \text{id} \quad\quad\quad \{ E.type = \text{lookup(id.name)} \}$
$E \rightarrow \text{num} \quad\quad \{ E.type = \text{int} \}$
$E \rightarrow \text{real} \quad\quad \{ E.type = \text{float} \}$

The `lookup` function consults a symbol table with the following entries: `p: int`, `q: float`, `r: int`. What is the synthesized type attribute of the root of the parse tree for the expression `p + r + q`?" options=["int", "float", "error", "The type cannot be determined"] answer="C" hint="Evaluate the type attributes from left to right, following the left-associativity of the `+` operator. Check if the type rules are satisfied at each step." solution="
Let us trace the evaluation of the `type` attribute for the expression `p + r + q`. The `+` operator is left-associative, so the expression is parsed as `(p + r) + q`.

The parse tree structure for this expression is:
```
E
/|\
E + q
/|\
p + r
```

We evaluate the `type` attributes in a bottom-up (post-order) fashion.

Step 1: Evaluate the types of the leaves.

• For `p`: The rule is $E \rightarrow \text{id}$. The action is $E.type = \text{lookup('p')}$. From the symbol table, the type of `p` is `int`. Let's call this node $E_p$. So, $E_p.type = \text{int}$.


• For `r`: The rule is $E \rightarrow \text{id}$. The action is $E.type = \text{lookup('r')}$. From the symbol table, the type of `r` is `int`. Let's call this node $E_r$. So, $E_r.type = \text{int}$.


• For `q`: The rule is $E \rightarrow \text{id}$. The action is $E.type = \text{lookup('q')}$. From the symbol table, the type of `q` is `float`. Let's call this node $E_q$. So, $E_q.type = \text{float}$.

Step 2: Evaluate the type of the subexpression `(p + r)`.

• This corresponds to the production $E \rightarrow E_1 + E_2$, where $E_1$ is $E_p$ and $E_2$ is $E_r$.


• We have $E_1.type = \text{int}$ and $E_2.type = \text{int}$.


• The semantic rule is: `{ if } E_1.type = \text{int and } E_2.type = \text{int then } E.type = \text{int else } E.type = \text{error} }`.


• Since both conditions are met, the type of the resulting node (let's call it $E_{pr}$) is `int`. So, $E_{pr}.type = \text{int}$.

Step 3: Evaluate the type of the final expression `(p + r) + q`.

• This corresponds to the production $E \rightarrow E_1 + E_2$, where $E_1$ is the node for `(p + r)` (i.e., $E_{pr}$) and $E_2$ is the node for `q` (i.e., $E_q$).


• We have $E_1.type = \text{int}$ and $E_2.type = \text{float}$.


• We apply the same semantic rule: `{ if } E_1.type = \text{int and } E_2.type = \text{int then } E.type = \text{int else } E.type = \text{error} }`.


• The condition `E_2.type = int` is false (since it is `float`).


• Therefore, the `else` part of the rule is executed, and the type of the root node is set to `error`.

The final synthesized type is `error`.
"
:::

---

What's Next?