solution

Một bộ phân tích LR (shift-reduce) hoạt động dựa trên một ngăn xếp chứa xen kẽ trạng thái và ký hiệu, cùng hai bảng: ACTION$[i, a]$ (với $i$ là trạng thái, $a$ là ký hiệu kết thúc kể cả $) cho biết hành động shift (đẩy vào ngăn xếp và chuyển sang trạng thái mới), reduce theo một luật sinh (rút gọn), accept (chấp nhận), hoặc rỗng (báo lỗi); và GOTO$[i, A]$ (với $A$ là non-terminal) cho biết trạng thái cần chuyển tới sau khi rút gọn về $A$.

Thuật toán mô phỏng: ngăn xếp khởi tạo chỉ chứa trạng thái $0$; con trỏ đọc token ở vị trí $0$. Lặp lại: gọi $i$ là trạng thái trên đỉnh ngăn xếp, $a$ là token hiện tại.

• Nếu ACTION$[i,a] =$ sJ (shift tới trạng thái $J$): đẩy $a$ rồi đẩy $J$ vào ngăn xếp, dịch con trỏ sang token kế tiếp.
• Nếu ACTION$[i,a] =$ rP (reduce theo luật sinh số $P$: $A \to X_1 \ldots X_k$): rút $2k$ phần tử khỏi đỉnh ngăn xếp ($k$ cặp ký hiệu-trạng thái, nếu $k=0$ thì không rút gì), gọi $t$ là trạng thái trên đỉnh ngăn xếp sau khi rút, đẩy $A$ rồi đẩy GOTO$[t, A]$ vào ngăn xếp; ghi nhận số hiệu luật sinh $P$ vào danh sách các bước reduce đã thực hiện (con trỏ đọc không dịch chuyển).
• Nếu ACTION$[i,a] =$ acc: dừng và kết luận chấp nhận.
• Nếu ô ACTION$[i,a]$ rỗng (không xác định), hoặc bước reduce mà GOTO$[t,A]$ rỗng: dừng và kết luận từ chối tại vị trí token hiện tại (0-indexed, tính trong danh sách token của xâu vào, kể cả $).

Cho trước bảng ACTION/GOTO đầy đủ của một văn phạm (đã mở rộng, luật sinh số 0 là luật mở rộng $S' \to S$) cùng một xâu token vào (luôn kết thúc bằng token $), hãy mô phỏng và đưa ra kết quả.

Ví dụ: với bảng SLR(1) chuẩn của văn phạm biểu thức số học E -> E + T | T, T -> T * F | F, F -> ( E ) | id, xâu vào id + id * id $ được chấp nhận qua dãy rút gọn theo số hiệu luật sinh: 6 4 2 6 4 6 3 1 (tương ứng F->id, T->F, E->T, rồi F->id, T->F, rồi F->id, T->T*F, E->E+T).