solution

Trong quá trình xây dựng bảng phân tích LR (đặc biệt là bước tính tập lookahead cho các mục LR(1) khi đóng tập item), người ta thường xuyên cần tính $FIRST(\alpha)$ của một chuỗi ký hiệu văn phạm $\alpha = X_1 X_2 \ldots X_k$, dựa trên các tập $FIRST$ của từng ký hiệu đã được tính sẵn (giả thiết đã đúng, không cần tính lại từ đầu bằng thuật toán điểm bất động).

Quy tắc chuẩn:

• $FIRST(\varepsilon) = \{\varepsilon\}$ (chuỗi rỗng, $k = 0$).
• $FIRST(X_1 X_2 \ldots X_k)$: duyệt lần lượt $X_1, X_2, \ldots$; với mỗi $X_i$, thêm $FIRST(X_i) \setminus \{\varepsilon\}$ vào kết quả; nếu $\varepsilon \notin FIRST(X_i)$ thì dừng lại ngay (không xét các ký hiệu sau); nếu duyệt hết toàn bộ $k$ ký hiệu mà ký hiệu nào cũng có $\varepsilon$ trong tập FIRST của nó (tức toàn bộ chuỗi có thể dẫn xuất ra rỗng) thì thêm $\varepsilon$ vào kết quả.
• Một ký hiệu là kết thúc (terminal) nếu nó không xuất hiện trong danh sách phi kết thúc cho trước; khi đó $FIRST$ của nó chỉ gồm chính nó và không chứa $\varepsilon$.

Ví dụ: Cho $FIRST(A) = \{a, \varepsilon\}$, $FIRST(B) = \{b\}$. Với chuỗi $\alpha = A\,B$: $FIRST(A) \setminus \{\varepsilon\} = \{a\}$ được thêm vào; vì $\varepsilon \in FIRST(A)$ nên xét tiếp $B$: thêm $\{b\}$; $B$ không có $\varepsilon$ nên dừng. Kết quả: $FIRST(\alpha) = \{a, b\}$, không chứa $\varepsilon$.

Hãy viết chương trình tính $FIRST(\alpha)$ theo đúng quy tắc trên.