📚 Attribute Grammar Foundations
🎯 What are Attribute Grammars?
Attribute Grammars extend context-free grammars with attributes and semantic rules, enabling static semantics, type checking, and code generation in compilers.
Core Concepts
Attributes: Values associated with grammar symbols. Semantic rules: Define how attributes are computed. Syntax-directed translation: Map syntax to semantics.
# Example: Simple arithmetic expression grammar
# E -> E + T { E.val = E1.val + T.val }
# E -> T { E.val = T.val }
# T -> T * F { T.val = T1.val * F.val }
# T -> F { T.val = F.val }
# F -> number { F.val = number.value }
class AttributeGrammar:
def __init__(self):
self.rules = {}
def add_rule(self, production, rule):
self.rules[production] = rule📝 Syntax-Directed Translation
🎯 Translating Syntax to Semantics
Syntax-directed translation attaches semantic rules to grammar productions, computing attribute values during parsing.
Translation Process
Parse tree: Built from grammar. Attribute evaluation: Compute attribute values. Output generation: Produce code or results.
class SyntaxDirectedTranslator:
def __init__(self, grammar):
self.grammar = grammar
self.semantic_actions = {}
def add_semantic_action(self, production, action):
self.semantic_actions[production] = action
def translate(self, parse_tree):
"""Perform syntax-directed translation"""
for node in parse_tree.postorder():
if node.production in self.semantic_actions:
self.semantic_actions[node.production](node)⬆️ Synthesized Attributes
🎯 Bottom-Up Computation
Synthesized attributes are computed from children of a node in the parse tree, flowing bottom-up.
Synthesized Examples
Expression value: Computed from operand values. Type: Derived from child types. Size: Sum of child sizes.
class SynthesizedAttribute:
def __init__(self, name, compute_fn):
self.name = name
self.compute_fn = compute_fn
def compute(self, node):
"""Compute attribute from children"""
child_values = [child.get_attr(self.name) for child in node.children]
return self.compute_fn(child_values)
# Example: Value attribute for expressions
def compute_value(child_values):
# child_values contains values of operands
return child_values[0] + child_values[1]⬇️ Inherited Attributes
🎯 Top-Down Flow
Inherited attributes flow from parent to children, providing context information down the parse tree.
Inherited Examples
Scope information: Passed to children. Symbol table: Inherited from parent. Environment: Context for evaluation.
class InheritedAttribute:
def __init__(self, name, compute_fn):
self.name = name
self.compute_fn = compute_fn
def compute(self, node):
"""Compute attribute from parent and siblings"""
parent_value = node.parent.get_attr(self.name)
return self.compute_fn(parent_value, node)
# Example: Scope information for variable declarations
def compute_scope(parent_scope, node):
if node.is_declaration():
return parent_scope + [node.var_name]
return parent_scope🔗 Dependency Graphs
🎯 Attribute Dependencies
Dependency graphs show which attributes depend on others, determining evaluation order.
Graph Properties
Nodes: Attribute instances. Edges: Dependencies between attributes. Acyclic: Must have no cycles for evaluation.
class DependencyGraph:
def __init__(self):
self.nodes = {}
self.edges = {}
def add_dependency(self, attr1, attr2):
"""Add dependency attr2 depends on attr1"""
if attr1 not in self.edges:
self.edges[attr1] = []
self.edges[attr1].append(attr2)
def topological_sort(self):
"""Compute evaluation order"""
visited = set()
order = []
def dfs(node):
visited.add(node)
for dep in self.edges.get(node, []):
if dep not in visited:
dfs(dep)
order.append(node)
for node in self.nodes:
if node not in visited:
dfs(node)
return list(reversed(order))⚡ Evaluation Orders
🎯 Attribute Evaluation Strategies
Various strategies for evaluating attributes: top-down, bottom-up, and topological order based on dependency graphs.
Evaluation Methods
Bottom-up: Evaluate synthesized attributes. Top-down: Evaluate inherited attributes. Hybrid: Combine both strategies.
class AttributeEvaluator:
def __init__(self, grammar):
self.grammar = grammar
self.dependency_graph = DependencyGraph()
def evaluate_bottom_up(self, parse_tree):
"""Evaluate synthesized attributes bottom-up"""
for node in parse_tree.postorder():
for attr in node.synthesized_attributes:
attr.compute(node)
def evaluate_top_down(self, parse_tree):
"""Evaluate inherited attributes top-down"""
for node in parse_tree.preorder():
for attr in node.inherited_attributes:
attr.compute(node)
def evaluate_hybrid(self, parse_tree):
"""Hybrid evaluation based on dependency graph"""
order = self.dependency_graph.topological_sort()
for attr in order:
attr.compute(attr.node)📊 L-Attributed Grammars
🎯 Left-to-Right Evaluation
L-attributed grammars allow evaluation during a left-to-right depth-first traversal of the parse tree.
L-Attributed Properties
Inherited attributes: Depend only on left siblings and parent. Synthesized attributes: Computed normally. Evaluation: One pass left-to-right.
class LAttributedGrammar:
def __init__(self):
self.productions = {}
def is_l_attributed(self):
"""Check if grammar is L-attributed"""
for production in self.productions:
for attr in production.inherited:
# Check that inherited attributes only depend on
# left siblings and parent attributes
if not self.depends_on_right(attr):
return False
return True
def evaluate(self, parse_tree):
"""Evaluate L-attributed grammar"""
# Depth-first left-to-right traversal
def dfs(node):
for child in node.children:
# Compute inherited attributes for child
for attr in child.inherited:
attr.compute(child)
dfs(child)
# Compute synthesized attributes
for attr in node.synthesized:
attr.compute(node)
dfs(parse_tree.root)📊 S-Attributed Grammars
🎯 Only Synthesized Attributes
S-attributed grammars use only synthesized attributes, allowing simple bottom-up evaluation during LR parsing.
S-Attributed Properties
No inherited attributes: Only synthesized. Simple evaluation: Bottom-up only. Parse-time: Evaluate during parsing.
class SAttributedGrammar:
def __init__(self):
self.productions = {}
def evaluate_during_parse(self, tokens):
"""Evaluate S-attributed grammar during parsing"""
stack = []
for token in tokens:
# Shift token
stack.append(token)
# Reduce when possible
while self.can_reduce(stack):
production = self.find_production(stack)
# Compute synthesized attributes
result = production.evaluate(stack)
# Replace production with result
stack = self.replace(stack, production, result)
return stack[0] # Final result🎯 Semantic Actions
🎯 Actions During Parsing
Semantic actions are code snippets executed during parsing to perform semantic processing, type checking, or code generation.
Action Examples
Type checking: Verify operand types. Symbol table: Add declarations. Code generation: Generate intermediate code.
class SemanticAction:
def __init__(self, action_fn):
self.action_fn = action_fn
def execute(self, parse_node):
"""Execute semantic action"""
return self.action_fn(parse_node)
# Example: Type checking for arithmetic operations
def type_check_addition(node):
left_type = node.children[0].type
right_type = node.children[1].type
if left_type != right_type:
raise TypeError(f"Type mismatch: {left_type} vs {right_type}")
return left_type
# Example: Code generation for expressions
def generate_code_addition(node):
left_code = node.children[0].code
right_code = node.children[1].code
return f"{left_code} + {right_code}"🔍 Type Checking
🎯 Static Type Analysis
Attribute grammars are ideal for type checking, propagating type information through the parse tree.
Type Checking Process
Type inference: Compute types from context. Type compatibility: Check operation validity. Type errors: Report mismatches.
class TypeChecker:
def __init__(self):
self.type_table = {}
def check(self, parse_tree):
"""Perform type checking using attribute grammar"""
for node in parse_tree.postorder():
if node.production == "E -> E + T":
left_type = node.children[0].type
right_type = node.children[1].type
if left_type != right_type:
raise TypeError(f"Type mismatch in addition: {left_type} + {right_type}")
node.type = left_type
elif node.production == "T -> T * F":
left_type = node.children[0].type
right_type = node.children[1].type
if left_type != right_type:
raise TypeError(f"Type mismatch in multiplication: {left_type} * {right_type}")
node.type = left_type
# Additional type rules...
return parse_tree💻 Code Generation
🎯 Generating Output Code
Attribute grammars can generate code by attaching code generation rules to grammar productions.
Code Gen Process
Intermediate code: Three-address code. Target code: Assembly or bytecode. Optimization: Improve generated code.
class CodeGenerator:
def __init__(self):
self.temp_counter = 0
self.code = []
def new_temp(self):
self.temp_counter += 1
return f"t{self.temp_counter}"
def generate(self, parse_tree):
"""Generate three-address code from parse tree"""
for node in parse_tree.postorder():
if node.production == "E -> E + T":
left = node.children[0].code
right = node.children[1].code
temp = self.new_temp()
self.code.append(f"{temp} = {left} + {right}")
node.code = temp
elif node.production == "E -> T":
node.code = node.children[0].code
elif node.production == "T -> T * F":
left = node.children[0].code
right = node.children[1].code
temp = self.new_temp()
self.code.append(f"{temp} = {left} * {right}")
node.code = temp
elif node.production == "T -> F":
node.code = node.children[0].code
return self.code🛠️ Compiler Tools
🎯 Tools for Attribute Grammars
Tools like ANTLR, Yacc/Bison, and attribute grammar systems automate semantic processing from grammar specifications.
Tool Features
Parser generators: Yacc, ANTLR. Attribute evaluators: Automatic dependency analysis. IDE support: Syntax highlighting, debugging.
// ANTLR grammar with semantic actions
grammar Expr;
expr returns [int value]
: e1=expr '+' e2=expr { $value = $e1.value + $e2.value; }
| e1=expr '*' e2=expr { $value = $e1.value * $e2.value; }
| INT { $value = Integer.parseInt($INT.text); }
;
INT : [0-9]+ ;
WS : [ \t\r\n]+ -> skip ;🚀 Applications
🎯 Real-World Uses
Attribute grammars are used in compiler design, language processing, program analysis, and domain-specific languages.
Application Domains
Compilers: Semantic analysis, code generation. Language design: Defining semantics. Program analysis: Static analysis tools.
class Compiler:
def __init__(self):
self.lexer = Lexer()
self.parser = Parser()
self.semantic_analyzer = SemanticAnalyzer()
self.code_generator = CodeGenerator()
def compile(self, source):
tokens = self.lexer.tokenize(source)
parse_tree = self.parser.parse(tokens)
self.semantic_analyzer.analyze(parse_tree)
code = self.code_generator.generate(parse_tree)
return code🔬 Advanced Topics
🎯 Research Frontiers
Current research includes higher-order attribute grammars, circularity detection, and incremental evaluation.
Research Directions
Higher-order: Attributes that are functions. Incremental: Re-evaluate only affected attributes. Parallel: Parallel attribute evaluation.
class HigherOrderAttribute:
"""Attributes that are functions"""
def __init__(self, fn):
self.fn = fn
def compute(self, node):
# Function attribute returns other attributes
return self.fn(node)
# Incremental evaluator
class IncrementalEvaluator:
def __init__(self):
self.affected = set()
def mark_affected(self, node):
self.affected.add(node)
def re_evaluate(self):
"""Re-evaluate only affected nodes"""
for node in self.affected:
# Recompute attributes
pass