Semantic Analysis & Intermediate Code Generation

Semantic Analysis — Meaning Beyond Syntax

Analogy: You can write a grammatically correct sentence like "The colour seven drinks blue" — syntactically valid (subject, verb, object) but semantically NONSENSE. Semantic analysis catches these errors for programs.

Syntactically valid but semantically wrong:
  int x = "hello";       // type error: cannot assign string to int
  y = x + 1;             // undeclared variable y
  int arr[5]; arr[10] = 1; // array out of bounds (runtime)

---

Symbol Table — The Compiler's Encyclopedia

The symbol table maps: name → attributes

Attributes stored:
  name:     "count"
  type:     int
  scope:    function scope "main"
  address:  stack offset or register
  for function: parameter types, return type

Operations:
  insert(name, attributes)  ← at declaration
  lookup(name)              ← at each use
  delete(scope)             ← when scope exits

Implementation: hash table (O(1) average) or balanced BST

Scoping — Nested Scopes:

int x = 5;           // x in global scope
void foo() {
  float x = 3.14;    // x in foo scope (shadows global x)
  {
    int y = 1;       // y in inner block
    // can use x (float, 3.14) and y here
  }
  // y is gone, x is still float 3.14
}
// x is int 5 again

Implementation: STACK of scopes
  Enter scope  → push new hash table
  Exit scope   → pop hash table
  Lookup       → search from top of stack down

---

Type Checking

Static type checking: done at COMPILE TIME
  int x; x = 3.14;    // compile error: type mismatch
  Pros: catch errors early, no runtime overhead

Dynamic type checking: done at RUNTIME
  Python, JavaScript — types checked when code runs
  Pros: flexible; Cons: errors only at runtime

Coercion (implicit type conversion):
  int x = 3.14;    // C: float 3.14 → int 3 (truncation)
  double d = 5;    // C: int 5 → double 5.0

---

Three-Address Code (TAC) — The Universal IR

Each instruction has at most 3 operands (one result, two sources).

Forms:
  x = y op z    (binary operation)
  x = op y      (unary operation)
  x = y         (copy)
  goto L        (unconditional jump)
  if x relop y goto L   (conditional jump)
  x = y[i]      (array read)
  x[i] = y      (array write)
  param x       (push parameter)
  call f, n     (call function with n params)
  return x      (return value)

Example: Translate a = b + c * d - e

t1 = c * d
t2 = b + t1
t3 = t2 - e
a  = t3

Or more compactly:
t1 = c * d
t2 = b + t1
a  = t2 - e

---

Quadruples vs Triples

Quadruples — explicit temporary names:

(op,    arg1, arg2, result)
(  *,   c,    d,    t1    )
(  +,   b,    t1,   t2    )
(  -,   t2,   e,    a     )

Advantage: easy to reorder instructions during optimisation
           (result name can be changed without updating references)

Triples — no explicit names, use instruction number:

(op,  arg1,  arg2)
0: (*, c,    d   )
1: (+, b,    (0) )  ← arg2 = result of instruction 0
2: (-, (1),  e   )  ← arg1 = result of instruction 1
a = result of instruction 2

Advantage: saves space (no temp names)
Disadvantage: hard to reorder (all references use instruction numbers)

---

DAG — Detect Common Subexpressions

Expression: a + a * (b - c) + (b - c) * d

Build DAG:
     +
    / \
   +   *
  / \ / \
 a   *   d
    / \
   a  sub
       / \
      b   c

(b-c) node is SHARED — computed only once!
(a) also shared.

DAG detects and eliminates common subexpressions at the expression level.

---

Syntax-Directed Translation (SDT)

Attach semantic ACTIONS to grammar productions:

Grammar rule        │ Semantic action
────────────────────┼─────────────────────────────────────
E → E₁ + T          │ E.val = E₁.val + T.val
E → T               │ E.val = T.val
T → T₁ * F          │ T.val = T₁.val * F.val
T → F               │ T.val = F.val
F → ( E )           │ F.val = E.val
F → digit           │ F.val = digit.lexval

Synthesised attribute: computed from children (bottom-up)
Inherited attribute:   computed from parent or left siblings (top-down)

S-attributed: only synthesised attributes → evaluate in single bottom-up pass
L-attributed: inherited from left siblings + synthesised → left-to-right pass

---

Quick Check

Q1. Convert: x = (a + b) * (a + b) - c to TAC. Optimise with common subexpressions.

Naive:
  t1 = a + b
  t2 = a + b    ← same as t1!
  t3 = t1 * t2
  x  = t3 - c

Optimised (CSE):
  t1 = a + b
  t2 = t1 * t1  ← reuse t1 instead of recomputing
  x  = t2 - c

Q2. What is the difference between quadruples and triples? Answer: Quadruples have 4 fields including an explicit result name (temp variable). Triples have 3 fields; result is referenced by instruction index. Quadruples are easier to optimise (reorder without renumbering); triples are more compact.

Q3. What is an L-attributed grammar? Answer: A grammar where attributes can be inherited from parent or from LEFT siblings in a parse tree, plus synthesised attributes. Evaluatable in a single left-to-right pass (during LL parsing or similar). Contrasted with S-attributed (synthesised only, evaluated bottom-up).