Compilers: Type-check a small program

Combine scopes, type inference and type rules into a checker for statements.

What to build

A program that type-checks a small block-structured program and lists every line with an error.

Requirements

  • Statements: let NAME = EXPR declares NAME with the type of EXPR (inferred); set NAME = EXPR assigns; if EXPR and while EXPR start a block that ends at end; print EXPR. Expressions are trees in prefix form with the rules and messages of the previous exercise.
  • For each line, report only its first error as line K: MESSAGE: an expression error; NAME is already declared for a let of a name in the same scope; NAME is not declared for a set of an unknown name; cannot assign T to NAME of type U; condition is T, not bool. A let with an error declares nothing. If there are no errors, print no type errors.

Input

Line 1: n. Then n lines; blocks are balanced.

Output

One line per error, or no type errors.

Constraints

n ≤ 60.

Example

Input:

5
let n = 10
let big = (< 100 n)
set n = (+ n 1)
set big = n
print (+ "n = " n)

Output:

line 4: cannot assign int to big of type bool
line 5: + cannot take str and int

Why it works

The symbol table supplies each variable's type, inference fills it in at the let, and the expression rules check everything else, line by line.

Examples

Example 1 · Input
5
let n = 10
let big = (< 100 n)
set n = (+ n 1)
set big = n
print (+ "n = " n)
Expected output
line 4: cannot assign int to big of type bool
line 5: + cannot take str and int
Example 2 · Input
4
let i = 0
while (< i 3)
set i = (+ i 1)
end
Expected output
no type errors

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

Hints

Hint 1

Keep a stack of scopes mapping names to types; `if` and `while` push a scope, `end` pops it.

Hint 2

For each line, check its expression first; stop at the first error on that line and move on to the next line.

Solution

Show one correct solution (try it yourself first)
import re

RULES = {
    ("+", "int", "int"): "int",
    ("-", "int", "int"): "int",
    ("*", "int", "int"): "int",
    ("+", "str", "str"): "str",
    ("<", "int", "int"): "bool",
    ("and", "bool", "bool"): "bool",
    ("or", "bool", "bool"): "bool",
    ("not", "bool"): "bool",
}
scopes = [{}]


class TypeCheckError(Exception):
    pass


def lookup(name):
    for scope in reversed(scopes):
        if name in scope:
            return scope[name]
    return None


def read(text):
    tokens = re.findall(r'\(|\)|"[^"]*"|[^\s()]+', text)

    def node():
        token = tokens.pop(0)
        if token != "(":
            return token
        items = []
        while tokens[0] != ")":
            items.append(node())
        tokens.pop(0)
        return items

    return node()


def check(node):
    if isinstance(node, str):
        if node.isdigit():
            return "int"
        if node.startswith('"'):
            return "str"
        if node in ("true", "false"):
            return "bool"
        found = lookup(node)
        if found is None:
            raise TypeCheckError(f"{node} is not declared")
        return found
    op, *args = node
    types = [check(arg) for arg in args]
    if op == "if":
        if types[0] != "bool":
            raise TypeCheckError(f"if needs a bool condition, not {types[0]}")
        if types[1] != types[2]:
            raise TypeCheckError(f"if branches differ: {types[1]} and {types[2]}")
        return types[1]
    if op == "==" and types[0] == types[1]:
        return "bool"
    key = (op, *types)
    if key not in RULES:
        raise TypeCheckError(f"{op} cannot take {' and '.join(types)}")
    return RULES[key]


errors = []
for k in range(1, int(input()) + 1):
    line = input().strip()
    try:
        if line == "end":
            scopes.pop()
            continue
        m = re.fullmatch(r"(let|set) (\w+) = (.+)", line)
        if m:
            kind, name, expr = m.groups()
            t = check(read(expr))
            if kind == "let":
                if name in scopes[-1]:
                    raise TypeCheckError(f"{name} is already declared")
                scopes[-1][name] = t
            else:
                target = lookup(name)
                if target is None:
                    raise TypeCheckError(f"{name} is not declared")
                if target != t:
                    raise TypeCheckError(f"cannot assign {t} to {name} of type {target}")
            continue
        kind, expr = line.split(" ", 1)
        if kind in ("if", "while"):
            scopes.append({})
            t = check(read(expr))
            if t != "bool":
                raise TypeCheckError(f"condition is {t}, not bool")
        else:
            check(read(expr))
    except TypeCheckError as error:
        errors.append(f"line {k}: {error}")
print("\n".join(errors) if errors else "no type errors")

Lesson: Type checking →