solution

Với một văn phạm phi ngữ cảnh (quy ước ký hiệu như bài toán xây dựng tập trạng thái LR(0): ký hiệu chưa kết thúc là chữ in hoa A-Z; đảm bảo mọi ký hiệu chưa kết thúc dùng ở vế phải đều có luật sinh riêng), hãy:

1. Tính tập FIRST và tập FOLLOW của các ký hiệu chưa kết thúc theo thuật toán chuẩn (FOLLOW của ký hiệu bắt đầu luôn chứa $).
2. Xây dựng tập chính tắc các trạng thái LR(0) (theo đúng thuật toán và cách đánh số ở bài toán xây dựng tự động LR(0): BFS theo thứ tự tạo ra, ký hiệu goto duyệt theo thứ tự từ điển tăng dần, văn phạm mở rộng bằng $S' \to S$).
3. Với mỗi trạng thái, xây dựng các hành động ACTION theo quy tắc SLR(1):
   • Mục $A \to \alpha.a\beta$ ($a$ là ký hiệu kết thúc) → hành động shift trên $a$.
   • Mục $A \to \alpha.$ (dấu chấm cuối, $A \ne S'$) → hành động reduce theo luật sinh này, trên mọi ký hiệu $b \in \text{FOLLOW}(A)$.
   • Mục $S' \to S.$ → hành động accept trên $.
4. Với mỗi ô (trạng thái, ký hiệu kết thúc): nếu có shift và ít nhất một reduce/accept cùng lúc → xung đột SR; nếu có từ hai hành động reduce/accept trở lên → xung đột RR. Đếm tổng số ô xung đột SR và tổng số ô xung đột RR trên toàn bảng.

Văn phạm là SLR(1) khi và chỉ khi không có xung đột nào (cả SR lẫn RR đều bằng 0).

Ví dụ (văn phạm KHÔNG phải SLR(1)): $S \to L{=}R \mid R,\; L \to {*}R \mid \text{id},\; R \to L$ có 10 trạng thái LR(0), và có đúng 1 xung đột shift-reduce (tại trạng thái chứa đồng thời mục $S \to L.{=}R$ và $R \to L.$, khi ký hiệu vào là =), 0 xung đột reduce-reduce → không phải SLR(1).