JavaScript is required

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

A.

{ a, b, c, d, epsilon }

B.

{ a, epsilon }

C.

{ a, b, epsilon }

D.

{ a, b, c, epsilon }

Trả lời:

Đáp án đúng: A


Để tìm FIRST(S), ta cần xem xét các luật sinh bắt đầu từ S. Trong trường hợp này, S → A, vì vậy FIRST(S) = FIRST(A). Bây giờ ta xét A → BC hoặc A → DBC.

\n

- Nếu A → BC, thì FIRST(A) = FIRST(BC). Vì B → bB’ hoặc B → ε, nên FIRST(B) = {b, ε}. Vì C → c hoặc C → ε, nên FIRST(C) = {c, ε}. Vì vậy, FIRST(BC) = {b} ∪ (nếu ε ∈ FIRST(B) thì FIRST(C) nếu không thì {ε}) = {b} ∪ {c, ε} = {b, c, ε}.

\n

- Nếu A → DBC, thì FIRST(A) = FIRST(DBC). Vì D → a hoặc D → d, nên FIRST(D) = {a, d}. Vì vậy, FIRST(DBC) = {a, d}.

\n

Vậy, FIRST(A) = FIRST(BC) ∪ FIRST(DBC) = {b, c, ε} ∪ {a, d} = {a, b, c, d, ε}.

Tuy nhiên, khi xem lại các đáp án thì không có đáp án nào chính xác hoàn toàn với phân tích trên. Đáp án gần đúng nhất là đáp án D, tuy nhiên nó thiếu 'd'.

Do không có đáp án chính xác, ta cần xem xét lại ngữ cảnh và có thể có một số giả định hoặc đơn giản hóa mà câu hỏi mong muốn.

Nếu câu hỏi chỉ xét đến việc tìm các terminal có thể xuất hiện đầu tiên từ S, bỏ qua trường hợp D -> d thì FIRST(S) = {a, b, c, epsilon}

Câu hỏi liên quan