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. Phân tích xâu vào “1011” bằng thuật toán Bottom- up. Hành động của bộ phân tích lần lượt là: gạt (shift), thu gọn (reduce) theo (4), gạt, thu gọn theo (2), gạt, thu gọn theo (4) thì trạng thái phân tích tại thời điểm này là gì?

Để tìm FIRST(A), ta cần xác định tập hợp các terminal có thể xuất hiện đầu tiên khi dẫn xuất từ A.

• Từ luật (4): A -> 1, suy ra 1 ∈ FIRST(A).
• Từ luật (2): A -> A0, luật này không giúp tìm FIRST(A) trực tiếp vì A xuất hiện ở đầu vế phải.
• Từ luật (3): A -> B0, ta cần xét FIRST(B).
• Từ luật (6): B -> 0, suy ra 0 ∈ FIRST(B). Do đó, 0 ∈ FIRST(B) kéo theo 0 ∈ FIRST(A) (vì A -> B0).

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

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