Two Symbol Tables, One Compiler

1The question

Your textbook describes the symbol table: one structure, threaded through the phases, accumulating what the compiler learns about each name. Dragon §2.7.

Now grep this compiler. There are two, in two files, and they never exchange a single byte of data:

semantic.c   static Scope       scopes[MAX_SCOPE_DEPTH];  a stack of name lists
symtab.c     static SymbolTable locals, globals;         names with addresses

The natural conclusion is that one of them is redundant. It is not. They answer different questions, they are alive at different times, and — the part worth the rest of this page — neither one could do the other's job, even if you wanted it to.

2The two tables at a glance

3Where each one lives

The ordering is fixed in main.c: yyparse() at line 124, then semantic analysis, then generateTAC() at 167, optimizeTAC() at 176, and generateMIPSFromTAC() at 183.

Read that ordering again with the storage map in mind. Every entry in it is a byte offset. At the moment semantic analysis runs there is nothing to take an offset into: no TAC, no list of temporaries, no frame, no idea how big the frame will be. The storage map is not merely unpopulated during phase 3. It is unpopulatable.

4Table 1 — the scope stack in semantic.c

What one entry holds

typedef struct {
    char* names[MAX_VARS];   the entire entry: a string
    int   count;
} Scope;

static Scope scopes[MAX_SCOPE_DEPTH];
static int   scopeDepth = 0;

That really is the whole entry. No type, no size, no address — because none of those are needed to answer the only question this table is ever asked.

How it is searched

static int isVarDeclaredInScope(char* name) {
    for (int depth = scopeDepth - 1; depth >= 0; depth--)   innermost first
        for (int i = 0; i < scopes[depth].count; i++)
            if (strcmp(scopes[depth].names[i], name) == 0)
                return 1;
    return 0;
}

Innermost outward — the most-closely-nested rule from Dragon §2.7, written out in six lines. Compare it with addVarToScope(), which checks for duplicates in the current scope only, because shadowing an outer name is legal and redeclaring in the same block is not.

What it looks like running

Compile any test program without -q and phase 3 narrates itself. Each line is one query against the scope stack:

  ✓ Variable 'x' declared (line 3)
  ✓ Variable 'y' declared (line 4)
  ✓ Variable 'total' declared (line 5)
  ✓ Assignment to 'x' is valid (line 7)
  ✓ Assignment to 'y' is valid (line 8)
  ✓ Assignment to 'total' is valid (line 9)

Nothing is being allocated there. Names are only being accepted or rejected.

When it says no

$ ./minicompiler tests/t2_04_errors_undeclared.cm out.s

║ SEMANTIC ERROR - Undeclared Variable                      ║
  📍 Location: Line 8
  ❌ Error: Variable 'ghost' is used before being declared
  💡 Suggestion: Add a declaration before using this variable:
     → int ghost;  (add this before line 8)

5Table 2 — the storage map in symtab.c

What one entry holds

typedef struct {
    char* name;
    char* type;
    int   offset;       locals: byte offset from $sp
    int   isArray;
    int   arraySize;
    int   isGlobal;     1 = lives in .data instead
    int   isParamArray; slot holds a base address, not the data
} Symbol;

Two tables inside one file, because MIPS has two storage classes

GLOBALS  →  .data, addressed by label     la   $t0, counter
LOCALS   →  the current frame, by offset  lw   $t0, 8($sp)

locals is cleared at the start of every function by initSymTab(), because each function gets a fresh activation record. globals is built once by initGlobalScope() and persists for the whole program.

Where its functions are called

All of them, from one file. This is the complete list:

Nothing outside codegen.c calls into symtab.c — not the parser, not tac.c, and not semantic.c. That holds in all six topics. semantic.c does #include "symtab.h", but only to borrow the MAX_VARS constant.

What it looks like running

  ┌─ SYMBOL TABLE ─────────────────────────────────────────┐
  │ GLOBALS (.data)                                            │
    (none)
  │ LOCALS (current activation record,  12 bytes)              │
    x              int        0($sp)
    y              int        4($sp)
    total          int        8($sp)
  └──────────────────────────────────────────────────────┘

6Why the shapes differ

Scoping requires deletion. exitScope() frees the names and decrements the depth, because leaving a block has to make those names stop resolving. That is what scoping means. A table that never forgot anything could not implement it.

Storage requires permanence. A register spill near the bottom of a function has to find the home a declaration was given at the top. If the storage map popped entries the way a scope stack does, emitStoreHome() would fail on any name whose block had already ended.

And by phase 6 there is no nesting left to represent. TAC is a flat list; blocks have dissolved into labels and jumps. So the visibility question is meaningless in phase 6, and the storage question is unanswerable in phase 3. Each table has the only structure that fits its own question.

7One program through both tables

tests/t2_01_basics.cm — the whole starter language in four statements:

int x;
int y;
int total;

x = 5;
y = 10;
total = x + y + 3;

print(x);
print(y);
print(total);

Follow one name, total, and watch what each phase knows about it:

The two TAC listings, side by side, are the whole argument of this handout:

 unoptimized — 14 instructions          optimized — 12 instructions 
  FUNC_BEGIN main                        FUNC_BEGIN main
      DECL int x                             DECL int x
      DECL int y                             DECL int y
      DECL int total                         DECL int total
      x = 5                                  x = 5
      y = 10                                 y = 10
      t0 = x + y                             total = 18
      t1 = t0 + 3                            PRINT 5
      total = t1                             PRINT 10
      PRINT x                                PRINT 18
      PRINT y                                RETURN 0
      PRINT total                        FUNC_END main
      RETURN 0
  FUNC_END main

Three things changed between phase 4 and phase 6, and every one of them would have invalidated a storage map built during phase 3: two temporaries appeared, both were then deleted, and the frame size changed as a result.

8Why they cannot be merged

Four independent reasons, in increasing order of how hard they are to work around:

1. Ordering. Semantic analysis runs two phases before any TAC exists. There is no frame to measure offsets against.
2. Temporaries. t0 and t1 are invented by tac.c. They need frame slots — reserveTemp() hands them out — and in this program the temporaries are the only things that get spilled (the trace reports 3 spills, 0 reloads). A phase-3 table could not have named them.
3. Optimization. The frame size is a function of the optimized TAC, as the figure above shows. Any table filled earlier would reserve slots for names that no longer exist.
4. Structure. One question needs a stack that pops; the other needs a flat map that persists. Section 6.

9Where the two tables touch

They share no data structure. They coordinate through exactly one rule:

static int isReservedName(const char* name) {
    if (strncmp(name, "__sw", 4) == 0) return 1;   switch temporaries
    if (name[0] != 't' && name[0] != 'L') return 0;
    for (int i = 1; name[i]; i++)
        if (name[i] < '0' || name[i] > '9') return 0;
    return 1;
}

The storage map puts user names and generated temporaries into one flat namespace, where lookupSymbol() could not tell them apart. So the semantic analyzer, three phases earlier, refuses to let you declare a variable named t0:

  ❌ Error: 't0' is reserved for the compiler's own use
  📖 Note: names of the form t0, t1, ... are three-address-code
           temporaries and L0, L1, ... are generated labels.

One of phase 3's jobs, then, is protecting phase 6's key space. That is the entire interface between the two tables: a naming convention, enforced early, with a decent error message attached.

10What the split costs

Declarations get recorded twice, and there are two independent duplicate checks that know nothing about each other:

 semantic.c — reported to the user, with a line number 
if (addVarToScope(node->data.decl.name) == -1) { ...SEMANTIC ERROR... }

 symtab.c — the same question, asked again in phase 6 
int addVar(char* name, char* type) {
    if (findIn(&locals, name)) return -1;      duplicate declaration
    ...
}

layoutFrame() discards that -1 without looking at it, and is entitled to: phase 3 already guaranteed there are no duplicates. But it is a genuine redundancy, and the kind of thing worth noticing — it is the seam where two tables that should arguably be one rub against each other.

What a production compiler does instead

Keeps one table whose entries accumulate attributes across phases: the parser inserts the name, the semantic pass annotates type and scope, the back end annotates the address. That requires the table to model scopes as a persistent tree rather than a stack that frees as it pops, and to survive every phase rather than one. It also means every phase can see fields that are meaningless to it.

What the split buys

symtab.c does not know what a scope is. semantic.c does not know what MIPS is. Each file is 300-odd lines and readable on its own, which is why this compiler is a teaching compiler and GCC is not.

11Check yourself