Compilers: Lower an assignment

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, print NAME = 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)

Lesson: Three-address code →