solution

Cho văn phạm, trước tiên dựng họ tập mục LR(1) chính tắc $\{I_0, I_1, \ldots, I_{N_1-1}\}$ (như mô tả ở bài "Dựng họ tập mục LR(1) chính tắc"). Gọi CORE của một trạng thái là tập các cặp (sản xuất, vị trí con trỏ) — BỎ QUA lookahead. Hai trạng thái LR(1) có CÙNG CORE sẽ được GỘP lại thành một trạng thái LALR(1) duy nhất; khi gộp, lookahead của mỗi mục là HỢP (union) các lookahead tương ứng từ mọi trạng thái được gộp.

Sau khi gộp xong còn lại $N_2$ trạng thái LALR(1) ($N_2 \le N_1$). Việc gộp có thể sinh THÊM xung đột reduce/reduce MỚI (theo lý thuyết, việc gộp KHÔNG BAO GIỜ sinh thêm xung đột shift/reduce mới nên chỉ cần xét reduce/reduce): tại một trạng thái đã gộp, nếu tồn tại 2 mục hoàn chỉnh KHÁC NHAU (khác sản xuất, không tính mục có $LHS=S'$) mà tập lookahead SAU KHI GỘP của chúng giao nhau khác rỗng, đó là xung đột.

Ví dụ kinh điển: văn phạm S -> a A d, S -> b B d, S -> a B e, S -> b A e, A -> c, B -> c là LR(1) (không có xung đột trong 14 trạng thái LR(1) chính tắc) NHƯNG không phải LALR(1): sau khi gộp còn 13 trạng thái, một trong số đó có xung đột reduce/reduce mới giữa A -> c . và B -> c ..