solution

Cho văn phạm phi ngữ cảnh, dựng bộ tự động LR(0) chính tắc (như mô tả ở bài "Số trạng thái của bộ tự động LR(0) chính tắc": tăng cường $S' \to S$, đánh số trạng thái bằng BFS, duyệt ký hiệu theo thứ tự từ điển) và tính tập $FOLLOW$ cho từng non-terminal theo thuật toán chuẩn (coi ký hiệu kết thúc chuỗi là $, $FOLLOW(S)$ chứa $).

Với mỗi trạng thái $I_i$ của bộ tự động, gọi $I_i$ có XUNG ĐỘT nếu:

1. reduce/reduce: tồn tại 2 mục hoàn chỉnh (con trỏ ở cuối) KHÁC NHAU $A \to \alpha.$ và $B \to \beta.$ trong $I_i$ (có thể $A=B$ nếu khác vế phải) sao cho $FOLLOW(A) \cap FOLLOW(B) \ne \emptyset$; hoặc
2. shift/reduce: tồn tại mục hoàn chỉnh $A \to \alpha.$ trong $I_i$ và một terminal $a \in FOLLOW(A)$ sao cho $GOTO(I_i, a)$ khác rỗng (tức $I_i$ có mục dạng $\cdot \to \ldots . a \ldots$).

(Mục hoàn chỉnh có $LHS = S'$ ứng với hành động ACCEPT, không tính là reduce, bỏ qua khi xét xung đột.)

Văn phạm là SLR(1) khi và chỉ khi KHÔNG trạng thái nào có xung đột.

Ví dụ: văn phạm S -> L = R, S -> R, L -> * R, L -> id, R -> L KHÔNG phải SLR(1) — trạng thái chứa mục R -> L . có xung đột shift/reduce trên ký hiệu =.