Yasir Explains/Compiler Design/Syntax-Directed Translation/Type Checking of Expressions, Statements and Functions
Syntax-Directed Translation

Type Checking of Expressions, Statements and Functions

On this page

How the Rules WorkType Checking ExpressionsType Checking StatementsType Checking FunctionsFull Worked ExampleThe Annotated ASTSummary
Syntax-Directed Translation

Type Checking of Expressions, Statements and Functions

The practical SDD rules a compiler uses to check types in expressions, statements, and functions — each rule stated plainly and shown with a worked example.

How the Rules Work

Type checking is written as a syntax-directed definition (SDD): each grammar production gets a rule that computes a .type attribute, bottom-up from the leaves to the root.

Definitions you need:

  • E.type — the type of an expression node, computed from its children.
  • lookup(id) — ask the symbol table for the declared type of id.
  • type_error — a sentinel meaning "type rule violated". If any child is type_error, the parent becomes type_error too.
  • s → t — a function type: takes an argument of type s, returns type t.
  • void — the type of a correct statement (statements do work; they have no value).

A program is well-typed if no node ends up as type_error.

Coercion: widening (integer → float) is usually allowed automatically. Narrowing (float → integer) needs an explicit cast.

Type Checking Expressions

An expression has a value, so it has a type. Compute it bottom-up.

Leaves: literals and identifiers

Example
E → integer-literal E.type = integer
E → real-literal E.type = float
E → true | false E.type = boolean
E → char-literal E.type = char
E → id E.type = lookup(id) ← symbol table

Literals carry their own type. An identifier's type comes from the symbol table; an undeclared name gives type_error.

Arithmetic: + − * /

Example
E → E₁ + E₂ both integer → integer
both numeric → float (widen)
otherwise → type_error

Plain version: int + int is int; mixing int and float gives float; anything non-numeric (like int + bool) is an error.

Relational: < > <= >= == !=

Example
E → E₁ < E₂ both numeric → boolean
otherwise → type_error

A comparison always returns boolean, whatever the operand precision.

Logical: && || !

Example
E → E₁ && E₂ both boolean → boolean, else type_error
E → ! E₁ E₁ boolean → boolean, else type_error

Logical operators demand boolean and produce boolean.

Array access and pointer dereference

Example
E → E₁ [ E₂ ] E₁ : array(s,t) and E₂ : integer → t
E → * E₁ E₁ : pointer(t) → t

Indexing an array of element type t gives t (index must be an integer). Dereferencing pointer(t) gives t.

Worked example: a[i] < 3

Symbol table: a : array(10, float), i : integer.

Example
a → array(10, float)
i → integer
a[i] → array index ok, result = element type = float
3 → integer
a[i]<3 → both numeric (float, integer) = boolean ✓

Type Checking Statements

A statement has no value. If it is correct its type is void; if any rule fails its type is type_error.

Assignment — left and right must match

Example
S → id = E lookup(id) = E.type → void, else type_error

If widening is allowed, integer on the right may be stored in a float variable.

Conditions must be boolean

Example
S → if ( E ) S₁ E:boolean, S₁:void → void
S → if ( E ) S₁ else S₂ E:boolean, both branches void → void
S → while ( E ) S₁ E:boolean, S₁:void → void

Every if/while rule says the same thing: the guard E must be boolean, and the body must be well-typed.

Sequences and declarations

Example
S → S₁ ; S₂ both void → void, else type_error
S → T id insert id:T in symbol table; void
S → T id = E T = E.type → insert id:T; void, else type_error

A block S₁; S₂; S₃ is just this rule applied repeatedly — every statement must be void.

Worked example

Symbol table: x : integer, flag : boolean.

Example
while (flag) x = x + 1;
flag → boolean (guard ok)
x + 1 → integer + integer = integer
x = x+1 → lookup(x)=integer = E.type ✓ → void
while(...) → guard boolean, body void → void ✓

Now break it — make the guard x instead of flag:

Example
while (x) ... → x is integer, not boolean → type_error

Type Checking Functions

A function's type is s → t: argument type s, return type t. With several parameters, s is a tuple.

Example
int square(int x) → integer → integer
bool isEven(int n) → integer → boolean
int add(int a, int b) → integer × integer → integer

Definition — record the type, check the return

Example
FuncDef → T id (Params) { Body }
s = tuple of parameter types
t = T (declared return type)
insert id : s → t in symbol table
check Body with expected return type = t
every "return E" must satisfy E.type = t

Call — arguments must match the domain

Example
E → id ( A ) lookup(id) = s → t and A.type = s → t, else type_error

In plain words: id must name a function; the argument list A must match the domain s exactly (count and types); the call's type is the return type t.

Argument lists build a tuple left to right:

Example
A → ε void (no arguments)
A → E E.type
A → A₁ , E A₁.type × E.type

Worked example

g : integer × float → boolean. Check g(1, 2.5):

Example
A = (1, 2.5) → integer × float
domain of g → integer × float match ✓
result → boolean

Common call errors

Example
g : integer × float → boolean int x; bool b;
g(1) type_error too few args (domain is int × float)
g(1, 2, 3) type_error too many args
g(1, b) type_error boolean ≠ float
x(3) type_error x is integer, not a function
float f(){return 3>2;} type_error returns boolean, declared float

Full Worked Example

Symbol table (already built):

Example
x : integer
y : float
f : float → integer (takes a float, returns an integer)

Statement to check: x = f(y) + 3;

The AST

S: assign
id: x
E: +
E: call f(y)
id: f
arg: y
E: 3

Compute types bottom-up

Example
Node Rule Type
------------ -------------------------------------- ---------
y lookup(y) float
f lookup(f) float→integer
f(y) arg float = domain float ✓, result integer
3 integer-literal integer
f(y) + 3 integer + integer integer
x lookup(x) integer
x = f(y)+3 lookup(x)=integer = E.type ✓ void ✓

No node is type_error, so the statement is well-typed.

Two ways it could fail

Example
If x were declared boolean:
x = f(y)+3 → boolean ≠ integer → type_error (bad assignment)
If we wrote f(true) instead of f(y):
call f → boolean ≠ float domain → type_error (bad argument)

The Annotated AST

After checking, every node carries its .type. This annotated AST is what the next phase (IR generation) consumes.

Example
S [void]
└── =
├── id: x [integer]
└── + [integer]
├── call f(y) [integer] ← return type of f
│ ├── id: f [float→integer]
│ └── arg: y [float]
└── 3 [integer]

Synthesised vs inherited

AttributeDirectionMeaning
E.typeup (synthesised)type built from children
return typedown (inherited)passed into the body so return can check itself

Almost everything is synthesised (computed from children). The one common inherited attribute is the expected return type flowing down into a function body.

Error recovery

On an error, the compiler records it and sets that node to type_error, then keeps going — so a single pass can report all type errors, not just the first.

Summary

Expressions

NodeRuleResult
literalinherentint / float / bool / char
idlookup(id)declared type
E₁ op E₂ (arith)both numericint if both int, else float
E₁ < E₂both numericboolean
E₁ && E₂both booleanboolean
E₁[E₂]array(s,t), index intt
id(A)id:s→t, A=st

Statements (all produce void or type_error)

StatementRule
id = Elookup(id) = E.type
if/while (E) …E must be boolean, body void
S₁ ; S₂both void

The three things to remember

  1. Literals carry their type; identifiers get theirs from the symbol table.
  2. Expressions compute type bottom-up; statements are void or type_error.
  3. A call is well-typed only when the argument types exactly match the function's domain.