CD Notes

Syntax-Directed Translation Schemes: Execution Semantics and Code Generation

Master syntax-directed translation schemes (SDT) with evaluation order, semantic actions, attribute dependencies, L-attributed vs R-attributed grammars, parsing algorithm integration with complete examples.

Overview

Syntax-Directed Translation Schemes (SDT) specify how to compute attributes for parse tree nodes by embedding semantic actions in grammar productions. Actions execute at specific parser points, enabling on-the-fly translation without explicit tree construction.

What is an SDT?

An SDT extends a context-free grammar with semantic actions (code fragments):

Example

Production: E → E₁ + E₂ { print("+"); } └─ semantic action executes after matching

Evaluation Order: L-Attributed vs R-Attributed

L-Attributed Grammars

L-attributed: Attributes depend only on:

Left siblings (already computed)
Parent attributes (from above)

Can use	parent, B
Cannot use	C, D (right siblings)
A	B C D {

R-Attributed Grammars

R-attributed: Attributes depend only on:

Inherited attributes of children
Synthesized attributes of right siblings

Example

Can be computed bottom-up in one pass Synthesized attributes only → automatically R-attributed

Semantic Action Placement

Embedding Actions in Productions

Production Forms

1. {action} A → B {action} C D {action}

↑ before parsing ↑ middle ↑ after parsing

Execution Order (during predictive parsing)

{action} (execute before)

parse B (match B)

{action} (execute after B)

parse C (match C)

parse D (match D)

{action} (execute after production)

Example: Expression Translation

Grammar

E → E₁ + T {E.code = E₁.code || T.code || "add"}

E → T {E.code = T.code}

T → id {T.code = "load " || id.name}

Parse: id + id

Execution

E → T: load id1

E → E + T: load id1, load id2, add

Result: load id1; load id2; add;

Attribute Evaluation Algorithms

Algorithm 1: Top-Down Evaluation (LL Parsers)

Code example

Best for L-attributed grammars

During predictive parsing:
1. Initialize inherited attributes
2. Parse non-terminal B
3. Compute B's synthesized attributes
4. Use B's values for following symbols

Pseudocode:
  parseA(parent_inh):
    compute A's inherited attributes from parent
    for each symbol in production A → ... S ... :
      if S is terminal:
        match S
      else:
        parseS(A's computed inherited for S)
      compute synthesized attributes using matched symbols
    return synthesized attributes

Algorithm 2: Bottom-Up Evaluation (LR Parsers)

Example

Best for R-attributed grammars During LR parsing: 1. Reduce by production 2. Action executes 3. Use synthesized attributes of children Pseudocode: On reduce by A → X₁X₂...Xₖ: gather attributes from X₁...Xₖ (synthesized) execute action for production assign A's synthesized attributes push A onto stack with its attribute values

Practical Implementation Patterns

Pattern 1: Expressions with Intermediate Code

Grammar

E → E₁ + E₂ {

E.code = E₁.code || E₂.code ||

"add(" || E₁.place || "," || E₂.place || ")"

E.place = newtemp()

}

E → id {E.place = id.name; E.code = ""}

Parse tree attribute computation

E (code, place)

/|\

/ | \

E + E

(id1) (id2)

Action sequence

E(id2): place=id2, code=""

E(id1): place=id1, code=""

E(+): code="add(id1,id2)"

place=t1

Result: t1 = add(id1, id2)

Pattern 2: Type Checking via Attributes

Grammar

D → id : T {symbolTable[id.name] = T.type}

T → int {T.type = "int"}

T → real {T.type = "real"}

Translation

int x; → symbolTable[x] = "int"

real y; → symbolTable[y] = "real"

Distinguishing LL vs LR SDT Usage

Aspect	LL(1) + SDT	LR + SDT
Attribute flow	Top-down (inherited first)	Bottom-up (synthesized first)
Attribute type	L-attributed	R-attributed or L-attributed
Action timing	Before/during production parsing	After completion (reduce)
Grammar requirements	LL(1) form	LR(1) form
Use case	Top-down translation	Bottom-up translation

Error Recovery with Actions

On error in action

1. Catch exception

2. Set default values for attributes

3. Continue parsing if possible

4. Report error with context

Example

T → id {

if id not in symbol_table:

T.type = "error"

error(id.name + " undefined")

else:

T.type = symbol_table[id.type]

}

Comparison with Abstract Syntax Trees

With SDT (Direct Translation)

Grammar: E	E + E
Parse	1 + 2
Action immediately produces	code or object
Result	3 or intermediate code directly
Memory	O(input length) only for actions

With AST (Separate Phase)

Grammar: E	E + E
Parse: 1 + 2	builds AST
AST	Plus(Num(1), Num(2))
Translation	Walk AST, produce code
Memory	O(tree size) AST + workspace

Quick Revision Notes

SDT = Grammar + Semantic Actions embedded in productions
L-attributed: Attributes from left siblings and parent (predictable order)
R-attributed: Attributes from right siblings (bottom-up computation)
Action timing: {action} at different positions in production execute at different parsing points
LL parser: Top-down evaluation order, inherited attributes computed first
LR parser: Bottom-up evaluation order, synthesized attributes computed first
Attribute dependency: Cannot have cycles; evaluation order must be acyclic

Interview Q&A

Q1: When should you use SDT vs building a separate AST?

A: Use SDT when you translate during parsing (more efficient memory-wise for one-pass compilation). Build AST when: code is complex, multiple passes needed, or you need to traverse different ways. For modern compilers with optimization, AST is often better despite extra memory.

Q2: What's the difference between L-attributed and R-attributed grammars?

A: L-attributed allows attributes from parent and left siblings (top-down flow), matching LL parser evaluation. R-attributed attributes depend on right siblings (bottom-up flow), matching LR parser evaluation. L-attributed is more restrictive but works with predictive parsers.

Q3: Where do you place semantic actions in a production to compute an attribute correctly?

A: Place the action after the symbols it depends on are parsed. For inherited attributes of right siblings, place early. For synthesized attributes, place at end. You can also embed multiple actions for side effects.

Q4: Can you use SDT with any grammar or only LL(1)/LR(1)?

A: You can use SDT with any grammar that can be parsed, but the evaluation order matters. L-attributed requirements may force LL(1) structure; R-attributed requirements match LR parsing. Other grammars might need restructuring.

Q5: How do you handle attribute computation with ε productions (epsilon)?

A: Epsilon productions still have attributes. Place action at production position: A → ε {action} or at beginning. Synthesized attributes are assigned even though no symbols are parsed. Inherited attributes flow to nothing.

Q6: What happens if you forget to compute a required attribute in a semantic action?

A: The attribute remains uninitialized, causing incorrect translation, crashes, or undefined behavior. Good practice: use strong typing, default all attributes, and assert all required values are set before use.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Syntax-Directed Translation Schemes: Execution Semantics and Code Generation.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, syntax, directed, translation, schemes

Continue learning this concept

Syntax Directed TranslationAttribute Grammars: Foundation of Semantic Analysis and Code GenerationComprehensive study of attribute grammars in compiler design: attribute definitions, evaluation schemes, dependency graphs, parsing integration, practical implementations for modern compilers with industry examples.Syntax Directed TranslationDependency Graphs: Visualizing Attribute Computation Order in Semantic AnalysisUnderstand dependency graphs for attribute evaluation: node ordering, cycle detection, topological sort algorithms, evaluation schemes, practical implementations in modern compilers with visual examples.Syntax Directed TranslationInherited Attributes: Top-Down Attribute Computation for Context TransferDeep dive into inherited attributes: computation semantics, parent-to-child propagation, L-attributed grammars, evaluation algorithms, practical uses in type checking and code generation with examples.Syntax Directed TranslationSyntax-Directed Definitions: Attribute Grammars for Semantic AnalysisComplete guide to syntax-directed definitions (SDD) with attribute types, semantic rules, translation tables, consistency checking, dependency analysis, and practical compiler implementation techniques.Syntax Directed TranslationSynthesized Attributes: Bottom-Up Attribute Computation in Compiler DesignIn-depth exploration of synthesized attributes in compilers: definition, computation rules, dependency analysis, parsing table integration, S-attributed grammar implementation with complex examples.Intermediate Code GenerationDirected Acyclic Graphs (DAGs) in Compiler DesignComplete guide to DAGs as intermediate representation covering DAG construction, common subexpression detection, code generation from DAGs, and optimization using DAG representation.

PreviousSyntax-Directed Definitions: Attribute Grammars for Semantic Analysis NextSynthesized Attributes: Bottom-Up Attribute Computation in Compiler Design

CD Notes

Syntax-Directed Translation Schemes: Execution Semantics and Code Generation

Overview

What is an SDT?

An SDT extends a context-free grammar with semantic actions (code fragments):

Example

Production: E → E₁ + E₂ { print("+"); } └─ semantic action executes after matching

Evaluation Order: L-Attributed vs R-Attributed

L-Attributed Grammars

L-attributed: Attributes depend only on:

Left siblings (already computed)
Parent attributes (from above)

Can use	parent, B
Cannot use	C, D (right siblings)
A	B C D {

R-Attributed Grammars

R-attributed: Attributes depend only on:

Inherited attributes of children
Synthesized attributes of right siblings

Example

Can be computed bottom-up in one pass Synthesized attributes only → automatically R-attributed

Semantic Action Placement

Embedding Actions in Productions

Production Forms

1. {action} A → B {action} C D {action}

↑ before parsing ↑ middle ↑ after parsing

Execution Order (during predictive parsing)

{action} (execute before)

parse B (match B)

{action} (execute after B)

parse C (match C)

parse D (match D)

{action} (execute after production)

Example: Expression Translation

Grammar

E → E₁ + T {E.code = E₁.code || T.code || "add"}

E → T {E.code = T.code}

T → id {T.code = "load " || id.name}

Parse: id + id

Execution

E → T: load id1

E → E + T: load id1, load id2, add

Result: load id1; load id2; add;

Attribute Evaluation Algorithms

Algorithm 1: Top-Down Evaluation (LL Parsers)

Code example

Best for L-attributed grammars

During predictive parsing:
1. Initialize inherited attributes
2. Parse non-terminal B
3. Compute B's synthesized attributes
4. Use B's values for following symbols

Pseudocode:
  parseA(parent_inh):
    compute A's inherited attributes from parent
    for each symbol in production A → ... S ... :
      if S is terminal:
        match S
      else:
        parseS(A's computed inherited for S)
      compute synthesized attributes using matched symbols
    return synthesized attributes

Algorithm 2: Bottom-Up Evaluation (LR Parsers)

Example

Practical Implementation Patterns

Pattern 1: Expressions with Intermediate Code

Grammar

E → E₁ + E₂ {

E.code = E₁.code || E₂.code ||

"add(" || E₁.place || "," || E₂.place || ")"

E.place = newtemp()

}

E → id {E.place = id.name; E.code = ""}

Parse tree attribute computation

E (code, place)

/|\

/ | \

E + E

(id1) (id2)

Action sequence

E(id2): place=id2, code=""

E(id1): place=id1, code=""

E(+): code="add(id1,id2)"

place=t1

Result: t1 = add(id1, id2)

Pattern 2: Type Checking via Attributes

Grammar

D → id : T {symbolTable[id.name] = T.type}

T → int {T.type = "int"}

T → real {T.type = "real"}

Translation

int x; → symbolTable[x] = "int"

real y; → symbolTable[y] = "real"

Distinguishing LL vs LR SDT Usage

Aspect	LL(1) + SDT	LR + SDT
Attribute flow	Top-down (inherited first)	Bottom-up (synthesized first)
Attribute type	L-attributed	R-attributed or L-attributed
Action timing	Before/during production parsing	After completion (reduce)
Grammar requirements	LL(1) form	LR(1) form
Use case	Top-down translation	Bottom-up translation

Error Recovery with Actions

On error in action

1. Catch exception

2. Set default values for attributes

3. Continue parsing if possible

4. Report error with context

Example

T → id {

if id not in symbol_table:

T.type = "error"

error(id.name + " undefined")

else:

T.type = symbol_table[id.type]

}

Comparison with Abstract Syntax Trees

With SDT (Direct Translation)

Grammar: E	E + E
Parse	1 + 2
Action immediately produces	code or object
Result	3 or intermediate code directly
Memory	O(input length) only for actions

With AST (Separate Phase)

Grammar: E	E + E
Parse: 1 + 2	builds AST
AST	Plus(Num(1), Num(2))
Translation	Walk AST, produce code
Memory	O(tree size) AST + workspace

Quick Revision Notes

SDT = Grammar + Semantic Actions embedded in productions
L-attributed: Attributes from left siblings and parent (predictable order)
R-attributed: Attributes from right siblings (bottom-up computation)
Action timing: {action} at different positions in production execute at different parsing points
LL parser: Top-down evaluation order, inherited attributes computed first
LR parser: Bottom-up evaluation order, synthesized attributes computed first
Attribute dependency: Cannot have cycles; evaluation order must be acyclic

Interview Q&A

Q1: When should you use SDT vs building a separate AST?

Q2: What's the difference between L-attributed and R-attributed grammars?

Q3: Where do you place semantic actions in a production to compute an attribute correctly?

Q4: Can you use SDT with any grammar or only LL(1)/LR(1)?

Q5: How do you handle attribute computation with ε productions (epsilon)?

Q6: What happens if you forget to compute a required attribute in a semantic action?

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Syntax-Directed Translation Schemes: Execution Semantics and Code Generation.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, syntax, directed, translation, schemes

Continue learning this concept

PreviousSyntax-Directed Definitions: Attribute Grammars for Semantic Analysis NextSynthesized Attributes: Bottom-Up Attribute Computation in Compiler Design