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

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

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

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

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

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 1

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 37:

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. First(A)=?

Lời giải:

Đáp án đúng: C

Để tìm First(A), ta cần xem xét các luật sinh có A ở vế trái và tìm các terminal có thể bắt đầu từ A.

- Luật (2): A -> 0A, cho thấy 0 có thể là ký tự đầu tiên của A. Vì vậy, 0 ∈ First(A).

- Luật (3): A -> 1, cho thấy 1 có thể là ký tự đầu tiên của A. Vì vậy, 1 ∈ First(A).

Do đó, First(A) = {0, 1}.

Câu 38:

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

Lời giải:

Đáp án đúng: D

Để tìm First(S), ta cần xem xét các luật sinh có S ở vế trái. Trong trường hợp này, ta có luật S -> AB.

Nếu A dẫn xuất ra một chuỗi bắt đầu bằng terminal '0', thì '0' sẽ thuộc First(S). Luật A -> 0A cho thấy A có thể dẫn xuất ra một chuỗi bắt đầu bằng '0'.
Nếu A dẫn xuất ra một chuỗi bắt đầu bằng terminal '1', thì '1' sẽ thuộc First(S). Luật A -> 1 cho thấy A có thể dẫn xuất ra '1'.
Nếu A dẫn xuất ra epsilon (chuỗi rỗng), ta cần xét đến B. Nếu B dẫn xuất ra một chuỗi bắt đầu bằng terminal '0', thì '0' sẽ thuộc First(S). Luật B -> 0 cho thấy B có thể dẫn xuất ra '0'.
Nếu A dẫn xuất ra epsilon, và B dẫn xuất ra một chuỗi bắt đầu bằng terminal '1', thì '1' sẽ thuộc First(S). Luật B -> 1A cho thấy B có thể dẫn xuất ra chuỗi bắt đầu bằng '1'.
Nếu A và B đều dẫn xuất ra epsilon, thì epsilon thuộc First(S).

Tuy nhiên, câu hỏi này chỉ yêu cầu First(S) mà không yêu cầu phải loại bỏ epsilon nếu có. Vậy, First(S) = {0, 1}.

Câu 39:

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. FOLLOW(A)=?

Lời giải:

Đáp án đúng: C

Để tìm FOLLOW(A), ta xét các luật sinh có A ở vế phải:

(1) S -> BA: FOLLOW(A) chứa FIRST(A) \ {ε}. Trong trường hợp này, FIRST(A) = {1, ε}, do đó FOLLOW(A) chứa {1}. Nếu ε thuộc FIRST(A) thì FOLLOW(A) chứa FOLLOW(S).
(2) C -> A0: FOLLOW(A) chứa {0}.
(4) B -> A1: FOLLOW(A) chứa {1}.

Kết hợp lại, FOLLOW(A) = {0, 1}.

Câu 40:

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. FOLLOW(S)=?

Lời giải:

Đáp án đúng: D

Để tìm FOLLOW(S), ta cần xác định các ký tự có thể xuất hiện ngay sau S trong các chuỗi dẫn xuất từ văn phạm đã cho.

Tuy nhiên, S là ký hiệu bắt đầu, do đó theo định nghĩa, FOLLOW(S) luôn chứa ký hiệu kết thúc chuỗi (thường ký hiệu là $).

Vậy, FOLLOW(S) = {$} hay {dollar}.

Câu 41:

Trường hợp nào sau đây, đúng với dạng luật sinh của văn bản

Lời giải:

Đáp án đúng: B

Câu hỏi này kiểm tra kiến thức về dạng luật sinh trong ngữ pháp hình thức, thường được sử dụng trong lý thuyết ngôn ngữ và trình biên dịch. Luật sinh mô tả cách các ký hiệu phi kết thúc (non-terminal) được thay thế bằng các chuỗi ký hiệu khác, có thể bao gồm cả ký hiệu kết thúc (terminal) và ký hiệu phi kết thúc.

* Phương án A: A=BC - Dạng này thường thấy, nhưng ký hiệu `=` không phổ biến trong ký pháp luật sinh chuẩn.
* Phương án B: X->Y*Z - Đây là dạng luật sinh phổ biến và đúng. Ký hiệu `->` biểu thị sự thay thế (X được thay thế bằng Y*Z). Dấu `*` ở đây có thể hiểu là một toán tử hoặc một phần của chuỗi ký hiệu.
* Phương án C: A=B+C - Tương tự A, sử dụng `=` không phải là ký pháp chuẩn.
* Phương án D: A=B-C - Tương tự A và C, sử dụng `=` không phải là ký pháp chuẩn.

Vì vậy, phương án B là phù hợp nhất với dạng luật sinh thường thấy trong lý thuyết ngôn ngữ hình thức.

Câu 42:

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

Lời giải: