CD Notes

Semantic Analysis Introduction

Overview of semantic analysis, type checking, scope validation, and semantic rules

Introduction: Beyond Syntax

Imagine a sentence in English that is grammatically perfect but meaningless: "The colorless green ideas sleep furiously." The grammar is correct — it has a subject, verb, and adverb — but the meaning makes no sense. Compilers face the same challenge. The parser ensures that code follows grammar rules (syntax), but that alone does not guarantee the code is meaningful. Semantic analysis is the phase that checks whether syntactically correct code actually makes sense.

Consider this C code: int x = "hello";. The syntax is perfect — it follows the pattern type identifier = expression;. But semantically, it is nonsense: you cannot store a string in an integer variable. The parser would accept it happily; only semantic analysis catches this error. This is why semantic analysis exists as a separate, essential phase.

What Semantic Analysis Checks

Semantic analysis performs several categories of validation, all of which go beyond what grammar rules can express:

Type Checking

The most prominent task — verifying that operations are applied to compatible types:

Example

int a = 10; float b = 3.14; int c = a + b; // OK: float→int conversion (with truncation warning) char *str = "hello"; int d = str + 5; // ERROR: cannot add integer to pointer in this context int e = str * 2; // ERROR: cannot multiply a string pointer float arr[10]; arr = 3.14; // ERROR: cannot assign scalar to array

The semantic analyzer walks the parse tree bottom-up, computing the type of each expression from the types of its subexpressions. When an operator is applied, it checks whether the operand types are compatible with that operator.

Scope Validation

Ensuring that every identifier is declared before use and used within its valid scope:

c example

void process() {
    y = x + 5;       // ERROR: 'x' not declared in this scope
    int x = 10;      // (Even though x is declared later, C requires declaration first)
    
    {
        int temp = x;
        // temp is valid here
    }
    
    temp = 20;        // ERROR: 'temp' not in scope (block ended)
}

Declaration Checking

Verifying that identifiers are declared exactly once in their scope (no duplicates) and that they are used consistently with their declarations:

c example

int count = 0;
float count = 1.0;   // ERROR: 'count' already declared in this scope

void display(int n);
display(1, 2, 3);    // ERROR: too many arguments (expected 1, got 3)

int max(int a, int b);
float result = max(3.14, 2.71);  // OK but arguments truncated to int

Other Semantic Checks

Return type consistency: Every return statement must return a value compatible with the function's declared return type
Break/continue validity: These statements must appear inside a loop
Array index type: Array indices must be integers, not floats or strings
Assignment target: The left side of an assignment must be an lvalue (a modifiable memory location)

The Symbol Table: Heart of Semantic Analysis

The symbol table is the central data structure that makes semantic analysis possible. It stores information about every declared identifier:

Example

typedef struct Symbol { char name[64]; // Identifier name char type[32]; // "int", "float", "char*", "int[]", etc. int scope_level; // Nesting depth (0=global, 1=function, 2=block, ...) int line_declared; // Source line of declaration int is_function; // Whether this is a function int param_count; // Number of parameters (if function) char param_types[10][32]; // Types of each parameter int memory_offset; // Where in memory/stack this lives } Symbol;

The symbol table supports nested scopes using a stack structure:

Entering function	push new scope
Entering block	push new scope
int x;	insert into current (top) scope
x + 5	lookup: search from top scope downward until found
Exiting block	pop scope (x disappears)
Exiting function	pop scope

How Semantic Analysis Works: An Algorithm

The semantic analyzer performs a depth-first traversal of the AST. At each node, it performs checks appropriate to that node type:

Example

Type analyze_node(ASTNode *node, SymbolTable *symtab) { switch (node->type) { case NODE_VAR_DECL: // Check not already declared in current scope if (lookup_current_scope(symtab, node->name)) error("'%s' already declared at line %d", node->name, ...); // Insert into symbol table insert(symtab, node->name, node->declared_type); // Check initializer type matches if (node->initializer) { Type init_type = analyze_node(node->initializer, symtab); check_compatible(node->declared_type, init_type, node->line); } return make_type(node->declared_type); case NODE_IDENTIFIER: // Look up in symbol table Symbol *sym = lookup(symtab, node->name); if (!sym) error("Undeclared variable '%s' at line %d", node->name, node->line); return sym->type; case NODE_BINARY_OP: Type left = analyze_node(node->left, symtab); Type right = analyze_node(node->right, symtab); return check_binary_op(node->op, left, right, node->line); case NODE_FUNC_CALL: Symbol *func = lookup(symtab, node->func_name); if (!func || !func->is_function) error("'%s' is not a function", node->func_name); check_argument_count(func, node->arg_count, node->line); check_argument_types(func, node->args, symtab, node->line); return func->return_type; } }

Worked Example: Tracing Semantic Analysis

Consider analyzing this program:

c example

int add(int a, int b) {
    return a + b;
}

void main() {
    float x = 3.14;
    int result = add(x, "hello");  // Multiple errors here!
}

The semantic analyzer processes this as follows:

- Insert add(int, int)	int into global symbol table
- Insert parameter 'a'	int
- Insert parameter 'b'	int
- Analyze return statement	a + b
- a is int, b is int	int + int = int ✓
- Process declaration	float x = 3.14
- 3.14 is float, x is float	compatible ✓
- Process declaration	int result = add(x, "hello")
- Lookup 'add': found, expects (int, int)	int
- Check argument 1	x is float, parameter expects int
- Check argument 2	"hello" is char*, parameter expects int
- Return type of add is int, result is int	compatible ✓

Semantic Errors vs Syntax Errors

Understanding the boundary between syntax and semantics is a common exam question:

Code	Error Type	Phase Detected	Reason
`int x = ;`	Syntax	Parser	Violates grammar rule
`int 5 = x;`	Syntax	Parser	Number cannot be lvalue
`int x = "hi";`	Semantic	Semantic analyzer	Type mismatch
`y = x + 1;` (x undeclared)	Semantic	Semantic analyzer	Undeclared variable
`int x; int x;`	Semantic	Semantic analyzer	Duplicate declaration
`break;` (outside loop)	Semantic	Semantic analyzer	Invalid context

Attribute Grammars: Formalizing Semantics

Attribute grammars provide a rigorous mathematical framework for specifying semantic analysis. Each grammar symbol gets attributes, and semantic rules define how to compute them:

Production: E	E₁ + E₂
Semantic Rule	E.type =
Production: D	type id
Semantic Rule	id.entry = insert(symtab, id.name, type.value)

This formalism separates the "what" (semantic rules) from the "how" (tree traversal algorithm), making it easier to reason about correctness and to automatically generate semantic analyzers from specifications.

Key Takeaways

Semantic analysis bridges the gap between syntactic correctness and meaningful computation. It validates that programs obey the rules that grammars cannot express — type compatibility, scope restrictions, declaration requirements, and usage constraints. The symbol table is its essential data structure, tracking what has been declared and what properties each identifier has. Without semantic analysis, a compiler would happily generate code for nonsensical programs, producing mysterious runtime failures instead of clear compile-time error messages.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Semantic Analysis Introduction.

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, introduction, semantic analysis introduction

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 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 AnalysisSymbol Table: Core Data Structure for Semantic Analysis and Code GenerationComprehensive guide to symbol tables: implementation strategies (hash tables, trees), entry structure, scope management, attribute storage, update mechanisms, practical compiler implementation with code.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.

PreviousScope Management: Symbol Table Design for Language Implementation NextSemantic Errors: Detection and Reporting in Compiler Construction

CD Notes

Semantic Analysis Introduction

Overview of semantic analysis, type checking, scope validation, and semantic rules

Introduction: Beyond Syntax

What Semantic Analysis Checks

Semantic analysis performs several categories of validation, all of which go beyond what grammar rules can express:

Type Checking

The most prominent task — verifying that operations are applied to compatible types:

Example

Scope Validation

Ensuring that every identifier is declared before use and used within its valid scope:

c example

void process() {
    y = x + 5;       // ERROR: 'x' not declared in this scope
    int x = 10;      // (Even though x is declared later, C requires declaration first)
    
    {
        int temp = x;
        // temp is valid here
    }
    
    temp = 20;        // ERROR: 'temp' not in scope (block ended)
}

Declaration Checking

Verifying that identifiers are declared exactly once in their scope (no duplicates) and that they are used consistently with their declarations:

c example

int count = 0;
float count = 1.0;   // ERROR: 'count' already declared in this scope

void display(int n);
display(1, 2, 3);    // ERROR: too many arguments (expected 1, got 3)

int max(int a, int b);
float result = max(3.14, 2.71);  // OK but arguments truncated to int

Other Semantic Checks

Return type consistency: Every return statement must return a value compatible with the function's declared return type
Break/continue validity: These statements must appear inside a loop
Array index type: Array indices must be integers, not floats or strings
Assignment target: The left side of an assignment must be an lvalue (a modifiable memory location)

The Symbol Table: Heart of Semantic Analysis

The symbol table is the central data structure that makes semantic analysis possible. It stores information about every declared identifier:

Example

The symbol table supports nested scopes using a stack structure:

Entering function	push new scope
Entering block	push new scope
int x;	insert into current (top) scope
x + 5	lookup: search from top scope downward until found
Exiting block	pop scope (x disappears)
Exiting function	pop scope

How Semantic Analysis Works: An Algorithm

The semantic analyzer performs a depth-first traversal of the AST. At each node, it performs checks appropriate to that node type:

Example

Worked Example: Tracing Semantic Analysis

Consider analyzing this program:

c example

int add(int a, int b) {
    return a + b;
}

void main() {
    float x = 3.14;
    int result = add(x, "hello");  // Multiple errors here!
}

The semantic analyzer processes this as follows:

- Insert add(int, int)	int into global symbol table
- Insert parameter 'a'	int
- Insert parameter 'b'	int
- Analyze return statement	a + b
- a is int, b is int	int + int = int ✓
- Process declaration	float x = 3.14
- 3.14 is float, x is float	compatible ✓
- Process declaration	int result = add(x, "hello")
- Lookup 'add': found, expects (int, int)	int
- Check argument 1	x is float, parameter expects int
- Check argument 2	"hello" is char*, parameter expects int
- Return type of add is int, result is int	compatible ✓

Semantic Errors vs Syntax Errors

Understanding the boundary between syntax and semantics is a common exam question:

Code	Error Type	Phase Detected	Reason
`int x = ;`	Syntax	Parser	Violates grammar rule
`int 5 = x;`	Syntax	Parser	Number cannot be lvalue
`int x = "hi";`	Semantic	Semantic analyzer	Type mismatch
`y = x + 1;` (x undeclared)	Semantic	Semantic analyzer	Undeclared variable
`int x; int x;`	Semantic	Semantic analyzer	Duplicate declaration
`break;` (outside loop)	Semantic	Semantic analyzer	Invalid context

Attribute Grammars: Formalizing Semantics

Attribute grammars provide a rigorous mathematical framework for specifying semantic analysis. Each grammar symbol gets attributes, and semantic rules define how to compute them:

Production: E	E₁ + E₂
Semantic Rule	E.type =
Production: D	type id
Semantic Rule	id.entry = insert(symtab, id.name, type.value)

Key Takeaways

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Semantic Analysis Introduction.

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, introduction, semantic analysis introduction

Continue learning this concept

PreviousScope Management: Symbol Table Design for Language Implementation NextSemantic Errors: Detection and Reporting in Compiler Construction