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 withgoto,iforifFalse. - Leaders are line 1, every label and every line just after a jump. Print
Bk: lines a-bfor 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]}")