solution

Bộ phân tích LALR(1) được xây dựng bằng cách gộp các trạng thái của tự động hóa LR(1) chính tắc có cùng lõi (core — tập mục bỏ qua ký hiệu nhìn trước), rồi hợp (union) các tập ký hiệu nhìn trước tương ứng với từng mục. Việc gộp này giúp giảm đáng kể số trạng thái so với LR(1) chính tắc, nhưng có thể sinh ra xung đột reduce-reduce mới — xung đột không tồn tại ở bất kỳ trạng thái LR(1) gốc nào trước khi gộp, mà chỉ xuất hiện sau khi hợp các tập nhìn trước lại với nhau. Đây là điểm yếu kinh điển của LALR(1) so với LR(1).

Đề bài cho sẵn (không cần xây dựng từ văn phạm) một số trạng thái LR(1), mỗi trạng thái gồm một số mục rút gọn (reduce item), mỗi mục xác định bởi số hiệu luật sinh và tập ký hiệu nhìn trước hợp lệ để rút gọn theo luật đó tại trạng thái này. Mỗi trạng thái có kèm một mã lõi (core) — hai trạng thái có cùng mã lõi sẽ được gộp lại thành một trạng thái LALR(1).

Tại một trạng thái (LR(1) gốc hoặc LALR(1) sau gộp), có xung đột reduce-reduce nếu tồn tại một ký hiệu nhìn trước được "đòi" rút gọn bởi từ hai luật sinh khác nhau.

Hãy xác định: (1) tổng số trạng thái LALR(1) sau khi gộp (số mã lõi phân biệt); (2) trong số đó, có bao nhiêu trạng thái LALR(1) có xung đột reduce-reduce; (3) trong số các trạng thái có xung đột đó, có bao nhiêu trạng thái mà xung đột này là mới hoàn toàn — tức là không một trạng thái LR(1) gốc nào (thuộc nhóm được gộp vào đó) tự nó đã có xung đột reduce-reduce từ trước.

Ví dụ kinh điển: hai trạng thái LR(1) cùng lõi, trạng thái thứ nhất có mục rút gọn theo luật 10 với nhìn trước {d} và luật 11 với nhìn trước {e} (không xung đột); trạng thái thứ hai có luật 10 với nhìn trước {e} và luật 11 với nhìn trước {d} (cũng không xung đột). Sau khi gộp, luật 10 và luật 11 đều có nhìn trước {d, e} $\Rightarrow$ xung đột reduce-reduce mới phát sinh. Kết quả: 1 trạng thái LALR(1), 1 trạng thái có xung đột, 1 xung đột mới.