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

Để tìm FIRST(B), ta xem xét các luật sinh có B ở vế trái:

• (5) B -> A1
• (6) B -> 0

Từ luật (6), ta thấy ngay 0 thuộc FIRST(B). Từ luật (5), ta cần tìm FIRST(A).

Các luật sinh có A ở vế trái là:

• (2) A -> A0
• (3) A -> B0
• (4) A -> 1

Từ luật (4), ta có 1 thuộc FIRST(A). Từ luật (3), ta cần tìm FIRST(B). Vì B -> 0, nên 0 thuộc FIRST(B), do đó 0 thuộc FIRST(A). Vì A -> 1, nên 1 thuộc FIRST(A).

Vậy FIRST(A) = {0, 1}.

Do B -> A1 và FIRST(A) = {0, 1}, nên B có thể bắt đầu bằng 0 hoặc 1, sau đó là 1.

Ngoài ra, B -> 0, nên 0 thuộc FIRST(B).

Vậy FIRST(B) = {0, 1}.

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.