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

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

Trong văn phạm đã cho, ta có luật: A → DBC.

Theo định nghĩa của FOLLOW, FOLLOW(D) là tập hợp các terminal có thể xuất hiện ngay sau D trong một số dẫn xuất.

Trong luật A → DBC, ký hiệu theo sau D là C. Do đó, FIRST(C) sẽ thuộc FOLLOW(D).

Vì C → c, nên c thuộc FOLLOW(D).

Ngoài ra, nếu C có thể dẫn xuất ra ε (epsilon), thì FOLLOW(A) sẽ thuộc FOLLOW(D).

Trong trường hợp này, C không thể dẫn xuất ra ε.

Tuy nhiên, ta cần xem xét các trường hợp khác mà D có thể ở cuối chuỗi dẫn xuất.

Trong luật A → DBC, nếu C -> epsilon, thì FOLLOW(D) sẽ chứa FOLLOW(A).

Vì S -> A nên FOLLOW(A) sẽ chứa FOLLOW(S) = {$}, trong đó $ là ký hiệu kết thúc chuỗi.

Nhưng do C -> c, C không thể dẫn xuất ra epsilon. Do đó, FOLLOW(D) chỉ chứa FIRST(C).

FIRST(C) = {c}.

Nhưng D-> a hoặc D-> d nên cần xem xét thêm các luật khác.

Vì D → a hoặc D → d, thì FIRST(D) = {a, d}.

Theo luật A → DBC, FIRST(C) sẽ nằm trong FOLLOW(D), vậy {c} ∈ FOLLOW(D).

Nếu C có thể dẫn tới ε, thì FOLLOW(A) sẽ nằm trong FOLLOW(D).

Mà S → A, nên FOLLOW(A) chứa dấu $ (kết thúc chuỗi).

Nhưng C → c, nên C không thể dẫn tới ε.

Vậy FOLLOW(D) = {c, $}. Nhưng vì D -> a hoặc D -> d nên {a, d} cũng phải nằm trong tập FOLLOW(D).

Vậy FOLLOW(D) = {a, d, $}.

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

B → bB’ hoặc B-> Epsilon

B’→ bB’ hoặc B’- > Epsilon

Từ B’→ bB’ hoặc B’- > Epsilon, suy ra nếu B' là cuối cùng, thì FOLLOW(B') sẽ chứa FOLLOW(B). B sẽ xuất hiện trong A → BC hoặc A-> DBC. Do đó FOLLOW(B) sẽ chứa FIRST(C) nếu C không thể dẫn đến epsilon, hoặc chứa FIRST(C) và FOLLOW(A) nếu C có thể dẫn đến epsilon. FIRST(C) = {c, epsilon}. Do đó, c thuộc FOLLOW(B).

Tiếp theo, xét A → BC hoặc A-> DBC. FOLLOW(A) = {$} (vì A là ký hiệu bắt đầu). Vì C có thể dẫn đến epsilon (C -> epsilon), FOLLOW(B) phải chứa FOLLOW(A) = {$}. Do đó, $ thuộc FOLLOW(B). Vậy FOLLOW(B) = {c, $}

Vì B' có thể là cuối cùng trong B -> bB', suy ra FOLLOW(B') = FOLLOW(B). Vì vậy FOLLOW(B') = {c, $}.

Để tìm FOLLOW(A), ta cần xem xét các luật sinh có A ở vế trái và vế phải. Trong văn phạm đã cho, ta có các luật sinh:

• S → A
• A → BC
• A → DBC

Từ luật sinh S → A, vì A là ký hiệu cuối cùng trong luật sinh này, nên mọi ký hiệu trong FOLLOW(S) cũng thuộc FOLLOW(A). Vì S là ký hiệu bắt đầu, FOLLOW(S) chứa $. Do đó, $ ∈ FOLLOW(A).

Từ luật sinh A → BC, FIRST(C) (nếu C không suy dẫn ra ε) hoặc FOLLOW(A) (nếu C suy dẫn ra ε) sẽ thuộc FOLLOW(A). Vì C → c hoặc C → ε, FIRST(C) = {c}. Tuy nhiên, vì C có thể là ε, FOLLOW(A) sẽ chứa FOLLOW(A), không mang lại thông tin mới.

Từ luật sinh A → DBC, FIRST(C) (nếu C không suy dẫn ra ε) hoặc FOLLOW(A) (nếu C suy dẫn ra ε) sẽ thuộc FOLLOW(A). Tương tự như trên, vì C có thể là ε, FOLLOW(A) sẽ chứa FOLLOW(A), không mang lại thông tin mới.

Vậy, FOLLOW(A) = { $ }.

Trong lý thuyết ngôn ngữ hình thức, First(X) là tập hợp các ký tự đầu cuối có thể xuất hiện đầu tiên trong một chuỗi được dẫn xuất từ X.

Trong trường hợp này, C -> c, nên First(C) = {c}.