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 bwith 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
printvalue on its own line, thensteps: S, the number of instructions run (labels do not count). If a 10,001st instruction is about to run, printstopped after 10000 stepsinstead 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
8 i = 0 L1: t1 = i < 3 ifFalse t1 goto L2 print i i = i + 1 goto L1 L2:
0 1 2 steps: 18
3 a = 7 b = a / 2 print b
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)