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

Tổng kết
Các chương trinh sinh bộ phân tích cú
pháp sử dụng phương pháp LALR(1)
Thứ tự ưu tiên và kết hợp cho phép viết
cú pháp ngôn ngữ dễ dàng hơn
Văn phạm ngôn ngữ gần với cách viết
thông thường
Chương trình chính
của một chương trình dịch (1)
class Compiler {
void compile() throws CompileError {
Lexer l = new Lexer(input);
Parser p = new Parser(l);
AST tree = p.parse();
// gọi l.getToken() để lấy dãy từ tố
if (typeCheck(tree))
IR = genIntermediateCode(tree);
IR.emitCode();
}
}
Chương trình chính
của một chương trình dịch (2)
Compiler.compile()
Parser.parse()
Lexer.getToken()
InputStream.read()
cây cú pháp
từ tố
ký tự
Cây cú pháp

+ 2) + 3
) + 3
) + 3
) + 3
+ 3
+ 3
(1
(E
(E + 2
(E + E
(E
(E)
E
E + 3
E + E
E
Num(1)
Num(2)
Add()
Num(3)
Add()
RESULT = new Num(1)
RESULT = new Num(2)
RESULT = new Add(e1,e2)
RESULT = new Num(3)
RESULT = new Add(e1,e2)
RESULT = e
Hướng đối tượng (1)
 Viết lớp trừu tượng (abstract class) cho các kí
hiệu không kết thúc

Chương trình nguồn