Compilers: Compile loops to stack code

Generate stack code with backpatched jumps.

What to build

A program that compiles a small program to stack-machine code and prints it with addresses.

Requirements

  • Lines: NAME = EXPR, print EXPR, while EXPR … end, if EXPR … end. Expressions: whole numbers, names, + - * and < (lowest precedence), brackets; all operators group from the left.
  • Use the instructions of the previous exercise: post-order code for expressions (ADD, SUB, MUL, LESS), STORE after an assignment, PRINT after a print, and the loop and if layouts of the lesson. Print each instruction as K: INSTRUCTION.

Input

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

Output

The code, one instruction per line.

Constraints

n ≤ 40.

Example

Input:

2
x = 2 + 3 * 4
print x

Output:

0: PUSH 2
1: PUSH 3
2: PUSH 4
3: MUL
4: ADD
5: STORE x
6: LOAD x
7: PRINT

Why it works

Each forward jump is emitted when its block begins and patched when the block ends, which is the moment its target address becomes known.

Examples

Example 1 · Input
2
x = 2 + 3 * 4
print x
Expected output
0: PUSH 2
1: PUSH 3
2: PUSH 4
3: MUL
4: ADD
5: STORE x
6: LOAD x
7: PRINT
Example 2 · Input
4
i = 0
while i < 3
i = i + 1
end
Expected output
0: PUSH 0
1: STORE i
2: LOAD i
3: PUSH 3
4: LESS
5: JUMP_IF_FALSE 11
6: LOAD i
7: PUSH 1
8: ADD
9: STORE i
10: JUMP 2

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

Hints

Hint 1

Record the address where a while loop's condition starts, and the address of its JUMP_IF_FALSE, on a stack of open blocks.

Hint 2

At `end`, emit `JUMP start` for a while loop, then patch the JUMP_IF_FALSE to the next free address.

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() == "<":
            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() == "*":
            node = (take(), node, atom())
        return node

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

    return compare()


code, blocks = [], []


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


def gen(node):
    if isinstance(node, str):
        emit("PUSH", node) if node.isdigit() else emit("LOAD", node)
        return
    op, left, right = node
    gen(left)
    gen(right)
    emit({"+": "ADD", "-": "SUB", "*": "MUL", "<": "LESS"}[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] == "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])
for address, instruction in enumerate(code):
    print(f"{address}: " + " ".join(str(part) for part in instruction))

Lesson: Generating code for a stack machine →