solution

Với văn phạm biểu thức nhị phân mơ hồ điển hình $E \to E\ op\ E \mid \text{id}$ (nhiều toán tử $op$), bảng LR(0)/SLR(1) dựng trực tiếp sẽ có rất nhiều xung đột shift-reduce. Các công cụ sinh parser (như yacc/bison) giải quyết vấn đề này bằng cách khai báo cho mỗi toán tử một độ ưu tiên (precedence) — số nguyên, càng lớn càng liên kết chặt hơn — và một tính kết hợp (associativity) là trái (L) hoặc phải (R), rồi dùng quy tắc: khi có xung đột shift-reduce giữa việc rút gọn theo toán tử $op_1$ (đang trên đỉnh ngăn xếp) và việc dịch chuyển toán tử $op_2$ (đang chờ ở token hiện tại),

• nếu $\text{prec}(op_1) > \text{prec}(op_2)$: rút gọn;
• nếu $\text{prec}(op_1) < \text{prec}(op_2)$: dịch chuyển;
• nếu bằng nhau: dịch chuyển nếu $op_1$ (và $op_2$, cùng độ ưu tiên nên cùng khai báo) có tính kết hợp R, ngược lại rút gọn nếu là L.

Áp dụng quy tắc trên vào toàn bộ quá trình phân tích, kết quả tương đương với thuật toán phân tích biểu thức theo độ ưu tiên kinh điển (precedence climbing): với chuỗi các toán hạng và toán tử hai ngôi (không có toán tử một ngôi), có thể có dấu ngoặc đơn ( ), hãy xác định cách nhóm các phép toán mà một bộ phân tích LR dùng bảng khai báo độ ưu tiên nêu trên sẽ tạo ra, rồi in biểu thức đó dưới dạng đã đặt ngoặc đầy đủ (mỗi phép áp dụng toán tử nhị phân được bao trong một cặp ngoặc ( toán_hạng_trái op toán_hạng_phải )).

Toán hạng là bất kỳ token nào không phải là một trong các toán tử được khai báo và không phải ( hoặc ) (ví dụ tên biến, hằng số); đề bài đảm bảo xâu vào là một biểu thức hợp lệ theo văn phạm (không cần xử lý lỗi cú pháp).

Ví dụ: với 2 toán tử + 1 L và * 2 L, biểu thức a + b * c được nhóm thành ( a + ( b * c ) ) vì * có độ ưu tiên cao hơn +.