solution

Automat LALR(1) được xây dựng từ automat LR(1) chính tắc bằng cách hợp nhất (merge) các trạng thái có cùng "lõi" (core) — tức cùng tập mục LR(0) khi bỏ qua lookahead — 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ương ứng từ các trạng thái được hợp nhất.

Việc hợp nhất này đôi khi làm xuất hiện xung đột reduce/reduce mới vốn không tồn tại ở từng trạng thái LR(1) riêng lẻ: nếu sau khi hợp nhất, có hai mục đầy đủ (dạng $A \to \alpha \cdot$) thuộc hai sản xuất khác nhau mà tập lookahead (đã hợp) của chúng giao nhau khác rỗng, đó là một xung đột reduce/reduce của automat LALR(1) (dù trước khi hợp nhất, tại mỗi trạng thái LR(1) gốc có thể hoàn toàn không có xung đột).

Cho một tập các trạng thái LR(1) (mỗi trạng thái là một tập mục kèm lookahead, cho sẵn — không cần tính đóng), hãy:

1. Nhóm các trạng thái có cùng lõi (cùng tập mục LR(0), bỏ qua lookahead) lại với nhau — đây chính là cách LALR(1) hợp nhất trạng thái.
2. Với mỗi nhóm, hợp các tập lookahead theo từng mục lõi.
3. Kiểm tra xem trạng thái đã hợp nhất có xung đột reduce/reduce hay không (xét mọi cặp mục đầy đủ khác sản xuất trong nhóm).

Ví dụ kinh điển: với văn phạm $S \to aAd \mid bAe \mid aBe \mid bBd$, $A \to c$, $B \to c$, hai trạng thái LR(1) chính tắc chứa cùng lõi $\{A \to c\cdot,\ B \to c\cdot\}$ nhưng với lookahead $\{d\}/\{e\}$ ở trạng thái này và $\{e\}/\{d\}$ ở trạng thái kia (không xung đột ở từng trạng thái riêng). Khi LALR(1) hợp nhất hai trạng thái đó, cả hai mục đều nhận lookahead $\{d, e\}$ — sinh ra xung đột reduce/reduce trên $\{d, e\}$.