solution

Khác với việc tự suy ra dãy hành động shift/reduce từ một văn phạm, bài này yêu cầu bạn đóng vai "máy thực thi": cho trước một văn phạm phi ngữ cảnh (các sản xuất được đánh số 1-based), một chuỗi token đầu vào, và một dãy hành động shift/reduce đã định sẵn — hãy mô phỏng chính xác ngăn xếp ký hiệu (symbol stack) khi thực hiện lần lượt các hành động đó.

• Hành động S (SHIFT): lấy token tiếp theo trong luồng vào và đẩy vào đỉnh ngăn xếp. Nếu không còn token nào để lấy, đây là lỗi.
• Hành động R i (REDUCE theo sản xuất thứ $i$, dạng $A \to \alpha$): xét $|\alpha|$ ký hiệu ở đỉnh ngăn xếp (nếu $\alpha$ rỗng thì không cần lấy gì); nếu $|\alpha|$ ký hiệu đó (theo đúng thứ tự, từ dưới lên trên) không khớp với $\alpha$, hoặc ngăn xếp không đủ $|\alpha|$ phần tử, đây là lỗi. Nếu khớp, lấy $|\alpha|$ ký hiệu đó ra khỏi ngăn xếp rồi đẩy $A$ (vế trái) vào.

Nếu một hành động gây lỗi, dừng ngay lập tức tại hành động đó (các hành động sau không thực hiện). Nếu toàn bộ dãy hành động thực hiện thành công, xét: nếu đã dùng hết toàn bộ token đầu vào và ngăn xếp cuối cùng chỉ còn đúng 1 ký hiệu, đúng bằng vế trái của sản xuất thứ 1 (quy ước là ký hiệu bắt đầu văn phạm) — kết quả là ACCEPT; ngược lại là REJECT (đây không phải là lỗi thực thi, chỉ là chưa phân tích trọn vẹn).

Ví dụ: văn phạm gồm 2 sản xuất S -> S + S và S -> id; token vào: id + id; dãy hành động: S, R 2, S, S, R 2, R 1 — ngăn xếp cuối cùng là S, đã dùng hết token → in ra ACCEPT rồi S.