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

Để 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}.

Để 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}.

Để 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ế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ế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}.

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}

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

A → BC

A → DBC

FIRST(A) sẽ bao gồm FIRST(BC) và FIRST(DBC).

FIRST(BC) = FIRST(B). Vì B → bB' | epsilon, nên FIRST(B) = {b, epsilon}.

FIRST(DBC) = FIRST(D). Vì D → a | d, nên FIRST(D) = {a, d}.

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

Tuy nhiên, do C → c | epsilon nên nếu B và D đều dẫn đến epsilon thì C sẽ được xét. Vì có B → epsilon và C → c | epsilon nên c có thể thuộc FIRST(A). Nhưng vì không có trường hợp B và D cùng dẫn đến epsilon trong các luật sinh, ta cần xem xét các trường hợp cụ thể hơn.

Nếu A → BC, và B → epsilon, thì FIRST(C) được thêm vào FIRST(A). Vì C → c | epsilon, FIRST(C) = {c, epsilon}. Vậy {c} có thể thuộc FIRST(A).

Nếu A → DBC, và D → a | d, thì FIRST(D) = {a, d}.

Như vậy, FIRST(A) = {a, b, c, d, epsilon}.