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)=?

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:

Đáp án đúng: B

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

T -> FT'
T' -> *FT'
F -> (E)
F -> id

Từ luật 1: T -> FT', FOLLOW(F) chứa FIRST(T'). FIRST(T') = {*, epsilon}. Vậy FOLLOW(F) chứa {*}. Nếu T' -> epsilon, thì FOLLOW(F) chứa FOLLOW(T').

Từ luật T'- >*FT’, FOLLOW(F) chứa FIRST(T'). FIRST(T') = {*, epsilon}. Vậy FOLLOW(F) chứa {*}. Nếu T' -> epsilon, thì FOLLOW(F) chứa FOLLOW(T').

Xét FOLLOW(T'):

Từ luật E -> TE', FOLLOW(T) chứa FIRST(E'). FIRST(E') = {+, epsilon}. Vậy FOLLOW(T) chứa {+}. Nếu E' -> epsilon, thì FOLLOW(T) chứa FOLLOW(E').

Từ luật E' -> +TE', FOLLOW(E') chứa FOLLOW(E). FOLLOW(E) = {)}. Vậy FOLLOW(E') chứa {)}.

Vậy FOLLOW(T) chứa {+, )}.

Từ T -> FT', FOLLOW(T') chứa FOLLOW(T). Vậy FOLLOW(T') chứa {+, )}. Do đó FOLLOW(F) cũng chứa {+, )}.

Kết hợp lại, FOLLOW(F) = {*, +, )}. Thêm ký tự kết thúc chuỗi (dollar) thì không đúng vì F không nằm ở cuối chuỗi bắt đầu (start symbol).

Vậy đáp án đúng là {*, +, )}.

Câu 50:

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 (E’)=?

Lời giải: