solution

Trong xây dựng bộ phân tích LR, mỗi trạng thái của automaton LR(0) là một tập mục (item set). Một mục của luật sinh $A \to X_1 X_2 \ldots X_m$ được ký hiệu bằng cặp $(i, p)$ với $i$ là số hiệu luật sinh và $0 \le p \le m$ là vị trí dấu chấm — nghĩa là mục $[A \to X_1 \ldots X_p \,.\, X_{p+1} \ldots X_m]$.

Phép toán CLOSURE trên một tập mục $I$ được định nghĩa như sau: lặp lại cho tới khi không còn thay đổi — với mỗi mục $[A \to \alpha \,.\, B\beta] \in I$ mà $B$ là một ký hiệu không kết thúc (non-terminal), với mỗi luật sinh $B \to \gamma$ trong văn phạm, nếu mục $[B \to .\, \gamma]$ (tức $(j, 0)$ với $j$ là số hiệu luật $B \to \gamma$) chưa có trong $I$ thì thêm vào $I$.

Một ký hiệu được coi là non-terminal nếu nó xuất hiện ở vế trái (LHS) của ít nhất một luật sinh trong văn phạm cho trước; các ký hiệu khác là terminal.

Cho văn phạm và một tập mục lõi (kernel) $I$ ban đầu, hãy tính $\text{CLOSURE}(I)$.

Ví dụ: văn phạm gồm 2 luật E -> E + T(1), E -> T(2); kernel $I = \{(1,0)\}$ (tức $[E \to . E + T]$). Vì sau dấu chấm là $E$ (non-terminal), ta thêm mục $(2,0)$ ($E \to .T$). Với $T$ không phải LHS của luật nào trong văn phạm này nên không mở rộng thêm. Kết quả: $\text{CLOSURE}(I) = \{(1,0), (2,0)\}$.