solution

Với ôtômat LR(0) chính tắc của văn phạm mở rộng $G'$ (xây dựng như mô tả ở bài toán dựng tập mục LR(0): closure, goto, họ tập mục chính tắc bắt đầu từ $I_0 = \mathrm{closure}(\{[S' \to \cdot S]\})$), phương pháp SLR(1) xây dựng bảng phân tích bằng cách, tại mỗi trạng thái $I$:

• Với mỗi mục $[A \to \alpha \cdot a \beta] \in I$ ($a$ là terminal): thêm hành động shift trên $a$.
• Với mỗi mục hoàn chỉnh $[A \to \alpha \cdot] \in I$ (với $A \ne S'$): với mọi $a \in \mathrm{FOLLOW}(A)$, thêm hành động reduce theo luật $A \to \alpha$ trên $a$.

Nếu tại một ô $(I, a)$ nào đó tồn tại nhiều hơn một hành động được đề xuất, văn phạm có xung đột và không phải SLR(1). Có hai loại xung đột: shift-reduce (vừa có shift vừa có reduce trên cùng $a$) và reduce-reduce (có từ hai luật sinh khác nhau trở lên cùng muốn reduce trên $a$).

Quy ước ký hiệu văn phạm (áp dụng cho toàn bộ đề bài này): mỗi luật sinh được cho ở dạng A -> X1 X2 ... Xk (các ký hiệu cách nhau bởi dấu cách); nếu vế phải là rỗng thì ghi A -> eps. Một ký hiệu được coi là ký hiệu chưa kết thúc (non-terminal) nếu và chỉ nếu ký tự đầu tiên của nó là một chữ cái in hoa (A-Z); mọi ký hiệu còn lại (chữ thường, chữ số, dấu (, ), +, id, ... ) đều là ký hiệu kết thúc (terminal). Ký hiệu đặc biệt eps chỉ dùng để biểu diễn xâu rỗng $\varepsilon$ và không phải là một terminal thật sự. Ký hiệu $ là ký hiệu kết thúc xâu vào (end-marker).

Cho văn phạm phi ngữ cảnh $G$ với ký hiệu bắt đầu $S$, hãy xác định văn phạm (mở rộng) có phải SLR(1) hay không. Nếu có xung đột, đếm: số trạng thái có ít nhất một xung đột, tổng số xung đột shift-reduce (mỗi cặp $(I,a)$ tính 1), và tổng số xung đột reduce-reduce (mỗi cặp $(I,a)$ có từ 2 luật sinh muốn reduce trở lên cũng chỉ tính 1, bất kể có bao nhiêu luật).