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, andif 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
DIVandEQUAL. 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, theninstructions: N(the code length) andsteps: 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
6 x = 7 if x < 5 print 1 else print 2 end
2 instructions: 11 steps: 8
5 i = 0 while i < 3 print i * i i = i + 1 end
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)