Cho văn phạm gồm 5 luật sinh: (1) S->AB; (2) A->0A; (3) A->1; (4) B->1A; (5) B- >0. Phân tích xâu vào “1011” bằng thuật toán Bottom-up. Quá trình phân tích nào sau đây đạt trạng thái thành công?

Để tìm First(A), ta cần xem xét các luật sinh có A ở vế trái và tìm các terminal có thể bắt đầu từ A.

- Luật (2): A -> 0A, cho thấy 0 có thể là ký tự đầu tiên của A. Vì vậy, 0 ∈ First(A).

- Luật (3): A -> 1, cho thấy 1 có thể là ký tự đầu tiên của A. Vì vậy, 1 ∈ First(A).

Do đó, First(A) = {0, 1}.

Để tìm First(S), ta cần xem xét các luật sinh có S ở vế trái. Trong trường hợp này, ta có luật S -> AB.

1. Nếu A dẫn xuất ra một chuỗi bắt đầu bằng terminal '0', thì '0' sẽ thuộc First(S). Luật A -> 0A cho thấy A có thể dẫn xuất ra một chuỗi bắt đầu bằng '0'.
2. Nếu A dẫn xuất ra một chuỗi bắt đầu bằng terminal '1', thì '1' sẽ thuộc First(S). Luật A -> 1 cho thấy A có thể dẫn xuất ra '1'.
3. Nếu A dẫn xuất ra epsilon (chuỗi rỗng), ta cần xét đến B. Nếu B dẫn xuất ra một chuỗi bắt đầu bằng terminal '0', thì '0' sẽ thuộc First(S). Luật B -> 0 cho thấy B có thể dẫn xuất ra '0'.
4. Nếu A dẫn xuất ra epsilon, và B dẫn xuất ra một chuỗi bắt đầu bằng terminal '1', thì '1' sẽ thuộc First(S). Luật B -> 1A cho thấy B có thể dẫn xuất ra chuỗi bắt đầu bằng '1'.
5. Nếu A và B đều dẫn xuất ra epsilon, thì epsilon thuộc First(S).

Tuy nhiên, câu hỏi này chỉ yêu cầu First(S) mà không yêu cầu phải loại bỏ epsilon nếu có. Vậy, First(S) = {0, 1}.

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

• (1) S -> BA: FOLLOW(A) chứa FIRST(A) \ {ε}. Trong trường hợp này, FIRST(A) = {1, ε}, do đó FOLLOW(A) chứa {1}. Nếu ε thuộc FIRST(A) thì FOLLOW(A) chứa FOLLOW(S).
• (2) C -> A0: FOLLOW(A) chứa {0}.
• (4) B -> A1: FOLLOW(A) chứa {1}.

Kết hợp lại, FOLLOW(A) = {0, 1}.

Để tìm FOLLOW(S), ta cần xác định các ký tự có thể xuất hiện ngay sau S trong các chuỗi dẫn xuất từ văn phạm đã cho.

Tuy nhiên, S là ký hiệu bắt đầu, do đó theo định nghĩa, FOLLOW(S) luôn chứa ký hiệu kết thúc chuỗi (thường ký hiệu là $).

Vậy, FOLLOW(S) = {$} hay {dollar}.