CD Notes
HubApplications of Compiler DesignCompiler vs Interpreter — Compiler DesignLanguage ProcessorsPhases of a CompilerWhat is Compiler Design?The AssemblerCompiler OverviewComplete Compilation ProcessThe LinkerThe LoaderThe PreprocessorFinite Automata in Lexical AnalysisIntroduction to Lexical AnalysisLex Tool - Lexical Analyzer GeneratorLexemes in Compiler DesignLexical Analyzer DesignLexical Errors and Error RecoveryPatterns in Lexical AnalysisRegular Expressions in Compiler DesignTokens in Compiler DesignAmbiguity in Grammars for Compiler DesignBottom-Up Parsing in Compiler DesignCLR Parser: Canonical LR(1) Parsing with Complete Lookahead InformationContext-Free Grammars for Syntax AnalysisDerivations in Syntax AnalysisIntroduction to Parsing in Compiler DesignLALR Parser: Practical LR(1) With State Merging for EfficiencyLL(1) Parser: Single Lookahead Predictive Parsing from First PrinciplesLR Parsers: Canonical LR Parsing for Complex Language SyntaxParse Trees in Compiler DesignPredictive Parsers: Lookahead-Guided Top-Down ParsingRecursive Descent Parsers: Procedural Approach to Top-Down ParsingShift-Reduce Parsing: Fundamental Mechanism of Bottom-Up Syntax AnalysisSLR Parser: Simple LR Parsing with Efficient AutomataTop-Down Parsing Techniques in Compiler DesignScope Management: Symbol Table Design for Language ImplementationSemantic Analysis IntroductionSemantic Errors: Detection and Reporting in Compiler ConstructionSemantic Rules: Defining Language Semantics in Compiler ConstructionSymbol Table: Core Data Structure for Semantic Analysis and Code GenerationType Checking: Static Analysis for Type Safety in Compiler DesignType Conversion and Coercion in Compiler Semantic AnalysisAttribute Grammars: Foundation of Semantic Analysis and Code GenerationDependency Graphs: Visualizing Attribute Computation Order in Semantic AnalysisInherited Attributes: Top-Down Attribute Computation for Context TransferSyntax-Directed Definitions: Attribute Grammars for Semantic AnalysisSyntax-Directed Translation Schemes: Execution Semantics and Code GenerationSynthesized Attributes: Bottom-Up Attribute Computation in Compiler DesignDirected Acyclic Graphs (DAGs) in Compiler DesignIndirect Triples in Compiler DesignIntroduction to Intermediate Code GenerationQuadruples Representation in Compiler DesignSyntax Trees as Intermediate RepresentationThree-Address Code in Compiler DesignTriples Representation in Compiler DesignActivation Records: Function Call ManagementHeap Allocation: Dynamic Memory ManagementMemory Management: Strategies and OptimizationParameter Passing: Communication Between FunctionsRuntime Environment: Program Execution ContextStack Allocation: Automatic Memory ManagementStorage Organization: Memory Sections and LayoutIntroduction to Code Generation in Compiler DesignCode Generator Design in Compiler ConstructionInstruction Selection in Code GenerationMachine Code Generation in CompilersRegister Allocation in Compiler DesignRegister Assignment Strategies in Code GenerationTarget Machine Architecture for Code GenerationIntroduction to Code Optimization in Compiler DesignCommon Subexpression Elimination (CSE) in Compiler OptimizationConstant Folding Optimization in Compiler DesignConstant Propagation in Compiler OptimizationDead Code Elimination in Compiler OptimizationGlobal Optimization Techniques in Compiler DesignLocal Optimization Techniques in Compiler DesignLoop Optimization Techniques in Compiler DesignPeephole Optimization in Compiler DesignBison: LALR Parser GeneratorFlex: Lexical Analyzer GeneratorLex: Original Lexical AnalyzerParser Generator WorkflowPractical Parser ProjectsYACC: Original Parser GeneratorBytecode and Virtual MachinesGCC ArchitectureJava Compiler and BytecodeJust-In-Time CompilationLLVM: The Low-Level Virtual MachinePython Interpreter ArchitectureWebAssembly BasicsCalculator Compiler ProjectExpression Parser ProjectLexical Analyzer ProjectMini Programming Language ProjectSyntax Checker ProjectToy Compiler Project: Minimal Complete CompilerCompiler Design CheatsheetCompiler Design Interview QuestionsGATE Compiler Design QuestionsLexical Analysis Interview QuestionsParsing Interview QuestionsGlossary of Compiler Design TermsImportant Formulas and RulesQuick Revision Notes for ExamsRecommended Books and Resources — Compiler DesignContext-Free Languages in Compiler DesignDeterministic Finite Automata (DFA) in Compiler DesignFinite Automata Review for Compiler DesignNondeterministic Finite Automata (NFA) in Compiler DesignPushdown Automata (PDA) in Compiler DesignRegular Languages in Compiler DesignTuring Machines and Their Role in Compiler Theory
Comprehensive guide to symbol tables: implementation strategies (hash tables, trees), entry structure, scope management, attribute storage, update mechanisms, practical compiler implementation with code.
Purpose
A symbol table is a core data structure that maps names (identifiers) to their attributes (type, scope, address, etc.). It enables:
| 1. Name Resolution | Find what identifier refers to |
| 2. Semantic Checking | Verify valid usage |
| 3. Code Generation | Get address/register for identifier |
| 4. Error Reporting | Provide context for errors |
Symbol Table Structure
Symbol Entry
| name | string // Identifier name |
| kind | enum // variable, function, class, constant |
| type | Type // int, float, array, struct, etc. |
| scope_level | integer // 0=global, 1=first nested, ... |
| attributes | { |
| address | memory_location // Where stored in memory |
| size | integer // Bytes allocated |
| initialized | boolean // Has value been set? |
| used | boolean // Has been referenced? |
| declared_line | integer // For error reporting |
| is_constant | boolean // Read-only? |
| visibility | enum // public, private, protected |
| initial_value | value // For constants |
Multiple Symbol Tables (Scope Chain)
| Global Scope Table | {x: int, foo: function} |
| ├─ Function A Scope | {x: local int, y: local int} |
| │ └─ Block 1 Scope | {z: local int} |
| └─ Function B Scope | {a: parameter, b: local int} |
| 1. Check Block 1 | not found |
| 2. Check Function A | found! (local x) |
Implementation Strategies
Strategy 1: Hash Table + Scope Chain
Example
class SymbolTable:
def __init__(self, parent=None):
self.parent = parent
self.symbols = {} # name → Symbol
self.scope_level = (parent.scope_level + 1) if parent else 0
def add_symbol(self, name, symbol):
if name in self.symbols:
raise SemanticError(f"{name} already in scope")
self.symbols[name] = symbol
def lookup(self, name):
# Check current scope first
if name in self.symbols:
return self.symbols[name]
# Check parent scopes
if self.parent:
return self.parent.lookup(name)
# Not found
return None
def lookup_local(self, name):
# Only current scope, no parent lookup
return self.symbols.get(name)
def enter_scope(self):
# Push new scope
return SymbolTable(parent=self)
# Usage:
global_scope = SymbolTable()
global_scope.add_symbol('printf', Function('printf', StringType))
func_a_scope = global_scope.enter_scope()
func_a_scope.add_symbol('x', Variable('x', IntType))
block_scope = func_a_scope.enter_scope()
block_scope.add_symbol('y', Variable('y', FloatType))
# Lookup x from block scope:
x = block_scope.lookup('x') # Found in func_a_scope
Strategy 2: Tree Structure (BST)
| - Fast lookup | O(log n) |
| - Range queries | Find all symbols in range |
| - Ordered traversal | Process symbols in order |
Symbol Table Operations
Insert Symbol
Example
def insert(identifier, type_info, attributes):
# Check not already in current scope
if self.lookup_local(identifier) is not None:
error(f"'{identifier}' redefined")
return
# Create symbol entry
symbol = Symbol(
name=identifier,
type=type_info,
scope_level=self.scope_level,
attributes=attributes
)
self.symbols[identifier] = symbol
# Mark as declared for error reporting
symbol.declared_at = (current_file, current_line)
Lookup Symbol
Example
def lookup(identifier):
# Search from current to global scope
scope = current_scope
while scope is not None:
if identifier in scope.symbols:
return scope.symbols[identifier]
scope = scope.parent
# Not found
error(f"Undefined: '{identifier}'")
return None
Update Symbol
Example
def update_symbol(identifier, new_attributes):
symbol = self.lookup(identifier)
if symbol is None:
error(f"Cannot update undefined '{identifier}'")
return
# Update attributes
symbol.attributes.update(new_attributes)
# Examples:
# symbol.attributes['initialized'] = True
# symbol.attributes['used'] = True
# symbol.attributes['type'] = new_type
Practical Implementation
Semantic Analysis with Symbol Table
Example
def process_declaration(var_name, var_type):
# Check not already declared in current scope
if current_scope.lookup_local(var_name) is not None:
error(f"Redeclaration: {var_name}")
return
# Add to symbol table
current_scope.add_symbol(
var_name,
Symbol(
name=var_name,
type=var_type,
kind='variable',
attributes={
'initialized': False,
'used': False,
'address': allocate_memory(var_type.size),
'declared_line': current_line
}
)
)
def process_usage(var_name):
symbol = current_scope.lookup(var_name)
if symbol is None:
error(f"Undefined: {var_name}")
return ErrorType()
# Mark as used
symbol.attributes['used'] = True
return symbol.type
def process_assignment(var_name, value_type):
symbol = current_scope.lookup(var_name)
if symbol is None:
error(f"Undefined: {var_name}")
return
# Check type compatibility
if not is_compatible(value_type, symbol.type):
error(f"Cannot assign {value_type} to {symbol.type}")
return
# Mark as initialized
symbol.attributes['initialized'] = True
Advanced Features
Shadowing Warnings
python example
def add_symbol_with_shadowing_check(name, symbol):
if self.parent and self.parent.lookup(name) is not None:
warning(f"'{name}' shadows outer scope declaration")
self.add_symbol(name, symbol)Unused Variable Detection
Example
def check_unused_variables():
for scope in all_scopes:
for name, symbol in scope.symbols.items():
if symbol.kind == 'variable' and not symbol.attributes['used']:
warning(f"Unused variable: {name} (declared at {symbol.declared_at})")
Quick Revision Notes
- Symbol table: Maps identifiers to attributes
- Entry: name, type, kind, scope, attributes
- Scope chain: Current scope + parent scopes
- Lookup: Search chain from innermost to global
- Insert: Add to current scope only
- Hash table: Fast O(1) lookup
- Scope level: Tracks nesting depth
Interview Q&A
Q1: Why use scope chains instead of flat symbol table?
A: Scope chains enable shadowing (inner scope can hide outer names) and automatic cleanup when scope exits. Flat tables require manual namespace management and cannot express nested scopes naturally.
Q2: How do hash table collisions affect symbol table performance?
A: Collisions slow lookup from O(1) to O(chain_length). Good hash function and load factor control minimize collisions. Linear probing or chaining handles collisions. Typically O(1) amortized in practice.
Q3: How do you handle function overloading in symbol tables?
A: Store multiple symbols with same name but different signatures (parameter types). Lookup includes signature matching: find symbol matching name + parameter types. Many languages use separate lookup_function(name, types).
Q4: What's the difference between symbol table and name mangling?
A: Symbol table: runtime data structure for compiler. Name mangling: encoding names to avoid conflicts (C++ mangles function names based on signature). Related: mangling helps generate unique names for symbol table.
Q5: How do you handle forward declarations in symbol tables?
A: Two-pass approach: first pass collects all declarations (create symbol table entries), second pass checks usage. Or: create placeholder symbols on first mention, verify on definition.
Q6: How do symbol tables support code generation?
A: Symbol table provides: memory addresses for variables, function entry points, type information for type-specific instructions. Code generator queries symbol table to get this info during translation.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Symbol Table: Core Data Structure for 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, semantic, analysis, symbol, table
Related Compiler Design Topics
Continue learning this concept
Semantic AnalysisScope Management: Symbol Table Design for Language ImplementationIn-depth guide to scope management: nested scopes, scope chains, symbol table implementation, scope resolution, variable shadowing, lifetime management, practical compiler symbol management techniques.Semantic AnalysisSemantic Analysis IntroductionOverview of semantic analysis, type checking, scope validation, and semantic rulesSemantic AnalysisSemantic Errors: Detection and Reporting in Compiler ConstructionComprehensive treatment of semantic errors: error classification, detection strategies, error recovery, reporting mechanisms, parser integration, practical error handling in modern compilers.Semantic AnalysisSemantic Rules: Defining Language Semantics in Compiler ConstructionMaster semantic rules: rule specification, constraint checking, type rules, scope rules, dependency resolution, practical implementation in attribute grammar frameworks for modern language compilers.Semantic AnalysisType Checking: Static Analysis for Type Safety in Compiler DesignComprehensive exploration of type checking: type system fundamentals, type inference algorithms, compatibility checking, polymorphism handling, practical static type analysis for modern programming languages.Semantic AnalysisType Conversion and Coercion in Compiler Semantic AnalysisComprehensive guide to type conversions: implicit coercion rules, explicit casting, type promotion hierarchies, compatibility checking, code generation for conversions, practical compiler implementation strategies.