Syntax-Directed Translation and Semantic Analysis (part 2: 4.5–4.8)
Open in the Padhaiko app4.5 Semantic analysis, including static and dynamic checks
Syntactic correctness alone does not guarantee that a program is meaningful. A statement such as int x = "hello" + 5; or break; outside any loop conforms to a language's context-free grammar, yet violates language semantics. Semantic analysis verifies context-sensitive rules, gathers type and scope information into the symbol table, and prepares the AST for intermediate code generation.
4.5.1 Core Responsibilities of Semantic Analysis
- Declaration and Scope Resolution: Ensures every identifier is declared before use (where required) and binds each usage to its exact declaration under lexical or dynamic scoping rules.
- Type Checking and Coercion Insertion: Verifies operand compatibility for operators, assignments, array subscripts, and function calls, inserting implicit widening conversions (e.g.,
int_to_float) where permitted. - Uniqueness Checks: Detects duplicate variable names in the same scope, duplicate
caselabels in aswitchstatement, or repeated parameter names. - Flow-of-Control Checks: Ensures
breakandcontinueappear inside an enclosing loop orswitch, and that non-voidfunctions return a compatible value. - Name-Related Checks: Matches opening and closing block labels (e.g., in Ada/VHDL) or constructor/destructor names with their class name.
4.5.2 Static vs. Dynamic Semantic Checks
Semantic checks are divided into static checks (performed at compile time) and dynamic checks (performed at run time during program execution).
| Aspect | Static Checks (Compile-Time) | Dynamic Checks (Run-Time) |
|---|---|---|
| When Performed | During compilation (before execution) | During program execution (via compiler-emitted guard code or runtime hardware traps) |
| Information Used | Declarations, symbol table types, control-flow structure, constant expressions | Actual run-time values of variables, array indices, pointers, and dynamic object tags |
| Runtime Overhead | Zero runtime execution overhead; catches bugs early | Adds runtime instructions and memory overhead (bounds checks, tag fields) |
| Typical Examples | Type mismatch (int + string), undeclared variable, wrong argument count, duplicate case value, break outside loop | Array index out of bounds (a[i] where i >= n), null-pointer dereference, integer division by zero, unsafe downcast failure (ClassCastException) |
4.6 Type checking and type systems
A type checker verifies that the type of every construct matches what the surrounding context expects.
Type System
A type system is a collection of rules for assigning type expressions to the syntactic constructs of a program (constants, variables, operators, statements, and functions). A type error occurs when an operator or function is applied to an operand of an incompatible type.
4.6.1 Type Expressions
Types are represented systematically using type expressions:
- Basic (Primitive) Types: Atomic types such as
boolean,char,integer,float,void, and a special sentineltype_errorused to signal an error without cascading false diagnostics. - Type Names: User-defined names introduced via
typedef,struct, orclass. - Type Constructors: Applied to simpler type expressions to build composite types:
- Array: denotes an array of elements of type indexed by index set (e.g., ).
- Product (Cartesian Product): represents pairs/tuples, commonly used for argument lists of functions.
- Record (Struct): maps named fields to types .
- Pointer: denotes a memory reference to a value of type .
- Function: maps domain type (argument tuple) to range type (return type), e.g., .
4.6.2 Type Equivalence: Structural vs. Name Equivalence
When checking whether an expression of type can be assigned to a variable of type , the compiler must define what " equals " means:
| Aspect | Structural Equivalence | Name Equivalence |
|---|---|---|
| Criterion | Two type expressions are equivalent if and only if they are the same basic type or are formed by applying the same type constructor to structurally equivalent components | Two types are equivalent only if they have the exact same type name (declaration identity) |
| Behavior on Distinct Typedefs | typedef int Age; typedef int Score; — Age and Score are equivalent because both expand to int | Under strict name equivalence, Age and Score are distinct types |
| Recursive Types | Requires cycle detection (e.g., linked-list node pointers referencing themselves) | Checked in by comparing symbol-table pointers |
| Language Examples | Algol 68, Go (for unnamed struct/interface types), TypeScript (structural subtyping) | C/C++ (for struct and class), Java, Ada |
4.6.3 Type Conversion, Coercion, and Overloading
- Widening Conversion: Converts a value from a narrower type to a wider type capable of representing all values of the source type without information loss (e.g.,
charintlongfloatdouble). - Narrowing Conversion: Converts from a wider type to a narrower type (e.g.,
doubleint), risking precision loss or overflow. - Coercion vs. Explicit Cast: An implicit conversion inserted automatically by the compiler (typically widening) is called a coercion. A programmer-specified conversion such as
(int) xis an explicit cast. - Overloading and Polymorphism: An overloaded symbol (such as
+for both integer and floating-point addition, or a function name with multiple parameter signatures) has multiple candidate types resolved from operand context. Parametric polymorphism (generics/templates) allows a single function or data structure to operate uniformly over a type variable (e.g.,List<T>).
4.6.4 Simple Type Checking Rules (SDT)
| Construct / Production | Type Rule |
|---|---|
If both int, ; if one int and one float, coerce int to float and ; else type_error | |
If and , then ; else type_error | |
If , then ; else type_error | |
If and , then ; else type_error | |
If , then ; else type_error |
4.7 Symbol table construction, attributes, and data structures for symbol table
Symbol Table
A symbol table is a central compiler data structure that records every declared identifier (variables, constants, functions, types, labels) together with its semantic attributes. It is shared across all compiler phases—from lexical analysis (creating entries) through semantic analysis (populating types and scopes) to code generation (determining memory offsets and registers).
4.7.1 Attributes Stored in a Symbol Table
Each symbol table entry typically stores:
- Lexeme / Identifier Name: Character string (or pointer into a string pool) naming the symbol.
- Kind / Category: Variable, constant, formal parameter, function, array, struct/class, or label.
- Type Expression: Primitive type or composite type descriptor (e.g.,
array(0..9, float)). - Scope / Nesting Level: Lexical block depth or enclosing function identifier.
- Storage Allocation Information: Relative memory offset (within static area or stack frame), size in bytes, alignment, and storage class (
auto,static,extern,register). - Function Metadata: Number of parameters, parameter types, passing modes, and return type.
4.7.2 Scope Handling and Chained Symbol Tables
Block-structured languages (such as C, Java, and Pascal) obey the most closely nested scope rule: a reference to identifier x resolves to the declaration of x in the innermost enclosing block that declares x.
Compilers implement nested scopes in two standard ways:
- Chained (Linked) Scope Tables: Each block creates its own small symbol table containing a
parent(previous scope) pointer.lookup(name)searches the current block's table first and followsparentpointers outward untilnameis found or the global scope ends. When the parser exits a block, the current scope pointer moves back toparent. - Global Scoped Hash Table with Scope Stack: A single hash table maps each name to a stack of declarations (most recent scope on top). Entering a scope pushes new declarations onto their name stacks; exiting a scope pops all entries recorded on a scope undo list.
4.7.3 Data Structures for Symbol Tables
| Data Structure | Average Lookup | Insertion | Space Overhead | Best Use Case |
|---|---|---|---|---|
| Unordered Linear List | Minimal | Very small local scopes (e.g., locals) | ||
| Ordered Linear Array | (binary search) | (shifting elements) | Low | Static keyword tables known at compiler start |
| Binary Search Tree (BST) | balanced, skewed | balanced | Moderate (2 pointers/node) | Sorted symbol dumps, moderate tables |
| Hash Table (with Chaining) | expected () | expected | Bucket array + chain pointers | Production compilers with large programs (fast insert and lookup) |
For a chained hash table with symbols and buckets, the load factor is . Under uniform hashing:
- Expected probes for an unsuccessful search: .
- Expected probes for a successful search: .
4.8 Run–time storage management
During execution, a compiled program requires organized memory regions for instructions, global data, procedure call frames, and dynamically allocated objects.
4.8.1 Logical Subdivision of Run-Time Memory
Low Addresses
+---------------------------------------+
| Code (Text) Area | Fixed size, read-only machine instructions
+---------------------------------------+
| Static Data Area | Global variables, static locals, constants
+---------------------------------------+
| Heap | Grows upward (malloc / new)
| | |
| v |
| ... Free Memory ... |
| ^ |
| | |
| Control Stack (Activation Records) | Grows downward (procedure calls / returns)
+---------------------------------------+
High Addresses4.8.2 Storage Allocation Strategies
| Strategy | Binding Time | Recursion Support | Key Characteristics & Trade-offs |
|---|---|---|---|
| Static Allocation | Compile time | No | Every data object has a fixed address throughout execution; no stack/heap overhead; cannot support recursion or dynamic data sizes |
| Stack Allocation | Procedure call / return time | Yes | Memory managed as a LIFO control stack of activation records; local variables die when the procedure returns; very fast ( pointer bump) |
| Heap Allocation | Arbitrary run-time (malloc / new and free / GC) | Yes | Objects can outlive the procedure that created them; suffers from fragmentation and requires explicit deallocation or garbage collection |
4.8.3 Activation Trees and Activation Records (Stack Frames)
Each execution of a procedure is called an activation. The call-and-return nesting of activations forms an activation tree, and each active call owns an activation record (stack frame) on the run-time stack:
| Field | Purpose |
|---|---|
| Return Value | Space for the value returned by the callee to the caller (often passed in a register on modern CPUs) |
| Actual Parameters | Arguments passed by the caller to the callee |
| Control Link (Dynamic Link) | Pointer to the activation record of the caller (used to restore the stack frame pointer on return) |
| Access Link (Static Link) | Pointer to the activation record of the lexically enclosing procedure (used in languages with nested functions like Pascal/Python to access non-local variables) |
| Saved Machine Status | Return address (saved program counter) and callee-saved CPU registers |
| Local Data | Local variables whose lifetimes are bound to this activation |
| Temporaries | Intermediate values generated during expression evaluation |
4.8.4 Accessing Non-Local Data (Static Links and Displays)
When nested procedure at lexical nesting depth references a variable declared in an enclosing procedure at depth :
- Static-Link Chaining: Follow access links starting from the current frame pointer to reach 's frame, then add 's fixed compile-time offset.
- Display: A small global array
display[0..k]wheredisplay[d]always holds a pointer to the most recent active frame at nesting depth , allowing access to any non-local variable regardless of nesting depth.
4.8.5 Parameter Passing Mechanisms
| Mechanism | What Is Passed | Effect of Modifying Formal Parameter |
|---|---|---|
| Call-by-Value | Copy of the actual argument's value | Modifications inside the callee do not affect the caller's variable (pointers passed by value still allow modifying the pointee) |
| Call-by-Reference | Address (l-value) of the actual argument | Formal parameter is an alias for the caller's variable; updates immediately modify the caller's variable (can create aliasing hazards) |
| Call-by-Value-Result (Copy-Restore) | Value copied in on call; final formal value copied back to actual's address on return | Caller's variable changes only upon procedure return, avoiding mid-execution aliasing side effects |
| Call-by-Name | Unevaluated expression (thunk) substituted textually at each use | Re-evaluated every time the formal parameter is accessed inside the callee |
Worked Examples
1
Consider the C-like declaration:
struct Record {
int id;
double scores[4];
char flag;
} items[5];Assume sizeof(int) = 4, sizeof(double) = 8, sizeof(char) = 1, each field must be aligned to a multiple of its own primitive element size, and the total struct size is padded to a multiple of its largest alignment requirement ().
- Write the formal type expression for
items. - Compute the byte offset of each field in
struct Record, the padded size of onestruct Record, and the total memory occupied byitems.
Constructing the Type Expression:
scoresis .struct Recordis .itemsis an array of such records:
Computing Field Offsets and Alignment Padding:
id(int, size , align ): offset , occupies bytes .scores(double[4], element size , align ): next multiple of after is ( bytes of padding at bytes ). Occupies bytes ().flag(char, size , align ): offset , occupies byte .- Raw size .
- Tail padding to next multiple of : (bytes ).
- Size of one
struct Record.
Total Memory for items[5]:
- Type expression: .
- Offsets:
id,scores,flag; paddedstruct Recordsize ; total size ofitems[5].
2
A compiler uses a chained hash table with buckets (indexed to ) for its symbol table, with hash function , where a , b , , z . Insert the identifiers count, sum, avg, idx, max, flag, ptr, and val in order (new entries inserted at the head of each bucket chain).
- Show the final contents of each bucket.
- Compute the load factor and the expected number of probes for a successful search under uniform hashing.
Computing Hash Buckets:
count: length ,c.sum: length ,s.avg: length ,a.idx: length ,i.max: length ,m.flag: length ,f.ptr: length ,p.val: length ,v.
Final Chained Hash Table Layout (Head Insertion):
| Bucket Index | Chain (Head to Tail) |
|---|---|
0 | val flag |
1 | max |
2 | idx sum |
3 | count |
4 | ptr avg |
Load Factor and Expected Successful Search Probes:
Under uniform chaining with head insertion, the expected probes for a successful lookup is:
Bucket chains are [val, flag], [max], [idx, sum], [count], and [ptr, avg]. The load factor is , giving an expected successful lookup cost of probes.
3
Consider the following pseudocode where a is initially 5:
procedure update(x, y):
x = x + 3
y = y + 2
end
update(a, a)
print(a)Determine the printed value of a under each of the following parameter-passing mechanisms:
- Call-by-Value
- Call-by-Reference
- Call-by-Value-Result (copy-in left-to-right, copy-out left-to-right on return)
Case 1: Call-by-Value: Both x and y receive private local copies initialized to .
x = 5 + 3 = 8;y = 5 + 2 = 7.- Neither update writes back to the caller's variable
a. - Printed value of
a.
Case 2: Call-by-Reference: Both x and y are aliases pointing to the exact same memory location a!
- Initially
a = 5. x = x + 3modifiesadirectly to .y = y + 2reads the updateda() and modifiesato .- Printed value of
a.
Case 3: Call-by-Value-Result (Copy-Restore):
- Copy-in: local
x = 5, localy = 5. - Execute body:
x = 5 + 3 = 8,y = 5 + 2 = 7. - Copy-out left-to-right: first
a = x = 8, thena = y = 7(overwriting ). - Printed value of
a.
The printed value of a is under Call-by-Value, under Call-by-Reference, and under left-to-right Call-by-Value-Result.
Exercises
Practice Exercises — Semantic Analysis, Symbol Tables, and Run-Time Storage
Classify each of the following semantic checks as static (compile-time) or dynamic (run-time), and justify each classification:
- Assigning a
stringliteral to anintvariable. - Accessing
arr[k]wherekis computed from user input. - Placing a
break;statement outside any loop orswitch. - Dividing
total / countwherecountis a runtime parameter.
Classifying Each Check:
- Assigning
stringtoint— Static Check: Both types are completely known from declarations and literals at compile time. - Array subscript
arr[k]— Dynamic Check: Sincekdepends on runtime input, bounds verification () cannot be resolved statically and requires runtime guard code. - Misplaced
break;— Static Check: Enclosing loop/switch nesting is purely structural in the AST and verified during compile-time flow-of-control analysis. - Division by
count— Dynamic Check: Whethercount == 0depends on the runtime argument value, handled by runtime check or hardware division-by-zero trap.
Checks (1) and (3) are static (decidable from compile-time AST/type declarations), whereas checks (2) and (4) are dynamic (depend on runtime values).
Consider the Pascal-style type and variable declarations:
type T1 = array[1..10] of integer;
type T2 = array[1..10] of integer;
type T3 = T1;
var a, b : T1;
var c : T2;
var d : T3;
var e : array[1..10] of integer;Which pairs among variables a, b, c, d, and e have equivalent types under:
- Structural equivalence
- Strict name equivalence (where every
typealias and anonymous constructor introduces a distinct name) - Loose name equivalence (where
type T3 = T1makesT3an alias ofT1)
Under Structural Equivalence: Every variable expands to . Therefore, all five variables (a, b, c, d, e) are mutually type-equivalent.
Under Strict Name Equivalence: Distinct type names T1, T2, T3, and the anonymous type on e are all separate types. Only a and b share the exact same type name (T1), so only {a, b} are equivalent.
Under Loose Name Equivalence: Since T3 = T1 is treated as an alias for T1 rather than a fresh type constructor, a, b, and d share T1. Variable c (T2) and e (anonymous type) remain distinct. Thus {a, b, d} are equivalent.
- Structural equivalence:
{a, b, c, d, e}are all equivalent. - Strict name equivalence: only
{a, b}are equivalent. - Loose name equivalence:
{a, b, d}are equivalent (candeare distinct).
Given declarations int a[10]; int i = 2; int b = 3; float c = 2.5;, trace the type checking and implicit type coercions performed on the expression a[i] + b * c. If a[2] = 5, verify the resulting expression type and numeric value.
Type Checking Subexpressions Bottom-Up:
ahas type , andihas typeint. By the array-indexing rule,a[i]is valid and has typeint.- In
b * c:bhas typeintandchas typefloat. The type checker inserts a widening coercionint_to_float(b)so both operands arefloat, yieldingfloatforb * c(). - In
a[i] + (b * c):a[i]isintandb * cisfloat. A second widening coercionint_to_float(a[i])promotes5to5.0, yielding final typefloat.
Evaluating the Numeric Result:
Two int_to_float coercions are inserted (for b and a[i]), assigning the expression the final type float and value .
A symbol table holds identifiers. Compare the expected number of comparisons (probes) for a successful lookup using:
- An unordered linear linked list
- A chained hash table with buckets (assuming uniform hashing)
Unordered Linear List: For a successful search uniformly distributed across elements, the target is equally likely to be at positions :
Chained Hash Table (): Load factor:
Expected probes for a successful search under uniform chaining:
An unordered linear list averages comparisons per successful lookup, whereas a -bucket chained hash table averages probes—over faster.
Explain the difference between a Control Link (Dynamic Link) and an Access Link (Static Link) in an activation record. Consider a program where main (depth 0) defines nested procedure P (depth 1, local x = 10), P defines nested procedure Q (depth 2), and P calls R (depth 1) which calls Q. How many access links must Q traverse to read x?
Control Link vs. Access Link:
- Control Link (Dynamic Link): Points to the stack frame of the caller (
Q's control link points toR's frame;R's points toP's). It restores the caller's frame pointer uponreturn. - Access Link (Static Link): Points to the most recent active stack frame of the lexically enclosing procedure (
Qis lexically declared insideP, soQ's access link points directly toP's frame, bypassingR).
Calculating Access Link Traversals: Q is at lexical nesting depth , and variable x is declared in P at lexical nesting depth . The number of access links Q follows is:
Even though the runtime call stack is main -> P -> R -> Q, following Q's single access link jumps straight to P's activation record to read x = 10.
The control link tracks the runtime caller (Q R P), whereas the access link tracks lexical enclosure (Q P). Because , Q traverses access link to reach x in P's frame.