Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Trình biên dịch] Loại bỏ mã chết trên mã ba địa chỉ

    Cho một chương trình mã ba địa chỉ tuyến tính gồm mmm câu lệnh, được đánh số ngầm 1,2,…,m1, 2, \dots, m1,2,…,m theo thứ tự xuất hiện. Lệnh thứ iii luôn có dạng:

    tI = A OP B

    hoặc

    tI = A

    trong đó tI chính là biến tạm được định nghĩa tại lệnh iii (chỉ số III trong tên biến trùng với thứ tự lệnh iii, mỗi tit_iti​ chỉ được định nghĩa đúng một lần), OP∈{+,−,∗,/}OP \in \{+, -, *, /\}OP∈{+,−,∗,/}, và mỗi toán hạng AAA, BBB hoặc là một hằng số nguyên, hoặc là một biến tạm tjt_jtj​ với j<ij < ij<i đã được định nghĩa trước đó.

    Sau mmm câu lệnh, có thêm một dòng print tK cho biết giá trị cuối cùng cần quan tâm là tKt_KtK​.

    Một câu lệnh được gọi là sống (live) nếu nó cần thiết để tính ra giá trị tKt_KtK​, xác định bằng phân tích lùi: lệnh định nghĩa tKt_KtK​ là sống; nếu lệnh định nghĩa tit_iti​ là sống và tit_iti​ sử dụng toán hạng tjt_jtj​ thì lệnh định nghĩa tjt_jtj​ cũng là sống. Các lệnh còn lại là mã chết (dead code), có thể loại bỏ khỏi chương trình mà không ảnh hưởng tới giá trị in ra.

    Hãy đếm số lượng câu lệnh là mã chết trong tổng số mmm câu lệnh.

    • Định dạng đầu vào:

      Dòng 1: số nguyên mmm. mmm dòng tiếp theo: câu lệnh thứ iii theo đúng cú pháp tI = A OP B hoặc tI = A như mô tả ở trên (token cách nhau đúng 1 khoảng trắng, tI viết đúng là t nối với số thứ tự iii). Dòng cuối cùng: print tK (K là chỉ số của biến tạm cần quan tâm, 1≤K≤m1 \le K \le m1≤K≤m).

    • Định dạng đầu ra:

      In ra duy nhất một số nguyên - số lượng câu lệnh là mã chết (dead code).

      Ví dụ input:

      4
t1 = 5
t2 = 3
t3 = t1 + t2
t4 = t1 * 2
print t3

      Output: 1 (lệnh định nghĩa t4 không cần thiết để tính t3, nên là mã chết).

    Ví dụ:

    Đầu vào:

    4
t1 = 5
t2 = 3
t3 = t1 + t2
t4 = t1 * 2
print t3

    Đầu ra:

    1

    Đầu vào:

    1
t1 = 7
print t1

    Đầu ra:

    0

    Đang tải editor...