Cho văn phạm gồm 6 luật sinh: (1) S->AB; (2) A->A0; (3) A->B0; (4) A->1; (5) B- >A1; (6) B->0. FIRST(B)=?

Trong lý thuyết phân tích cú pháp, khi xây dựng các bảng phân tích (parsing tables) cho các văn phạm, đặc biệt là trong các phương pháp phân tích từ trên xuống (top-down parsing) như LL(1), tập FOLLOW(S) đóng vai trò quan trọng. FOLLOW(S) là tập hợp các terminal có thể xuất hiện ngay sau ký hiệu không kết thúc (non-terminal) S trong một số dẫn xuất của văn phạm.

Đối với ký hiệu bắt đầu S của văn phạm, theo quy ước, tập FOLLOW(S) luôn luôn chứa ký hiệu '$' (dollar), biểu thị cho ký hiệu kết thúc chuỗi nhập (end-of-input marker). Điều này có nghĩa là sau khi S dẫn xuất ra một chuỗi các ký hiệu, ký hiệu '$' sẽ đánh dấu sự kết thúc của chuỗi đó.

Vì vậy, đáp án đúng là: A. dollar

Để tìm Follow(A), ta thực hiện theo các bước sau:

• Nếu A là kí hiệu bắt đầu, thì $ ∈ Follow(A). Trong trường hợp này, A không phải là kí hiệu bắt đầu.
• Nếu có luật sinh B -> αAβ, thì mọi phần tử của First(β) (ngoại trừ ε) nằm trong Follow(A). Ở đây ta có luật S -> AB, nên First(B) nằm trong Follow(A). First(B) = {b}, do đó b ∈ Follow(A).
• Nếu có luật sinh B -> αA hoặc B -> αAβ, trong đó First(β) chứa ε, thì mọi phần tử của Follow(B) nằm trong Follow(A). Ở đây ta có S -> AB và B -> ε, nên Follow(S) nằm trong Follow(A). Vì S là ký hiệu bắt đầu, Follow(S) = {$} do đó $ ∈ Follow(A).

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

Để tìm FOLLOW(S), ta xét các luật sinh có S ở vế trái hoặc vế phải.

- Ta có luật sinh S → A, nên FOLLOW(S) sẽ chứa tất cả các phần tử của FOLLOW(A).

- Bây giờ ta cần tìm FOLLOW(A). Xét các luật sinh có A ở vế phải: S → A; A → BC; A → DBC.

+ Từ S → A, ta suy ra FOLLOW(A) chứa FOLLOW(S). Vì S là ký hiệu bắt đầu, nên $ thuộc FOLLOW(S).

+ Từ A → BC, ta suy ra FIRST(C) - {ε} thuộc FOLLOW(B). Vì C → c hoặc C → ε, nên FIRST(C) = {c, ε}. Do đó, c thuộc FOLLOW(B).

+ Từ A → DBC, ta suy ra FIRST(C) - {ε} thuộc FOLLOW(B). Vì C → c hoặc C → ε, nên FIRST(C) = {c, ε}. Do đó, c thuộc FOLLOW(B).

+ Từ A → BC, ta suy ra nếu C → ε thì FOLLOW(A) chứa FOLLOW(BC) = FOLLOW(A) chứa FOLLOW(C) (nếu C dẫn xuất ra ε). FOLLOW(A) chứa FIRST(C) - {ε} = {c}. Ngoài ra, nếu C dẫn xuất ra ε, thì FOLLOW(A) chứa FOLLOW(A) chứa FOLLOW(S)={$} .

+ Từ A → DBC, ta suy ra FOLLOW(A) chứa FIRST(C) - {ε} = {c}. Ngoài ra, nếu C dẫn xuất ra ε, thì FOLLOW(A) chứa FOLLOW(BC) = FOLLOW(A) chứa FOLLOW(S)={$} .

Vậy FOLLOW(A) chứa {$}. Do đó, FOLLOW(S) chứa {$}.

Đáp án đúng là D.

Để tìm First(S), ta cần xem xét các sản xuất của S:

S → A

S → BCD

Với S → A, ta cần tìm First(A). Các sản xuất của A là:

A → BBA

A → EB

Với A → BBA, ta cần tìm First(B). Các sản xuất của B là:

B → bEc

B → BC

B → BDc

First(B) = {b}.

Với A → EB, ta cần tìm First(E). Các sản xuất của E là:

E → a

E → bE

First(E) = {a, b}.

Vậy First(A) = First(B) ∪ First(E) = {b} ∪ {a, b} = {a, b}.

Do đó, nếu S → A thì First(S) chứa {a, b}.

Với S → BCD, ta cần tìm First(B). Như đã thấy, First(B) = {b}.

Vậy First(S) chứa {b}.

Tuy nhiên, chúng ta cần xem xét kỹ hơn sản xuất B → BC. Điều này có nghĩa là B có thể dẫn đến chuỗi rỗng (nếu C dẫn đến rỗng), do đó ta cần xem xét First(C) nếu B có thể dẫn đến rỗng.

First(C) = {c}.

Vậy nếu S → BCD, First(S) có thể chứa {b, c}.

Kết hợp lại, First(S) = First(A) ∪ First(BCD) = {a, b} ∪ {b, c} = {a, b, c}.