solution

Cho một văn phạm phi ngữ cảnh (CFG) với ký hiệu bắt đầu $S$, được đảm bảo là LL(1).

Quy ước biểu diễn văn phạm phi ngữ cảnh (CFG) dùng chung cho đề này:

• Mỗi ký hiệu chưa kết thúc (non-terminal) là một chữ cái in hoa (A-Z).
• Mọi token khác (chữ thường, số, hoặc ký hiệu như (, ), +, *, id, num, ...) là ký hiệu kết thúc (terminal); terminal có thể dài nhiều ký tự nhưng không chứa khoảng trắng.
• Token đặc biệt e ở vế phải nghĩa là luật sinh sinh ra chuỗi rỗng $\varepsilon$ (ví dụ A -> e).
• Ký hiệu kết thúc đầu vào (end-of-input) được ký hiệu là $ khi cần dùng tới FOLLOW.
• Đảm bảo mọi ký hiệu chưa kết thúc xuất hiện ở vế phải của bất kỳ luật sinh nào cũng đều có ít nhất một luật sinh định nghĩa nó (văn phạm "đóng", không có non-terminal mồ côi).

Bộ phân tích cú pháp LL(1) chuẩn dùng một ngăn xếp và bảng dự đoán $M[A,a]$ để quyết định luật sinh áp dụng. Trong bài này, thay vì luôn bắt đầu từ $S$, ta muốn kiểm tra khả năng dẫn xuất bắt đầu từ một ký hiệu chưa kết thúc bất kỳ $X$ của văn phạm (không nhất thiết là $S$): khởi tạo ngăn xếp gồm $ và $X$ (với $X$ ở đỉnh), sau đó chạy thuật toán phân tích dự đoán như thường lệ trên chuỗi terminal $w$ cho trước để xác định $X \Rightarrow^{*} w$ hay không.

Cho $q$ truy vấn, mỗi truy vấn gồm một ký hiệu chưa kết thúc $X$ và một chuỗi terminal $w$ (có thể rỗng). Với mỗi truy vấn, hãy xác định $X$ có dẫn xuất được chính xác chuỗi $w$ hay không bằng thuật toán phân tích LL(1) dựa trên bảng.

Ví dụ

Với văn phạm biểu thức số học kinh điển, truy vấn xuất phát từ $Y$ với chuỗi rỗng cho kết quả OK (vì $Y \Rightarrow \varepsilon$), còn truy vấn xuất phát từ $X$ với chuỗi chỉ gồm + cho kết quả LOI (vì sau dấu + bắt buộc phải có thêm $T$ và $X$, không thể dừng lại ngay).