2쪽
Kiểm tra bài trước • Bài tập 2.1: Cho văn phạm phi ngữ cảnh: S → S S + | S S * | a Xây dựng cây PTCP cho câu nhập: aa+a* • Bài 2.2 Đâu là văn phạm mơ hồ: 2 goupee.com fb.com/groups/goupee
자료 내용
3쪽
Mục đích • Sau khi học xong chương này, sinh viên sẽ nắm được: – Các kỹ thuật xác định và cài đặt bộ PTTV. – Xây dựng các lược đồ cho các biểu thức chính quy mô tả ngôn ngữ. – DFA và NFA. Các automata hữu hạn xác định và không xác định dùng để nhận dạng chính xác ngôn ngữ. – Sử dụng công cụ có sẵn Lex để sinh ra bộ PTTV 3 goupee.com fb.com/groups/goupee
4쪽
Điều kiện • Kiến thức cần có: – Kiến thức cơ bản về NFA và DFA – Cách chuyển đổi giữa các Automata. 4 goupee.com fb.com/groups/goupee
5쪽
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 goupee.com fb.com/groups/goupee
6쪽
Nội dung 1. Vai trò của bộ phân tích từ vựng 2. Lữu trữ tạm chương trình nguồn 3. Đặc tả Token 4. Nhận dạng Token 5. Sơ đồ dịch 6. Automat hữu hạn 7. Từ biểu thức chính quy đến NFA 8. Tổng kết quá trình PTTV 9. Thiết kế bộ sinh bộ PTTV 6 goupee.com fb.com/groups/goupee
7쪽
Nội dung 1. Vai trò của bộ phân tích từ vựng 2. Lữu trữ tạm chương trình nguồn 3. Đặc tả Token 4. Nhận dạng Token 5. Sơ đồ dịch 6. Automat hữu hạn 7. Từ biểu thức chính quy đến NFA 8. Tổng kết quá trình PTTV 9. Thiết kế bộ sinh bộ PTTV 7 goupee.com fb.com/groups/goupee
8쪽
1. Vai trò của bộ phân tích từ vựng 1.1 Ý nghĩa của giai đoạn PTTV 1.2 Các khái niệm 1.3 Thuộc tính của Token 1.4 Lỗi từ vựng 8 goupee.com fb.com/groups/goupee
10쪽
1.1 Ý nghĩa của giai đoạn PTTV • Làm cho việc thiết kế đơn giản và dễ hiểu hơn • Hiệu quả của trình biên dịch được cải thiện nhờ một số chương trình xử lý chuyên dụng. • Tính đa tương tích của trình biên dịch được cải thiện. 10 goupee.com fb.com/groups/goupee
11쪽
1.2 Các khái niệm • Từ tố (Token): là các ký hiệu kết thúc trong văn phạm đối với ngôn ngữ nguồn. Ví dụ: từ khóa, toán tử, dấu câu, hằng, định danh… • Trị từ vựng (Lexeme) của một token là một chuỗi ký tự biểu diễn cho token đó • Mẫu từ vựng (pattern) là qui luật mô tả một tập các trị từ vựng kết hợp với một token nào đó. 11 goupee.com fb.com/groups/goupee
13쪽
1.3 Thuộc tính của Token • Khi có nhiều mẫu từ vựng khớp với trị từ vựng, bộ PTTV phải cung cấp thêm thông tin và cất chúng vào bảng danh biểu (Ví dụ trị từ vựng). Token luôn mang trong mình một thuộc tính duy nhất là con trỏ để chỉ đến vị trí của nó trong bảng danh biểu. Khi một token được chuyển đến bộ phân tích cú pháp nó sẽ có dạng. <Token, thuộc tính> 13 goupee.com fb.com/groups/goupee
14쪽
1.3 Thuộc tính của Token • Ví dụ 3.1: Câu lệnh: X=Y*2, được viết như một dãy các bộ: – <id, con trỏ trong bảng ký hiệu của X> – <assign_op, > – <id, con trỏ trong bảng ký hiệu của Y> – <mult_op, > – <num, giá trị nguyên 2> Chú ý: Một số bộ không cần giá trị thuộc tính, thành phần đầu tiên là đủ nhận dạng trị từ vựng 14 goupee.com fb.com/groups/goupee
15쪽
1.4 Lỗi từ vựng • Chỉ một số ít lỗi được phát hiện tại bước PTTV. • Ví dụ: fi (i>=m)… fi lỗi viết sai từ khóa if ? Hay một id (danh biểu) chưa được khai báo? • Các chiến lược khắc phục lỗi: • Xóa đi 1 ký tự dư • Xen thêm 1 ký tự bị mất • Thay thế ký tự sai bằng ký tự đúng • Chuyển đổi hai ký tự kề nhau 15 goupee.com fb.com/groups/goupee
16쪽
Nội dung 1. Vai trò của bộ phân tích từ vựng 2. Lữu trữ tạm chương trình nguồn 3. Đặc tả Token 4. Nhận dạng Token 5. Sơ đồ dịch 6. Automat hữu hạn 7. Từ biểu thức chính quy đến NFA 8. Thiết kế bộ sinh bộ PTTV 16 goupee.com fb.com/groups/goupee
18쪽
2. Lưu trữ tạm chương trình nguồn • Vấn đề: Đọc từng ký tự chương trình nguồn tốn nhiều thời gian và ảnh hưởng tốc độ dịch • Giải quyết: Đọc một lúc một chuỗi ký tự và lưu vào bộ đệm buffer. • Thế nào cho trọn vẹn Token? 18 goupee.com fb.com/groups/goupee
19쪽
2.1 Cặp bộ đệm • Vùng đệm chia làm 2 nửa với kích thước N (1024 hoặc 4096) • Sử dụng 2 con trỏ P1, P2 để dò tìm. – P1 đặt tại vị trí đầu của 1 trị từ vựng – P2 dịch chuyển để xác định trị từ vựng cho token. Vấn đề? 19 goupee.com fb.com/groups/goupee
20쪽
2.1 Cặp bộ đệm Giải thuật: if p2 ở ranh giới một nửa bộ đệm then begin lấp đầy N ký hiệu nhập mới vào nửa bên phải. p2 := p2 + 1; end else if p2 ở tận cùng bên phải bộ đệm then begin lấp đầy N kỳ hiệu nhập vào nửa bên trái bộ đệm. chuyển p2 về ký tự tận cùng bên trái của bộ đệm. end else p2 := p2 + 1; 20 goupee.com fb.com/groups/goupee
앞 20페이지만 표시됩니다. 전체를 보려면 자료를 다운로드하세요.
댓글 (0)
댓글이 없습니다. 첫 댓글을 남겨보세요!