Chapter 21 of 33

Semantic Analysis & Type Checking

"Colourless green ideas sleep furiously" is a perfectly grammatical English sentence. Subject, verb, adverb, all in the right places. It is also complete nonsense. Programs can be like that too. Look at this C code:

struct Point { int x, y; };
struct Pair  { int x, y; };

int square(int n) { return n * n; }

int main(void) {
    int count = 10;
    int count = 20;
    struct Point p = {1, 2};
    struct Pair  q;
    total = count + 1;
    q = p;
    count = square(3, 4);
    5 = count;
    count();
    break;
    return 0;
}

Every line fits C's grammar, so the parser is perfectly happy. Yet almost every line in main is wrong. Here is what GCC 15.2 (gcc -std=c17 -fsyntax-only) reports:

sem.c:8:9: error: redefinition of 'count'
sem.c:11:5: error: 'total' undeclared (first use in this function)
sem.c:12:9: error: incompatible types when assigning to type 'struct Pair' from type 'struct Point'
sem.c:13:13: error: too many arguments to function 'square'; expected 1, have 2
sem.c:14:7: error: lvalue required as left operand of assignment
sem.c:15:5: error: called object 'count' is not a function or function pointer
sem.c:16:5: error: break statement not within loop or switch

None of these are syntax errors. They are found by the phase that comes after parsing:

Semantic analysis is the compiler phase that checks a syntactically correct program for consistency with the language's rules of meaning (declarations, scopes, types, and context rules), using the syntax tree and the symbol table. Its most important part is type checking.

In this chapter we will see what semantic analysis checks and why a grammar cannot do it, learn to write types as type expressions, write type-checking rules as syntax-directed translations (from the previous two chapters), handle type conversions, compare structural and name equivalence, and compute storage layouts for declarations.


Why the Parser Cannot Do This

The parser works with a context-free grammar. "Context-free" means that whether a piece of code is valid cannot depend on what appears elsewhere in the program. But many rules of a programming language are exactly about context:

  • "A variable must be declared before it is used": the declaration may be hundreds of lines away.

  • "The number of arguments must match the number of parameters": the function may be defined in another part of the file.

  • "break must be inside a loop or switch": the loop is an enclosing construct, not a neighbour.

In theory some of these could be forced into a much bigger grammar, but the declare-before-use rule in general cannot be expressed by any context-free grammar at all. So compilers keep the grammar simple and push these checks into a separate phase that can look things up in the symbol table and carry information around the tree with attributes.


What Semantic Analysis Checks

Kind of check

Example of a violation

Needs

Declaration before use

total = count + 1; with no declaration of total

Symbol table lookup

No duplicate declarations in one scope

Two int count in the same block

Symbol table lookup in the current scope

Type compatibility of operands

Assigning a struct Point to a struct Pair

Type checking

Function calls

Wrong number or types of arguments; calling a non-function

Function signature from the symbol table

L-values

5 = count;

Knowing which expressions denote a storage location

Flow-of-control rules

break outside a loop, return with the wrong type

Inherited context ("am I inside a loop?")

Uniqueness

Two case 3: labels in one switch, duplicate enum names

A set of labels seen so far

Name-related rules

In some languages, a block's closing name must match its opening name

Comparing attributes

The result of semantic analysis is usually an annotated syntax tree: the same tree, with each expression node labelled with its type and each name linked to its symbol-table entry. Later phases (intermediate code generation especially) rely on these annotations to choose the right instructions, for example integer addition versus floating-point addition.


Static and Dynamic Checking

Static checking is done by the compiler, before the program runs. Dynamic checking is done while the program runs, by code that the compiler or runtime inserts.

Point

Static checking

Dynamic checking

When

Compile time

Run time

Cost at run time

None

Extra checks on every operation

Errors found

On every path, even code that never runs in testing

Only on paths that actually execute

What it can check

Types, declarations, most context rules

Things that depend on values: array index in bounds, null pointer, division by zero, downcasts

Languages

C, C++, Java, Rust, Go (mostly static)

Python, JavaScript (types checked at run time); Java also checks array bounds dynamically

Some checks can only be dynamic. If a has 10 elements, whether a[i] is in bounds depends on the value of i, which is generally unknown at compile time. Java checks this at run time and throws an exception; C does not check at all, which is the root of many security bugs.

Two more terms you will meet:

  • A type system is sound if a program that passes the static type check can never have a type error at run time.

  • A language is strongly typed if the compiler can guarantee that accepted programs run without type errors (some checks may still be dynamic). C is not strongly typed in this sense, because casts and unions let you treat memory as any type. Java is much closer to it.


Type Expressions

To check types we first need a way to write types down precisely. Types in a program have structure (an array of pointers to integers), so we describe them with expressions built from basic types and type constructors.

A type expression is either a basic type (boolean, char, integer, float, void, ...), a type name, or a type constructor applied to type expressions: array(n, T), pointer(T), record(fields), s × t (Cartesian product) and s → t (function from s to t).

Constructor

Meaning

array(n, T)

An array of n elements of type T

pointer(T)

A pointer to an object of type T

record((f1 × T1) × (f2 × T2) ...)

A structure with named fields

s × t

A pair: used for lists of parameters

s → t

A function taking type s and returning type t

C declarations and their type expressions:

Declaration

Type expression of the name

int a[3][4];

array(3, array(4, integer))

char *names[10];

array(10, pointer(char))

int *f(char, int);

(char × integer) → pointer(integer)

int (*fp)(int);

pointer(integer → integer)

struct { int x; double y; } s;

record((x × integer) × (y × double))

Note how int a[3][4] is an array of 3 elements, each of which is an array of 4 integers: the first dimension is the outer constructor. And compare int *f(char, int), a function returning a pointer, with int (*fp)(int), a pointer to a function. The type expressions make that difference obvious, while the C syntax hides it.

Inside the compiler a type expression is stored as a tree (or a DAG, sharing identical subtrees):

Type of f:   (char × integer) → pointer(integer)

                 →
               /   \
              ×     pointer
             / \       |
          char integer integer

Rules for Type Checking

Type checking takes two forms.

  • Type synthesis builds the type of an expression from the types of its parts. The names must be declared first (C, Java). A typical rule:

    if f has type s → t and x has type s, then the expression f(x) has type t.

  • Type inference works out the types of names from how they are used, without declarations (ML, Haskell; also auto in C++ and var in Java in a limited form). A typical rule:

    if f(x) is an expression, then for some types α and β, f has type α → β and x has type α.

Most exam questions and most C-like compilers use type synthesis, so that is what we will implement.

Type Checking as a Syntax-Directed Translation

Give each expression a synthesized attribute type. Then type checking is just an S-attributed SDT. The function lookup(id) returns the symbol-table entry of an identifier, and type_error reports an error.

E → num          { E.type = integer }
E → id           { E.type = lookup(id.lexeme).type }
E → E1 + E2      { if E1.type == integer and E2.type == integer
                       then E.type = integer
                       else E.type = type_error }
E → E1 [ E2 ]    { if E2.type == integer and E1.type == array(n, t)
                       then E.type = t
                       else E.type = type_error }
E → * E1         { if E1.type == pointer(t)
                       then E.type = t
                       else E.type = type_error }
E → E1 ( E2 )    { if E1.type == s → t and E2.type == s
                       then E.type = t
                       else E.type = type_error }

Statements do not have a value, so they get the type void if they are correct:

S → id = E          { if lookup(id.lexeme).type == E.type
                          then S.type = void else S.type = type_error }
S → if ( E ) S1     { if E.type == boolean
                          then S.type = S1.type else S.type = type_error }
S → while ( E ) S1  { if E.type == boolean
                          then S.type = S1.type else S.type = type_error }
S → S1 ; S2         { if S1.type == void and S2.type == void
                          then S.type = void else S.type = type_error }

Worked Example

Declarations: int a[10]; int i; int *p; int (*g)(int);. Check the expression a[i] + *p, and then g(a).

Symbol table:
  a : array(10, integer)
  i : integer
  p : pointer(integer)
  g : pointer(integer → integer)

a[i] + *p
                      + : integer             (integer + integer)
                    /     \
     [ ] : integer          * : integer       (p is pointer(integer))
      /        \            |
  a : array(10,int)   i : integer      p : pointer(integer)

Result: the expression has type integer.

For g(a), the rule for calls wants E1.type to be a function type s → t. But g has type pointer(integer → integer). Under our strict rules that is a type error. (Real C quietly allows calling through a function pointer, and also converts the array a to pointer(integer); even then the argument type pointer(integer) does not match the parameter type integer, so C still rejects g(a): GCC 15 reports "passing argument 1 of 'g' makes integer from pointer without a cast" as an error.) The point: the checker follows the rules exactly, and every implicit convenience a language offers has to be written as an explicit rule.


Type Conversions

What is the type of i + f when i is an int and f is a float? The machine has separate instructions for integer and floating-point addition, so the compiler must first convert i to float. Conversions come in two kinds:

Kind

Who writes it

Example

Implicit conversion (coercion)

Inserted automatically by the compiler

i + 2.5: i becomes double

Explicit conversion (cast)

Written by the programmer

(int) 3.9 gives 3

Languages usually allow implicit widening conversions, which do not lose information (or lose very little), and require explicit casts for narrowing ones. The widening hierarchy used in Java-like languages:

   double
     ↑
   float
     ↑
   long
     ↑
    int  ←── char
     ↑
   short
     ↑
   byte            (an arrow means "can be widened to")

The type checker uses two helper functions:

  • max(t1, t2): the higher of the two types in the hierarchy.

  • widen(a, t, w): generates code to convert address a from type t to type w (if t ≠ w), and returns the address of the converted value.

E → E1 + E2   { E.type = max(E1.type, E2.type);
                a1 = widen(E1.addr, E1.type, E.type);
                a2 = widen(E2.addr, E2.type, E.type);
                E.addr = new Temp();
                gen(E.addr '=' a1 '+' a2); }

For x = i * 2 + f with i an int, and f and x floats, this produces:

t1 = i * 2              integer multiply (both int)
t2 = (float) t1         widen int to float
t3 = t2 + f             float addition
x  = t3

The conversion happens where the types first differ, not at the start. That is why, in C, the position of a conversion changes the answer. A real run with GCC:

int i = 7;
float a = i / 2;      /* int / int, then converted */
float b = i / 2.0;    /* i is converted to double first */
char c = 'A';
int d = c + 1;        /* char promoted to int */
a = 3.0
b = 3.5
d = 66
sizeof(c + 1) = 4, sizeof(i * 2.0f) = 4

i / 2 is computed entirely in integers (giving 3), and only the result is widened to 3.0. In i / 2.0, the literal is a double, so i is widened first and the division is done in floating point. The sizeof line shows that c + 1 has type int (4 bytes: char was promoted) and i * 2.0f has type float.


Type Equivalence

Type checking constantly asks "are these two types the same?". There are two standard answers.

Structural equivalence: two types are equivalent if they are the same basic type, or are formed by applying the same constructor to structurally equivalent types. Name equivalence: two types are equivalent only if they have the same type name (each type name, and each separately written type expression, is a distinct type).

Consider these Pascal-style declarations:

type nodeptr = ↑node;
var  head : nodeptr;
     tail : nodeptr;
     cur  : ↑node;
     a, b : ↑node;

Pair

Structural equivalence

Name equivalence

head, tail

Same (both pointer(node))

Same (both named nodeptr)

a, b

Same

Same (declared together, one implicit name)

cur, a

Same

Different (two separately written ↑node expressions)

head, cur

Same

Different (nodeptr vs an unnamed type)

Structural equivalence is more permissive; name equivalence is stricter and safer, because two types that just happen to look alike (say, metres and seconds, both record(value × float)) are kept apart.

C mixes the two. A typedef only creates an alias, so typedef int Length; makes Length and int the same type. But each struct declaration creates a new, distinct type, even when the fields are identical. That is exactly the GCC error we saw at the top of the chapter: struct Point and struct Pair both have fields int x, y, yet assigning one to the other is "incompatible types". Structures in C use name equivalence; most other types use structural equivalence.

Checking structural equivalence is a simple recursive comparison of two type trees. Recursive types (a node containing a pointer to node) would make that recursion run forever, which is one reason C breaks the cycle at struct names.


Declarations: Types, Widths and Offsets

While processing declarations, the semantic phase also decides how much storage each name needs and where it goes. Each type has a width (its size in bytes), and each local name gets an offset from the start of the data area. Assume integers take 4 bytes and doubles 8, and ignore alignment for now. An SDT that computes both:

P → { offset = 0 } D
D → T id ;    { top.put(id.lexeme, T.type, offset);
                offset = offset + T.width; }
    D1
D → ε
T → B         { t = B.type; w = B.width; }
    C         { T.type = C.type; T.width = C.width; }
B → int       { B.type = integer; B.width = 4; }
B → double    { B.type = double;  B.width = 8; }
C → ε         { C.type = t; C.width = w; }
C → [ num ] C1 { C.type = array(num.value, C1.type);
                 C.width = num.value × C1.width; }

The global variables t and w carry the base type into C (they play the role of inherited attributes), and C builds the array type from the inside out. For int c[2][3]:

C → [2] C1,  C1 → [3] C2,  C2 → ε

C2 : type = integer                       width = 4
C1 : type = array(3, integer)             width = 3 × 4  = 12
C  : type = array(2, array(3, integer))   width = 2 × 12 = 24

Now the whole declaration list int a; double b; int c[2][3]; char d; (with char = 1 byte):

Name

Type

Width

Offset (no alignment)

Offset in a real C struct (GCC, x86-64)

a

integer

4

0

0

b

double

8

4

8

c

array(2, array(3, integer))

24

12

16

d

char

1

36

40

Total

37

48 (sizeof)

The last column was measured with offsetof on struct S { int a; double b; int c[2][3]; char d; }. Real machines want a double to start at an address divisible by 8, so the compiler inserts 4 bytes of padding after a, and pads the end so that an array of these structs keeps every b aligned. Exam questions almost always say "ignore alignment", which gives the simple running sum. These offsets are stored in the symbol table (next chapter) and used when generating addresses (Intermediate Code & Three-Address Code).


Overloading and Polymorphism

  • Overloading: one name, several meanings, chosen by the types involved. + means integer addition or float addition; in C++ and Java, several functions can share a name if their parameter types differ. The type checker resolves each use by looking at the argument types, and reports an error if no version (or more than one equally good version) fits.

  • Parametric polymorphism: one piece of code works for many types. A function computing the length of a list does not care what the elements are, so its type is list(α) → integer for any type α. C++ templates, Java generics and ML functions are examples.

  • Type inference with unification: in ML-like languages the compiler gives unknown types variables (α, β, ...) and solves the equations that come from how the names are used. Unification is the step that makes two type expressions equal by choosing values for their variables, for example making pointer(α) and pointer(integer) equal by setting α = integer.


Common Mistakes

  • Calling a type error a syntax error. q = p; with incompatible structs parses perfectly; it is a semantic error.

  • Reading array type expressions inside out. int a[3][4] is array(3, array(4, integer)), not array(4, array(3, integer)).

  • Converting too early or too late. In i / 2 + f, the division is still integer division; only its result is widened.

  • Assuming C uses structural equivalence for structs. Two struct types with identical fields are still different types.

  • Forgetting alignment when asked about real sizes, or adding it when the question says to ignore it.

  • Thinking static checking can catch everything. Array bounds and null pointers generally need run-time checks.


Interview and Exam Questions

Q1. Which phase detects "variable used before declaration", and why not the parser?

Semantic analysis. Whether a name is declared depends on context elsewhere in the program, which a context-free grammar cannot express; the semantic analyzer checks it with the symbol table.

Q2. What is the difference between static and dynamic type checking?

Static checking happens at compile time and costs nothing at run time, but cannot check value-dependent properties. Dynamic checking happens while the program runs, catching errors such as out-of-bounds indexes, at the cost of extra run-time work.

Q3. Write the type expression for int *x[5] and for int (*y)[5].

x: array(5, pointer(integer)), an array of 5 pointers. y: pointer(array(5, integer)), a pointer to an array of 5 integers.

Q4. What is the difference between coercion and casting?

Both convert values between types. A coercion is implicit and inserted by the compiler (usually only for widening); a cast is explicit, written by the programmer, and may narrow.

Q5. Under name equivalence, are two variables declared as var x : ↑cell; var y : ↑cell; of the same type?

No. Each separately written type expression gets its own implicit name, so x and y have different types. Under structural equivalence they are the same.

Q6. Ignoring alignment, with int = 4 and float = 8 bytes, what are the offsets in float x; int y[5]; float z;?

x at 0 (width 8), y at 8 (width 5 × 4 = 20), z at 28 (width 8). Total 36 bytes.

Q7. What does a type checker produce besides error messages?

An annotated syntax tree (types on expression nodes, symbol-table links on names) and inserted conversion operations, which the intermediate code generator uses to pick the right operations.


Summary

  • Semantic analysis checks rules that a context-free grammar cannot: declarations, scopes, types, argument counts, l-values and flow-of-control context.

  • Static checks run at compile time; dynamic checks run at run time for value-dependent properties.

  • Type expressions are built from basic types with array, pointer, record, × and →.

  • Type checking is an S-attributed SDT with a synthesized type attribute; synthesis needs declarations, inference works them out from use.

  • Widening conversions are inserted implicitly at the point where operand types differ; narrowing needs a cast.

  • Structural equivalence compares shapes; name equivalence compares names. C uses name equivalence for structs.

  • Declarations also produce widths and offsets for storage layout; real compilers add alignment padding.

All of this depends on one data structure that every phase keeps asking questions: "what is this name, and what do we know about it?" That is the Symbol Table, the subject of the next chapter.