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),STOREafter an assignment,PRINTafter a print, and the loop andiflayouts of the lesson. Print each instruction asK: 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))