intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

BÀI GIẢNG CHƯƠNG TRÌNH DỊCH

Chia sẻ: Ad Sadad | Ngày: | Loại File: PDF | Số trang:61

Thêm vào BST
Báo xấu
92
lượt xem 11
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chiến lược phân tích top-down: Quá trình xây dựng cây phân tích cú pháp theo lối từ gốc đến lá. Xuất phát từ gốc là ký tự bắt đầu, cố gắng áp dụng các sản xuất để xây dựng một cây có tập các nhãn của lá từ trái qua phải là xâu vào

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: BÀI GIẢNG CHƯƠNG TRÌNH DỊCH

  1. BÀI GIẢNG CHƯƠNG TRÌNH DỊCH Bộ môn khoa học máy tính 1
  2. Chương 3: Phân tích cú pháp 1. Các chiến lược phân tích 2. Phân tích top-down 3. Phân tích bottom-up 4. Phân tích bảng CYK 5. Phân tích LL 6. Phân tích đệ quy trên xuống Trang 2
  3. 1. Các chiến lược phân tích  Sử dụng văn phạm phi ngữ cảnh (VPPNC) để biểu diễn cú pháp của NNLT  Cơ sở phân tích cú pháp đối với VPPNC là bài toán thành viên: Cho G = (VT, VN, S, P), L(G) = {w  VT*: S * w}, xâu vào w Câu hỏi: wL(G) ??? Trang 3
  4. 1. Các chiến lược phân tích  Chiến lược phân tích top-down: Quá trình xây dựng cây phân tích cú pháp theo lối từ gốc đến lá. Xuất phát từ gốc là ký tự bắt đầu, cố gắng áp dụng các sản xuất để xây dựng một cây có tập các nhãn của lá từ trái qua phải là xâu vào Trang 4
  5. 1. Các chiến lược phân tích  Chiến lược phân tích bottom-up Xuất phát từ các lá có nhãn là các ký tự của xâu vào, ta cố gắng áp dụng các sản xuất để xây dựng các nút trong. Nếu xây dựng được một nút gốc là ký tự bắt đầu thì được cây suy dẫn cho xâu vào Trang 5
  6. 1. Các chiến lược phân tích  Có 2 phương pháp Phân tích quay lui: trong quá trình xây dựng cây cú pháp thực hiện thử lần lượt, có bước quay lại để thử sản xuất khác Phân tích tất định: trong quá trình xây dựng cây cú pháp ta luôn lựa chọn đúng sản xuất cần dùng. Trang 6
  7. 2. Phân tích top-down  Input: Văn phạm G=(VT,VN,S,P), một xâu vào x  Output: Cây suy dẫn cho xâu vào x hoặc trả lời x không được đoán nhận  Thuật toán: đánh số các sản xuất 1, 2, 3… Bước 1: Xây dựng một cây chỉ có nút S làm gốc, gọi S là nút hoạt động và ký hiệu cần phân tích là ký hiệu đầu tiên trên xâu vào. Trang 7
  8. 2. Phân tích top-down  Bước 2: Nếu nút hoạt động là một kí hiệu không kết thúc A: Chọn sản xuất đầu tiên có A làm vế trái để tạo ra k con trực tiếp của A (AX1X2…Xk), sau đó lấy X1 làm nút hoạt động. Nếu k = 0 (A) thì nút hoạt động là nút bên phải của A trên cây. Trang 8
  9. 2. Phân tích top-down  Bước 2: Nếu nút hoạt động là kí hiệu kết thúc a thì sẽ so sánh a với kí hiệu cần phân tích: Trùng nhau: nút hoạt động là nút bên phải của a trên cây và kí hiệu cần phân tích là kí hiệu tiếp theo trên xâu vào. Không trùng: quay lại 1 bước để thử một sản xuất khác. Nếu tất cả sản xuất đã được thử thì quay lại bước trước đó. Trang 9
  10. 2. Phân tích top-down  Quá trình dừng lại khi: Tạo ra cây suy dẫn cho xâu vào Thử hết khả năng nhưng không xây dựng lên cây suy dẫn. Tức là xâu không được đoán nhận  Điều kiện dừng: văn phạm không có đệ qui trái Trang 10
  11. 2. Phân tích top-down  Ví dụ: Cho văn phạm sau S  cAd A  ab | a  Xâu vào là cad  Đánh số sản xuất: (1) : S  cAd (2) : A  ab (3) : A  a Trang 11
  12. 2. Phân tích top-down  Quá trình phân tích top-down Trang 12
  13. 3. Phân tích bottom-up  Đây là phương pháp gạt thu gọn (shift Reduce Parsing).  Sử dụng Stack S dùng để chứa kí hiệu của văn phạm cần phân tích.  Mỗi bước thực hiện một trong hai hành động gạt hoặc thu gọn. Luôn thử thu gọn trước khi gạt Trang 13
  14. 3. Phân tích bottom-up  Input: Văn phạm G không có -sản xuất và A + A, xâu vào x  Output: x có được đoán nhận hay không?  Thuật toán: Bước 1: Gạt ký tự đầu tiên của xâu x vào Stack S Bước 2: Lặp Xét mọi xâu  có thể trên đỉnh Stack. Ví dụ: Stack có abcd  d, cd, bcd, abcd. Trang 14
  15. 3. Phân tích bottom-up Nếu tồn tại A   thì thực hiện thu gọn: Lấy tất cả các ký hiệu của xâu  trong Stack. Đẩy ký hiệu A vào Stack. Trong trường hợp có nhiều xâu  cùng thỏa mãn thì đánh số để thử lần lượt. Nếu không thể thu gọn thì gạt ký hiệu tiếp theo trên xâu vào x vào Stack. Trang 15
  16. 3. Phân tích bottom-up  Nếu đã gạt hết ký hiệu trên x mà trong Stack không phải còn S thì quay lui lại địa chỉ sau cùng mà ở đó đã tiến hành thu gọn (khôi phục hiện trạng xâu vào, Stack tại thời điểm trước khi thu gọn)  Nếu còn một thu gọn nào khác có thể thì sẽ tiến hành thử theo thu gọn đó. Trang 16
  17. 3. Phân tích bottom-up  Thuật toán dừng khi đã gạt hết các ký hiệu trên xâu vào và trong Stack chỉ có một ký hiệu S. Khi đó ta kết luận xâu vào x được đoán nhận.  Ngược lại, khi thử hết các trường hợp mà trong Stack không chứa chỉ S thì kết luận xâu x không được đoán nhận. Trang 17
  18. 3. Phân tích bottom-up  Ví dụ: Cho văn phạm S  aABe A  Abc | b B  d  Xâu vào: abbcde Trang 18
  19. Trang 19
  20. 4. Phân tích bảng CYK  Dạng chuẩn Chomsky  VPPNC ở dạng chuẩn Chomsky nếu mọi sản xuất có dạng A  BC hoặc A  a  Mọi văn phạm không chứa  - sản xuất thì đều có thể chuyển về dạng chuẩn Chomsky. Trang 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2