Compilers: Lower loops and conditions

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 C gives L_start:, the condition's code, ifFalse C goto L_end, the body, goto L_start, L_end:. if C gives 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))

Lesson: Three-address code →