solution

Ta xây dựng một máy Shift-Reduce đơn giản để kiểm tra tính hợp lệ của một chuỗi dấu ngoặc gồm ba loại: tròn (), vuông [], nhọn {}, ứng với văn phạm

$S \to (S) \mid [S] \mid \{S\} \mid SS \mid \varepsilon$

Máy xử lý chuỗi $s$ từ trái sang phải bằng một ngăn xếp (stack), khởi đầu rỗng:

• Nếu ký tự hiện tại là dấu mở ((, [, {): thực hiện SHIFT — đẩy ký tự đó vào đỉnh stack.
• Nếu ký tự hiện tại là dấu đóng (), ], }):
  • Nếu đỉnh stack đang có đúng dấu mở tương ứng cùng loại → thực hiện REDUCE: lấy (pop) dấu mở đó ra khỏi stack (tượng trưng cho việc thu gọn một cặp ngoặc thành ký hiệu $S$), tăng biến đếm số lần reduce lên 1.
  • Ngược lại (stack rỗng hoặc đỉnh không khớp loại) → dừng ngay và báo lỗi tại vị trí ký tự đó (đánh số từ 1).
• Nếu xử lý hết chuỗi mà stack vẫn còn phần tử (còn dấu mở chưa được đóng) → báo lỗi tại vị trí $|s|+1$.

Cho chuỗi $s$ (có thể rỗng, chỉ gồm các ký tự trong tập (){}[]), hãy mô phỏng máy trên và xác định:

• Chuỗi có hợp lệ (không có lỗi) hay không.
• Nếu hợp lệ: tổng số lần reduce đã thực hiện, và độ sâu ngăn xếp lớn nhất (giá trị lớn nhất của kích thước stack) đạt được trong toàn bộ quá trình.
• Nếu không hợp lệ: vị trí (1-indexed) xảy ra lỗi đầu tiên.

Ví dụ: với $s =$ ([{}]), máy shift 3 lần ((, [, {), sau đó reduce 3 lần khi gặp }, ], ). Kết quả: hợp lệ, số reduce = 3, độ sâu lớn nhất = 3.