CPSC 323: Semantic Anaylsis and Intermediate Code Generation

Semantic Analysis

• Bridges syntax and logic

  • The phase of compilation that checks the source program for semantic consistency with the language definition.

  • Syntax analysis only ensures the code "looks" right.

  • Semantic analysis ensures the code "makes sense”.

Semantic Analysis Input

Abstract Syntax Tree (AST) generated by the Parser.

Semantic Analysis output

Annotated/Decorated AST or Intermediate Representation (IR). Shows type and variable reference

Type checking

Verifying that operators and functions are applied to compatible operands (e.g. ensuring a boolean isn't used in a multiplication).

Label/Flow Checking

Ensuring control flow statements are valid (e.g., a break statement must be inside a loop, if/else statements ).

Uniqueness Checks

Ensuring identifiers are declared only once within a specific scope.

Symbol Table Management

Maintains a record of every identifier, its type, its scope, and its memory location

Symbol Table

• Compiler memory bank

• Data structure storing nformation about the occurrence of entities such as variable names, function names, objects, and classes.

• Has Insert() and Lookup() operations

Information stored in a symbol table

• Name (Identifier)

• Type (int, float, char, etc.)

• Scope (Global, Local, Block-level)

• Memory Address/Offset

Static checking

Performed during compile-time (C++, Java, Rust). It catches errors before the program runs.

Dynamic Checking

Performed during execution (Python, JavaScript). Errors are only caught when the specific line of code is hit.

Dynamic Checking

Performed during execution (Python, JavaScript). Errors are only caught when the specific line of code is hit.

Implicit(Coercion) type conversion

Done automatically by the compiler (e.g., float x = 5;)

Explicit (Casting) Type Casting

Controlled by the programmer (e.g., int y = (int)3.14;).

Static Scope(Lexical)

This variable attribute is determined by its position in the source code. Most modern languages use this.

Dynamic Scope

Determined by the calling sequence of functions at runtime

Scope Rules

• Inner scopes can access outer scope variables (Shadowing).

• Outer scopes cannot see "inside" nested functions or blocks.

• The Semantic Analyzer must verify that every variable used has been declared in a reachable scope.

Causes of compile errors

• Type Mismatch: string result = 10 * "hello";

• Undeclared Variables: Using x before defining it.

• Multiple Declarations: Defining int count; twice in the same block.

• Function Argument Mismatch: Passing 3 arguments to a function that only accepts 2.

• Illegal Flow: Using return outside of a function body.

Intermediate Code/Intermediate Representation(IR)

• Intermediate stage between high-level code → assembly

• Makes the compiler easier to design, optimize, and port to multiple architectures.

• Bridges between front and back ends

• Makes compilers modular, portable, and optimizable

What does Intermediate Code Generation do?

• Converts the annotated syntax tree into a machine-independent representation

• Breaks complex expressions into simpler steps

• Prepares the program for optimization

• Makes translation to target machine code easier

Types of intermediate representations

• Postfix notation

• Three Address Code (TAC)

• Syntax Tree / Abstract Syntax Tree based IR

• Directed Acyclic Graph (DAG)

Directed Acyclic Graph(DAG)

Linear Form Intermediate Codes

• Postfix expressions

  • Three Address Code(TAC)

Postfix Expressions

• Also called reverse polish notation(RPN)

• Operators follow their operands

• EX: (a + b) × (a + b + c)

  • Output: a b + a b c + + x

• REVIEW THIS

Three Address Code(TAC)

• Complex expressions are split into <=3 operand instructions

• 2 for operation, 1 for result

• Useful for machine code generation and optimization

x = y op z

• TAC Form

• x = y op z For binary operations followed by assignment.

x = op z

• TAC Form

• For unary operations followed by assignment

Type 1: Quadruple Form

• Represents TAC as a 4 tuple

  • (operator, arg1, arg2, result)

  • Each operation explicitly shows the operator, operands, and the result variable

Usage of Quadruple form

Intermediate code generation and optimization stages

Advantages of Quadruple Form

• Clear and easy to interpret

• Easy to optimize, modify, reorder

Quadruple form example

a = b + c * d

Type 2: Triple Form

• TAC is represented as a 3-Tuple

  • (operator, arg1, arg2)

  • Results are referred to by instruction indices (handles variables) instead of variable names which makes it more space-efficient

−(a+b) x (c+d) +(a+b+c)

• Only pointers change, not triples

  • Pointers have the address of the next node

Slide 25

Abstract Syntax Tree

• Represents hierarchy of syntactic structure after parsing source code

Structure of an AST

• Internal nodes: Operators/statements

• Leaf nodes: Operands/identifiers