solution

Trong xây dựng bộ phân tích LR nâng cao (đặc biệt là tính tập lookahead khi dựng các tập mục LR(1)), ta thường xuyên cần tính $\mathrm{FIRST}$ không chỉ của một ký hiệu chưa kết thúc, mà của cả một chuỗi ký hiệu $\alpha = X_1 X_2 \ldots X_k$ (có thể trộn lẫn terminal và non-terminal, ví dụ $\mathrm{FIRST}(\beta a)$ khi đóng mục LR(1)).

Định nghĩa: $\mathrm{FIRST}(\alpha)$ là tập tất cả các ký hiệu kết thúc $a$ sao cho tồn tại một dẫn xuất $\alpha \Rightarrow^{*} a \ldots$. Nếu $\alpha \Rightarrow^{*} \varepsilon$ thì $\varepsilon \in \mathrm{FIRST}(\alpha)$ (ta ký hiệu $\varepsilon$ bằng chuỗi eps trong kết quả).

Quy tắc tính $\mathrm{FIRST}(X_1 X_2 \ldots X_k)$: xét lần lượt $X_1, X_2, \ldots$; với mỗi $X_i$, thêm $\mathrm{FIRST}(X_i) \setminus \{\varepsilon\}$ vào kết quả; nếu $\varepsilon \notin \mathrm{FIRST}(X_i)$ thì dừng lại (không xét các $X_j, j>i$ nữa); nếu $\varepsilon \in \mathrm{FIRST}(X_i)$ với mọi $i = 1, \ldots, k$ (tức toàn bộ chuỗi có thể sinh ra rỗng) thì thêm eps vào kết quả.

Quy ước ký hiệu văn phạm (áp dụng cho toàn bộ đề bài này): mỗi luật sinh được cho ở dạng A -> X1 X2 ... Xk (các ký hiệu cách nhau bởi dấu cách); nếu vế phải là rỗng thì ghi A -> eps. Một ký hiệu được coi là ký hiệu chưa kết thúc (non-terminal) nếu và chỉ nếu ký tự đầu tiên của nó là một chữ cái in hoa (A-Z); mọi ký hiệu còn lại (chữ thường, chữ số, dấu (, ), +, id, ... ) đều là ký hiệu kết thúc (terminal). Ký hiệu đặc biệt eps chỉ dùng để biểu diễn xâu rỗng $\varepsilon$ và không phải là một terminal thật sự. Ký hiệu $ là ký hiệu kết thúc xâu vào (end-marker).

Cho một văn phạm phi ngữ cảnh (đảm bảo mọi ký hiệu chưa kết thúc xuất hiện trong đề đều có ít nhất một luật sinh) và $m$ truy vấn, mỗi truy vấn là một chuỗi ký hiệu $\alpha$ (không rỗng). Với mỗi truy vấn, hãy tính $\mathrm{FIRST}(\alpha)$.

Ví dụ: Với văn phạm biểu thức

E -> T E1
E1 -> + T E1
E1 -> eps
T -> F T1
T1 -> * F T1
T1 -> eps
F -> ( E )
F -> id

truy vấn E1 $ cho kết quả \mathrm{FIRST}(E1\ \) = {+, $}$(vì$E1$nullable nên phải xét tiếp `$), in ra là $,+`.