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] Xung đột trong bảng ACTION

    Trong bảng ACTION của một bộ phân tích LR, mỗi ô ứng với một cặp (trạng thái, ký hiệu kết thúc) có thể chứa nhiều hơn một hành động — đây chính là các xung đột khiến văn phạm không thuộc lớp LR đang xét. Có hai loại xung đột:

    • Xung đột dịch chuyển/rút gọn (shift-reduce, SR): ô chứa ít nhất một hành động dịch chuyển (sK) và ít nhất một hành động rút gọn (rK).
    • Xung đột rút gọn/rút gọn (reduce-reduce, RR): ô chứa từ hai hành động rút gọn khác nhau trở lên (rK1, rK2, ... với K1≠K2K_1 \ne K_2K1​=K2​).

    Một ô có thể vừa là SR vừa là RR (ví dụ: 1 shift + 2 reduce khác nhau). Cho danh sách các ô của bảng ACTION cùng toàn bộ hành động được liệt kê trong từng ô, hãy đếm số ô có xung đột SR, số ô có xung đột RR, và liệt kê chi tiết.

    Ví dụ: ô (trạng thái 2, ký hiệu +) chứa {s6, r3} → xung đột SR. Ô (trạng thái 2, ký hiệu *) chứa {r2, r4} → xung đột RR.

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

      Dòng đầu là CCC (0≤C≤3000 \le C \le 3000≤C≤300) — số ô được liệt kê. Với mỗi ô: một dòng state symbol k (state là tên trạng thái dạng chuỗi/số, symbol là ký hiệu kết thúc, k≥1k \ge 1k≥1 là số hành động trong ô), tiếp theo kkk dòng, mỗi dòng một hành động dạng sK (shift), rK (reduce), hoặc acc. Nếu C=0C = 0C=0 thì không còn dòng nào tiếp theo.

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

      In ra dòng 1: số ô có xung đột SR. Dòng 2: số ô có xung đột RR. Sau đó, với mỗi ô có ít nhất một xung đột (sắp xếp theo state rồi theo symbol, so sánh chuỗi tăng dần), in một dòng state symbol LOAI với LOAI là SR, RR, hoặc SR+RR nếu ô có cả hai loại xung đột. Nếu không có ô nào xung đột, chỉ in 2 dòng số ở trên.

    Ví dụ:

    Đầu vào:

    3
0 a 1
s1
1 b 1
r2
2 c 1
acc

    Đầu ra:

    0
0

    Đầu vào:

    4
0 id 1
s5
2 + 2
s6
r3
2 * 2
r2
r4
7 $ 1
acc

    Đầu ra:

    1
1
2 * RR
2 + SR

    Đang tải editor...