Compilers: Live ranges

Compute the live range of every value in straight-line code.

What to build

A program that prints the live range of each variable.

Requirements

  • Instructions are x = a, x = a op b and print a, numbered from 1; operands are names or numbers. Each variable is written at most once, and never after it has been read.
  • A variable's range starts at the line that writes it (0 for an input) and ends at the last line that reads it (its start if it is never read). Print NAME: START-END for each variable, sorted by start and then by name.

Input

Line 1: n. Then n instructions.

Output

One line per variable.

Constraints

n ≤ 100.

Example

Input:

4
a = x + 1
b = a * a
c = b - x
print c

Output:

x: 0-3
a: 1-2
b: 2-3
c: 3-4

Why it works

A value occupies storage from the moment it is written until it is read for the last time; outside that range, its register is free.

Examples

Example 1 · Input
4
a = x + 1
b = a * a
c = b - x
print c
Expected output
x: 0-3
a: 1-2
b: 2-3
c: 3-4
Example 2 · Input
2
t = 5
u = t
Expected output
t: 1-2
u: 2-2

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

Hints

Hint 1

An operand that has not been written yet is an input and starts at line 0.

Hint 2

Update a variable's end every time it is read; a variable that is never read ends where it starts.

Solution

Show one correct solution (try it yourself first)
start, end = {}, {}
for k in range(1, int(input()) + 1):
    words = input().split()
    dest, read = (None, words[1:]) if words[0] == "print" else (words[0], words[2:])
    for word in read:
        if word.isidentifier():
            start.setdefault(word, 0)
            end[word] = k
    if dest:
        start[dest] = k
        end.setdefault(dest, k)
for name in sorted(start, key=lambda n: (start[n], n)):
    print(f"{name}: {start[name]}-{end[name]}")

Lesson: Register allocation →