Syntax-Directed Translation

Syntax-Directed Translation

Syntax-Directed Translation associates semantic actions with grammar productions.

Syntax-Directed Definition (SDD)

SDD associates semantic rules with grammar productions.

Components:

• Grammar productions
• Semantic rules (attributes)

Example:

E → E + T { E.val = E.val + T.val }
E → T { E.val = T.val }
T → number { T.val = number.lexval }

Attributes

Synthesized Attribute:

• Computed from children
• Bottom-up evaluation
• Example: Expression value

Inherited Attribute:

• Computed from parent/siblings
• Top-down evaluation
• Example: Type information

Attribute Grammar

Attribute Grammar: Grammar with attributes and semantic rules.

S-Attributed Grammar:

• Only synthesized attributes
• Bottom-up evaluation
• Compatible with LR parsing

L-Attributed Grammar:

• Synthesized and inherited attributes
• Left-to-right evaluation
• Compatible with LL parsing

Translation Schemes

Syntax-Directed Translation Scheme (SDT):

• Semantic actions embedded in productions
• Actions executed during parsing

Example:

E → E + T { print('+') }
E → T
T → number { print(number.lexval) }

Three-Address Code

Three-Address Code: Intermediate representation with at most three operands.

Forms:

• Quadruples: (op, arg1, arg2, result)
• Triples: (op, arg1, arg2)
• Indirect triples: Reference to triple table

Example:

x = y + z * 2

Three-Address Code:

t1 = z * 2
t2 = y + t1
x = t2

GATE CS Important Points

1. Attributes: Synthesized vs inherited
2. SDT Schemes: Translation rules
3. Three-Address Code: Generation
4. Quadruples/Triples: Representation
5. Code Generation: From intermediate code

Practice Tips

1. SDT Schemes: Write translation rules
2. Attributes: Identify synthesized/inherited
3. Three-Address Code: Generate for expressions
4. Quadruples: Convert to quadruple form
5. Previous Year Questions: Solve GATE SDT questions