Bài tập | NEU OJ

Cho một chương trình gồm $n$ dòng lệnh giả-TAC, đánh số thứ tự từ $1$ đến $n$ . Mỗi dòng có thể có tiền tố nhãn dạng Lk: (k là số nguyên dương) đứng trước nội dung lệnh (cách nhau đúng 1 khoảng trắng); phần nội dung sau nhãn (hoặc toàn bộ dòng nếu không có nhãn) thuộc một trong ba dạng:

goto Lk: nhảy không điều kiện tới dòng có nhãn Lk.
if <dieu_kien> goto Lk: nhảy có điều kiện tới dòng có nhãn Lk (<dieu_kien> có thể chứa nhiều token và khoảng trắng, nhưng từ khoá goto chỉ xuất hiện đúng một lần trong dòng, ngay trước Lk).
Lệnh thường (gán,...) — không thuộc hai dạng trên.

Mỗi nhãn xuất hiện đúng một lần trong toàn bộ chương trình, và mọi nhãn đích được tham chiếu bởi goto/if...goto đều tồn tại.

Xác định các leader (lệnh dẫn đầu khối cơ bản) theo đúng thuật toán kinh điển:

Dòng $1$ luôn là leader.
Bất kỳ dòng nào là đích của một lệnh goto hoặc if...goto đều là leader.
Bất kỳ dòng nào đứng ngay sau một lệnh goto hoặc if...goto (nếu tồn tại, tức không phải dòng cuối chương trình) đều là leader.

Mỗi khối cơ bản bắt đầu tại một leader và gồm mọi dòng liên tiếp cho tới trước leader kế tiếp (hoặc tới hết chương trình nếu là leader cuối cùng).

Ví dụ: với chương trình

i = 0
L1: i = i + 1
if i < 5 goto L1
x = i

kết quả là 3 khối: khối 1 gồm dòng 1 (size=1), khối 2 gồm dòng 2-3 (leader=2, size=2), khối 3 gồm dòng 4 (leader=4, size=1).

Định dạng đầu vào:
Dòng 1: số nguyên $n$ . $n$ dòng tiếp theo: nội dung các dòng lệnh, giữ nguyên định dạng mô tả ở trên.
Định dạng đầu ra:
Dòng đầu: SO_KHOI = <so khoi co ban>. Sau đó, với mỗi khối theo thứ tự leader tăng dần, in một dòng Block i: leader=X, size=Y (i đánh số từ 1; X là số thứ tự dòng leader của khối; Y là số lệnh trong khối).

solution

Đề bài: [Trình biên dịch] Xác định các khối cơ bản từ mã có nhãn và lệnh rẽ nhánh