Page 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
Document content
Page 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
Page 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
Page 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
Page 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
Page 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
Page 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
Page 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
Page 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
Page 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
Page 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
Page 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
Page 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
Page 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
Page 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
Page 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
Showing the first 20 pages. Download the document to see it all.
Comments (0)
No comments yet. Be the first!