solution

Mục LR(1) có dạng $[A \to \alpha \cdot \beta,\ a]$ với $a$ là một ký hiệu kết thúc (lookahead) cụ thể. Phép closure$(I)$ cho LR(1): với mỗi mục $[A \to \alpha \cdot B \beta,\ a] \in I$ ($B$ là non-terminal), với mỗi luật sinh $B \to \gamma$ và mỗi $b \in \mathrm{FIRST}(\beta a)$ ($\mathrm{FIRST}$ của chuỗi $\beta$ nối thêm $a$ ở cuối), thêm mục $[B \to \cdot \gamma,\ b]$. Phép goto$(I, X)$ định nghĩa tương tự LR(0) nhưng giữ nguyên lookahead. Họ tập mục chính tắc LR(1) bắt đầu từ \mathrm{closure}(\{[S' \to \cdot S,\ \]})$(với$G'$là văn phạm mở rộng thêm$S' \to S$), xây dựng bằng closure/goto lặp lại như thường lệ.

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).

Hai trạng thái LR(1) có cùng lõi (core) nếu bỏ lookahead đi thì tập mục LR(0) tương ứng giống hệt nhau. Phương pháp LALR(1) gộp tất cả các trạng thái LR(1) có cùng lõi thành một trạng thái duy nhất, với tập lookahead của mỗi mục là hợp các tập lookahead từ mọi trạng thái được gộp. Việc gộp có thể làm phát sinh xung đột reduce-reduce mới vốn không tồn tại ở bất kỳ trạng thái LR(1) riêng lẻ nào trước khi gộp: xảy ra khi, tại một ký hiệu kết thúc $t$, sau khi hợp lookahead có từ 2 luật sinh khác nhau trở lên cùng muốn reduce trên $t$ trong trạng thái đã gộp, nhưng không có trạng thái LR(1) gốc nào (trước khi gộp) tự nó đã có từ 2 luật sinh muốn reduce trên $t$ (nếu đã có sẵn xung đột ở một trạng thái gốc, xung đột đó không phải do gộp gây ra).

Cho văn phạm phi ngữ cảnh $G$ với ký hiệu bắt đầu $S$, hãy tính: (1) số trạng thái sau khi gộp thành LALR(1) (chính là số lõi phân biệt), và (2) số cặp (trạng thái đã gộp, ký hiệu kết thúc $t$) mà tại đó xung đột reduce-reduce chỉ phát sinh do quá trình gộp như mô tả ở trên.

Ví dụ kinh điển: văn phạm S -> a A d | b B d | a B e | b A e, A -> c, B -> c có 13 trạng thái sau khi gộp, và việc gộp làm phát sinh đúng 2 xung đột reduce-reduce mới (tại ký hiệu d và tại ký hiệu e, trong trạng thái gộp từ hai trạng thái LR(1) ứng với c được đọc sau a và sau b).