Compilers: Find the basic blocks

Split three-address code into basic blocks.

What to build

A program that finds the basic blocks of three-address code.

Requirements

  • Lines are three-address code: labels end with :, and jumps start with goto, if or ifFalse.
  • Leaders are line 1, every label and every line just after a jump. Print Bk: lines a-b for each block, numbered in order.

Input

Line 1: n. Then n lines of three-address code.

Output

One line per block.

Constraints

n ≤ 100.

Example

Input:

8
i = 0
L1:
t1 = i < 3
ifFalse t1 goto L2
print i
i = i + 1
goto L1
L2:

Output:

B1: lines 1-1
B2: lines 2-4
B3: lines 5-7
B4: lines 8-8

Why it works

Control can enter only at a leader and leave only at a block's last line, so the code between two leaders always runs as a unit.

Examples

Example 1 · Input
8
i = 0
L1:
t1 = i < 3
ifFalse t1 goto L2
print i
i = i + 1
goto L1
L2:
Expected output
B1: lines 1-1
B2: lines 2-4
B3: lines 5-7
B4: lines 8-8
Example 2 · Input
3
a = 1
b = a + 2
print b
Expected output
B1: lines 1-3

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Mark line 1, every label line, and every line right after a `goto`, `if` or `ifFalse` line.

Hint 2

Each block runs from one leader to the line before the next leader.

Solution

Show one correct solution (try it yourself first)
lines = [input().strip() for _ in range(int(input()))]
leaders = {0}
for i, line in enumerate(lines):
    if line.endswith(":"):
        leaders.add(i)
    if line.split()[0] in ("goto", "if", "ifFalse") and i + 1 < len(lines):
        leaders.add(i + 1)
starts = sorted(leaders) + [len(lines)]
for k in range(len(starts) - 1):
    print(f"B{k + 1}: lines {starts[k] + 1}-{starts[k + 1]}")

Lesson: Basic blocks, control-flow graphs and liveness →