Cho văn phạm với các luật sinh: S->aAb; S->c; A->hSg. FIRST(A) =?

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

• A -> 0A: Vì bắt đầu bằng terminal 0, nên 0 thuộc First(A)
• A -> 1: Vì bắt đầu bằng terminal 1, nên 1 thuộc First(A)
• A -> epsilon: Vì A có thể dẫn đến epsilon, nên epsilon thuộc First(A)

Vậy First(A) = {0, 1, epsilon}

Để tìm FOLLOW(B), ta cần xem xét các luật sinh có B ở vế phải. FOLLOW(B) là tập hợp các terminal có thể xuất hiện ngay sau B trong quá trình dẫn xuất.

1. Từ luật S -> BA, FOLLOW(B) chứa FIRST(A). FIRST(A) = {1, epsilon}. Tuy nhiên, nếu FIRST(A) chứa epsilon, thì FOLLOW(B) cũng chứa FOLLOW(S). Vì S là ký hiệu bắt đầu, nên $ thuộc FOLLOW(S).

2. Xem xét luật khác không có B ở vế phải.

3. Vì A -> epsilon, nên từ S -> BA, ta có FOLLOW(B) chứa FOLLOW(S). Giả sử S không xuất hiện ở vế phải của bất kỳ luật nào, ta không cần phải xem xét thêm.

4. Do A->1 và A->epsilon, nên FIRST(A) = {1}. Vì A có thể dẫn xuất ra epsilon, FOLLOW(B) sẽ chứa FOLLOW(S). Vì S là ký hiệu bắt đầu, FOLLOW(S) chứa $.

5. Vì B có thể là cuối chuỗi (S -> BA, A -> epsilon), nên FOLLOW(B) có thể chứa $ (end marker).

Tuy nhiên, vì không có dấu $ trong các lựa chọn, ta cần xem xét kỹ hơn. Từ S -> BA, nếu A -> 1 thì B đứng trước 1, nếu A -> epsilon thì B đứng cuối chuỗi, nhưng không có terminal nào theo sau. Nhưng nếu A -> epsilon, ta có thể coi như B là cuối của S.

Từ S -> BA, FIRST(A) = {1, epsilon}. Nếu epsilon thuộc FIRST(A), thì FOLLOW(B) sẽ chứa FOLLOW(S). Vì S là ký hiệu bắt đầu, FOLLOW(S) chứa $, nhưng $ không có trong các đáp án. Trong trường hợp này, khi A -> 1, thì 1 thuộc FIRST(A). Khi A -> epsilon, thì không có gì theo sau B.

Tuy nhiên, ta cần xem xét kỹ các luật sinh. S -> BA, A -> 1 hoặc A -> epsilon. Vậy FOLLOW(B) chứa FIRST(A) ngoại trừ epsilon. Do đó, FOLLOW(B) chứa {1}. Nếu A -> epsilon, thì FOLLOW(B) chứa FOLLOW(S), tức là không có gì cả. Vì không có đáp án nào là {1}, ta cần xem xét lại.

Nếu ta có thêm một luật sinh nữa có dạng X -> BY, thì FOLLOW(B) sẽ chứa FIRST(Y). Nhưng ở đây không có.

Nếu A -> 0, thì ta sẽ có 0 thuộc FIRST(A), vậy 0 thuộc FOLLOW(B). Nhưng A -> 1 hoặc epsilon, không phải A -> 0.

Như vậy, chúng ta có A -> 1 hoặc A -> epsilon. Nên FOLLOW(B) chỉ chứa 1 khi A -> 1.

Xét luật B -> A1. Ta thấy 1 luôn theo sau A. Vậy A thuộc FIRST(B). Khi đó, A -> 1 và A -> epsilon, suy ra 1 thuộc FIRST(A). Do đó, FIRST(A) = {1}.

Vậy FOLLOW(B) chứa FIRST(A) = {1}.

Đáp án chính xác nhất là B. {1}

Trong quá trình phân tích cú pháp, chuỗi đầu vào thường là một chuỗi các ký hiệu kết thúc (terminal symbols) được tạo ra từ văn phạm. Chuỗi này thường kết thúc bằng một ký hiệu đặc biệt, thường là ký hiệu '$' (dollar), để đánh dấu sự kết thúc của chuỗi đầu vào. Điều này giúp bộ phân tích cú pháp biết khi nào nó đã xử lý hết chuỗi đầu vào.

1. Phương án A đúng vì nó mô tả chính xác thành phần của chuỗi đầu vào: các ký hiệu kết thúc và ký hiệu kết thúc chuỗi '$'.
2. Phương án B sai vì nó bao gồm cả ký hiệu không kết thúc, trong khi chuỗi đầu vào chỉ chứa ký hiệu kết thúc.
3. Phương án C sai vì nó chỉ đề cập đến ký hiệu không kết thúc, trong khi chuỗi đầu vào chứa ký hiệu kết thúc.
4. Phương án D sai vì các luật sinh là một phần của văn phạm, không phải là chuỗi đầu vào.