solution

Cho một văn phạm phi ngữ cảnh (CFG) với các luật sinh được đánh số $1, 2, \ldots, k$, một chuỗi token đầu vào, và một dãy hành động được đề xuất gồm các bước SHIFT hoặc REDUCE i. Hãy mô phỏng một máy Shift-Reduce dùng ngăn xếp (stack) để kiểm chứng xem dãy hành động này có được thực hiện hợp lệ hay không.

Máy có một ngăn xếp ban đầu rỗng và một con trỏ đọc, ban đầu trỏ vào token đầu tiên của chuỗi input. Các hành động được thực hiện tuần tự:

• SHIFT: lấy token tiếp theo mà con trỏ đang trỏ tới, đẩy nó vào đỉnh stack, di chuyển con trỏ sang phải 1 vị trí. Nếu không còn token nào để lấy (đã đọc hết input) → hành động này không hợp lệ.
• REDUCE i: luật sinh $i$ có dạng $A \to X_1 X_2 \ldots X_m$ (nếu luật rỗng, $m = 0$, ứng với $A \to \varepsilon$). Xét $m$ ký hiệu trên cùng của stack (theo đúng thứ tự từ dưới lên trên phải bằng $X_1, X_2, \ldots, X_m$). Nếu stack có ít hơn $m$ phần tử, hoặc không khớp thứ tự $X_1 \ldots X_m$ → hành động này không hợp lệ. Nếu khớp, lấy (pop) $m$ ký hiệu đó ra và đẩy $A$ vào đỉnh stack (nếu $m=0$ thì không pop gì cả, chỉ đẩy $A$).

Nếu tại bước thứ $j$ (1-indexed) gặp một hành động không hợp lệ, dừng ngay lập tức và báo lỗi tại bước đó — các bước sau không được xét tới.

Nếu toàn bộ dãy hành động đều hợp lệ, kiểm tra thêm: input đã được đọc hết (con trỏ đã vượt qua token cuối) và trên stack chỉ còn đúng 1 ký hiệu, đúng bằng ký hiệu bắt đầu $S_0$ của văn phạm hay không — nếu đúng thì dãy hành động này đã phân tích chấp nhận (ACCEPT) chuỗi input, ngược lại chỉ là một dãy hành động hợp lệ nhưng chưa hoàn tất phân tích (REJECT).

Ví dụ: văn phạm $S \to (S) \mid \varepsilon$ (luật 1, luật 2), input ( ), dãy hành động SHIFT, REDUCE 2, SHIFT, REDUCE 1 mô phỏng: stack lần lượt là [(], [(, S], [(, S, )], rồi reduce luật 1 khớp ( S ) cho ra [S]. Toàn bộ input đã đọc hết, stack chỉ còn S = S_0$ → kết quả ACCEPT.