Principles of compilers GIẢNG VIÊN: TS HÀ CHÍ TRUNG BỘ MÔN: KHMT KHOA CNTT, HVKTQS ĐT:0168.558.21.02 EMAIL: HCT2009@YAHOO.COM Bài Phân tích cú pháp 3.1 Vị trí phân tích cú pháp 3.2 Một số vấn đề phân tích cú pháp 3.2.1 Văn phạm phi ngữ cảnh 3.2.2 Phân tích cú pháp từ xuống 3.2.3 Một số chiến lược phục hồi lỗi 3.2.4 Phân tích cú pháp từ lên 3.3 Công cụ xây dựng SA 3.4 Bài tập thực hành ©TS Hà Chí Trung, Khoa CNTT - HVKTQS 19/05/2012 Bài Phân tích cú pháp 2.1 Vị trí phân tích cú pháp 2.2 Một số vấn đề phân tích cú pháp 2.2.1 Văn phạm phi ngữ cảnh 2.2.2 Phân tích cú pháp từ xuống 2.2.3 Một số chiến lược phục hồi lỗi 2.2.4 Phân tích cú pháp từ lên 2.3 Cơng cụ xây dựng SA 2.4 Bài tập thực hành ©TS Hà Chí Trung, Khoa CNTT - HVKTQS 19/05/2012 3.1 Vị trí phân tích cú pháp Chương trình nguồn (Source program) Phân tích từ vựng (Lexical analyzer) Phân tích cú pháp (Syntactic analyzer) Quản lí bảng kí tự (Symbol-table manager) Phân tích ngữ nghĩa (Semantic analyzer) Sinh mã trung gian (Intermediate code generator) Quản lí lỗi (Error handler) Tối ưu mã (Code optimizer) Sinh mã (Code generator) Chương trình đích (Target program) ©TS Hà Chí Trung, Khoa CNTT - HVKTQS 19/05/2012 3.1 Vị trí phân tích cú pháp  Cú pháp PL miêu tả CFG Thông thường người ta sử dụng dạng BNF (Backus-Naur Form) để diễn đạt chúng  Nhiệm vụ SA (Syntax Analyzer, parser): kiểm tra xem SP chương trình có thỏa mãn cú pháp ngôn ngữ hay không, cách nhận chuỗi token từ phân tích từ vựng xác định chuỗi có sinh văn phạm SL không  Thông thường, parser cấu trúc cú pháp mã nguồn, cấu trúc hầu hết trường hợp biểu diễn parse tree  Ngược lại, trả thông báo lỗi  ©TS Hà Chí Trung, Khoa CNTT - HVKTQS 19/05/2012 3.1 Vị trí phân tích cú pháp Source Lexical Token program analyzer Get next token Parser Parse tree Semantic analyzer Symbol table  Các chiến lược phân tích cú pháp:   Phân tích từ xuống (top-down parsing): Cây cú pháp tạo từ xuống, gốc; Phân tích từ lên (bottom-up parsing): Cây cú pháp tạo từ lên,  Cả hai dạng parsers quét luồng liệu vào từ trái qua phải (tại thời điểm thường token) ©TS Hà Chí Trung, Khoa CNTT - HVKTQS 19/05/2012 3.1 Vị trí phân tích cú pháp  Vấn đề: Trong trình biên dịch xuất nhiều lỗi SA phải phát thơng báo lỗi xác cho người lập trình đồng thời khơng làm chậm chương trình viết  Trên thực tế, parsers hiệu ứng dụng cho lớp CFGs: Phân tích đệ quy (O(cn));  thuật tốn phân tích CYK (Coke-Younger-Kasami) (O(n3));  (thuật tốn phân tích Earley) (O(n3) O(n2) O(n));  LL(k) top-down parsing (O(n));  LR(k) bottom-up parsing (O(n))  ©TS Hà Chí Trung, Khoa CNTT - HVKTQS 19/05/2012 Bài Phân tích cú pháp 3.1 Vị trí phân tích cú pháp 3.2 Một số vấn đề phân tích cú pháp 3.2.1 Văn phạm phi ngữ cảnh 3.2.2 Phân tích cú pháp từ xuống 3.2.3 Một số chiến lược phục hồi lỗi 3.2.4 Phân tích cú pháp từ lên 3.3 Công cụ xây dựng SA 3.4 Bài tập thực hành ©TS Hà Chí Trung, Khoa CNTT - HVKTQS 19/05/2012 3.2.1 Văn phạm phi ngữ cảnh  Để định nghĩa cấu trúc PL ta dùng CFG:  Chỉ rõ đăc điểm cú pháp PL;  Thiết kế văn phạm với ngơn ngữ cho;  Có thể chuyển đổi từ CFG sang parser nhờ số công cụ có sẵn ( !.)  VD: CFG sau định nghĩa biểu thức số học đơn giản: E → E A E | (E) | -E | id A → + | - | * | / |^ Trong E, A kí tự chưa kết thúc (E cịn kí tự bắt đầu), kí tự cịn lại kí tự kết thúc  Một số khái niệm liên quan: dẫn xuất trực tiếp, gián tiếp trái nhất, phải ©TS Hà Chí Trung, Khoa CNTT - HVKTQS 19/05/2012 3.2.1 Văn phạm phi ngữ cảnh  Dẫn xuất dạng dẫn xuất (bài – L{ thuyết Automata ngơn ngữ hình thức): Dẫn xuất trái nhất: E  -E  -(E)  -(E+E)  -(id+E)  -(id+id)  Dẫn xuất phải nhất: E  -E  -(E)  -(E+E)  -(E+id)  -(id+id)   Đặc điểm: Top-down parsing cố gắng tìm dẫn xuất trái chương trình nguồn  Bottom-up parsing cố tìm dẫn xuất phải chương trình nguồn  ©TS Hà Chí Trung, Khoa CNTT - HVKTQS 10 19/05/2012 ... -( id+id)  Dẫn xuất phải nhất: E  -E  -( E)  -( E+E)  -( E+id)  -( id+id)   Đặc điểm: Top-down parsing cố gắng tìm dẫn xuất trái chương trình nguồn  Bottom-up parsing cố tìm dẫn xuất phải chương... CNTT - HVKTQS 10 19/05/2012 3.2.1 Văn phạm phi ngữ cảnh  Parse tree dạng biểu diễn hình học dẫn xuất  VD: parse tree cho biểu thức –(id+id) là: E E  -E - E E  -( E) -  -( E+E) E ( E ) E  -( id+E)... Khoa CNTT - HVKTQS 19/05/2012 3.2.1 Văn phạm phi ngữ cảnh  Dẫn xuất dạng dẫn xuất (bài – L{ thuyết Automata ngôn ngữ hình thức): Dẫn xuất trái nhất: E  -E  -( E)  -( E+E)  -( id+E)  -( id+id)