Compilers: Resolve names in nested scopes

Resolve every use of a name to the declaration it refers to.

What to build

A program that resolves names in a block-structured program.

Requirements

  • Lines are {, }, let NAME or use NAME. A declaration is visible from its line to the end of its block, including inner blocks; an inner declaration shadows an outer one.
  • For each use print line K: NAME -> line D (D is the declaration it refers to) or line K: NAME is not declared. For a second declaration of a name in the same scope, print line K: NAME is already declared in this scope and keep the first.

Input

Line 1: n. Then n lines; the braces are balanced.

Output

One line per use and per duplicate declaration, in order.

Constraints

n ≤ 100.

Example

Input:

7
let x
{
let x
use x
}
use x
use y

Output:

line 4: x -> line 3
line 6: x -> line 1
line 7: y is not declared

Why it works

A stack of scopes gives each use the nearest visible declaration, and popping a scope at } makes its names disappear.

Examples

Example 1 · Input
7
let x
{
let x
use x
}
use x
use y
Expected output
line 4: x -> line 3
line 6: x -> line 1
line 7: y is not declared
Example 2 · Input
5
let a
{
use a
let a
}
Expected output
line 3: a -> line 1

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Use a list of dictionaries: push one at `{`, pop it at `}`, and store each name's declaration line.

Hint 2

Search the scopes from the last one to the first, and stop at the first match.

Solution

Show one correct solution (try it yourself first)
scopes = [{}]
for k in range(1, int(input()) + 1):
    parts = input().split()
    if parts == ["{"]:
        scopes.append({})
    elif parts == ["}"]:
        scopes.pop()
    elif parts[0] == "let":
        name = parts[1]
        if name in scopes[-1]:
            print(f"line {k}: {name} is already declared in this scope")
        else:
            scopes[-1][name] = k
    else:
        name = parts[1]
        for scope in reversed(scopes):
            if name in scope:
                print(f"line {k}: {name} -> line {scope[name]}")
                break
        else:
            print(f"line {k}: {name} is not declared")

Lesson: Symbol tables and scopes →