solution

Cho một văn phạm phi ngữ cảnh với $k$ luật sinh và ký hiệu bắt đầu $S$ (định dạng như các bài trên). Hãy tự động xây dựng bảng phân tích SLR(1) rồi dùng bảng đó để mô phỏng phân tích cú pháp (shift-reduce) một chuỗi token cho trước.

Các bước xây dựng (tương tự lý thuyết SLR chuẩn, thực hiện tự động, không cho sẵn trong input):

1. Mở rộng văn phạm với luật $0$: $S' \to S$.
2. Ký hiệu là non-terminal nếu nó xuất hiện ở vế trái của một luật sinh (kể cả $S'$); ngược lại là terminal.
3. Tính tập $\text{FIRST}$ và $\text{FOLLOW}$ theo thuật toán chuẩn (\text{FOLLOW}(S') = \{\}$).
4. Xây dựng tập mục chính tắc LR(0) (như bài trước) và từ đó suy ra bảng $\text{ACTION}$/$\text{GOTO}$ theo quy tắc SLR:
   • Mục $[A \to \alpha \,.\, a\beta]$ với $a$ là terminal: $\text{ACTION}[I,a] =$ shift đến $\text{GOTO}(I,a)$.
   • Mục $[A \to \alpha \,.]$ với $A \ne S'$: với mọi $b \in \text{FOLLOW}(A)$, $\text{ACTION}[I,b] =$ reduce theo luật đó.
   • Mục $[S' \to S\,.]$: \text{ACTION}[I, \] = $ accept.
   • Nếu một ô của bảng nhận từ 2 giá trị khác nhau trở lên → văn phạm không phải SLR(1).

Mô phỏng phân tích: dùng ngăn xếp trạng thái, bắt đầu $[0]$, đọc chuỗi input nối thêm $ ở cuối, áp dụng ACTION/GOTO theo đúng thuật toán LR chuẩn (shift, reduce dùng GOTO trên đỉnh stack sau khi pop, accept khi gặp hành động accept). Nếu tại một bước không có hành động nào trong bảng ứng với (trạng thái hiện tại, ký hiệu input hiện tại) → chuỗi bị từ chối (REJECT).

Yêu cầu: nếu văn phạm không phải SLR(1) thì báo ngay; nếu là SLR(1), mô phỏng phân tích chuỗi input đã cho và cho biết kết quả.