Compilers: Type-check expression trees

Type-check whole expressions with variables, operators and conditionals.

What to build

A program that prints the type of each expression tree, or its first type error.

Requirements

  • Literals: whole numbers (int), "strings" (str), true and false (bool). Variables take their declared types. Rules: + - * int, int → int; + str, str → str; < int, int → bool; == two of the same type → bool; and, or bool, bool → bool; not bool → bool; (if c a b) needs c bool and a, b of the same type, and has that type.
  • Errors, checking children left to right: error: NAME is not declared, error: OP cannot take T1 and T2 (for not, just T), error: if needs a bool condition, not T, error: if branches differ: T1 and T2.

Input

Line 1: d. Then d lines name type. Then a line with m, then m expression trees in prefix form.

Output

m lines.

Constraints

d, m ≤ 20; strings contain no spaces or brackets.

Example

Input:

2
x int
ok bool
3
(+ x 1)
(and ok (< x 10))
(+ x "a")

Output:

int
bool
error: + cannot take int and str

Why it works

Each node's type follows from its children's types and one rule, so a single recursive walk types the whole tree or finds the first mistake.

Examples

Example 1 · Input
2
x int
ok bool
3
(+ x 1)
(and ok (< x 10))
(+ x "a")
Expected output
int
bool
error: + cannot take int and str
Example 2 · Input
1
s str
2
(if (== s "hi") 1 0)
(if s 1 0)
Expected output
int
error: if needs a bool condition, not str

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

Hints

Hint 1

Read each tree recursively, check the children first, then apply the rule for the operator.

Hint 2

Raise an exception with the message at the first error and catch it once per expression.

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",
}
env = dict(input().split() for _ in range(int(input())))


class TypeCheckError(Exception):
    pass


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"
        if node in env:
            return env[node]
        raise TypeCheckError(f"{node} is not declared")
    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]


for _ in range(int(input())):
    try:
        print(check(read(input())))
    except TypeCheckError as error:
        print(f"error: {error}")

Lesson: Type checking →