CD Notes

Syntax-Directed Definitions: Attribute Grammars for Semantic Analysis

Complete guide to syntax-directed definitions (SDD) with attribute types, semantic rules, translation tables, consistency checking, dependency analysis, and practical compiler implementation techniques.

Introduction

Syntax-Directed Definitions (SDD) specify how to attach attributes to parse tree nodes and compute them using semantic rules. Unlike SDT which embeds actions in grammar, SDD is a declarative specification of semantics independent of evaluation order.

SDD vs SDT

SDD (Declarative)

E → E₁ + E₂ {E.val = E₁.val + E₂.val}

No evaluation order specified

SDT (Procedural)

E → E₁ + E₂ {E.val = E₁.val + E₂.val}

Specifies when action executes

Attribute Types

Synthesized Attributes

Computed from children's values (bottom-up):

Example

E (val) /|\ / | \ E₁ + E₂ (val) (val) E.val = E₁.val + E₂.val

Inherited Attributes

Computed from parent's/siblings' values (top-down):

Example

A (inh) /|\ / | \ B₁ B₂ B₃ (inh) (inh) (inh) B₁.inh from A.inh, A's other attributes B₂.inh from B₁.inh, B₁'s attributes

SDD Formal Definition

An SDD is a context-free grammar plus:

Attribute set for each grammar symbol
Semantic rule for each attribute
Predicate (semantic conditions) on rules

SDD Structure

Production: A → X₁ X₂ ... Xₖ

Semantic Rules

A.s₁ := f₁(X₁.a, X₁.b, X₂.c, ..., A.d)

X₁.b := f₂(A.inh, X₂.syn)

...

Semantic Rules and Consistency

Well-Defined SDD Rules

Rules must be:

Consistent: Each attribute assigned exactly once
Non-circular: No attribute depends on itself
Acyclic: No cycles in dependency graph

Example: Consistent SDD

Production: E	E₁ + T
E.type	= E₁.type ✓ Consistent
E.val	= E₁.val + T.val
E.val	= E₁.val + E.val ✗ Circular

Dependency Graphs

Construction Algorithm

For each parse tree

1. For each attribute instance a:

Create node in graph

2. For each attribute use:

Draw edge from defining rule to using rule

A depends on B if

- B appears on right side of rule computing A

- B is attribute of ancestor/sibling in grammar

Example: Dependency Analysis

Grammar

A → B C {A.s₁ := B.s₂ + C.s₁; B.inh := A.inh}

B → b {B.s₂ := 5}

C → c {C.s₁ := C.inh * 2}

Parse: b c

Dependency Graph

A.inh (input)

↓

B.inh (from A)

↓ (via rule)

C.s₁ (B.inh unknown unless value known)

Evaluation Order

1. B.s₂ := 5 (B rule)

2. Set B.inh from A.inh

3. C.s₁ := C.inh * 2

4. A.s₁ := B.s₂ + C.s₁

S-Attributed and L-Attributed SDDs

S-Attributed (Synthesized-Only)

E	E₁ + T {E.val := E₁.val + T.val}
E	T {E.val := T.val}
T	id {T.val := id.value}
Evaluation: leaves	root

L-Attributed (with Inherited)

For production A	X₁ X₂ ... Xₖ:
D	T L {T.prec := 0; L.type := T.type}
L	L₁ , id {L₁.type := L.type;

Translation Strategies

Strategy 1: Recursive Descent with SDT

python example

class Parser:
    def parse_E(self, inherited_attr):
        # Compute attributes during parsing
        if lookahead == '+':
            e1_val = parse_E(inherited_attr)
            consume('+')
            t_val = parse_T(inherited_attr)
            result = e1_val + t_val  # Semantic rule
            return result

Strategy 2: Bottom-Up (LR) Evaluation

Example

During LR parsing, maintain attribute stack: - Stack: [state₁, attr₁, state₂, attr₂, ...] - On reduce: pop attributes, apply semantic rule - Push result attribute

Practical Implementation Example

Symbol Table Declaration

Grammar

D → id : T {addSymbol(id.name, T.type)}

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

T → array [ num ] of T₁ {T.type = ArrayType(num, T₁.type)}

SDD Rules

addSymbol(name, type):

Check name not already defined

Insert into symbol table

Parse: array[10] of int x

Result: symbol_table[x] = array[10] of integer

Error Handling in SDD

Add error-handling attribute

Production: E → E₁ + E₂

Rules

if E₁.type == E₂.type:

E.type := E₁.type

E.val := E₁.val + E₂.val

else:

E.type := "error"

E.error := "type mismatch"

Quick Revision Notes

SDD: Declarative semantic specification (grammar + attribute rules)
Attribute: Value computed for each parse tree node
Synthesized: Computed from children (bottom-up)
Inherited: Computed from parent/siblings (top-down)
S-attributed: Only synthesized attributes (simple evaluation)
L-attributed: Inherited + synthesized, left-to-right (LL-compatible)
Dependency graph: Determines attribute evaluation order
Evaluation order: Must be acyclic; many valid orders possible

Interview Q&A

Q1: How does SDD differ from SDT in terms of implementation?

A: SDD is declarative—you specify what attributes mean, not when to compute them. SDT is procedural—you specify when actions execute. SDD is more abstract; you must choose an evaluation strategy (top-down, bottom-up, dynamic programming). SDT directly specifies execution.

Q2: Can you have cycles in dependency graphs?

A: No. Cycles would mean no valid evaluation order exists. The parser would not know when all dependencies are satisfied. SDD design must ensure acyclic dependencies. If cycles appear, the grammar/rules need restructuring.

Q3: What's the difference between S-attributed and L-attributed SDDs?

A: S-attributed uses only synthesized attributes (computable in one bottom-up pass). L-attributed adds inherited attributes but ensures no right-to-left data flow within a production. L-attributed is more expressive but requires careful evaluation order.

Q4: How do you handle symbol table lookups (which are external state) in SDD?

A: Use global/shared state accessed via attribute rules. Declare a semantic predicate that checks symbol table during evaluation. Many implementations use procedures (actions) rather than pure attribute rules for practical side effects.

Q5: Can you convert any SDD into a semantically equivalent SDT?

A: Not always directly. SDD allows any acyclic evaluation order. SDT forces a specific order (tied to parsing). Converting may require reordering or restructuring. However, any S-attributed SDD converts easily to SDT (bottom-up after reductions).

Q6: What happens if you evaluate a dependency graph in the wrong order?

A: You'll try to use uninitialized values, producing garbage results, crashes, or undefined behavior. Good compilers detect dependency violations at compile-time by analyzing the SDD before parsing begins.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Syntax-Directed Definitions: Attribute Grammars for Semantic Analysis.

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, definitions

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 Translation Schemes: Execution Semantics and Code GenerationMaster syntax-directed translation schemes (SDT) with evaluation order, semantic actions, attribute dependencies, L-attributed vs R-attributed grammars, parsing algorithm integration with complete examples.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.

PreviousInherited Attributes: Top-Down Attribute Computation for Context Transfer NextSyntax-Directed Translation Schemes: Execution Semantics and Code Generation

CD Notes

Syntax-Directed Definitions: Attribute Grammars for Semantic Analysis

Introduction

SDD vs SDT

SDD (Declarative)

E → E₁ + E₂ {E.val = E₁.val + E₂.val}

No evaluation order specified

SDT (Procedural)

E → E₁ + E₂ {E.val = E₁.val + E₂.val}

Specifies when action executes

Attribute Types

Synthesized Attributes

Computed from children's values (bottom-up):

Example

E (val) /|\ / | \ E₁ + E₂ (val) (val) E.val = E₁.val + E₂.val

Inherited Attributes

Computed from parent's/siblings' values (top-down):

Example

A (inh) /|\ / | \ B₁ B₂ B₃ (inh) (inh) (inh) B₁.inh from A.inh, A's other attributes B₂.inh from B₁.inh, B₁'s attributes

SDD Formal Definition

An SDD is a context-free grammar plus:

Attribute set for each grammar symbol
Semantic rule for each attribute
Predicate (semantic conditions) on rules

SDD Structure

Production: A → X₁ X₂ ... Xₖ

Semantic Rules

A.s₁ := f₁(X₁.a, X₁.b, X₂.c, ..., A.d)

X₁.b := f₂(A.inh, X₂.syn)

...

Semantic Rules and Consistency

Well-Defined SDD Rules

Rules must be:

Consistent: Each attribute assigned exactly once
Non-circular: No attribute depends on itself
Acyclic: No cycles in dependency graph

Example: Consistent SDD

Production: E	E₁ + T
E.type	= E₁.type ✓ Consistent
E.val	= E₁.val + T.val
E.val	= E₁.val + E.val ✗ Circular

Dependency Graphs

Construction Algorithm

For each parse tree

1. For each attribute instance a:

Create node in graph

2. For each attribute use:

Draw edge from defining rule to using rule

A depends on B if

- B appears on right side of rule computing A

- B is attribute of ancestor/sibling in grammar

Example: Dependency Analysis

Grammar

A → B C {A.s₁ := B.s₂ + C.s₁; B.inh := A.inh}

B → b {B.s₂ := 5}

C → c {C.s₁ := C.inh * 2}

Parse: b c

Dependency Graph

A.inh (input)

↓

B.inh (from A)

↓ (via rule)

C.s₁ (B.inh unknown unless value known)

Evaluation Order

1. B.s₂ := 5 (B rule)

2. Set B.inh from A.inh

3. C.s₁ := C.inh * 2

4. A.s₁ := B.s₂ + C.s₁

S-Attributed and L-Attributed SDDs

S-Attributed (Synthesized-Only)

E	E₁ + T {E.val := E₁.val + T.val}
E	T {E.val := T.val}
T	id {T.val := id.value}
Evaluation: leaves	root

L-Attributed (with Inherited)

For production A	X₁ X₂ ... Xₖ:
D	T L {T.prec := 0; L.type := T.type}
L	L₁ , id {L₁.type := L.type;

Translation Strategies

Strategy 1: Recursive Descent with SDT

python example

class Parser:
    def parse_E(self, inherited_attr):
        # Compute attributes during parsing
        if lookahead == '+':
            e1_val = parse_E(inherited_attr)
            consume('+')
            t_val = parse_T(inherited_attr)
            result = e1_val + t_val  # Semantic rule
            return result

Strategy 2: Bottom-Up (LR) Evaluation

Example

During LR parsing, maintain attribute stack: - Stack: [state₁, attr₁, state₂, attr₂, ...] - On reduce: pop attributes, apply semantic rule - Push result attribute

Practical Implementation Example

Symbol Table Declaration

Grammar

D → id : T {addSymbol(id.name, T.type)}

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

T → array [ num ] of T₁ {T.type = ArrayType(num, T₁.type)}

SDD Rules

addSymbol(name, type):

Check name not already defined

Insert into symbol table

Parse: array[10] of int x

Result: symbol_table[x] = array[10] of integer

Error Handling in SDD

Add error-handling attribute

Production: E → E₁ + E₂

Rules

if E₁.type == E₂.type:

E.type := E₁.type

E.val := E₁.val + E₂.val

else:

E.type := "error"

E.error := "type mismatch"

Quick Revision Notes

SDD: Declarative semantic specification (grammar + attribute rules)
Attribute: Value computed for each parse tree node
Synthesized: Computed from children (bottom-up)
Inherited: Computed from parent/siblings (top-down)
S-attributed: Only synthesized attributes (simple evaluation)
L-attributed: Inherited + synthesized, left-to-right (LL-compatible)
Dependency graph: Determines attribute evaluation order
Evaluation order: Must be acyclic; many valid orders possible

Interview Q&A

Q1: How does SDD differ from SDT in terms of implementation?

Q2: Can you have cycles in dependency graphs?

Q3: What's the difference between S-attributed and L-attributed SDDs?

Q4: How do you handle symbol table lookups (which are external state) in SDD?

Q5: Can you convert any SDD into a semantically equivalent SDT?

Q6: What happens if you evaluate a dependency graph in the wrong order?

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Syntax-Directed Definitions: Attribute Grammars for Semantic Analysis.

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, definitions

Continue learning this concept

PreviousInherited Attributes: Top-Down Attribute Computation for Context Transfer NextSyntax-Directed Translation Schemes: Execution Semantics and Code Generation