"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 switchNone 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.
"
breakmust 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 |
| Symbol table lookup |
No duplicate declarations in one scope | Two | Symbol table lookup in the current scope |
Type compatibility of operands | Assigning a | Type checking |
Function calls | Wrong number or types of arguments; calling a non-function | Function signature from the symbol table |
L-values |
| Knowing which expressions denote a storage location |
Flow-of-control rules |
| Inherited context ("am I inside a loop?") |
Uniqueness | Two | 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 |
|---|---|
| array(3, array(4, integer)) |
| array(10, pointer(char)) |
| (char × integer) → pointer(integer) |
| pointer(integer → integer) |
| 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 integerRules 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
autoin C++ andvarin 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 |
|
Explicit conversion (cast) | Written by the programmer |
|
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 addressafrom 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 = t3The 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) = 4i / 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 = 24Now 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(α) → integerfor 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(α)andpointer(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
typeattribute; 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.