Symbol Table

Work on this exercise locally

This web app is a reference guide — you can read instructions, browse starter code, and view tests here. To actually complete the exercise, you need to work in your local development environment.

1Clone the repo: git clone https://github.com/weihaoqu/program-analysis-bootcamp-student

2Edit the starter file in your editor (VS Code, Vim, etc.) — replace failwith "TODO" with your implementation.

3Run the tests: dune runtest modules/module2-ast/exercises/symbol-table

5. Exercise 3: Symbol Table (6 tests)

Goal: Implement a scoped symbol table using a stack of maps. This exercise is self-contained -- it does not depend on shared_ast.

Time: ~15 minutes

Files to edit:

exercises/symbol-table/starter/symbol_table.ml -- the implementation
exercises/symbol-table/starter/symbol_table.mli -- the interface (provided, read-only)

The data structures

(* Each symbol has a name, type, and mutability flag *)
type symbol_info = {
  sym_name : string;
  sym_type : string;
  mutable_flag : bool;
}

(* The table is a scope stack: a list of maps from names to symbol_info.
   Head = innermost scope, tail = enclosing scopes. *)
type t = symbol_info StringMap.t list

How scoping works

Global scope:  { x -> int }
               |
               +-- Inner scope: { x -> float, y -> bool }
                                  ^
                    x is shadowed (float wins over int)
                    y is only visible here

After exit_scope:
Global scope:  { x -> int }
               y is gone, x is int again

What to implement

#	Function	Hint
1	`create ()`	Return a list with one empty `StringMap.t`: `[StringMap.empty]`
2	`define tbl name info`	Add the binding to the head (innermost) map using `StringMap.add`
3	`lookup tbl name`	Search from innermost scope outward; return the first match. Use `List.find_map` or a recursive scan
4	`enter_scope tbl`	Push `StringMap.empty` onto the front of the list
5	`exit_scope tbl`	Pop the head. If only one scope remains (the global scope), return `None`; otherwise return `Some rest`

Run tests

dune runtest modules/module2-ast/exercises/symbol-table/

Starter output: EEEEEE (6 errors -- all TODOs)

Hints

The entire implementation is a list of StringMap.t values. create returns [StringMap.empty], enter_scope conses another empty map, and exit_scope returns the tail.
For lookup, iterate through the list of scopes and check StringMap.find_opt name scope in each. The first Some you find is the answer (innermost scope wins).
exit_scope should refuse to pop the last remaining scope (the global scope).

Starter Files

starter

Test Files

tests

starter/symbol_table.ml

Read-only

Loading editor...