Compilers: Compile and run, with else

Build a complete compiler for a small language: parse, generate code with backpatching, and run it.

What to build

A program that compiles a small language to stack code, runs it, and reports the code size and the number of steps.

Requirements

  • Lines: NAME = EXPR, print EXPR, while EXPR … end, if EXPR … end, and if EXPR … else … end. Expressions: whole numbers, names, brackets, * / (highest, / rounds down), + -, then < and == (lowest); all group from the left.
  • Code as in the previous exercise, plus DIV and EQUAL. An if with else compiles to: condition, JUMP_IF_FALSE else, then part, JUMP end, else part. Run the code (variables start at 0) and print each printed value, then instructions: N (the code length) and steps: S (instructions run).

Input

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

Output

The printed values, then the two counts.

Constraints

n ≤ 40; programs finish within 10,000 steps and never divide by zero.

Example

Input:

6
x = 7
if x < 5
print 1
else
print 2
end

Output:

2
instructions: 11
steps: 8

Why it works

Each control structure becomes a fixed pattern of jumps, and backpatching fills in every forward address, so a single pass over the program produces runnable code.

Examples

Example 1 · Input
6
x = 7
if x < 5
print 1
else
print 2
end
Expected output
2
instructions: 11
steps: 8
Example 2 · Input
5
i = 0
while i < 3
print i * i
i = i + 1
end
Expected output
0
1
4
instructions: 15
steps: 45

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

Hints

Hint 1

At `else`, emit a JUMP with a blank address (to skip the else part), patch the if's JUMP_IF_FALSE to the next address, and remember the new jump for the `end`.

Hint 2

Reuse your virtual machine, counting every instruction it runs.

Solution

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


def parse(tokens):
    pos = 0

    def peek():
        return tokens[pos] if pos < len(tokens) else None

    def take():
        nonlocal pos
        pos += 1
        return tokens[pos - 1]

    def compare():
        node = arith()
        while peek() in ("<", "=="):
            node = (take(), node, arith())
        return node

    def arith():
        node = term()
        while peek() in ("+", "-"):
            node = (take(), node, term())
        return node

    def term():
        node = atom()
        while peek() in ("*", "/"):
            node = (take(), node, atom())
        return node

    def atom():
        token = take()
        if token == "(":
            node = compare()
            take()
            return node
        return token

    return compare()


NAMES = {"+": "ADD", "-": "SUB", "*": "MUL", "/": "DIV", "<": "LESS", "==": "EQUAL"}
code, blocks = [], []


def emit(*instruction):
    code.append(list(instruction))
    return len(code) - 1


def gen(node):
    if isinstance(node, str):
        emit("PUSH", int(node)) if node.isdigit() else emit("LOAD", node)
        return
    op, left, right = node
    gen(left)
    gen(right)
    emit(NAMES[op])


for _ in range(int(input())):
    tokens = re.findall(r"\d+|\w+|==|\S", input())
    if tokens[0] in ("while", "if"):
        start = len(code)
        gen(parse(tokens[1:]))
        blocks.append([tokens[0], start, emit("JUMP_IF_FALSE", None)])
    elif tokens[0] == "else":
        block = blocks[-1]
        skip = emit("JUMP", None)
        code[block[2]][1] = len(code)
        block[0], block[2] = "else", skip
    elif tokens[0] == "end":
        kind, start, jump = blocks.pop()
        if kind == "while":
            emit("JUMP", start)
        code[jump][1] = len(code)
    elif tokens[0] == "print":
        gen(parse(tokens[1:]))
        emit("PRINT")
    else:
        gen(parse(tokens[2:]))
        emit("STORE", tokens[0])

stack, memory, pc, steps = [], {}, 0, 0
while pc < len(code):
    op, *arg = code[pc]
    pc += 1
    steps += 1
    if op == "PUSH":
        stack.append(arg[0])
    elif op == "LOAD":
        stack.append(memory.get(arg[0], 0))
    elif op == "STORE":
        memory[arg[0]] = stack.pop()
    elif op == "PRINT":
        print(stack.pop())
    elif op == "JUMP":
        pc = arg[0]
    elif op == "JUMP_IF_FALSE":
        if stack.pop() == 0:
            pc = arg[0]
    else:
        b, a = stack.pop(), stack.pop()
        if op == "ADD":
            stack.append(a + b)
        elif op == "SUB":
            stack.append(a - b)
        elif op == "MUL":
            stack.append(a * b)
        elif op == "DIV":
            stack.append(a // b)
        elif op == "LESS":
            stack.append(int(a < b))
        else:
            stack.append(int(a == b))
print("instructions:", len(code))
print("steps:", steps)

Lesson: Generating code for a stack machine →