Đang tạo bản xem trước...
Mục đích • Sau khi học xong chương này, sinh viên sẽ nắm được: – Các phương pháp phân tích cú pháp – Cách cài đặt một bộ PTCP từ một Văn phạm phi ngữ cảnh – Các khái niệm và sử dụng công cụ sinh bộ PTCP: Yacc. 2 goupee.com fb.com/groups/goupee
Điều kiện • Kiến thức cần có: – Kiến thức cơ bản về Automat. – Kiến thức về văn phạm phi ngữ cảnh CFG. 3 goupee.com fb.com/groups/goupee
Tài liệu tham khảo [1] Slide bài giảng [2] Compilers : Principles, Technique and Tools - Alfred V.Aho, Jeffrey D.Ullman - Addison - Wesley Publishing Company, 1986. [3] Automata and Formal Language, An Introduction- Dean Kelley- Prentice Hall, Englewood Cliffs, New Jersey 07632 [4] Compilers course, CS 143 summer 2010, Standford University. [5] Compiler Design – Reinhard Wilhelm, Dieter Maurer - Addison – Wesley Publishing Company, 1996. 4 goupee.com fb.com/groups/goupee
Nội dung 1. Vai trò của bộ phân tích cú pháp (PTCP) 2. Văn phạm của ngôn ngữ lập trình 3. Phân tích cú pháp từ trên xuống 4. Phân tích cú pháp từ dưới lên 5. Bộ sinh bộ PTCP 5 goupee.com fb.com/groups/goupee
Nội dung 1. Vai trò của bộ phân tích cú pháp (PTCP) 2. Văn phạm của ngôn ngữ lập trình 3. Phân tích cú pháp từ trên xuống 4. Phân tích cú pháp từ dưới lên 5. Bộ sinh bộ PTCP 6 goupee.com fb.com/groups/goupee
1. Vai trò của bộ phân tích cú pháp • Bộ phân tích cú pháp nhận chuổi các token từ bộ phân tích từ vựng để tạo ra cấu trúc cú pháp của chương trình nguồn. • Tồn tại ba loại bộ phân tích cú pháp: • Phương pháp tổng quát: • Cocke-Younger-Kasami. • Earley. • Phương pháp thông dụng: Phân tích từ trên xuống hay phân tích từ dưới lên. 7 goupee.com fb.com/groups/goupee
1. Vai trò của bộ phân tích cú pháp Mã nguồn (dãy các kí tự) If (a == 0) min = a; Phân tích từ Dãy các từ tố (token) vựng If ( Id:a == 0 ) Id:min = Id:a ; Cây cú pháp if Phân tích cú == = ; pháp a 0 min a Phân tích ngữ nghĩa goupee.com fb.com/groups/goupee
1. Vai trò của bộ phân tích cú pháp { • Mã nguồn if (b == (0)) a = b; while (a != 1) { stdio.print(a); a = a - 1; } block • Cây cú pháp } if_stmt while_stmt bin_op … … bin_op block == variable const != variable const expr_stmt … b 0 b 1 call • variable stdio print a goupee.com fb.com/groups/goupee
1. Vai trò của bộ phân tích cú pháp • Kiểm tra tính đúng đắn về cú pháp của chương trình nguồn • Xác định chức năng của các thành phần trong chương trình nguồn câu I gave him the book chủ ngữ vị ngữ bổ ngữ trực tiếpbổ ngữ gián tiếp I gave him cụm danh từ quán từ danh từ the book goupee.com fb.com/groups/goupee
1. Vai trò của bộ phân tích cú pháp • Input: Dãy các từ tố • Output: Cây cú pháp • Cài đặt: – Duyệt qua dãy các từ tố – Xây dựng cây cú pháp – Loại bỏ các cú pháp thừa trong cây cú pháp VD: a+b (a)+(b) ((a)+((b))) bin_op + a b goupee.com fb.com/groups/goupee
1. Vai trò của bộ phân tích cú pháp • Phân tích cú pháp không làm tất cả mọi công đoạn của chương trình dịch. Ví dụ: kiểm tra kiểu, khai báo biến, khởi tạo biến… =>Để lại cho phần phân tích ngữ nghĩa. • Bộ PTCP có cơ chế ghi nhận và xử lý các lỗi cú pháp thường gặp. goupee.com fb.com/groups/goupee
Nội dung 1. Vai trò của bộ phân tích cú pháp (PTCP) 2. Văn phạm của ngôn ngữ lập trình 3. Phân tích cú pháp từ trên xuống 4. Phân tích cú pháp từ dưới lên 5. Bộ sinh bộ PTCP 13 goupee.com fb.com/groups/goupee
2. Văn phạm của ngôn ngữ lập trình 2.1 Đặc tả cú pháp của ngôn ngữ 2.2 Văn phạm nhập nhằng 2.3 Loại bỏ nhập nhằng 14 goupee.com fb.com/groups/goupee
2.1. Đặc tả cú pháp của ngôn ngữ • Vấn đề: Làm thế nào để mô tả chính xác và dễ dàng cú pháp của ngôn ngữ tạo nên mã nguồn? • Giống như từ tố được mô tả bằng REs • REs dễ cài đặt (bằng NFA hoặc DFA) • Có thể dùng REs để mô tả cú pháp của ngôn ngữ lập trình được không? 15 goupee.com fb.com/groups/goupee
2.1. Đặc tả cú pháp của ngôn ngữ • Cú pháp của ngôn ngữ lập trình không thuộc lớp ngôn ngữ chính quy không thể mô tả bằng REs được • Ví dụ: L { (, ) }* sao cho L là tập các cách viết () đúng. • Nếu dùng RE để biểu diễn L phải đếm số lượng dấu “(“ chưa có dấu “)” tương ứng số đếm không bị giới hạn 16 goupee.com fb.com/groups/goupee
2.1. Đặc tả cú pháp của ngôn ngữ • Ta biết: RE DFA • Số đếm không giới hạn số trạng thái không giới hạn mâu thuẫn với cấu trúc của DFA (hữu hạn) ( ( ( ( ( ) ) ) ) ) < 6: OK >=6 17 goupee.com fb.com/groups/goupee
2.1. Đặc tả cú pháp của ngôn ngữ • Nhiều NNLT có cấu trúc đệ quy mà nó có thể được định nghĩa bằng các VP PNC (context- free grammar) G với 4 thành phần G (V, T, P, S), trong đó: – V : là tập hữu hạn các ký hiệu chưa kết thúc hay các biến (variables) – T : là tập hữu hạn các ký hiệu kết thúc (terminals). – P : là tập luật sinh của văn phạm (productions). – S ∈ V: là ký hiệu bắt đầu của văn phạm (start symbol). 18 goupee.com fb.com/groups/goupee
2.1. Đặc tả cú pháp của ngôn ngữ • Ví dụ: mô tả ngôn ngữ L S (S)S S • CFG sử dụng định nghĩa đệ quy • CFG trực quan hơn REs S (S)S ((S)S)S (( )S)S … (()) • Một xâu nằm trong ngôn ngữ của CFG nếu có một dãy suy dẫn sử dụng các sản xuất của CFG tạo nên xâu đó 19 goupee.com fb.com/groups/goupee
2.1. Đặc tả cú pháp của ngôn ngữ • Cây PTCP có thể được xem như một dạng biểu diễn hình ảnh của một dẫn xuất. • αAβ dẫn xuất ra αγβ (ký hiệu: αAβ ⇒ αγβ) nếu A → γ là một luật sinh, α và β là các chuỗi tùy ý các ký hiệu văn phạm. • Nếu α1 ⇒ α2 ⇒ .. .. ⇒ αn ta nói α1 dẫn xuất ra (suy ra) αn • Ký hiệu: ⇒ : dẫn xuất ra qua 1 bước ⇒*: dẫn xuất ra qua 0 hoặc nhiều bước. ⇒+ : dẫn xuất ra qua 1 hoặc nhiều bước.20 goupee.com fb.com/groups/goupee
Hiển thị 20 trang đầu. Tải tài liệu để xem đầy đủ.
Chưa có bình luận nào. Hãy là người đầu tiên!
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!