Cho văn phạm S → A hoặc S-> BCD; A → BBA hoặc A->EB; B → bEc hoặc B->BC hoặc B->BDc ; C → c ; D → a hoặc D-> BDb; E → a hoặc E->bE , First(D)=?

{ a,b,c }

{ b,c }

{ a,b}

{ a}

Trả lời:

Đáp án đúng: A

Để tìm First(D), ta cần xác định tập hợp các ký tự đầu cuối có thể xuất hiện đầu tiên khi suy dẫn từ D. Theo văn phạm đã cho, D → a hoặc D → BDb. Vì vậy:

Từ D → a, ta có 'a' thuộc First(D).
Từ D → BDb, ta cần tìm First(B). Theo văn phạm, B → bEc hoặc B → BC hoặc B → BDc. Do đó, 'b' thuộc First(B).
Vì 'b' thuộc First(B) và D → BDb, nên 'b' cũng có thể xuất hiện ở đầu khi suy dẫn từ D.
Tuy nhiên, cần lưu ý rằng C → c.
Vậy, First(D) = {a, b}.

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 4

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 44:

Cho văn phạm S → A hoặc S-> BCD; A → BBA hoặc A->EB; B → bEc hoặc B->BC hoặc B->BDc ; C → c ; D → a hoặc D-> BDb; E → a hoặc E->bE , Follow(A)=?

Lời giải:

Đáp án đúng: D

Để tìm Follow(A), ta cần xem xét các quy tắc sinh trong văn phạm mà A xuất hiện ở vế phải. Trong trường hợp này, A xuất hiện trong quy tắc S → A.

Vì A là ký tự đầu tiên trong quy tắc S → A và S là ký tự bắt đầu, $ (ký tự kết thúc) sẽ thuộc Follow(A).
Trong quy tắc A → BBA, B theo sau A. Do đó, First(B) cần được đưa vào Follow(A). First(B) = {b}. Vậy 'b' thuộc Follow(A). Tuy nhiên, vì có A -> EB, E có thể dẫn đến xâu rỗng, nên ta cần xem xét Follow(A) khi A đứng cuối. Trong quy tắc A -> BBA, A đứng cuối cùng, do đó Follow(S) cần được thêm vào Follow(A). Vì S là ký tự bắt đầu, Follow(S) = {$}
Trong quy tắc A -> EB, B theo sau E. Do đó, First(B) cần được đưa vào Follow(E). First(B) = {b}. Vậy 'b' thuộc Follow(E). Tuy nhiên, vì A -> EB, nên Follow(A) bao gồm Follow(B). First(B) = {b}. Vậy 'b' thuộc Follow(A).

Do đó, Follow(A) = {b, $}.

Vậy đáp án đúng là B. { b, dollar }

Câu 45:

Cho văn phạm S → A hoặc S-> BCD; A → BBA hoặc A->EB; B → bEc hoặc B->BC hoặc B->BDc ; C → c ; D → a hoặc D-> BDb; E → a hoặc E->bE , Follow(C)=?

Lời giải:

Đáp án đúng: A

To find Follow(C), we analyze where C appears on the right-hand side of productions. From S → BCD, Follow(C) includes First(D). First(D) = {a, b} because D → a or D → BDb. From B → BC, Follow(C) includes Follow(B). From B → BDc, Follow(B) contains 'c'. Also, since C → c, First(C) is {c}. Therefore, Follow(C) includes {a, b, c, $} where '$' represents the end of input.

Câu 46:

Cho văn phạm ang cường gồm các luật sinh E’->E; E-> E+T ; E-> T; T- >T*F; T-> F; F- > € ; F-> id. Nếu I là tập bao đóng của văn phạm và I = { E’->E.; E-> E .+T} Goto (I, +) =?

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 cú pháp (parsing table) cho một văn phạm bằng cách sử dụng kỹ thuật phân tích LR (hoặc cụ thể hơn là SLR, CLR, LALR). Cụ thể, nó kiểm tra kiến thức về hàm `GOTO` trong thuật toán xây dựng tập các mục LR(0) và cách tính bao đóng (closure) của một tập các mục LR(0).

Chúng ta có tập các mục `I = { E' -> E.; E -> E. + T }`. Hàm `GOTO(I, +)` có nghĩa là chúng ta xét tất cả các mục trong `I` mà dấu chấm nằm trước ký hiệu '+', sau đó dịch chuyển dấu chấm qua ký hiệu '+' và tính bao đóng của tập các mục mới này.

Trong `I`, chỉ có mục `E -> E. + T` thỏa mãn điều kiện trên. Khi dịch chuyển dấu chấm qua '+', ta được `E -> E + .T`.

Bây giờ, chúng ta cần tính bao đóng của `{E -> E + .T}`. Bao đóng bao gồm việc thêm tất cả các luật sinh có `T` ở vế trái (bên trái mũi tên) và dấu chấm ở đầu vế phải. Các luật sinh đó là `T -> .T * F`, `T -> .F`.

Tiếp theo, chúng ta cần tính bao đóng của các luật sinh mới thêm vào. Ta thấy `F` ở vế trái của `T -> .F`, vì vậy ta thêm các luật sinh có `F` ở vế trái và dấu chấm ở đầu vế phải: `F -> .€` và `F -> .id`.

Vậy, `GOTO(I, +)` sẽ là tập hợp các mục sau: `{ E -> E + .T; T -> .T * F; T -> .F; F -> .€; F -> .id }`.

So sánh với các đáp án, ta thấy đáp án C phù hợp nhất.

Câu 47:

Cho văn phạm ang cường gồm các luật sinh E’->E; E-> E+T ; E-> T; T- >T*F; T-> F; F- > € ; F-> id. Nếu I là tập mục của văn phạm và I = { E’->E.; E-> E .+T} Goto (I, +) =?

Lời giải:

Đáp án đúng: C

Câu hỏi này kiểm tra kiến thức về việc xây dựng tập các mục (items) trong phân tích cú pháp LR (Left-to-right Rightmost derivation). Cụ thể, nó yêu cầu xác định kết quả của hàm `Goto(I, +)` khi `I` là một tập mục và `+` là một ký hiệu đầu vào.

* Phân tích: Hàm `Goto(I, X)` tính tập các mục mới bằng cách dịch chuyển dấu chấm (`.`) qua ký hiệu `X` trong tất cả các mục của tập `I` mà có `X` đứng sau dấu chấm. Sau đó, nó thực hiện phép bao đóng (closure) trên tập các mục mới này để thêm vào tất cả các mục có thể được suy dẫn từ các biến chưa được xử lý (các biến đứng sau dấu chấm).

Trong trường hợp này, `I = { E' -> E.; E -> E. + T }` và `X = +`. Khi ta thực hiện `Goto(I, +)`, ta chỉ quan tâm đến các mục trong `I` mà có `+` đứng sau dấu chấm, đó là `E -> E. + T`. Dịch chuyển dấu chấm qua `+`, ta được `E -> E + .T`.

Tiếp theo, ta cần thực hiện phép bao đóng trên `T`. Điều này có nghĩa là ta cần thêm vào tất cả các luật sinh có `T` ở vế trái: `T -> .T * F` và `T -> .F`. Cuối cùng, ta cần thực hiện phép bao đóng trên `F`, thêm vào `F -> .€` và `F -> .id`

Kết hợp lại, `Goto(I, +) = { E -> E + .T; T -> .T * F; T -> .F; F -> .€; F -> .id }`

* Đánh giá các phương án:

* A: Sai. Tập mục này không phải là kết quả của `Goto(I, +)`.
* B: Sai. Tập mục này không phải là kết quả của `Goto(I, +)`.
* C: Đúng. Tập mục này chính xác là kết quả của `Goto(I, +)` như đã phân tích ở trên.
* D: Sai. Tập mục này không phải là kết quả của `Goto(I, +)`.

Vậy đáp án đúng là C.

Câu 48:

Cho văn phạm tăng cường gồm các luật sinh E’->E; E-> E+T ; E-> T; T- >T*F; T-> F; F-> (E) ; F-> id. Tập mục I0 là tập mục thứ nhất của văn phạm, Goto (I0, id) =?

Lời giải:

Đáp án đúng: A

Để tìm Goto(I0, id), ta cần thực hiện các bước sau:

1. Xác định I0: I0 là closure của mục E' -> .E. Trong trường hợp này, I0 bao gồm các mục sau:

- E' -> .E

- E -> .E + T

- E -> .T

- T -> .T * F

- T -> .F

- F -> .(E)

- F -> .id

2. Tính Goto(I0, id): Goto(I0, id) là closure của tập các mục mà từ I0, ta "đi" được bằng cách đọc 'id'. Trong I0, mục duy nhất có thể "đi" bằng 'id' là F -> .id. Sau khi "đi" qua 'id', ta được F -> id.

3. Tính closure của F -> id.: Closure(F -> id.) chỉ bao gồm chính mục đó, vì không có ký hiệu không kết thúc nào sau dấu chấm.

Vậy, Goto(I0, id) = {F -> id.}.

Câu 49:

Cho văn phạm với các luật sinh sau: E->TE; E’->+T E’; E’->epsilon; T->FT'; T'- >*FT’; T’->epsilon; F->(E); F->id; FOLLOW (F)=?

Lời giải: