Trong thực tế (như công cụ yacc/bison), thay vì viết lại văn phạm để loại bỏ xung đột shift-reduce của các toán tử hai ngôi, người ta thường gán cho mỗi ký hiệu kết thúc (toán tử) một mức ưu tiên (số nguyên, càng lớn càng ưu tiên) và một tính kết hợp (L — trái, R — phải, N — không kết hợp). Mức ưu tiên của một luật sinh được quy ước là mức ưu tiên của ký hiệu kết thúc cuối cùng (phải nhất) xuất hiện ở vế phải của nó; nếu vế phải không chứa ký hiệu kết thúc nào có khai báo ưu tiên, luật sinh được xem là không có ưu tiên xác định.
Cho một xung đột shift-reduce tại trạng thái s với ký hiệu nhìn trước a (đang muốn dịch chuyển) và luật sinh số p (đang muốn rút gọn), quyết định được đưa ra theo quy tắc:
S).S).R).L) thì chọn reduce (R); phải (R) thì chọn shift (S); không kết hợp (N) thì báo lỗi (E, không hợp lệ về mặt cú pháp).Cho bảng ưu tiên/kết hợp của các toán tử, danh sách các luật sinh liên quan (chỉ cần vế phải để xác định ký hiệu kết thúc phải nhất), và danh sách các xung đột shift-reduce cần giải quyết, hãy đưa ra quyết định cho từng xung đột theo đúng thứ tự cho trong đầu vào.
Ví dụ: + mức 1 trái, * mức 2 trái; luật E -> E + E. Xung đột tại trạng thái 1, ký hiệu +, luật này: cùng mức ưu tiên, + kết hợp trái ⇒ quyết định R.
Dòng 1: số nguyên t — số ký hiệu kết thúc có khai báo ưu tiên.
t dòng tiếp theo: terminal level assoc (level là số nguyên, assoc ∈{L,R,N}).
Dòng tiếp theo: số nguyên p — số luật sinh được khai báo.
p dòng tiếp theo: id s1 s2 ... sk với id là số hiệu luật sinh (số nguyên, không nhất thiết liên tục từ 1) và s1…sk là các ký hiệu ở vế phải (chỉ cần liệt kê đủ để xác định ký hiệu kết thúc phải nhất có ưu tiên; ký hiệu chưa kết thúc có thể xuất hiện lẫn trong danh sách và được bỏ qua khi tìm ký hiệu kết thúc).
Dòng tiếp theo: số nguyên c — số xung đột cần giải quyết.
c dòng tiếp theo: state terminal prodId — trạng thái, ký hiệu nhìn trước đang xung đột, và số hiệu luật sinh muốn rút gọn.
In ra đúng c dòng theo thứ tự cho trong đầu vào, mỗi dòng dạng state terminal decision với decision ∈{S,R,E} là quyết định giải quyết xung đột tương ứng.
Ví dụ:
Đầu vào:
1
< 1 N
1
1 E < E
1
1 < 1
Đầu ra:
1 < E
Đầu vào:
5
+ 1 L
- 1 L
* 2 L
/ 2 L
^ 3 R
7
1 E + E
2 E - E
3 E * E
4 E / E
5 E ^ E
6 ( E )
7 id
5
1 + 1
2 * 1
3 + 3
4 ^ 5
5 ) 7
Đầu ra:
1 + R
2 * S
3 + R
4 ^ S
5 ) S
Đang tải editor...