Compilers: Run three-address code

Write an interpreter for three-address code, which is how you test a code generator.

What to build

A program that runs three-address code and reports what it prints and how many instructions ran.

Requirements

  • Forms: L: (a label), x = a, x = a op b with op one of + - * / % < <= > >= == !=, goto L, ifFalse a goto L (jump if a is 0), if a goto L (jump if a is not 0), print a. Operands are names or whole numbers; variables start at 0; / and % round down as in Python; comparisons give 1 or 0.
  • Run from the first line until the end. Print each print value on its own line, then steps: S, the number of instructions run (labels do not count). If a 10,001st instruction is about to run, print stopped after 10000 steps instead of the steps line and stop.

Input

Line 1: n. Then n lines of three-address code.

Output

The printed values, then the steps line or the stop line.

Constraints

n ≤ 100; there is no division by zero.

Example

Input:

8
i = 0
L1:
t1 = i < 3
ifFalse t1 goto L2
print i
i = i + 1
goto L1
L2:

Output:

0
1
2
steps: 18

Why it works

Three-address code is simple enough that a short loop can run it, which lets you check a compiler's output before any machine code exists.

Examples

Example 1 · Input
8
i = 0
L1:
t1 = i < 3
ifFalse t1 goto L2
print i
i = i + 1
goto L1
L2:
Expected output
0
1
2
steps: 18
Example 2 · Input
3
a = 7
b = a / 2
print b
Expected output
3
steps: 3

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

Hints

Hint 1

First record the position of every label; then run with a program counter, moving it on by one or jumping to a label.

Hint 2

Count only instructions (not labels), and check the limit before running each one.

Solution

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

lines = [input().strip() for _ in range(int(input()))]
labels = {line[:-1]: i for i, line in enumerate(lines) if line.endswith(":")}
env = {}
OPS = {
    "+": lambda a, b: a + b,
    "-": lambda a, b: a - b,
    "*": lambda a, b: a * b,
    "/": lambda a, b: a // b,
    "%": lambda a, b: a % b,
    "<": lambda a, b: int(a < b),
    "<=": lambda a, b: int(a <= b),
    ">": lambda a, b: int(a > b),
    ">=": lambda a, b: int(a >= b),
    "==": lambda a, b: int(a == b),
    "!=": lambda a, b: int(a != b),
}


def value(token):
    return int(token) if re.fullmatch(r"-?\d+", token) else env.get(token, 0)


pc = steps = 0
while pc < len(lines):
    line = lines[pc]
    pc += 1
    if line.endswith(":"):
        continue
    if steps == 10000:
        print("stopped after 10000 steps")
        break
    steps += 1
    words = line.split()
    if words[0] == "goto":
        pc = labels[words[1]]
    elif words[0] == "ifFalse":
        if value(words[1]) == 0:
            pc = labels[words[3]]
    elif words[0] == "if":
        if value(words[1]) != 0:
            pc = labels[words[3]]
    elif words[0] == "print":
        print(value(words[1]))
    else:
        rhs = words[2:]
        env[words[0]] = value(rhs[0]) if len(rhs) == 1 else OPS[rhs[1]](value(rhs[0]), value(rhs[2]))
else:
    print("steps:", steps)

Lesson: Three-address code →