solution

Cho một trạng thái (tập mục — item set) của tự động LR(0)/SLR(1) trong quá trình phân tích cú pháp, hãy xác định xem trạng thái đó có gây xung đột khi xây dựng bảng phân tích SLR(1) hay không.

Quy ước ký hiệu: một ký hiệu bắt đầu bằng chữ in hoa (có thể có dấu ' theo sau, ví dụ S') là ký hiệu chưa kết thúc (non-terminal); mọi ký hiệu khác (chữ thường, chữ số, hoặc các ký hiệu như +, *, (, ), id, $) là ký hiệu kết thúc (terminal). Ký hiệu $ là ký hiệu kết thúc xâu vào.

Mỗi mục (item) trong trạng thái có dạng A -> α . β với dấu chấm . thể hiện vị trí đã đọc tới. Với mỗi mục:

• Nếu dấu chấm nằm ngay trước một terminal $a$ (mục dạng A -> α . a γ), trạng thái này cho phép SHIFT trên $a$.
• Nếu dấu chấm ở cuối (mục hoàn chỉnh, dạng A -> α .), và $A \ne$ S', trạng thái này cho phép REDUCE theo sản xuất $A \to \alpha$ đối với mọi terminal $a \in \text{FOLLOW}(A)$ (quy tắc SLR(1)). Riêng mục hoàn chỉnh với $A =$ S' (ví dụ S' -> E .) chỉ tương ứng hành động ACCEPT trên $, không tính là REDUCE khi xét xung đột.

Với mỗi terminal $a$, nếu có từ 2 hành động khả dụng trở lên (được suy ra như trên) thì đó là xung đột tại $a$:

• đúng 1 SHIFT và đúng 1 REDUCE → shift-reduce;
• từ 2 REDUCE trở lên, không có SHIFT → reduce-reduce;
• 1 SHIFT và từ 2 REDUCE trở lên → shift-reduce-reduce.

Ví dụ: trạng thái gồm 2 mục A -> a . và B -> a . b, với \text{FOLLOW}(A) = \{b, \}$. Tại$b$: vừa có SHIFT (từ mục thứ hai) vừa có REDUCE$A \to a$(vì$b \in \text{FOLLOW}(A)$) → xung đột `shift-reduce` tại `b`. Tại `$`: chỉ có REDUCE → không xung đột.