Lower one assignment to three-address code.
What to build
A program that turns NAME = EXPRESSION into three-address instructions.
Requirements
- Operators
+ - * /with the usual precedence, grouped from the left, and brackets. Temporaries are t1, t2, … in the order they are created. - Each operator becomes
DEST = A OP B; the root writes to NAME directly. If the expression is a single name or number, printNAME = VALUE.
Input
One line: NAME = EXPRESSION.
Output
One instruction per line.
Constraints
At most 80 characters; the expression is valid.
Example
Input:
x = a + b * c
Output:
t1 = b * c
x = a + t1
Why it works
A post-order walk produces each operand before the operator that needs it, and a fresh temporary keeps every partial result separate.
Examples
Example 1 · Input
x = a + b * c
Expected output
t1 = b * c x = a + t1
Example 2 · Input
y = (a + b) * (a - b)
Expected output
t1 = a + b t2 = a - b y = t1 * t2
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Parse into a tree (+ − below * /), then lower the left child, the right child, and the node.
Hint 2
Only the root writes to the assigned variable; every other operator gets the next temporary t1, t2, …
Solution
Show one correct solution (try it yourself first)
import re
tokens = re.findall(r"\d+|\w+|\S", input())
target, tokens = tokens[0], tokens[2:]
pos = 0
temps = 0
def peek():
return tokens[pos] if pos < len(tokens) else None
def take():
global pos
pos += 1
return tokens[pos - 1]
def expr():
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 = expr()
take()
return node
return token
def lower(node, dest=None):
global temps
if isinstance(node, str):
if dest:
print(f"{dest} = {node}")
return node
op, left, right = node
a = lower(left)
b = lower(right)
if dest is None:
temps += 1
dest = f"t{temps}"
print(f"{dest} = {a} {op} {b}")
return dest
lower(expr(), target)