CD Notes

Attribute Grammars: Foundation of Semantic Analysis and Code Generation

Comprehensive study of attribute grammars in compiler design: attribute definitions, evaluation schemes, dependency graphs, parsing integration, practical implementations for modern compilers with industry examples.

Fundamentals

An Attribute Grammar is a context-free grammar augmented with attributes (values associated with symbols) and semantic rules (specifying how to compute them). It bridges syntax and semantics.

Components

1. Context-Free Grammar	Defines syntax structure
2. Attributes	Values attached to each symbol occurrence
3. Semantic Rules	Formulas defining attribute computation
4. Conditions/Predicates	Validity constraints on values

Attribute Definitions

Attribute Classification

For each grammar symbol X

- Synthesized attributes: X.s depends on children

- Inherited attributes: X.i depends on parent/siblings

For each symbol occurrence in parse tree

- Attribute value computed via semantic rules

- Value persists for use by other rules

Example: Type System Attribute Grammar

Grammar

Program → Decl* Stmt*

Decl → id : T

Stmt → id := Expr

T → int | real

Expr → id | Expr + Expr

Attributes

id.name ← token value (synthesized)

T.type ← "int"|"real" (synthesized)

Decl.scope ← symbol table entry (side-effect)

Expr.type ← inferred type (synthesized)

Expr.error ← type compatibility (synthesized)

Semantic Rules

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

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

Decl → id : T {addToSymbolTable(id.name, T.type)}

Expr → id {Expr.type = getSymbolType(id.name)}

Expr → Expr₁ + Expr₂ {

if Expr₁.type == Expr₂.type:

Expr.type = Expr₁.type

Expr.error = false

else:

Expr.type = "error"

Expr.error = true

}

Dependency Analysis

Building Dependency Graphs

For each attribute value in parse tree

1. Create node in dependency graph

2. For each rule computing attribute a:

- Add node for a

- For each attribute b used in rule:

- Add edge from b to a (b must be computed before a)

Constraints

- Acyclic: No cycles allowed (no valid evaluation order)

- Connected: Single source determines all values

Topological Sorting

Example

Algorithm: In-degree = 0 nodes (no dependencies) go first Process nodes, decrement in-degrees Continue until all processed Result: Valid evaluation order If cycle detected: Grammar is not well-defined

Example: Dependency in Type-Checking Grammar

Example

Production: Expr → Expr₁ + Expr₂ Parse tree: Expr (type=?) / | \ Expr₁ + Expr₂ (type=2) (type=2) Dependencies: Expr.type ← Expr₁.type ✓ (available) Expr.type ← Expr₂.type ✓ (available) No cycle ✓ Evaluation order: 1. Compute Expr₁.type (may be synthesized from children) 2. Compute Expr₂.type 3. Compute Expr.type using both

Evaluation Schemes

Scheme 1: Top-Down (LL-Compatible)

Evaluation

1. Process node's inherited attributes (from parent/context)

2. Process children recursively (top-down)

3. Synthesized attributes remain for siblings/parents

Example

procedure evalE(E, inherited_type):

if E has children E₁ op E₂:

evalE₁(E₁, inherited_type)

evalOp(op)

evalE₂(E₂, inherited_type)

E.synthesized := compute_from_children()

Scheme 2: Bottom-Up (LR-Compatible)

Evaluation

1. Process children recursively (bottom-up)

2. Compute node's synthesized attributes

3. Return to parent context

Example

procedure evalE(E):

if E has children E₁ op E₂:

E₁.syn := evalE(E₁)

E₂.syn := evalE(E₂)

E.syn := compute_from_children(E₁.syn, E₂.syn)

return E.syn

Grammar Properties

Well-Defined Attribute Grammars

Example

Conditions for soundness: 1. Consistency: - Each attribute assigned at most once - No attribute mentioned in both left and right side 2. Acyclic: - Dependency graph is acyclic - Valid evaluation order exists 3. Finite: - All computations terminate - No infinite loops in rules

Circularity Detection

Algorithm

1. Build dependency graph for parse tree

2. Perform DFS from each node

3. If node reachable from itself: CYCLE EXISTS

Example

A.x := A.y + 1 ✗ Direct cycle

A.x := B.y; B.y := A.x ✗ Indirect cycle

A.x := B.y; B.y := 5 ✓ No cycle

Parsing Integration

LL Parser + Attribute Grammar

During predictive parsing

1. Initialize inherited attributes from parent

2. Process right side of production

3. Synthesized attributes available for use above

Implementation

procedure A(inh):

-- compute A's synthesized from inh

for each symbol in production:

if symbol is non-terminal B:

B's inherited := compute_from_A_and_processed_symbols

recurse: B(inherited)

else terminal:

match token

A.synthesized := f(children_values)

LR Parser + Attribute Grammar

State Stack	[s₀, s₁, ..., sₙ]
Value Stack	[v₀, v₁, ..., vₙ]
Symbol Stack	[A₀, A₁, ..., Aₙ]
On reduce by A	X₁X₂...Xₖ:
Get values	v₁, v₂, ..., vₖ
Compute	new_value = f(v₁, v₂, ..., vₖ)

Practical Implementation Patterns

Pattern: Multi-Pass Compilation

Pass 1	Build symbol table (inherited: scope)
Pass 2	Type checking (inherited: expected type)
Pass 3	Code generation (synthesized: code string)

Pattern: Context-Aware Translation

Program	globalDecl* func*
globalDecl	id : T {context.global_scope.add(id, T)}
func	id ( param* ) T body

Error Handling via Attributes

Example

Add error attributes to track compilation issues: Grammar: Expr → Expr₁ + Expr₂ {if Expr₁.error or Expr₂.error: Expr.error = true Expr.type = "error" else if Expr₁.type ≠ Expr₂.type: Expr.error = true Expr.type = "error" report_error(...) else: Expr.error = false Expr.type = Expr₁.type} Errors propagate upward Compilation continues despite errors Multiple errors reported

Quick Revision Notes

Attribute Grammar: CFG + attributes + semantic rules
Synthesized: Computed from children (↑ upward flow)
Inherited: Computed from parent/siblings (↓ downward flow)
Dependency graph: Shows evaluation order constraints
Acyclic: Required for well-defined semantics
Evaluation strategies: Top-down (LL), bottom-up (LR), or multi-pass
Integration: Attributes computed during/after parsing

Interview Q&A

Q1: What is the fundamental difference between a grammar and an attribute grammar?

A: A grammar specifies syntax structure (what strings are valid). An attribute grammar adds semantics (what those strings mean). Attributes and rules specify properties of valid parse trees and how to compute translations (code, types, intermediate representations).

Q2: How do you detect if an attribute grammar is ill-formed?

A: Check for: 1) Circular dependencies in the dependency graph, 2) Attributes assigned in multiple rules (not single-assignment), 3) Use before definition. Build the dependency graph for sample parse trees and verify it's acyclic.

Q3: Can you have both inherited and synthesized attributes in the same production?

A: Yes, and this is common. Inherited attributes bring context down; synthesized flow up. The key is ensuring no circular dependencies. L-attributed grammars restrict how inherited can depend on synthesized in the same production.

Q4: What happens if your attribute grammar has circular dependencies?

A: No valid evaluation order exists. The compiler cannot decide which attribute to compute first. Parsing cannot proceed. You must restructure the grammar to break the cycle or separate into multiple passes.

Q5: How do attribute grammars relate to compilers in practice?

A: Most compilers use attribute grammar concepts: symbol tables (attributes), type checking (semantic rules), code generation (attributes computed during parsing or afterward). Parser generators like YACC embed action code equivalent to semantic rules.

Q6: Why are attribute grammars more powerful than plain context-free grammars?

A: CFGs specify syntax only. Attribute grammars specify syntax and semantic constraints (type checking, scope rules, attribute consistency). They can express properties not captured by CFG alone, making them useful for full language specification.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Attribute Grammars: Foundation of Semantic Analysis 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, attribute

Continue learning this concept

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 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.Syntax AnalysisAmbiguity in Grammars for Compiler DesignGuide to grammar ambiguity covering detection, types of ambiguity, disambiguation techniques, operator precedence, associativity encoding, and the dangling else problem.

PreviousType Conversion and Coercion in Compiler Semantic Analysis NextDependency Graphs: Visualizing Attribute Computation Order in Semantic Analysis

CD Notes

Attribute Grammars: Foundation of Semantic Analysis and Code Generation

Fundamentals

Components

1. Context-Free Grammar	Defines syntax structure
2. Attributes	Values attached to each symbol occurrence
3. Semantic Rules	Formulas defining attribute computation
4. Conditions/Predicates	Validity constraints on values

Attribute Definitions

Attribute Classification

For each grammar symbol X

- Synthesized attributes: X.s depends on children

- Inherited attributes: X.i depends on parent/siblings

For each symbol occurrence in parse tree

- Attribute value computed via semantic rules

- Value persists for use by other rules

Example: Type System Attribute Grammar

Grammar

Program → Decl* Stmt*

Decl → id : T

Stmt → id := Expr

T → int | real

Expr → id | Expr + Expr

Attributes

id.name ← token value (synthesized)

T.type ← "int"|"real" (synthesized)

Decl.scope ← symbol table entry (side-effect)

Expr.type ← inferred type (synthesized)

Expr.error ← type compatibility (synthesized)

Semantic Rules

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

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

Decl → id : T {addToSymbolTable(id.name, T.type)}

Expr → id {Expr.type = getSymbolType(id.name)}

Expr → Expr₁ + Expr₂ {

if Expr₁.type == Expr₂.type:

Expr.type = Expr₁.type

Expr.error = false

else:

Expr.type = "error"

Expr.error = true

}

Dependency Analysis

Building Dependency Graphs

For each attribute value in parse tree

1. Create node in dependency graph

2. For each rule computing attribute a:

- Add node for a

- For each attribute b used in rule:

- Add edge from b to a (b must be computed before a)

Constraints

- Acyclic: No cycles allowed (no valid evaluation order)

- Connected: Single source determines all values

Topological Sorting

Example

Example: Dependency in Type-Checking Grammar

Example

Evaluation Schemes

Scheme 1: Top-Down (LL-Compatible)

Evaluation

1. Process node's inherited attributes (from parent/context)

2. Process children recursively (top-down)

3. Synthesized attributes remain for siblings/parents

Example

procedure evalE(E, inherited_type):

if E has children E₁ op E₂:

evalE₁(E₁, inherited_type)

evalOp(op)

evalE₂(E₂, inherited_type)

E.synthesized := compute_from_children()

Scheme 2: Bottom-Up (LR-Compatible)

Evaluation

1. Process children recursively (bottom-up)

2. Compute node's synthesized attributes

3. Return to parent context

Example

procedure evalE(E):

if E has children E₁ op E₂:

E₁.syn := evalE(E₁)

E₂.syn := evalE(E₂)

E.syn := compute_from_children(E₁.syn, E₂.syn)

return E.syn

Grammar Properties

Well-Defined Attribute Grammars

Example

Circularity Detection

Algorithm

1. Build dependency graph for parse tree

2. Perform DFS from each node

3. If node reachable from itself: CYCLE EXISTS

Example

A.x := A.y + 1 ✗ Direct cycle

A.x := B.y; B.y := A.x ✗ Indirect cycle

A.x := B.y; B.y := 5 ✓ No cycle

Parsing Integration

LL Parser + Attribute Grammar

During predictive parsing

1. Initialize inherited attributes from parent

2. Process right side of production

3. Synthesized attributes available for use above

Implementation

procedure A(inh):

-- compute A's synthesized from inh

for each symbol in production:

if symbol is non-terminal B:

B's inherited := compute_from_A_and_processed_symbols

recurse: B(inherited)

else terminal:

match token

A.synthesized := f(children_values)

LR Parser + Attribute Grammar

State Stack	[s₀, s₁, ..., sₙ]
Value Stack	[v₀, v₁, ..., vₙ]
Symbol Stack	[A₀, A₁, ..., Aₙ]
On reduce by A	X₁X₂...Xₖ:
Get values	v₁, v₂, ..., vₖ
Compute	new_value = f(v₁, v₂, ..., vₖ)

Practical Implementation Patterns

Pattern: Multi-Pass Compilation

Pass 1	Build symbol table (inherited: scope)
Pass 2	Type checking (inherited: expected type)
Pass 3	Code generation (synthesized: code string)

Pattern: Context-Aware Translation

Program	globalDecl* func*
globalDecl	id : T {context.global_scope.add(id, T)}
func	id ( param* ) T body

Error Handling via Attributes

Example

Quick Revision Notes

Attribute Grammar: CFG + attributes + semantic rules
Synthesized: Computed from children (↑ upward flow)
Inherited: Computed from parent/siblings (↓ downward flow)
Dependency graph: Shows evaluation order constraints
Acyclic: Required for well-defined semantics
Evaluation strategies: Top-down (LL), bottom-up (LR), or multi-pass
Integration: Attributes computed during/after parsing

Interview Q&A

Q1: What is the fundamental difference between a grammar and an attribute grammar?

Q2: How do you detect if an attribute grammar is ill-formed?

Q3: Can you have both inherited and synthesized attributes in the same production?

Q4: What happens if your attribute grammar has circular dependencies?

Q5: How do attribute grammars relate to compilers in practice?

Q6: Why are attribute grammars more powerful than plain context-free grammars?

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Attribute Grammars: Foundation of Semantic Analysis 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, attribute

Continue learning this concept

PreviousType Conversion and Coercion in Compiler Semantic Analysis NextDependency Graphs: Visualizing Attribute Computation Order in Semantic Analysis