Nhập môn Chương trình dịch
Học kì II 2006-2007
Bài 8: Phân tích LR (tiếp)
Lập trình bộphân tích cú pháp
Trước đây: tựviết bộphân tích cú pháp
Hiện nay: sửdụng các trình sinh bộphân
tích cú pháp. VD: yacc, cup, bison
Ưu điểm:
– Sửdụng phương pháp phân tích LALR(1)
– Cho phép khai báo thứtự ưu tiên, kết hợp
của các phép toán
– Tự động sinh code phân tích cú pháp (kểcả
bảng phân tích LALR(1))
Thứtựkết hợp (1)
Ví dụ
Nếu sửdụng phương pháp LALR(1), ta sẽ
được bộphân tích như thê nào ?
S S + E | E
E số| (S)
E E + E | (E) | số
Thứtựkết hợp (2)
Xung đột
E E + E | (E) | số
E E+ E +
E E + E+,$
xung đột gạt / thu gọn
gạt: 1 + (2 + 3)
thu gọn: (1 + 2) + 3
1 + 2 + 3
Khai báo cú pháp trong CUP
non terminal E; terminal PLUS, LPAREN...
precedence left PLUS;
E ::= E PLUS E
| LPAREN E RPAREN
| NUMBER ;
Khi gặp dấu cộng, thu gọnnếu vếphải có dấu cộng,
gạtnếu vếphải không có dấu cộng