JavaScript is required

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ì?

A.

Ngăn xếp: dollar A; Xâu vào: 011 dollar

B.

Ngăn xếp: dollar 1; Xâu vào: 011 dollar

C.

Ngăn xếp: dollar A; Xâu vào: 11 dollar

D.

Ngăn xếp: dollar A1; Xâu vào: 011 dollar

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$.

Câu hỏi liên quan