solution

Một mục LR(1) là một cặp $([A \to \alpha \cdot \gamma],\ L)$ gồm một mục LR(0) và một tập lookahead $L$ (tập ký hiệu kết thúc). Phép đóng (closure) LR(1) của một tập mục $I$ được tính theo quy tắc điểm bất động:

Nếu $([A \to \alpha \cdot B\,\beta],\ L) \in I$ với $B$ là phi kết thúc, thì với mọi sản xuất $B \to \delta$, thêm mục $([B \to \cdot\,\delta],\ L')$ vào $I$, trong đó $L' = FIRST(\beta\,a)$ hợp trên mọi $a \in L$; cụ thể $L' = FIRST(\beta) \setminus \{\varepsilon\}$, và nếu $\varepsilon \in FIRST(\beta)$ (hoặc $\beta$ rỗng) thì $L' = L' \cup L$. Nếu mục $[B \to \cdot\,\delta]$ đã có trong $I$ (với lookahead khác), hợp thêm $L'$ vào tập lookahead hiện có của nó thay vì tạo mục mới. Lặp lại đến khi không còn thay đổi.

$FIRST(\beta)$ được tính từ các tập $FIRST$ của từng ký hiệu phi kết thúc cho sẵn (ký hiệu kết thúc có $FIRST$ là chính nó); nếu $\beta$ rỗng thì $FIRST(\beta) = \{\varepsilon\}$.

Cho văn phạm, tập $FIRST$ của các phi kết thúc, và tập mục hạt nhân LR(1) (mỗi mục kèm một tập lookahead), hãy tính tập đóng LR(1) đầy đủ.

Ví dụ: văn phạm $S \to A\,B$, $A \to a\,|\,\varepsilon$, $B \to b$; hạt nhân (S \to \cdot\,A\,B,\ \{\})$. Vì sau$A$còn$B$với$FIRST(B) = {b}$(không nullable), lookahead truyền cho các sản xuất của$A$là${b}$(không hợp thêm${$}$). Đóng: thêm$(A \to \cdot,a,\ {b})$và$(A \to \cdot,\ {b})$.