Scoping & Symbol Table

Up until now, we have parsed our program, constructed an abstract syntax tree and attached some basic type information to nodes in our compiler journey. Before moving to the next part which is semantic analysis where we would try to understand what the program is trying to achieve, we’d want to build some data structures that will help us in analysing the program.

A program is usually a combination of two things: data and logic. Data, stored in variables, flows through the program according to some logic defined by the programmer. It is important for us, as compiler developers, to understand what data the program defines and works with, and how it moves it around the program. To do this, we will make use of a structure often called a symbol table.

Symbol Table

Symbols are values handled by a program. You can interchangeably use this term with variables, but it is better to call them symbols as they may not be “varying” in values always. Some symbols may be constants, or functions that are used as values in certain programming languages. Types are also symbols as Gom supports custom types and we need to keep track of these in our program.

In a compiler, a symbol table is a map-like data structure that stores information for each symbol that the compiler can refer to at later stages to make decisions. Take a simple example:

let a = 1, b = 2;
if (a > 0) {
  let a = "hello";
  a = "world";
  io.log("a: ", a, ", b: ", b);
}

This is a valid Gom syntax as the language allows block-scoped variable declarations. Hence, when the log statement runs, it will print a: world, b: 2. When we do semantic analysis, we would want to ensure that variable values respect their types and to do this we’d want to know about the allowed types for a symbol.

Scopes

Storing symbol information would have been as simple as maintaining a map of symbols and their type information but in somewhat-real languages, there’ll often be a concept of scopes. Scoping is crucial to define non-simple logic like conditions and creates a set of blocks in the program through which control flows.

Like in many other languages, each scope in Gom can define its own set of variables and also has access to variables from parent / ancestor scopes. In the example we saw above, the variable b was accessible in the if block even when it was defined outside the block. a was shadowed by a local declaration of a variable with the same name.

In order to support such behaviour, we’d have to think more than just maintaining a map. If you think about it, scopes can be entered into and exited from. Hence whatever structure we use to maintain symbol information should be able to store previous symbol information while using the latest block as the source for current state.

A great way to store scope information is using a scope tree.

Scopes in code

SymbolTableNode is a generic tree node which stores a reference to its parent and children. References to children are useful for cases we will encounter in the code generation chapter. value will store the scope information at each level of the program.

class SymbolTableNode<T> {
  private children: SymbolTableNode<T>[] = [];

  constructor(
    private name: string,
    private value: T,
    private parent?: SymbolTableNode<T>,
  ) {}

  addChild(value: SymbolTableNode<T>) {
    this.children.push(value);
  }

  getValue() {
    return this.value;
  }

  getParent() {
    return this.parent;
  }

  getChildren() {
    return this.children;
  }

  getName() {
    return this.name;
  }
}

We then define two kinds of entries that will be stored in the symbol table: TypeEntry and IdentifierEntry, for custom types and variables respectively. These are simple storage classes that hold details about each entry.

Now, we define the Scope class. This is where we will store entries for each scope and will expose methods to work with them. During semantic analysis, the compiler will collect all entries in a scope and store them in the scope object corresponding to that level.

interface ScopeEntries {
  types: Record<string, TypeEntry>;
  identifiers: Record<string, IdentifierEntry>;
}

export class Scope {
  private entries: ScopeEntries = {
    types: {},
    identifiers: {},
  };

  constructor(parent?: Scope) {
    if (parent) {
      this.entries = structuredClone(parent.entries);
    }
  }

  putType(name: string, node: NodeTypeDefinition) {
    const existingEntry =
      this.entries.types[name] ?? this.entries.identifiers[name];
    if (existingEntry) {
      throw new SyntaxError({
        message: `Block-scoped value "${name}" already declared: Name: ${name}, Value: ${existingEntry.getValue()}`,
        loc: [1, node.loc],
      });
    }
    this.entries.types[name] = new TypeEntry(name, node);
  }

  putIdentifier(
    name: string,
    node: NodeTerm | NodeFunctionDefinition,
    type: GomType,
    valueExpr?: NodeExpr,
  ) {
    const existingEntry =
      this.entries.types[name] ?? this.entries.identifiers[name];
    if (existingEntry) {
      throw new SyntaxError({
        message: `Block-scoped value "${name}" already declared: Name: ${name}, Value: ${existingEntry.getValue()}`,
        loc: [1, node.loc],
      });
    }

    this.entries.identifiers[name] = new IdentifierEntry(
      name,
      node,
      type,
      valueExpr,
    );
  }

  // ... other methods
}

Working with scopes using `ScopeManager`

Semantic analysis requires a way to do the following with scopes:

Define a new scope when it sees a new block starting e.g.
```
if(...) { // start
```
Add a new custom type or variable to the current scope
Get the type of a variable to determine inferred type e.g.
```
let a = 1;
let b = a;  // type of `b` inferred from `a`
```
End a scope
```
if(...) { ... } // end
```

Finally, we’ll provide this functionality in the compiler using a scope manager class.

export class ScopeManager {
  private currentSymbolTableNode: SymbolTableNode<Scope>;
  private primitiveTypes: Record<GomPrimitiveTypeOrAliasValue, TypeEntry> = {};

  constructor() {
    this.currentSymbolTableNode = new SymbolTableNode("root", new Scope());
    this.setPrimitiveTypes();
  }

  beginScope(name: string) {
    const newSymbolTable = new SymbolTableNode(
      name,
      new Scope(),
      this.currentSymbolTableNode,
    );
    this.currentSymbolTableNode.addChild(newSymbolTable);
    this.currentSymbolTableNode = newSymbolTable;
  }

  endScope() {
    const parent = this.currentSymbolTableNode.getParent();
    if (parent) {
      this.currentSymbolTableNode = parent;
    } else {
      throw new GomInternalError({
        message: "Cannot end root scope",
      });
    }
  }

  putType(name: string, node: NodeTypeDefinition) {
    this.getCurrentScope().putType(name, node);
  }

  putIdentifier(
    name: string,
    node: NodeTerm | NodeFunctionDefinition,
    type: GomType,
    valueExpr?: NodeExpr,
  ) {
    this.getCurrentScope().putIdentifier(name, node, type, valueExpr);
  }

  getIdentifier(name: string) {
    return this.getCurrentScope().getIdentifier(name);
  }

  getType(name: string) {
    if (this.primitiveTypes[name]) {
      return this.primitiveTypes[name];
    }
    return this.getCurrentScope().getType(name);
  }

  // ... other methods
}

Next steps

Now that we have our scope manager ready, it’s time to do the semantic analysis of our Gom source code. This is where we’ll use the symbol table (provided as an instance of ScopeManager) to walk through the source AST and collect information about the program. On the way, we’ll use the collected information to validate some of the source too.

gom/src/semantics/scope.ts Scope-related code in Gom compiler