Phát biểu nào sau đây đúng nhất đối với chuỗi đầu vào cho bộ phân tích cú pháp. Chuỗi đầu vào bao gồm

Để tìm First(S), ta cần xem xét các luật sinh của S. Trong trường hợp này, S -> AB. Do đó, First(S) sẽ chứa tất cả các phần tử có thể bắt đầu từ A và B.

• A -> aA | epsilon, vậy First(A) = {a, epsilon}
• B -> bB | epsilon, vậy First(B) = {b, epsilon}

Vì S -> AB, nên First(S) sẽ chứa First(A). Nếu epsilon thuộc First(A), thì First(S) cũng sẽ chứa First(B). Trong trường hợp này, epsilon thuộc First(A), vì vậy First(S) sẽ chứa {a} (từ First(A)) và {b} (từ First(B)). Do đó, First(S) = {a, b}.

Để tìm FIRST(B), ta cần xem xét các luật sinh có B ở vế trái: B → bBʼ hoặc B → epsilon.

• Từ B → bBʼ, ta thấy rằng 'b' là một phần tử của FIRST(B).
• Từ B → epsilon, ta thấy rằng epsilon (ký hiệu chuỗi rỗng) cũng là một phần tử của FIRST(B).

Vậy, FIRST(B) = {b, epsilon}.

Để tìm FIRST(C), ta xem xét các luật sinh có C ở vế trái. Trong văn phạm này, ta có luật C → c hoặc C-> D. Do đó, FIRST(C) sẽ chứa 'c'.
Tiếp theo ta xét luật D -> a hoặc D -> d, tức là FIRST(D) = {a, d}. Tuy nhiên, vì C -> D chứ không phải C -> epsilon D, nên FIRST(D) không đóng góp epsilon vào FIRST(C). Vì vậy, FIRST(C) chỉ chứa 'c'. Trong các đáp án đã cho, không có đáp án nào chính xác. Đáp án gần đúng nhất là C, nếu bỏ epsilon đi thì đáp án C đúng

Tuy nhiên, do không có đáp án đúng nên ta sẽ chọn đáp án gần đúng nhất.

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