intTypePromotion=1

Bài giảng Chương trình dịch: Bài giảng 4 - Nguyễn Phương Thái

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PPT | Số trang:20

0
37
lượt xem
5
download

Bài giảng Chương trình dịch: Bài giảng 4 - Nguyễn Phương Thái

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong bài giảng 4, người học sẽ tìm hiểu về phân tích cú pháp và các phương pháp phân tích cơ bản. Thông qua bài giảng người học có thể nắm bắt được một số phương pháp phân tích cú pháp như phân tích Top-Down và phân tích Bottom-Up, biết đươc một số khó khăn khi tiến hành phân tích cú pháp,... Mời các bạn cùng tham khảo.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Chương trình dịch: Bài giảng 4 - Nguyễn Phương Thái

  1. Bài giảng 4 ­ Phân tích cú pháp  và các phương pháp phân tích cơ  bản Nguyễn Phương Thái Bộ môn Khoa học Máy tính http://www.coltech.vnu.vn/~thainp/ 1
  2. Bài toán  Đầu vào: câu vào chứa toàn các từ tố  Phân tách câu vào thành các phần theo  văn phạm và biểu diễn cấu trúc này  bằng một cây (gọi là cây phân tích)  hoặc theo một cấu trúc nào đó tương  đương với cây. 2
  3. Bài toán (tiếp) Chæång yãu cáö u cáy trçnh láú y tæìtäú phán nguäön Phán têch têch Phán têch Phán têch ngæî tæìvæû ng cuïphaïp nghéa tæìtäú Baíng kyï hiãûu 3
  4. Văn phạm  Mọi ngôn ngữ lập trình đều có các luật mô tả các  cấu trúc cú pháp.  Một chương trình nguồn viết đúng phải tuân theo các  luật mô tả này ­ tức là viết đúng văn phạm (hay đúng  ngữ pháp).   Văn phạm của một ngôn ngữ lập trình có cấu trúc có  thể mô tả bằng văn phạm phi ngữ cảnh và biểu  diễn theo ký pháp BNF hoặc đồ thị chuyển. 4
  5. Các phương pháp phân tích Cơ sở của phân tích cú pháp đối với lớp  VPPNC là định lý Bài toán thành viên với  ngôn ngữ phi ngữ cảnh. Người ta đã chứng  minh được định lý này bằng cách đưa ra các  giải thuật cài đặt trên thực tế, ví dụ như:  Thuật toán phân tích Top­Down.  Thuật toán phân tích Bottom ­ Up.  Thuật toán phân tích CYK (Coke­Younger­ Kasami).  Thuật toán phân tích Earley. 5
  6. Các phương pháp phân tích  (tiếp)  Việc phân tích một câu là khôi phục  hoặc xây dựng suy dẫn sinh ra nó, do  đó ta sẽ dựng được cây suy dẫn.  Thông thường trong các thuật toán  phân tích, ta hay tiến hành từ một phía  của câu, kiểm tra lần lượt các thành  phần của câu đó cho đến hết (đa số từ  trái sang phải). 6
  7. Hai chiến lược phân tích chính  Chiến lược phân tích top­down (trên xuống): cho một  văn phạm phi ngữ cảnh G = ( ,  , P, S) và một câu  cần phân tích w. Ta xuất phát từ điểm khởi đầu,  nghĩa là từ S, áp dụng các suy dẫn trái, tiến từ trái  qua phải thử tạo ra câu đưa vào phân tích w.  Chiến lược phân tích bottom­up (dưới lên): Quá trình  ngược lại với phân tích top­down, xuất phát từ chính  câu vào phân tích w, bằng cách áp dụng thu gọn các  suy dẫn phải, tiến hành từ trái qua phải để đi tới ký  hiệu đầu S của văn phạm. 7
  8. Hai chiến lược phân tích chính  (tiếp) Điều kiện để các thuật toán trên là dừng như  sau:  Phân tích top­down (phân tích trái) là dừng  khi và chỉ khi G không có đệ quy trái.  Phân tích bottom­up (phân tích phải) là dừng  khi và chỉ khi G không chứa suy dẫn A=>+ A  và không có sản xuất B  (sản xuất rỗng). 8
  9. Khó khăn khi phân tích  Gặp các luật có nhiều lựa chọn ở vế phải như: A   1 |  2 |  3 ......... |  k,  k   2  Giải quyết: có hai chiến lược: 1. Phân tích quay lui (backtrack): ta thử lần lượt các  i  (1   i   k) để tìm  i  thích hợp. Rất tốn thời gian. 2. Phân tích không quay lui (without­backtrack). Trong  việc tìm sản xuất thích hợp, ta biết cách xác định  sản xuất duy nhất thích hợp mà không cần phải thử  các sản xuất khác. Các phương pháp phân tích như  vậy gọi là phân tích tất định (deterministic parsing). 9
  10. Phân tích Top­Down Chuẩn bị:  Với một VPPNC cho trước, đánh dấu mọi lựa  chọn trong từng sản xuất. Ví dụ: nếu các sản  xuất dạng S aSbS | aS | c thì aSbS là lựa  chọn thứ nhất, aS là lựa chọn thứ hai và c là  lựa chọn cuối của sản xuất S.  Dùng một con trỏ chỉ đến xâu vào. Ký hiệu  trên xâu vào do con trỏ chỉ đến gọi là ký hiệu  vào hiện tại. Vị trí đầu tiên của con trỏ là ký  hiệu bên trái nhất của xâu vào. 10
  11. Phân tích Top­Down (tiếp) Tiến hành các bước đệ quy sau:  Nếu nút đang xét là một nút ký hiệu không kết thúc A  thì lấy lựa chọn đầu tiên, ký hiệu là X1...Xk. Lại lấy  nút X1 làm nút đang xét. Trường hợp k = 0 (sản xuất   ) thì lấy nút ngay bên phải A làm nút đang xét.  Nếu nút đang xét là nút ký hiệu kết thúc a, thì so  sánh nó với ký hiệu vào hiện tại:  Nếu giống nhau thì lấy nút ngay bên trái a làm nút đang xét  và chuyển con trỏ xâu vào sang bên phải một ký hiệu.  Nếu a không giống thì quay lại nút do sản xuất trước tạo ra,  điều chỉnh lại con trỏ xâu vào nếu cần thiết, sau đó ta lại  thử lựa chọn tiếp theo. Nếu không còn lựa chọn nào nữa thì  lại qua lại nút trước đó và cứ như vậy. 11
  12. Ví dụ  VPPNC G=( ,  , P, S) (a) S  P: S aSbS | aS | c  w =aacbc a S b S a S b S c c 12
  13. Ví dụ S  VPPNC G=( ,  , P,  S)  P: S aSbS | aS | c a S b S  w =aacbc a S c c 13
  14. HaìGiang Cao Bàò ng Lai Cháu Thaïi Nguyãn Sån La Laû ng Sån Haìnäüi Haíi Phoìng Nam Âënh Thanh Hoaï Vinh Âäö ng Håïi Huãú ÂaìNàô ng Quaíng Ngaîi Qui Nhån NhaTrang Phan Rang Phan Thiãú t Tp HCM 14
  15. Phân tích Bottom­Up  Ngược lại với phương pháp top­down:  bắt đầu từ lá cố gắng xây dựng thành  cây bằng cách hướng lên gốc.  Phân tích bottom­up được gọi là phân  tích gạt thu gọn (shift­reduce parsing). 15
  16. Ví dụ  S AB, A ab,  B aba  ababa.  S A A B a b a b a 16
  17. Thời gian, bộ nhớ và độ phức tạp  của top­down & bottom­up  Với xâu vào w có độ dài n, độ phức tạp của  thuật toán cn.  Hình dung:  c = 3, n = 20   3n = 320 = trên 3 tỷ.  Với máy tính có khả năng thực hiện được 1000  phép xét từ tố mỗi giây, tổng thời gian cần để  phân tích mỗi một câu lệnh này là 3tỷ /1000/60/60  > 80 giờ.  Nếu máy tính có khả năng xử lý gấp 10 lần  (10.000 từ tố mỗi giây) thì cũng cần đến 8 giờ để  xử lý xong câu lệnh đó. 17
  18. Phát hiện lỗi  Nếu một chương trình dịch chỉ phải dịch các  chương trình máy tính viết đúng thì thiết kế  và hoạt động của nó sẽ rất đơn giản.  Một chương trình dịch tốt phải phát hiện,  định vị, phân loại được tất cả các lỗi để giúp  đỡ người viết.   Người thiết kế chương trình dịch phải tự  quyết định bắt và báo lỗi như thế nào 18
  19. Phát hiện lỗi (tiếp) Giai đoạn phân tích cú pháp phát hiện và khắc  phục được khá nhiều lỗi do:  Nhiều loại lỗi khác nhau đồng thời cũng là lỗi  cú pháp. Ví dụ lỗi do chuỗi từ tố từ bộ phân  tích từ vựng không theo thứ tự của luật văn  phạm của ngôn ngữ lập trình.  Nhờ sự chính xác của các phương pháp  phân tích.  19
  20. Các chiến lược phục hồi lỗi  Phục hồi kiểu trừng phạt  Khôi phục cụm từ  Gia cố luật (sản xuất) hay gặp lỗi  Chỉnh lý toàn cục. 20
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

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