Syntax-directed Translation

Syntax-Directed Translation (SDT)

Syntax-Directed Translation is a technique in compiler design where semantic actions are associated with grammar rules to perform translation during parsing.

Purpose of SDT

Perform semantic analysis
Generate intermediate code
Build syntax trees
Translate source language to target form

📌 Key idea:

Syntax controls semantics.

Syntax-Directed Translation Schemes

A Syntax-Directed Translation Scheme is a CFG with embedded semantic actions.

General Form


E → E1 + T   { E.val = E1.val + T.val }

Types of Translation Schemes

Scheme Type	Description
S-Attributed	Uses only synthesized attributes
L-Attributed	Allows inherited + synthesized attributes

Attributes Used

Attribute Type	Meaning
Synthesized	Computed from children
Inherited	Passed from parent or siblings

Implementation of Syntax-Directed Translators

Two Main Methods

Method	Description
Parse-Tree Based	Actions executed after tree construction
Parser-Based	Actions executed during parsing

Implementation Tools

YACC (LALR-based)
ANTLR
Hand-written parsers

Intermediate Code

Intermediate Code (IC) is a machine-independent representation generated between source and target code.

Why Intermediate Code?

Improves portability
Enables optimization
Simplifies code generation

Types of Intermediate Code

Type	Example
Syntax Trees	Hierarchical
Postfix Notation	a b +
Three-Address Code	t1 = a + b

Postfix (Reverse Polish) Notation

In postfix notation, operators come after operands.

Example

Infix	Postfix
a + b	a b +
a + b * c	a b c * +

Advantages

No parentheses required
Easy stack evaluation
Used in expression translation

Parse Trees and Syntax Trees

(a) Parse Tree

A parse tree shows the complete derivation using grammar rules.

Characteristics

Includes all grammar symbols
Reflects syntax strictly

(b) Syntax Tree (Abstract Syntax Tree – AST)

A syntax tree is a compressed form of parse tree.

Differences

Feature	Parse Tree	Syntax Tree
Grammar symbols	Yes	No
Size	Large	Compact
Used for	Syntax checking	Code generation

Three-Address Code (TAC)

Three-Address Code is an intermediate code where each instruction has at most three operands.

General Form


x = y op z

Example

Expression:


a = b + c * d

TAC:


t1 = c * d
t2 = b + t1
a = t2

Types of TAC Statements

Type	Example
Assignment	x = y
Binary op	x = y + z
Unary op	x = -y
Control flow	if x goto L

Quadruples and Triples

(a) Quadruples

Quadruple format: (op, arg1, arg2, result)

Example

Op	Arg1	Arg2	Result
*	c	d	t1
+	b	t1	t2
=	t2	—	a

(b) Triples

Triple format: (op, arg1, arg2)
Result is referred by position number.

Example

Index	Op	Arg1	Arg2
0	*	c	d
1	+	b	(0)
2	=	(1)	a

Quadruples vs Triples

Feature	Quadruples	Triples
Result field	Explicit	Implicit
Code motion	Easy	Difficult
Storage	More	Less

Translation of Assignment Statements

Grammar Rule


S → id = E

Semantic Action


S.code = E.code || gen(id.place = E.place)

Example

Statement:


a = b + c * d

Translation Steps

Translate expression c * d
Add result to b
Assign to a

Generated TAC:


t1 = c * d
t2 = b + t1
a = t2

Exam-Oriented Summary Table

Topic	Key Point
SDT	Grammar + semantic rules
Translation Scheme	CFG with actions
Intermediate Code	Machine-independent
Postfix	Operator after operands
Parse Tree	Full derivation
Syntax Tree	Compact form
TAC	Max 3 operands
Quadruples	Explicit result
Triples	Position-based
Assignment Translation	Expression → TAC

Boolean Expressions

A Boolean expression is an expression whose value is either TRUE or FALSE. These expressions are mainly used in decision-making and control flow statements.

Examples

a < b
x == y
!(a > b)
x < y && y < z

Boolean Operators

Operator	Meaning
`<, >, <=, >=`	Relational
`==, !=`	Equality
`&&`	Logical AND
`
`!`	Logical NOT

Translation of Boolean Expressions

Boolean expressions are translated using conditional jumps rather than computing TRUE/FALSE values directly.

Example


if (a < b && c < d)

Intermediate Code


if a < b goto L1
goto Lfalse
L1: if c < d goto Ltrue
goto Lfalse

Short-Circuit Evaluation

A && B: if A is false, B is not evaluated
A || B: if A is true, B is not evaluated

Statements that Alter the Flow of Control

These statements change the normal sequential execution of a program.

(a) If Statement

Example


if (x < y)
    x = y;

Intermediate Code


if x < y goto L1
goto L2
L1: x = y
L2:

(b) If–Else Statement


if (a > b)
    max = a;
else
    max = b;

Intermediate Code:


if a > b goto L1
max = b
goto L2
L1: max = a
L2:

(c) While Loop


while (x < 10)
    x = x + 1;

Intermediate Code:


L1: if x < 10 goto L2
goto L3
L2: x = x + 1
goto L1
L3:

Postfix Translation of Expressions

In postfix (Reverse Polish) notation, the operator appears after operands.

Why Postfix?

No parentheses needed
Easy stack-based evaluation
Useful in syntax-directed translation

Example

Infix	Postfix
`a + b`	`a b +`
`a + b * c`	`a b c * +`

Syntax-Directed Rule


E → E1 + T    { print('+') }

Translation with a Top-Down Parser

A top-down parser constructs the parse tree from root to leaves and executes semantic actions during parsing.

Characteristics

Uses LL(1) grammar
No left recursion
Suitable for postfix translation

Example Grammar


E → T E'
E' → + T E' | ε
T → id

Semantic Action (Postfix)


E' → + T { print('+') } E'

Output


a + b + c → a b + c +

Array References in Arithmetic Expressions

Array references require address calculation during translation.

Example


a[i]

Address Calculation


address = base(a) + i * width

Example Translation


t1 = i * 4
t2 = base(a) + t1
x = *t2

Procedure (Function) Calls

Procedure calls involve:

Parameter passing
Control transfer
Return values

Example


x = f(a, b)

Intermediate Code


param a
param b
t1 = call f, 2
x = t1

Activities During Procedure Call

Save return address
Pass parameters
Transfer control
Return value

Declarations Translation

Declarations allocate memory and type information.

Example


int a;
float b;

Actions Performed

Enter identifiers into symbol table
Assign type and size
Allocate memory

Symbol Table Entry

Name	Type	Size	Address
a	int	4	100
b	float	8	104

Case Statements Translation

A case statement selects execution based on a value.

Example


case (x)
  1: y = 10;
  2: y = 20;

Intermediate Code (Jump Table)


if x == 1 goto L1
if x == 2 goto L2
goto L3
L1: y = 10; goto L4
L2: y = 20; goto L4
L3:
L4:

Combined Exam-Oriented Summary Table

Topic	Key Concept
Boolean Expressions	TRUE/FALSE, short-circuit
Control Flow	if, while, goto
Postfix Translation	Stack-based
Top-Down Translation	LL parser + actions
Arrays	Address computation
Procedure Calls	Param + call + return
Declarations	Symbol table
Case Statements	Jump tables

Syntax-directed Translation