Lower a small program with loops and conditions to labels and jumps.
What to build
A program that lowers assignments, while and if blocks to three-address code.
Requirements
- Lines:
NAME = EXPR,while EXPR,if EXPR,end. Precedence from lowest:< <= > >= == !=, then+ -, then* /; all group from the left; brackets allowed. - Lower assignments as in the previous exercise.
while CgivesL_start:, the condition's code,ifFalse C goto L_end, the body,goto L_start,L_end:.if Cgives the condition's code,ifFalse C goto L_end, the body,L_end:. Temporaries t1, t2, … and labels L1, L2, … are numbered across the whole program in the order they are created; a block creates its labels when it begins.
Input
Line 1: n. Then n lines; blocks are balanced.
Output
The three-address code, one instruction or label per line.
Constraints
n ≤ 40.
Example
Input:
5
i = 0
while i < 3
i = i + 1
end
done = i
Output:
i = 0
L1:
t1 = i < 3
ifFalse t1 goto L2
i = i + 1
goto L1
L2:
done = i
Why it works
Labels and conditional jumps are all a machine has for control flow, and every structured loop or condition can be written with them.
Examples
Example 1 · Input
5 i = 0 while i < 3 i = i + 1 end done = i
Expected output
i = 0 L1: t1 = i < 3 ifFalse t1 goto L2 i = i + 1 goto L1 L2: done = i
Example 2 · Input
3 if x > y * 2 m = x end
Expected output
t1 = y * 2 t2 = x > t1 ifFalse t2 goto L1 m = x L1:
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
`while` makes two labels (start, then end) and places the start label before the condition; `if` makes one label.
Hint 2
Keep a stack of open blocks so that `end` knows whether to emit a goto and which label to place.
Solution
Show one correct solution (try it yourself first)
import re
code, blocks = [], []
temps = labels = 0
def new_temp():
global temps
temps += 1
return f"t{temps}"
def new_label():
global labels
labels += 1
return f"L{labels}"
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()
def lower(node, dest=None):
if isinstance(node, str):
if dest:
code.append(f"{dest} = {node}")
return node
op, left, right = node
a, b = lower(left), lower(right)
dest = dest or new_temp()
code.append(f"{dest} = {a} {op} {b}")
return dest
for _ in range(int(input())):
tokens = re.findall(r"\d+|\w+|[<>=!]=|\S", input())
if tokens[0] == "while":
start, end = new_label(), new_label()
code.append(f"{start}:")
code.append(f"ifFalse {lower(parse(tokens[1:]))} goto {end}")
blocks.append((start, end))
elif tokens[0] == "if":
end = new_label()
code.append(f"ifFalse {lower(parse(tokens[1:]))} goto {end}")
blocks.append((None, end))
elif tokens[0] == "end":
start, end = blocks.pop()
if start:
code.append(f"goto {start}")
code.append(f"{end}:")
else:
lower(parse(tokens[2:]), tokens[0])
print("\n".join(code))