PadhaikoAll subjects

Syntax-Directed Translation and Semantic Analysis (part 2: 4.5–4.8)

Compiler Design (ENCT 326)

Open in the Padhaiko app

4.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

  1. 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.
  2. 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.
  3. Uniqueness Checks: Detects duplicate variable names in the same scope, duplicate case labels in a switch statement, or repeated parameter names.
  4. Flow-of-Control Checks: Ensures break and continue appear inside an enclosing loop or switch, and that non-void functions return a compatible value.
  5. 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).

AspectStatic Checks (Compile-Time)Dynamic Checks (Run-Time)
When PerformedDuring compilation (before execution)During program execution (via compiler-emitted guard code or runtime hardware traps)
Information UsedDeclarations, symbol table types, control-flow structure, constant expressionsActual run-time values of variables, array indices, pointers, and dynamic object tags
Runtime OverheadZero runtime execution overhead; catches bugs earlyAdds runtime instructions and memory overhead (bounds checks, tag fields)
Typical ExamplesType mismatch (int + string), undeclared variable, wrong argument count, duplicate case value, break outside loopArray 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.

Definition

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:

  1. Basic (Primitive) Types: Atomic types such as boolean, char, integer, float, void, and a special sentinel type_error used to signal an error without cascading false diagnostics.
  2. Type Names: User-defined names introduced via typedef, struct, or class.
  3. 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:

AspectStructural EquivalenceName Equivalence
CriterionTwo 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 componentsTwo types are equivalent only if they have the exact same type name (declaration identity)
Behavior on Distinct Typedefstypedef int Age; typedef int Score; — Age and Score are equivalent because both expand to intUnder strict name equivalence, Age and Score are distinct types
Recursive TypesRequires cycle detection (e.g., linked-list node pointers referencing themselves)Checked in by comparing symbol-table pointers
Language ExamplesAlgol 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

4.6.4 Simple Type Checking Rules (SDT)

Type Checking Rules for Common Constructs
Construct / ProductionType 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

Definition

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:

  1. Lexeme / Identifier Name: Character string (or pointer into a string pool) naming the symbol.
  2. Kind / Category: Variable, constant, formal parameter, function, array, struct/class, or label.
  3. Type Expression: Primitive type or composite type descriptor (e.g., array(0..9, float)).
  4. Scope / Nesting Level: Lexical block depth or enclosing function identifier.
  5. Storage Allocation Information: Relative memory offset (within static area or stack frame), size in bytes, alignment, and storage class (auto, static, extern, register).
  6. 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:

  1. 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 follows parent pointers outward until name is found or the global scope ends. When the parser exits a block, the current scope pointer moves back to parent.
  2. 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

Comparison of Symbol Table Data Structures
Data StructureAverage LookupInsertionSpace OverheadBest Use Case
Unordered Linear ListMinimalVery small local scopes (e.g., locals)
Ordered Linear Array (binary search) (shifting elements)LowStatic keyword tables known at compiler start
Binary Search Tree (BST) balanced, skewed balancedModerate (2 pointers/node)Sorted symbol dumps, moderate tables
Hash Table (with Chaining) expected () expectedBucket array + chain pointersProduction compilers with large programs (fast insert and lookup)

For a chained hash table with symbols and buckets, the load factor is . Under uniform hashing:


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

Standard Run-Time Memory LayoutText
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 Addresses

4.8.2 Storage Allocation Strategies

Comparison of Storage Allocation Strategies
StrategyBinding TimeRecursion SupportKey Characteristics & Trade-offs
Static AllocationCompile timeNoEvery data object has a fixed address throughout execution; no stack/heap overhead; cannot support recursion or dynamic data sizes
Stack AllocationProcedure call / return timeYesMemory managed as a LIFO control stack of activation records; local variables die when the procedure returns; very fast ( pointer bump)
Heap AllocationArbitrary run-time (malloc / new and free / GC)YesObjects 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:

Fields of a Typical Activation Record
FieldPurpose
Return ValueSpace for the value returned by the callee to the caller (often passed in a register on modern CPUs)
Actual ParametersArguments 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 StatusReturn address (saved program counter) and callee-saved CPU registers
Local DataLocal variables whose lifetimes are bound to this activation
TemporariesIntermediate 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 :

4.8.5 Parameter Passing Mechanisms

Parameter Passing Mechanisms
MechanismWhat Is PassedEffect of Modifying Formal Parameter
Call-by-ValueCopy of the actual argument's valueModifications inside the callee do not affect the caller's variable (pointers passed by value still allow modifying the pointee)
Call-by-ReferenceAddress (l-value) of the actual argumentFormal 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 returnCaller's variable changes only upon procedure return, avoiding mid-execution aliasing side effects
Call-by-NameUnevaluated expression (thunk) substituted textually at each useRe-evaluated every time the formal parameter is accessed inside the callee

Worked Examples

Example 1

1

Consider the C-like declaration:

Struct DeclarationC
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 ().

  1. Write the formal type expression for items.
  2. Compute the byte offset of each field in struct Record, the padded size of one struct Record, and the total memory occupied by items.

Constructing the Type Expression:

  • scores is .
  • struct Record is .
  • items is 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]:

Answer:
  • Type expression: .
  • Offsets: id , scores , flag ; padded struct Record size ; total size of items[5] .
Example 2

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).

  1. Show the final contents of each bucket.
  2. 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):

Symbol Table Buckets
Bucket IndexChain (Head to Tail)
0val flag
1max
2idx sum
3count
4ptr avg

Load Factor and Expected Successful Search Probes:

Under uniform chaining with head insertion, the expected probes for a successful lookup is:

Answer:

Bucket chains are [val, flag], [max], [idx, sum], [count], and [ptr, avg]. The load factor is , giving an expected successful lookup cost of probes.

Example 3

3

Consider the following pseudocode where a is initially 5:

Parameter Passing SnippetText
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:

  1. Call-by-Value
  2. Call-by-Reference
  3. 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 + 3 modifies a directly to .
  • y = y + 2 reads the updated a () and modifies a to .
  • Printed value of a .

Case 3: Call-by-Value-Result (Copy-Restore):

  • Copy-in: local x = 5, local y = 5.
  • Execute body: x = 5 + 3 = 8, y = 5 + 2 = 7.
  • Copy-out left-to-right: first a = x = 8, then a = y = 7 (overwriting ).
  • Printed value of a .
Answer:

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

Question 1

Classify each of the following semantic checks as static (compile-time) or dynamic (run-time), and justify each classification:

  1. Assigning a string literal to an int variable.
  2. Accessing arr[k] where k is computed from user input.
  3. Placing a break; statement outside any loop or switch.
  4. Dividing total / count where count is a runtime parameter.

Classifying Each Check:

  1. Assigning string to int — Static Check: Both types are completely known from declarations and literals at compile time.
  2. Array subscript arr[k] — Dynamic Check: Since k depends on runtime input, bounds verification () cannot be resolved statically and requires runtime guard code.
  3. Misplaced break; — Static Check: Enclosing loop/switch nesting is purely structural in the AST and verified during compile-time flow-of-control analysis.
  4. Division by count — Dynamic Check: Whether count == 0 depends on the runtime argument value, handled by runtime check or hardware division-by-zero trap.
Answer:

Checks (1) and (3) are static (decidable from compile-time AST/type declarations), whereas checks (2) and (4) are dynamic (depend on runtime values).

Question 2

Consider the Pascal-style type and variable declarations:

Pascal Type DeclarationsText
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:

  1. Structural equivalence
  2. Strict name equivalence (where every type alias and anonymous constructor introduces a distinct name)
  3. Loose name equivalence (where type T3 = T1 makes T3 an alias of T1)

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.

Answer:
  • 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 (c and e are distinct).
Question 3

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:

  1. a has type , and i has type int. By the array-indexing rule, a[i] is valid and has type int.
  2. In b * c: b has type int and c has type float. The type checker inserts a widening coercion int_to_float(b) so both operands are float, yielding float for b * c ().
  3. In a[i] + (b * c): a[i] is int and b * c is float. A second widening coercion int_to_float(a[i]) promotes 5 to 5.0, yielding final type float.

Evaluating the Numeric Result:

Answer:

Two int_to_float coercions are inserted (for b and a[i]), assigning the expression the final type float and value .

Question 4

A symbol table holds identifiers. Compare the expected number of comparisons (probes) for a successful lookup using:

  1. An unordered linear linked list
  2. 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:

Answer:

An unordered linear list averages comparisons per successful lookup, whereas a -bucket chained hash table averages probes—over faster.

Question 5

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 to R's frame; R's points to P's). It restores the caller's frame pointer upon return.
  • Access Link (Static Link): Points to the most recent active stack frame of the lexically enclosing procedure (Q is lexically declared inside P, so Q's access link points directly to P's frame, bypassing R).

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.

Answer:

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.

← Syntax-Directed Translation and Semantic Analysis (part 1: 4.1–4.4)Code Generation →