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), gạt, thu gọn theo (4), gạt, thu gọn theo (5) thì trạng thái phân tích tại thời điểm này là gì?

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

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

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

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

Trả lời:

Đáp án đúng: D

Phân tích xâu "1011" theo thuật toán Bottom-up với các bước đã cho: 1. **Gạt:** Đọc '1' vào ngăn xếp. Ngăn xếp: `$` `1`, Xâu vào: `011$` 2. **Thu gọn theo (4): A -> 1:** Thay '1' trên ngăn xếp bằng 'A'. Ngăn xếp: `$` `A`, Xâu vào: `011$` 3. **Gạt:** Đọc '0' vào ngăn xếp. Ngăn xếp: `$` `A` `0`, Xâu vào: `11$` 4. **Thu gọn theo (2): A -> A0:** Thay 'A0' trên ngăn xếp bằng 'A'. Ngăn xếp: `$` `A`, Xâu vào: `11$` 5. **Gạt:** Đọc '1' vào ngăn xếp. Ngăn xếp: `$` `A` `1`, Xâu vào: `1$` 6. **Thu gọn theo (4): A -> 1:** Thay '1' trên ngăn xếp bằng 'A'. Ngăn xếp: `$` `A` `A`, Xâu vào: `1$` 7. **Gạt:** Đọc '1' vào ngăn xếp. Ngăn xếp: `$` `A` `A` `1`, Xâu vào: `$` 8. **Thu gọn theo (5): B -> A1:** Thay 'A1' trên ngăn xếp bằng 'B'. Ngăn xếp: `$` `A` `B`, Xâu vào: `$`. Trạng thái: $AB

200+ câu hỏi trắc nghiệm Chương trình dịch có lời giải theo từng bước - Phần 2

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 34:

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), gạt, thu gọn theo (4), gạt, thu gọn theo (5), thu gọn (1) thì trạng thái phân tích tại thời điểm này là gì?

Lời giải:

Đáp án đúng: A

Phân tích xâu "1011" theo thuật toán Bottom-up:
1. Gạt: Đọc '1' vào ngăn xếp. Ngăn xếp: `$1`, Xâu còn lại: `011$`
2. Thu gọn theo (4) A -> 1: Thay '1' bằng 'A'. Ngăn xếp: `$A`, Xâu còn lại: `011$`
3. Gạt: Đọc '0' vào ngăn xếp. Ngăn xếp: `$A0`, Xâu còn lại: `11$`
4. Thu gọn theo (2) A -> A0: Thay 'A0' bằng 'A'. Ngăn xếp: `$A`, Xâu còn lại: `11$`
5. Gạt: Đọc '1' vào ngăn xếp. Ngăn xếp: `$A1`, Xâu còn lại: `1$`
6. Gạt: Đọc '1' vào ngăn xếp. Ngăn xếp: `$A11`, Xâu còn lại: `$`
7. Thu gọn (4) A -> 1: Ngăn xếp: `$A1A`, Xâu còn lại: `$`
8. Thu gọn (5) B -> A1: Ngăn xếp: `$BA`, Xâu còn lại: `$`
9. Thu gọn (1) S -> AB: Khong the thu gon do B truoc A

Câu 35:

Cho văn phạm gồm 7 luật sinh: (1) S->BA; (2) C->A0; (3) A->1; (4) B->A1; (5) B- >0; (6) A-> epsilon; (7) B-> epsilon. FIRST (C)=?

Lời giải:

Đáp án đúng: D

Để tìm FIRST(C), ta cần xem xét các luật sinh có C ở vế trái, ở đây là luật C -> A0. Theo định nghĩa, FIRST(C) sẽ bao gồm FIRST(A0). Để tìm FIRST(A0), ta xét FIRST(A). Từ các luật sinh A -> 1 và A -> epsilon, ta có FIRST(A) = {1, epsilon}. Vì epsilon thuộc FIRST(A), ta cần xét đến phần tử tiếp theo sau A trong luật sinh C -> A0, đó là 0. Do đó, FIRST(A0) = {1} ∪ {0} = {0, 1}. Vậy FIRST(C) = {0, 1}.

Câu 36:

Trong phương pháp “Phân tích dự đoán không đệ qui” thì ký hiệu ‘dollar’ là

Lời giải:

Đáp án đúng: C

Trong phương pháp phân tích dự đoán không đệ quy (hay còn gọi là phân tích LL(1)), ký hiệu ‘dollar’ ($) được sử dụng để đánh dấu sự kết thúc của chuỗi nhập. Nó báo hiệu cho trình phân tích biết rằng không còn token nào để xử lý nữa.

Câu 37:

Trong phương pháp “Phân tích dự đoán không đệ qui”, khẳng định nào sau đây đúng nhất đối với INPUT (đầu vào)

Lời giải:

Đáp án đúng: A

Trong phương pháp phân tích dự đoán không đệ quy (non-recursive predictive parsing), đầu vào (INPUT) là bộ đệm (buffer) chứa chuỗi ký tự cần được phân tích cú pháp. Chuỗi này đại diện cho chương trình nguồn hoặc biểu thức cần được kiểm tra xem có tuân theo ngữ pháp đã định hay không. Thông thường, chuỗi đầu vào này được kết thúc bằng ký hiệu '$' (dollar sign) để đánh dấu sự kết thúc của chuỗi, giúp cho việc phân tích cú pháp được thực hiện một cách chính xác và tránh các lỗi không mong muốn. Vì vậy, phương án A là chính xác nhất.

Các phương án khác không đúng vì:
- Phương án B chỉ chứa các ký hiệu kết thúc của văn phạm, không phải là chuỗi đầu vào cần phân tích.
- Phương án C chứa cả ký hiệu kết thúc và không kết thúc, nhưng không phải là bộ đệm đầu vào mà là tập hợp các ký hiệu trong văn phạm.
- Phương án D là các luật sinh của văn phạm, không phải là đầu vào cần phân tích.

Câu 38:

Cho văn phạm với các luật sinh: S -> AB; A -> aA ; A -> epsilon; B -> bB ; B-> epsilon, Follow (B) = ?

Lời giải:

Đáp án đúng: D

Để tìm Follow(B), ta cần xem xét các luật sinh có B ở vế phải:

S -> AB

Theo định nghĩa, Follow(B) chứa tất cả các terminal có thể theo sau B trong một chuỗi dẫn xuất từ văn phạm. Trong trường hợp này, B xuất hiện ở cuối luật sinh S -> AB. Do đó, Follow(B) sẽ chứa tất cả các terminal thuộc Follow(S). Vì S là ký hiệu bắt đầu, Follow(S) chứa '$' (ký hiệu kết thúc chuỗi). Mặt khác, B có thể không xuất hiện ở cuối chuỗi dẫn xuất (ví dụ: S -> A), nên Follow(B) chỉ chứa các terminal theo sau B trong các luật sinh khác, hoặc Follow(S) nếu B ở cuối. Trong luật S -> AB, nếu A có thể dẫn xuất ra chuỗi rỗng (epsilon), thì Follow(B) sẽ chứa Follow(S). Vì A -> aA | epsilon, A có thể dẫn xuất ra epsilon. Do đó Follow(B) chứa Follow(S) = {$}

Tuy nhiên, ta cũng cần xét xem có luật sinh nào khác mà B xuất hiện ở vế phải không. Ở đây không có, nên Follow(B) = {$}

Câu 39:

Cho văn phạm gồm các luật sinh: epsilon; epsilon; S → A; A → BC hoặc A-> DBC; B → bBʼ hoặc B-> epsilon; B’→ bB’ hoặc B’- > C → c hoặc C-> D → a hoặc D-> d, FIRST(D) =?

Lời giải: