Cho văn phạm gồm 6 luật sinh: (1) S->AB; (2) A->A0; (3) A->B0; (4) A->1; (5) B- >A1; (6) B->0. Phân tích xâu vào “1011” bằng thuật toán Bottom- up. Hành động của bộ phân tích lần lượt là: gạt, thu gọn theo (4), gạt, thu gọn theo (2) thì trạng thái phân tích tại thời điểm này là gì?
Trả lời:
Đáp án đúng: C
Phân tích xâu "1011" bằng thuật toán Bottom-up:
1. **Gạt:** Đọc ký tự đầu tiên '1' vào ngăn xếp. Ngăn xếp: $1, Xâu vào: 011$
2. **Thu gọn theo (4):** Thay '1' bằng 'A' theo luật A -> 1. Ngăn xếp: $A, Xâu vào: 011$
3. **Gạt:** Đọc ký tự tiếp theo '0' vào ngăn xếp. Ngăn xếp: $A0, Xâu vào: 11$
4. **Thu gọn theo (2) KHÔNG THỂ, phải là (3):** A->A0 (sai), A -> B0 (đúng). Ngăn xếp: $B, Xâu vào: 11$
Như vậy trạng thái phân tích sau các bước trên là: Ngăn xếp $A; Xâu vào: 011$.