Loading page…
Master the fundamental concepts of semantic analysis through this focused micro-challenge.
You have read the whole brief, and the concepts above stay free on every task. Writing and running the code needs a plan.
Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.
Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.
How it worksEvery declaration inserts a name; every use looks it up. Compilers chain symbol tables for nested scopes: function body inside file scope inside namespace. LLVM, GCC, and Clang all use scoped hash tables with push/pop on block entry and exit.
On entering a block, push a new table. On declaration, insert (name, type, location) in the current scope. On use, search innermost scope first, then outer scopes. On exit, pop the inner table.
cLoading…
x hides outer xProduction compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.
You will implement a scoped symbol table with insert, lookup, and push/pop for blocks. This exercise requires tracking declared names and resolving identifiers to their declarations during semantic analysis.
Implement the symbol table every later compiler phase depends on: a chain of scopes with define, scoped lookup, local lookup and scope enter/exit. Stdin is a script of operations; print what each one does.
One operation per line (blank lines ignored):
| Operation | Effect |
|---|---|
enter | push a new scope |
exit | pop the current scope |
define NAME TYPE | add NAME with type TYPE (one word) to the current scope |
lookup NAME | find NAME in the current scope or the nearest enclosing one |
local NAME | find NAME in the current scope only |
exists NAME | is NAME defined in any visible scope? |
Scopes are numbered in creation order: the global scope is 0, the first enter creates scope 1, the next 2, and so on (numbers are never reused). The depth of the global scope is 0.
| Operation | Success | Failure |
|---|---|---|
enter | enter scope N (depth D) | - |
exit | exit scope N (K symbols) | error: cannot exit the global scope |
define | define NAME: TYPE in scope N | error: 'NAME' already defined in scope N |
lookup | lookup NAME: TYPE from scope N (U levels up) | lookup NAME: not found |
local | local NAME: TYPE | local NAME: not found in scope N |
exists | exists NAME: yes | exists NAME: no |
U is how many scopes outward the symbol was found (0 = the current scope). Redefining a name in an inner scope is allowed (it shadows). After the script, print scopes=S max_depth=D: scopes created including the global one, and the greatest depth reached.
Input:
cLoading…
Output:
cLoading…
Scope with a parent pointer and its own symbol storage (a hash table is ideal); scope_enter, scope_exit, symbol_define, symbol_lookup, symbol_lookup_local.scope_exit must free the scope and its symbols.Hidden tests cover deep nesting, sibling scopes (numbers keep increasing after an exit), redefinition errors, and lookups that fail after their scope has exited.