Cho văn phạm gồm 3 luật sinh: (1) S->aSbS; (2) S->aS; (3) S->c. Phân tích xâu vào “aacbc” bằng thuật toán Top-down. Từ gốc của cây, áp dụng suy dẫn (1) để triển khai, sau đó áp dụng suy dẫn (1) để triển khai bước sau thì cây suy dẫn tại thời điểm này có bao nhiêu nút?

A. 6

B. 7

C. 8

D. 9

Trả lời:

Đáp án đúng: D

Phân tích xâu "aacbc" bằng thuật toán Top-down, bắt đầu từ luật sinh S. Bước 1: Áp dụng luật sinh (1) S -> aSbS. Cây suy dẫn hiện tại có dạng: S /|\ a S b S Số nút hiện tại: 4 Bước 2: Tiếp tục áp dụng luật sinh (1) S -> aSbS vào nút S thứ nhất (từ trái sang). Cây suy dẫn trở thành: S /|\ a S b S /|\ a S b S Số nút hiện tại: 4 + 3 = 7 (Thêm 3 nút mới: a, S, b, S) Vậy, sau khi áp dụng suy dẫn (1) hai lần liên tiếp, cây suy dẫn có 7 nút.

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 3

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 các luật sinh: S –> T * P; T –> U ; T->T * U; P –> Q + P ; P->Q; Q –> id; U –> id Phát biểu nào bên dưới đúng?

Lời giải:

Đáp án đúng: B

Phân tích văn phạm: * `P -> Q + P | Q` cho thấy `+` là kết hợp phải vì `P` đệ quy ở bên phải của phép toán `+`. Điều này có nghĩa là biểu thức `a + b + c` sẽ được hiểu là `a + (b + c)`. * `T -> T * U | U` cho thấy `*` là kết hợp trái vì `T` đệ quy ở bên trái của phép toán `*`. Điều này có nghĩa là biểu thức `a * b * c` sẽ được hiểu là `(a * b) * c`. Vậy, đáp án đúng là: Toán tử + là kết hợp phải, trong khi * là kết hợp trái.

Câu 35:

Một ngôn ngữ được sinh ra bởi một văn phạm gọi là:

Lời giải:

Đáp án đúng: B

Văn phạm (Grammar) là một tập hợp các quy tắc được sử dụng để sinh ra một ngôn ngữ. Ngôn ngữ được sinh ra bởi một văn phạm được gọi là ngôn ngữ phi ngữ cảnh (Context-Free Language). Các ngôn ngữ lập trình, ngôn ngữ máy, và ngôn ngữ hợp ngữ đều có thể được mô tả bằng văn phạm, nhưng không phải văn phạm nào cũng sinh ra chúng. Ngôn ngữ phi ngữ cảnh là khái niệm bao quát nhất trong các lựa chọn này.

Câu 36:

Cho văn phạm với các luật sinh: S->AS, S->b, A->SA, A->a. Kí hiệu I0 là tập mục đầu tiên của văn phạm, phép toán Goto(I0,S) =?

Lời giải:

Đáp án đúng: C

Câu hỏi này liên quan đến việc xây dựng bảng phân tích LR(0) cho một văn phạm. Cụ thể, nó yêu cầu tính Goto(I0, S), tức là trạng thái mới của tập mục khi đọc ký hiệu S từ trạng thái I0. Để giải quyết, ta cần xác định I0 (tập mục khởi đầu) trước. I0 chứa luật sinh gốc (S' -> .S) và closure của nó. Closure bao gồm tất cả các luật sinh có vế phải bắt đầu bằng một non-terminal có mặt sau dấu chấm trong một luật sinh khác. Trong trường hợp này, I0 sẽ chứa S' -> .S, S -> .AS, S -> .b, A -> .SA và A -> .a. Goto(I0, S) là tập hợp các luật sinh có dạng X -> S.Y, với X -> .SY thuộc I0, sau đó tính closure của tập hợp này. Từ I0, ta thấy các luật sinh S' -> .S và A -> .SA có S sau dấu chấm. - Khi đọc S từ S' -> .S, ta được S' -> S. - Khi đọc S từ A -> .SA, ta được A -> S.A. Vậy, tập hợp ban đầu là {S' -> S., A -> S.A}. Ta cần tính closure của tập hợp này. Closure của A -> S.A bao gồm việc thêm tất cả các luật sinh có A ở vế trái, với dấu chấm ở đầu vế phải: A -> .SA và A -> .a. Do đó, Goto(I0, S) = {S' -> S., A -> S.A, A -> .SA, A -> .a}. Đáp án C: {S' -> S., A -> S.A, A -> .a} là gần đúng nhất, nhưng thiếu A -> .SA Đáp án B: {A -> S.A, S -> .b} là sai. Đáp án A: {S' -> S, A -> .a} là sai. Đáp án D: {S -> .b , A -> .a} là sai. Vì không có đáp án nào hoàn toàn chính xác, ta chọn đáp án gần đúng nhất là C, nhưng cần lưu ý rằng nó thiếu A -> .SA.

Câu 37:

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

Lời giải:

Đáp án đúng: A

Để tìm First(A), ta xem xét các luật sinh của A:

A -> aA: Vì luật sinh này bắt đầu bằng 'a', nên 'a' thuộc First(A).
A -> epsilon: Vì A có thể sinh ra epsilon, nên epsilon thuộc First(A).

Vậy, First(A) = {a, epsilon}.

Câu 38:

Cho văn phạm gồm 5 luật sinh: (1) S->AB; (2) A->0A; (3) A->1; (4) B- >1A; (5) B- >0. Phân tích xâu vào “0111” bằng thuật toán topdown. Chọn lần lượt các sản xuất (1) (2) (3) (4) (3) để phân tích thì phải quay lui bao nhiêu lần mới đạt trạng thái thành công?

Lời giải:

Đáp án đúng: A

Phân tích xâu "0111" bằng thuật toán top-down, bắt đầu với luật sinh S -> AB. 1. **S -> AB** (1) 2. **A -> 0A** (2) => 0AB 3. **A -> 1** (3) => 01B 4. **B -> 1A** (4) => 011A 5. **A -> 1** (3) => 0111 Như vậy, với các lựa chọn sản xuất (1), (2), (3), (4), (3), ta đạt được xâu mong muốn "0111" mà không cần quay lui lần nào. Vậy số lần quay lui là 0. Do đó, đáp án đúng là A. 0.

Câu 39:

Cho văn phạm gồm 5 luật sinh: (1) S->AB; (2) A->0A; (3) A->1; (4) B->1A; (5) B- >0. Phân tích xâu vào “1011” bằng thuật toán Topdown. Quá trình phân tích nào sau đây đạt trạng thái thành công?

Lời giải: