Giáo trình Chương trình dịch

186 trang Gia Huy 17/05/2022 2860

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Chương trình dịch", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_chuong_trinh_dich.pdf

Nội dung text: Giáo trình Chương trình dịch

MỤC LỤC LỜI NÓI ĐẦU 1 TỔNG QUAN VỀ NGÔN NGỮ LẬP TRÌNH VÀ CHƢƠNG TRÌNH DỊCH 2 TRÌNH BIÊN DỊCH 3 CHƢƠNG I.TỔNG QUAN 3 1.1. Các khái niệm liên quan 3 1.1.1. Trình biên dịch 3 1.1.2. Trình thông dịch: 3 1.2. Phân tích chƣơng trình nguồn 4 1.2.1. Phân tích từ vựng 4 1.2.2. Phân tích cú pháp 5 1.2.3. Phân tích ngữ nghĩa 6 1.3. Các giai đoạn của trình biên dịch 7 1.3.1. Kỳ đầu 8 1.3.2. Kỳ sau 8 CHƢƠNG II. PHÂN TÍCH TỪ VỰNG 12 2.1.Vai trò của bộ phân tích từ vựng 14 2.1.1. Nhiệm vụ. 14 2.1.2. Tiến trình phân tích từ vựng 15 2.1.3. Từ vị, từ tố, mẫu 16 2.1.4. Thuộc tính của token 17 2.1.5. Lỗi từ vựng 17 2.2. Lƣu trữ tạm thời trƣơng trình nguồn 18 2.2.1. Cặp bộ đệm 18 2.2.2. Khóa cầm canh 19 2.3. Tính chất và nhận dạng token 20 2.3.1. Đặc tả token 20 2.3.2. Nhận dạng token 23 2.4. Các bƣớc để xây dựng bộ phân tích từ vựng. 29 2.5. Ngôn ngữ và đặc tả cho bộ phân tích từ vựng 29 2.5.1. Bộ sinh bộ phân tích từ vựng 29 2.5.2. Ðặc tả lex 30 BÀI TẬP CHƢƠNG II- PHÂN TÍCH TỪ VỰNG 32 Trang i
CHƢƠNG III. PHÂN TÍCH CÚ PHÁP 33 3.1. Phƣơng pháp phân tích cú pháp 35 3.1.1. Vai trò của bộ phân tích cú pháp 35 3.1.2. Văn phạm phi ngữ cảnh 36 3.1.3. Các phƣơng pháp phân tích cú pháp 43 3.2.Các phƣơng pháp phân tích tất định 64 3.2.1. Bộ phân tích LL 64 3.2.2. Biến đổi văn phạm mơ hồ 80 3.3. Cú pháp điều khiển 84 3.3.1. Định nghĩa điều khiển dựa cú pháp 84 3.3.2. Xây dựng cây phân tích cú pháp 88 3.3.3. Thứ tự đánh giá thuộc tính 92 BÀI TẬP CHƢƠNG III. PHÂN TÍCH CÚ PHÁP 103 CHƢƠNG IV. PHÂN TÍCH NGỮ NGHĨA VÀ BẢNG DANH BIỂU 108 4.1. Các hệ thống kiểu 110 4.1.1. Biểu thức kiểu 110 4.1.2. Hệ thống kiểu 110 4.1.3. Kiểm tra kiểu tĩnh và động 110 4.2. Các vấn đề của kiểm tra kiểu 110 4.2.1. Đặc tả một bộ kiểm tra kiểu đơn giản 110 4.2.2. Sự tƣơng đƣơng của các biểu thức kiểu 112 4.2.3. Chuyển đổi kiểu 113 4.3. Bảng danh biểu 115 4.3.1. Mục đích của bảng danh biểu 115 4.3.2. Các yêu cầu bảng danh biểu 115 4.3.3. Cấu trúc dữ liệu của bảng danh biểu 115 CHƢƠNG V. SINH MÃ 120 5.1. Sinh mã trung gian 121 5.1.1. Các ngôn ngữ trung gian 121 5.1.2. Khai báo 127 5.1.3. Lệnh gán 131 5.1.4. Biểu thức logic 134 5.1.5. Phát biểu Case 139 5.2. Sinh mã đích 140 5.2.1. Các dạng mã đối tƣợng 140 5.2.2. Các vấn đề thiết kế bộ sinh mã 141 Trang ii
5.2.3. Máy đích 144 5.2.4. Quản lý bộ nhớ trong thời gian thực hiện 146 5.2.5. Khối cơ bản và lƣu đồ 152 5.2.6. Bộ sinh mã đơn giản 158 BÀI TẬP CHƢƠNG V. SINH MÃ 163 PHỤ LỤC A 165 PHỤ LỤC B 170 PHỤ LỤC C 177 TÀI LIỆU THAM KHẢO 183 Trang iii
LỜI NÓI ĐẦU Trong thời kỳ đầu của máy tính, cơ chế vận hành được lập trình viên chuyển từ mã nguồn sang mã máy để máy tính hiểu và thực hiện được công việc. Đến nay có nhiều ngôn ngữ lập trình được tạo ra với những trợ giúp và môi trường thuận tiện hơn để lập trình viên thiết kế các ứng dụng. Nội dung chính của chương trình dịch là thực hiện việc chuyển đổi một chương trình hay đoạn chương trình từ ngôn ngữ nguồn mà con người hiểu sang ngôn ngữ đích (ngôn ngữ máy; mã máy) tương đương để máy tính hiểu và thực hiện, việc chuyển đổi này phụ thuộc hoàn toàn vào môi trường của máy tính (phần cứng, hệ điều hành). Trong đó chương trình dịch là một minh họa của lý thuyết ngôn ngữ hình thức và Automata, là kết quả của việc nghiên cứu về sự diễn dịch làm nền tảng của việc hình thành tri thức loài người như: diễn giải và biên dịch, thông dịch lại các thông tin nguồn, ngôn ngữ nguồn (của tự nhiên, của những đối tượng thể hiện sự tồn tại) sang ngôn ngữ mà một đối tượng khác hiểu và thực hiện các công việc. Nội dung chính của giáo trình này giới thiệu cách tiếp cận sáu bước biên dịch của một ứng dụng tin học gọi là chương trình dịch (Trình biên dịch). Sáu bước biên dịch là: phân tích từ vựng, phân tích cú pháp, phân tích ngữ nghĩa, sinh mã trung gian, tối ưu hóa mã trung gian, sinh mã đích. Trong phần phụ lục tham khảo được trình bày kiến thức liên quan mà đường dẫn ở mỗi phần đã ghi rõ. Nhóm tác giả đã nghiên cứu từ nhiều nguồn tài liệu về trình biên dịch, với mong muốn có một giáo trình “Trình Biên Dịch” đáp ứng phần nào nhu cầu mong đợi của sinh viên chuyên ngành. Mặc dù nhiều cố gắng trong quá trình biên sọan nhưng vẫn còn hạn chế, rất mong nhận được nhiều ý kiến đóng góp của quý đồng nghiệp và bạn đọc gần xa, để lần tái bản sau hoàn chỉnh hơn. Trang 1
TỔNG QUAN VỀ NGÔN NGỮ LẬP TRÌNH VÀ CHƢƠNG TRÌNH DỊCH Nội dung chính: Chương này cung cấp những kiến thức cơ bản giúp cho bạn đọc hiểu sáu bước biên dịch là: bước 1: phân tích từ vựng; bước 2: phân tích cú pháp; bước 3: phân tích ngữ nghĩa; bước 4: sinh mã trung gian; bước 5: tối ưu hóa mã trung gian; bước 6: sinh mã đích. Mục tiêu Giúp cho bạn đọc hiểu cách thức một chương trình dịch nhân dạng mã nguồn, phân tích mã nguồn, xử lý mã nguồn. Nếu xử lý thành công: sinh mã đích, nếu xử lý không thành công: thông báo lỗi. Lĩnh vực ứng dụng Mô hình hóa việc xử lý thông tin đầu vào, thông tin đầu vào ở đây là đối tượng ngôn ngữ nguồn. Yêu cầu chung Đọc giả đã hiểu về ngôn ngữ lập trình, cấu trúc máy tính, lý thuyết ngôn ngữ, cấu trúc dữ liệu, phân tích thiết kế giải thuật và công nghệ phần mềm. TÀI LIỆU THAM KHẢO CHƢƠNG 1: [1] Dƣơng Tuấn Anh (1986), “Giáo trình trình biên dịch” - NXB Đại Học Bách Khoa TPHCM [2] Phạm Hồng Nguyên, “Giáo trình Chương trình Dịch” - NXB Đại Học Quốc Gia Hà Nội [3] Phan Thị Tƣơi (2011), “Trình Biên Dịch” - (Trường Ðại học kỹ thuật Tp.HCM) - NXB Giáo dục [4] Compilers : Principles, Technique and Tools - Alfred V.Aho, Jeffrey D.Ullman - Addison - Wesley Publishing Company, 1986. [5] Compiler Design – Reinhard Wilhelm, Dieter Maurer - Addison – Wesley Publishing Company, 1996. Trang 2
TRÌNH BIÊN DỊCH CHƢƠNG I.TỔNG QUAN 1.1. Các khái niệm liên quan 1.1.1. Trình biên dịch Trình biên dịch là một chương trình thực hiện việc chuyển đổi một chương trình hay đoạn chương trình từ ngôn ngữ này (gọi là ngôn ngữ nguồn) sang ngôn ngữ khác (gọi là ngôn ngữ đích) tương đương. Một phần quan trọng trong quá trình dịch là ghi nhận lại các lỗi có trong chương trình nguồn để thông báo lại cho người viết chương trình. chương trình chương trình nguồn (ngôn ngữ Trình biên đích dịch bậc cao) (ngôn ngữ máy) Lỗi Hình 1.1: Sơ đồ một trình biên dịch 1.1.2. Trình thông dịch: Trình thông dịch là quá trình xử lý dạng bên trong của chương trình nguồn và dữ liệu cùng một thời gian. Trong thông dịch thì mã nguồn không được dịch trước thành ngôn ngữ máy mà mỗi lần cần chạy chương trình thì mã nguồn mới được dịch để thực thi từng dòng một (line by line). Tất cả các ngôn ngữ không biên dịch ra mã máy điều phải sử dụng trình thông dịch (PHP, WScripts, Perl, Linux Shell, Python ). Chương trình Trình thông dịch nguồn Kết quả (ngôn ngữ bậc cao) Dữ liệu Hình 1.2: Sơ đồ một trình thông dịch Trang 3
1.2. Phân tích chƣơng trình nguồn 1.2.1. Phân tích từ vựng Trong một trình biên dịch, giai đoạn phân tích từ vựng sẽ đọc chương trình nguồn từ trái sang phải (scanning) để tách ra thành các thẻ từ ngữ (token). Các thẻ từ ngữ này thuộc dạng nào trong những dạng đã định nghĩa trước của trình biên dịch: danh biểu, ký hiệu, số. Có hai dạng danh biểu: danh biểu cài đặt sẵn (từ khóa, ví dụ Dim trong Visual Basic), danh biểu người dùng định nghĩa. Ví dụ 1.1a: Quá trình phân tích từ vựng cho câu lệnh gán position := initial + rate * 10 sẽ tách thành các token như sau: 1. Danh biểu position 5. Danh biểu rate 2. Ký hiệu phép gán:= 6. Ký hiệu phép nhân (*) 3. Danh biểu initial 7. Số 10 4. Ký hiệu phép cộng (+) Trong quá trình phân tích từ vựng các khoảng trắng (blank) sẽ bị bỏ qua. Ví dụ 1.1b: Xem chương trình nguồn được tạo bằng Visual Basic 6.0 Private Sub Form_Load() Dim namtam As Integer namtam = Year(Date) MsgBox (" Xin Chao " & namtam) End Sub Với kết quả hiển thị sẽ tách thành các token như sau: 1. Danh biểu Private 2. Danh biểu Sub 3. Danh biểu Form_Load 4. Ký hiệu ( 5. Ký hiệu ) 6. Danh biểu Dim Trang 4
7. Danh biểu namtam 8. Danh biểu As 9. Danh biểu Integer 10. Ký hiệu phép gán = 11. Danh biểu Year 12. Danh biểu Date 13. Danh biểu MsgBox 14. Ký hiệu “ 14. Ký hiệu ” 16. Danh biểu Xin 17. Danh biểu Chao 18. Ký hiệu & 19. Danh biểu End 20. Danh biểu Sub Trong quá trình phân tích từ vựng các khoảng trắng (blank) sẽ bị bỏ qua. Gặp Private Sub, End Sub bộ phân tích từ vựng nhóm lại thành một danh biểu cài đặt sẵn. Khi đọc ký hiệu “ ; bộ phân tích từ vựng sinh một danh biểu String1 và String1 lưu giử chuỗi kết thúc bằng ký hiệu ”. Đó là chuỗi “Xin Chào ” có cả khoảng trắng. Trong quá trình phân tích từ vựng các khoảng trắng (blank) sẽ bị bỏ qua. 1.2.2. Phân tích cú pháp Giai đoạn phân tích cú pháp thực hiện công việc xem chuỗi token có thể sinh ra từ văn phạm cho trước không. Đó cũng là quá trình xây dựng cây phân tích cho chuỗi token. Thông thường, các ngữ đoạn văn phạm này được biểu diễn bằng dạng cây phân tích cú pháp với : - Ngôn ngữ được đặc tả bởi các luật sinh. - Phân tích cú pháp dựa vào luật sinh để xây dựng cây phân tích cú pháp. Ví dụ 1.2: Giả sử ngôn ngữ đặc tả bởi các luật sinh sau: Stmt → id := expr expr → expr + expr | expr * expr | id | number Với câu nhập: position := initial + rate * 10, cây phân tích cú pháp được xây dựng như sau : Trang 5
Stmt | id := expr position expr + expr | | id expr * expr | | | initial id number | | rate 10 Hình 1.3 - Cây phân tích cú pháp Ví dụ 1.3: 1) Danh biểu (identifier) là một biểu thức (expr). 2) Số (number) là một biểu thức. 3) Nếu expr1 và expr2 là các biểu thức thì: expr1+ xpr2, expr1* xpr2, (expr) được xem là biểu thức Câu lệnh (statement) cũng có thể định nghĩa đệ qui : 1) Nếu id1 là một danh biểu và expr2 là một biểu thức thì id1 := expr2 là một lệnh (stmt). 2) Nếu expr1 là một biểu thức và stmt2 là một lệnh thì while (expr1) do stmt2 if (expr1) then stmt2 đều là các lệnh. Người ta dùng các qui tắc đệ qui như trên để đặc tả luật sinh (production) cho ngôn ngữ. Sự phân chia giữa quá trình phân tích từ vựng và phân tích cú pháp cũng tùy theo công việc thực hiện. 1.2.3. Phân tích ngữ nghĩa Giai đoạn phân tích ngữ nghĩa sẽ thực hiện việc kiểm tra xem chương trình nguồn có chứa lỗi về ngữ nghĩa hay không và tập hợp thông tin về kiểu cho giai đoạn sinh mã về sau. Một phần quan trọng trong giai đoạn phân tích ngữ nghĩa là kiểm tra kiểu và ép chuyển đổi kiểu. Ví dụ 1.4: Trong biểu thức position := initial + rate * 10 Các danh biểu (tên biến) được khai báo là real, 10 là số integer vì vậy trình biên dịch đổi số nguyên 10 thành số thực 10.0 Trang 6
:= := thành position + position + initial * initial * rate rate inttoreal 1 0 10.0 Hình 1.4 - Chuyển đổi kiểu trên cây phân tích cú pháp 1.3. Các giai đoạn của trình biên dịch Ðể dễ hình dung, một trình biên dịch được chia thành các giai đoạn, mỗi giai đoạn chuyển chương trình nguồn từ một dạng biểu diễn này sang một dạng biểu diễn khác. Một cách phân rã điển hình trình biên dịch được trình bày trong hình sau. Chương trình nguồn Phân tích từ vựng Quản Phân tích cú pháp lý Xử các Phân tích ngữ nghĩa lý bảng lỗi ký Sinh mã trung gian hiệu Tối ưu mã trung gian Sinh mã đích Chương trình đích Hình 1.5 - Các giai đoạn trình biên dịch Trang 7
Các giai đoạn mà chúng ta đề cập ở trên là thực hiện theo trình tự logic của một trình biên dịch. Nhưng trong thực tế, cài đặt các hoạt động của nhiều hơn một giai đoạn có thể được nhóm lại với nhau. Thông thường chúng được nhóm thành hai nhóm cơ bản, gọi là: kỳ đầu (Front end) và kỳ sau (Back end). 1.3.1. Kỳ đầu Kỳ đầu bao gồm các giai đoạn hoặc các phần giai đoạn phụ thuộc nhiều vào ngôn ngữ nguồn và hầu như độc lập với máy đích. Thông thường, nó chứa các giai đoạn sau: phân tích từ vựng, phân tích cú pháp, phân tích ngữ nghĩa và sinh mã trung gian. 1.3.2. Kỳ sau Kỳ sau bao gồm một số phần nào đó của trình biên dịch phụ thuộc vào máy đích và nói chung các phần này không phụ thuộc vào ngôn ngữ nguồn mà là ngôn ngữ trung gian. Trong kỳ sau, chúng ta gặp một số vấn đề tối ưu hoá mã, phát sinh mã đích cùng với việc xử lý lỗi và các thao tác trên Bảng danh biểu. Ví dụ 1.5 : các giai đoạn biên dịch một biểu thức Sáu giai đoạn biên dịch cho biểu thức position := initial + rate * 10. position := initial + rate * 10 Giai đoạn 1- phân tích từ vựng id1 := id2 + id3 * 10 Giai đoạn 2- phân tích cú pháp Giai đoạn 3 - phân tích ngữ nghĩa id1 := id2 + id3 * 10 := := position + position + initial * initial * rate inttoreal rate 10 10.0 Hình 1.7 - Minh họa giai đoạn biên dịch một biểu thức Trang 8
Giai đoạn 4 - Sinh mã trung gian t1 := inttoreal (10) t2:= id3 * t1 t3 := id2 + t2 id1 := t3 Giai đoạn 5 - Tối ưu hóa mã t1 := id3 * 10.0 id1 := id2 + t1 Giai đoạn 6 - Phát sinh mã đích MOVF id3, R2 MULF #10.0, R2 MOVF id2, R1 ADDF R2, R1 MOVF R1, id1 Trang 9
BÀI TẬP CHƢƠNG 1: 1. Bạn hãy lập bảng danh biểu được cài đặt sẵn (từ khóa, danh biểu, toán tử, dấu câu, hằng, chuỗi, ) của một ngôn ngữ lập trình họ Pascal, một ngôn ngữ lập trình họ C, một ngôn ngữ lập trình họ Basic, một ngôn ngữ lập trình họ Java. 2. Với mỗi ngôn ngữ đã lập bảng danh biểu được cài đặt sẵn, hãy viết một câu lệnh đúng và thực hiện hiểu sáu bước biên dịch ( bước 1: phân tích từ vựng; bước 2: phân tích cú pháp; bước 3: phân tích ngữ nghĩa; bước 4: sinh mã trung gian; bước 5: tối ưu hóa mã; bước 6: sinh mã đích). 3. Với mỗi ngôn ngữ đã lập bảng danh biểu được cài đặt sẵn, hãy viết một câu lệnh sai từ vựng và một câu lệnh sai cú pháp. Thực hiện hiểu sáu bước biên dịch. Chỉ ra nếu viết sai từ vựng và sai cú pháp thì thông báo lỗi xảy ra lúc nào, vì sao ? Bài thực hành chƣơng 1: Bạn hãy sử dụng ngôn ngữ lập trình Visual Basic 6.0 hay phiên bản mới hơn và tìm hiểu: Trang 10
1. Nhập lệnh và dùng tổ hợp phím Ctrl + Spacebar để trợ giúp nhập lệnh để không phạm lỗi từ vựng. 2. Tìm hiểu từ vựng của Visual Basic 6.0 3. Ghi ra các kinh nghiệm sử dụng và trên cơ sở này tự xây dựng phương pháp tìm hiểu thêm về các ngôn ngữ lập trình khác. Trang 11
CHƢƠNG II. PHÂN TÍCH TỪ VỰNG Nội dung chính: Chương này giúp cho bạn đọc hiểu vai trò của bộ phân tích từ vựng. Bộ vi xử lý của máy vi tính thực ra chỉ là máy nghiền số với tốc độ điện tử, chỉ biết hai bit 0 và 1, nôm na là có điện hay không có điện, và hai luật cho nó vận hành: Luật + và Luật -, nhân và chia là việc cộng hay trừ nhiều lần với số lần xác định rõ ràng. Để đưa số và luật cho nó nghiền cần thanh ghi với cấu trúc và cách thức vận hành riêng, với 2 mẫu: là lệnh hay dữ liệu, đều biểu diễn qua mẫu với tiền tố đầu xác định loại, tiền tố sau là giá trị. Người lập trình thiết kế một ứng dụng multimedia có video, âm thanh, hình ảnh, ký tự thì với bộ vi xử lý đều là một dãy bit 1001 .0110 Để biên dịch những gì lập trình viên tạo ra sang mã máy, việc đầu tiên mà trình biên dịch yêu cầu là lập trình viên phải hiểu từ vựng nào máy tính hiểu thông qua bảng danh biểu cài đặt sẵn (từ khóa, các tên hàm được cài đặt sẵn) trong ngôn ngữ lập trình, nếu không nhớ rõ thì ngôn ngữ lập trình hiện đại có module trợ giúp. Đây là bảng danh biểu được cài đặt sẵn với từ ngữ đã được định nghĩa. Bộ phân tích từ vựng chỉ thực hiện việc nhóm các ký tự nhập thành ra chuổi các từ ngữ (token), phân tích ngôn ngữ nguồn có bao nhiêu từ ngữ, từ ngữ nào đã được định nghĩa trước, từ ngữ nào người sử dụng định nghĩa. Kết thúc công việc của bộ phân tích từ vựng chính là hình thành được chuổi các từ ngữ (token), xác định được nó, hình thành bảng danh biểu người sử dụng định nghĩa (tên biến, tên hàm ), chuyển ký tự người dùng nhập sang dãy bit 01 10 Ngoài ra, chương này giúp bạn đọc hiểu việc thiết kế bộ phân tích từ vựng của thế hệ đi trước. Thiết kế bộ phân tích từ vựng chính là bước mở đường cho bài toán nhận dạng. Hiện nay, lập trình để nhận dạng dòng ký tự nguồn có bao nhiêu từ tố đã được thiết lập sẵn không còn quá khó, khó chăng là những bài toán khác như nhận dạng một bộ phận để tìm ra trong 1 cơ sở dữ liệu lớn như nhận dạng hình ảnh ( ví dụ bài toán nhận dạng vân tay, nhận dạng chuỗi gen), nhận dạng âm thanh. Nhưng trong thời kỳ đầu của vi tính, việc phải tính đến là tiết kiệm từng bit nhớ, tiết kiệm thời gian vận hành, đã là bài toán khó và đã nảy sinh các giải thuật thông minh. Nội dung chương này nêu hai vấn đề chính là giải thuật xử lý trong tình huống tiết kiệm từng bit nhớ, tiết kiệm thời gian dịch và việc dùng thuật toán định nghĩa ngôn ngữ, định nghĩa cú pháp để làm cơ sở cho việc nhận dạng thay vì như hiện nay lưu thành cơ sở dữ liệu các từ tố, các cấu trúc, các danh biểu xác định sẵn trong ngôn ngữ. Mục tiêu Giúp cho bạn đọc hiểu rằng máy vi tính chỉ hiểu ngôn ngữ nguồn với việc sử Trang 12
dụng từ ngữ đã được định nghĩa trước trong trình biên dịch, từ ngữ mà trình biên dịch giúp người sử dụng định nghĩa. Người sử dụng muốn sử dụng, đang sử dụng và sẽ sử dụng từ ngữ trong tiến trình trình biên dịch dịch mã nguổn sang mã đích và trong lúc mã đích vận hành rất quan trọng, với kết quả đúng sai rõ ràng ( từ ngữ dùng lập trình, từ ngữ phải nhập khi chương trình biên dịch xong và đang thực thi ). Bộ phân tích từ vựng tùy theo thiết kế riêng của từng ngôn ngữ lập trình, nếu xử lý thành công: sinh các bảng danh biểu lưu giử các từ mã theo mẫu (Tên_từ_mã; Loại_từ_mã ; Vị_trí_từ_mã ); hay chuỗi token; nếu xử lý không thành công thì thông báo lỗi. Giúp cho bạn đọc hiểu cách thiết kế bộ phân tích từ vựng nhận dạng máy ngôn ngữ nguồn với việc sử dụng từ ngữ đã được định nghĩa trước trong trình biên dịch, từ ngữ mà trình biên dịch giúp người sử dụng định nghĩa . Yêu cầu chung Đọc giả đã hiểu: - Về tiến trình xử lý thông tin với đầu vào – đầu ra. - Về tiến trình phân tích và thiết kế giải thuật. TÀI LIỆU THAM KHẢO CHƢƠNG 2: [1] Dƣơng Tuấn Anh (1986), “Giáo trình trình biên dịch” - NXB Đại Học Bách Khoa TPHCM [2] Phạm Hồng Nguyên, “Giáo trình Chương trình Dịch” - NXB Đại Học Quốc Gia Hà Nội [3] Phan Thị Tƣơi (2011), “Trình Biên Dịch” - (Trường Ðại học kỹ thuật Tp.HCM) - NXB Giáo dục [4] Automata and Formal Language. An Introduction – Dean Kelley – Prentice Hall, Englewood Cliffs, New Jersey 07632. [5] Compilers : Principles, Technique and Tools - Alfred V.Aho, Jeffrey D.Ullman - Addison - Wesley Publishing Company, 1986. [6] Compiler Design – Reinhard Wilhelm, Dieter Maurer - Addison – Wesley Publishing Company, 1996. [7] Design of Compilers : Techniques of Programming Language Translation - Karen A. Lemone - CRC Press, Inc, 1992. [8] Modern Compiler Implementation in C - Andrew W. Appel – Cambridge University Press, 1997. Trang 13
2.1.Vai trò của bộ phân tích từ vựng 2.1.1. Nhiệm vụ. Bộ phân tích từ vựng có nhiệm vụ là đọc các kí tự nhập vào từ chương trình nguồn và phân tích đưa ra danh sách các từ tố (từ vựng và phân loại cú pháp của nó) cùng một số thông tin thuộc tính, lưu vào một bảng tạm gọi là bảng danh biểu. Bộ phân tích từ vựng được thiết kế với hai ý tưởng: a. Xử lý hết từ ngữ đã nhập của nguôn ngữ nguồn lưu vào một bảng gọi là bảng danh biểu b. Hay xử lý từng từ ngữ đã nhập của nguôn ngữ nguồn, bộ phân tích từ vựng được thiết kế như một thủ tục được gọi bởi bộ phân tích cú pháp. Chương Bộ phân tích Bảng danh biểu Bộ phân tích trình nguồn từ vựng (kết quả) cú pháp Bảng ký hiệu (cài đặt sẵn) Hình 2.1a - Giao diện của bộ phân tích từ vựng Đầu ra của bộ phân tích từ vựng là danh sách các từ tố đã lưu vào một bảng tạm gọi là bảng danh biểu và là đầu vào cho phân tích cú pháp. Thực tế thì bộ phân tích cú pháp sẽ gọi lần lượt mỗi từ tố từ bộ phân tích để xử lý, chứ không gọi một lúc toàn bộ danh sách từ tố của cả chương trình nguồn. Khi nhận được yêu cầu lấy một từ tố tiếp theo từ bộ phân tích cú pháp, bộ phân tích từ vựng sẽ đọc kí tự vào và tra trong bảng danh biểu cài đặt sẵn cho đến khi đưa ra được một từ tố. Sự tương tác này được thể hiện như hình sau, trong đó bộ phân tích từ vựng được thiết kế như một thủ tục được gọi bởi bộ phân tích cú pháp, trả về một token khi được gọi. Trang 14
token Bộ phân tích Chương trình Bộ phân tích nguồn từ vựng cú pháp Lấy token kế Bảng ký hiệu (cài đặt sẵn) Hình 2.1 b- Giao diện của bộ phân tích từ vựng 2.1.2. Tiến trình phân tích từ vựng 1) Xóa bỏ kí tự không có nghĩa (các chú thích, dòng trống, kí hiệu xuống dòng, kí tự trống không cần thiết) Quá trình dịch sẽ xem xét tất cả các ký tự trong dòng nhập nên những ký tự không có nghĩa (khoảng trắng (blanks, tabs, newlines)) hoặc lời chú thích phải bị bỏ qua. Khi bộ phân tích từ vựng bỏ qua các khoảng trắng này thì bộ phân tích cú pháp không bao giờ quan tâm đến nó nữa. 2) Nhận dạng các kí hiệu: nhận dạng các từ tố. Ví dụ ghép các chữ số để được một số và sử dụng nó như một đơn vị trong suốt quá trình dịch. Đặt num là một token biểu diễn cho một số nguyên. Khi một chuỗi các chữ số xuất hiện trong dòng nhập thì bộ phân tích sẽ gửi cho bộ phân tích cú pháp num. Giá trị của số nguyên đã được chuyển cho bộ phân tích cú pháp như là một thuộc tính của token num. 3) Số hoá các kí hiệu: Do con số xử lý dễ dàng hơn các xâu, từ khoá, tên, nên xâu thay bằng số, các chữ số được đổi thành số thực sự biểu diễn trong máy. Các tên được cất trong danh sách tên, các xâu cất trong danh sách xâu, các chuỗi số trong danh sách hằng số. Các vấn đề của giai đoạn phân tích từ vựng Nhiều lý do để tách riêng giai đoạn phân tích từ vựng với giai đoạn phân tích cú pháp: 1. Thứ nhất, nó làm cho việc thiết kế đơn giản và dễ hiểu hơn. Chẳng hạn, bộ phân tích cú pháp sẽ không phải xử lý các khoảng trắng hay các lời chú thích nữa vì chúng đã được bộ phân tích từ vựng loại bỏ. 2. Hiệu quả của trình biên dịch cũng sẽ được cải thiện, nhờ vào một số chương trình xử lý chuyên dụng sẽ làm giảm đáng kể thời gian đọc dữ liệu từ chương trình Trang 15
nguồn và nhóm các token. 3. Tính đa tương thích (mang đi dễ dàng) của trình biên dịch cũng được cải thiện. Ðặc tính của bộ ký tự nhập và những khác biệt của từng loại thiết bị có thể được giới hạn trong bước phân tích từ vựng. Dạng biểu diễn của các ký hiệu đặc biệt hoặc là những ký hiệu không chuẩn, chẳng hạn như ký hiệu ( trong Pascal có thể được cô lập trong bộ phân tích từ vựng. 2.1.3. Từ vị, từ tố, mẫu Khi làm việc bộ phân tích từ vựng, ta sẽ sử dụng các thuật ngữ từ tố (thẻ từ, token), mẫu từ vựng (pattern) và trị từ vựng (lexeme) với nghĩa cụ thể như sau: 1) Từ tố (token) là các ký hiệu kết thúc trong văn phạm đối với một ngôn ngữ nguồn, chẳng hạn như: từ khóa, danh biểu, toán tử, dấu câu, hằng, chuỗi, - Đối với ngôn ngữ lập trình thì từ tố có thể được phân vào các loại sau: + từ khoá + tên của hằng, hàm, biến + số + xâu ký tự + các toán tử + các ký hiệu. Ví dụ 2.1: position := initial + 10 * rate ; Ta có các từ vựng position, :=, initial, +, 10, *, rate, ; Trong đó position, initial, rate là các từ vựng có cùng ý nghĩa cú pháp là các tên. := là phép gán + là phép cộng * là phép nhân 10 là một con số ; là dấu chấm phẩy Như vậy trong câu lệnh trên có 8 từ vựng thuộc 6 từ tố. Phân tích cú pháp sẽ làm việc trên các từ tố chứ không phải từ vựng, ví dụ như là làm việc trên khái niệm một số chứ không phải trên 5 hay 2; làm việc trên khái niệm tên chứ không phải là a, b hay c. 2) Trị từ vựng (lexeme) của một token là một chuỗi ký tự biểu diễn cho token đó. 3) 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 đó. Trang 16
Một số ví dụ về cách dùng của các thuật ngữ này được trình bày trong bảng sau: Token Trị từ vựng minh họa Mô tả của mẫu từ vựng const const const if if if relation , >, >= hoặc > hoặc >= id pi, count, d2 Mở đầu là chữ cái theo sau là chữ cái, chữ số num 3.1416, 0, 5 Bất kỳ hằng số nào literal “ hello ” Mọi chữ cái nằm giữa “ và “ ngoại trừ “ Bảng 2.1 - Các ví dụ về token 2.1.4. Thuộc tính của token Khi có nhiều mẫu từ vựng khớp với một trị từ vựng, bộ phân tích từ vựng trong trường hợp này phải cung cấp thêm một số thông tin khác cho các bước biên dịch sau đó. Do đó đối với mỗi token, bộ phân tích từ vựng sẽ đưa thông tin về các token vào các thuộc tính đi kèm của chúng. Các token có ảnh hưởng đến các quyết định phân tích cú pháp; các thuộc tính ảnh hưởng đến việc phiên dịch các thẻ từ. Token kết hợp với thuộc tính của nó tạo thành một bộ . Ví dụ 2.2 : Token và giá trị thuộc tính đi kèm của câu lệnh position := initial + rate*10 được viết như một dãy các bộ sau: Chú ý rằng 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. 2.1.5. Lỗi từ vựng Chỉ một số ít lỗi được phát hiện tại bước phân tích từ vựng, bởi vì bộ phân tích từ vựng có nhiều cách nhìn nhận chương trình nguồn. Ví dụ chuỗi fi được nhìn thấy lần đầu tiên trong một chương trình C với ngữ cảnh : fi ( a == f (x)) Bộ phân tích từ vựng không thể biết đây là lỗi không viết đúng từ khóa if hay một danh biểu chưa được khai báo. Vì fi là một danh biểu hợp lệ nên bộ phân tích từ vựng phải Trang 17
trả về một token và để một giai đoạn khác sau đó xác định lỗi. Tuy nhiên, trong một vài tình huống phải khắc phục lỗi để phân tích tiếp. Chiến lược đơn giản nhất là "phương thức hoảng sợ" (panic mode): Các ký tự tiếp theo sẽ được xóa ra khỏi chuỗi nhập còn lại cho đến khi tìm ra một token hoàn chỉnh. Kỹ thuật này đôi khi cũng gây ra sự nhầm lẫn cho giai đoạn phân tích cú pháp, nhưng nói chung là vẫn có thể sử dụng được. Một số chiến lược khắc phục lỗi khác là: 1. Xóa đi một ký tự dư. 2. Xen thêm một ký tự bị mất. 3. Thay thế một ký tự không đúng bằng một ký tự đúng. 4. Chuyển đổi hai ký tự kế tiếp nhau. 2.2. Lƣu trữ tạm thời trƣơng trình nguồn Việc đọc từng kí tự trong chương trình nguồn tốn một thời gian đáng kể nên nó ảnh hưởng tới tốc độ chương trình dịch. Để giải quyết vấn đề này, thiết kế đọc vào một lúc một chuỗi kí tự lưu trữ vào vùng nhớ tạm buffer. Nhưng việc đọc như vậy gặp khó khăn do không thể xác định được một chuỗi như thế nào thì chứa chọn vẹn 1 từ tố. Và phải phân biệt được một chuỗi như thế nào thì chứa chọn vẹn một từ tố.Có 2 phương pháp giải quyết như sau: 2.2.1. Cặp bộ đệm * Cấu tạo: - Chia buffer thành 2 nửa, mỗi nửa chứa N kí tự ( N = 1024, 4096, ). - Sử dụng 2 con trỏ dò tìm trong buffer: p1: (lexeme_ beginning) đặt tại vị trí đầu của một từ vị. p2: (forwar):di chuyển trên từng kí tự trong buffer để xác định từ tố. Mỗi lần đọc, N ký tự từ chương trình nguồn sẽ được đọc vào mỗi nửa bộ đệm bằng một lệnh đọc (read) của hệ thống. Nếu số ký tự còn lại trong chương trình nguồn ít hơn N thì một ký tự đặc biệt eof được đưa vào buffer sau các ký tự vừa đọc để báo hiệu chương trình nguồn đã được đọc hết. Sử dụng hai con trỏ dò tìm trong buffer. Chuỗi ký tự nằm giữa hai con trỏ luôn luôn là trị từ vựng hiện hành. Khởi đầu, cả hai con trỏ đặt trùng nhau tại vị trí bắt đầu của mỗi trị từ vựng. Con trỏ p1 (lexeme_beginning) - con trỏ bắt đầu trị từ vựng - sẽ giữ cố định tại vị trí này cho đến khi con trỏ p2 (forwar) - con trỏ tới - di chuyển qua từng ký tự trong buffer để xác định một token. Khi một trị từ vựng cho một token đã được xác định, con trỏ p1 dời lên trùng với p2 và bắt đầu dò tìm một trị từ vựng mới. Trang 18
E = M * C * * 2 EOF p1 p2 Hình 2.2 - Cặp hai nửa vùng đệm Khi con trỏ p2 tới ranh giới giữa 2 vùng đệm, nửa bên phải được lấp đầy bởi N ký tự tiếp theo trong chương trình nguồn. Khi con trỏ p2 tới vị trí cuối bộ đệm, nửa bên trái sẽ được lấp đầy bởi N ký tự mới và p2 sẽ được dời về vị trí bắt đầu bộ đệm. Phương pháp cặp bộ đệm này thường họat động rất tốt nhưng khi đó số lượng ký tự đọc trước bị giới hạn và trong một số trường hợp nó có thể không nhận dạng được token khi con trỏ p2 phải vượt qua một khoảng cách lớn hơn chiều dài vùng đệm. Giải thuật hình thức cho họat động của con trỏ p2 trong bộ đệm : if p2 ở cuối nửa đầu then begin Ðọc vào nửa cuối; p2 := p2 + 1; end else if p2 ở cuối của nửa cuối then begin Ðọc vào nửa đầu; Dời p2 về đầu bộ đệm ; end else p2 := p2 + 1 2.2.2. Khóa cầm canh Phương pháp cặp bộ đệm đòi hỏi mỗi lần di chuyển p2 đều phải kiểm tra xem có phải đã hết một nửa buffer chưa nên kém hiệu quả vì phải hai lần kiểm tra. Ðể khắc phục điều này, mỗi lần chỉ đọc N-1 ký tự vào mỗi nửa buffer còn ký tự thứ N là một ký tự đặc biệt, thường là eof. Như vậy chúng ta đã rút ngắn một lần kiểm tra. E = M * EOF C * * 2 EOF p1 p2 Hình 2.3 - Khóa cầm canh eof tại cuối mỗi vùng đệm Trang 19
Giải thuật hình thức cho họat động của con trỏ p2 trong bộ đệm : p2 := p2 + 1; if p2↑ = eof then begin if p2 ở cuối của nửa đầu then begin Ðọc vào nửa cuối; p2 := p2 + 1; end else if p2 ở cuối của nửa sau then begin Ðọc vào nửa đầu; Dời p2 vào đầu của nửa đầu; end else /* EOF ở giữa vùng đệm chỉ hết chương trình nguồn */ kết thúc phân tích từ vựng; end 2.3. Tính chất và nhận dạng token 2.3.1. Đặc tả token a. Chuỗi và ngôn ngữ Chuỗi là một tập hợp hữu hạn các ký tự. Ðộ dài chuỗi là số các ký tự trong chuỗi. Chuỗi rỗng ε là chuỗi có độ dài 0. Ngôn ngữ là tập hợp các chuỗi. Ngôn ngữ có thể chỉ bao gồm một chuỗi rỗng ký hiệu là ∅. b. Các phép toán trên ngôn ngữ - Hợp của L và M : L ∪ M = { s | s ∈ L hoặc s ∈ M } - Ghép (concatenation) của L và M: LM = { st | s ∈ L và t ∈ M } * ∞ i - Bao đóng Kleen của L: L = ∪i = 0 L (Ghép của 0 hoặc nhiều L) + ∞ i - Bao đóng dƣơng (positive closure) của L: L = ∪i = 1 L (Ghép của 1 hoặc nhiều L) Ví dụ 2.3: L = {A, B, , Z, a, b, , z } D = { 0, 1, , , 9 } Trang 20
1) L ∪ D là tập hợp các chữ cái và số. 2) LD là tập hợp các chuỗi bao gồm một chữ cái và một chữ số. 3) L4 là tập hợp tất cả các chuỗi 4 chữ cái. 4) L* là tâp hợp tất cả các chuỗi của các chữ cái bao gồm cả chuỗi rỗng. 5) L( L ∪ D)* là tập hợp tất cả các chuỗi mở đầu bằng một chữ cái theo sau là chữ cái hay chữ số 6) D+ là tập hợp tất cả các chuỗi gồm một hoặc nhiều chữ số. c. Biểu thức chính quy (Regular Expression) Trong Pascal, một danh biểu là một phần tử của tập hợp L (L ∪ D)*. Chúng ta có thể viết: danhbiểu = letter (letter | digit)* - Ðây là một biểu thức chính quy. Biểu thức chính quy được xây dựng trên một tập hợp các luật xác định. Mỗi biểu thức chính quy r đặc tả một ngôn ngữ L(r). Sau đây là các luật xác định biểu thức chính quy trên tập Alphabet ∑. 1) ε là một biểu thức chính quy đặc tả cho một chuỗi rỗng {ε }. 2) Nếu a ∈ ∑ thì a là biểu thức chính quy r đặc tả tập hợp các chuỗi {a} 3) Giả sử r và s là các biểu thức chính quy đặc tả các ngôn ngữ L(r) và L(s) ta có: a. (r) | (s) là một biểu thức chính quy đặc tả L(r) ∪ L(s) b. (r) (s) là một biểu thức chính quy đặc tả L(r)L(s). c. (r)* là một biểu thức chính quy đặc tả (L(r))* Quy ước: Toán tử bao đóng * có độ ưu tiên cao nhất và kết hợp trái. Toán tử ghép có độ ưu tiên thứ hai và kết hợp trái. Toán tử hợp | có độ ưu tiên thấp nhất và kết hợp trái. Ví dụ 2.4: Cho ∑ = { a, b} 1) Biểu thức chính quy a | b đặc tả {a, b} 2) Biểu thức chính quy (a | b) (a | b) đặc tả tập hợp {aa, ab, ba, bb}.Tập hợp này có thể được đặc tả bởi biểu thức chính quy tương đương sau: aa | ab | ba | bb. 3) Biểu thức chính quy a* đặc tả { ε, a, aa, aaa, } 4) Biểu thức chính quy (a | b)* đặc tả {(, a, b, aa,bb, }. Tập này có thể đặc tả bởi (a*b* )*. 5) Biểu thức chính quy a | a* b đặc tả {a, b, ab, aab, } Hai biểu thức chính quy cùng đặc tả một tập hợp ta nói rằng chúng tương đương và viết r = s. Trang 21
d. Các tính chất đại số của biểu thức chính quy Biểu thức chính quy cũng tuân theo một số luật đại số và có thể dùng các luật này để biến đổi biểu thức thành những dạng tương đương. Bảng sau trình bày một số luật đại số cho các biểu thức chính quy r, s và t. Tính chất Mô tả r | s = s | r | có tính chất giao hoán r | (s | t) = (r | s ) | t | có tính chất kết hợp (rs) t = r (st) Phép ghép có tính chất kết hợp r (s | t) = rs | rt Phép ghép phân phối đối với phép | (s | t) r = sr | tr εr = r ε là phần tử đơn vị của phép ghép rε = r Quan hệ giữa r và ε r* = ( r | ε )* * có hiệu lực như nhau r* * = r * Bảng 2.3 - Một số tính chất đại số của biểu thức chính quy e. Ðịnh nghĩa chính quy (Regular Definitions) Ðịnh nghĩa chính quy là một chuỗi các định nghĩa có dạng : d1 → r1 di là một tên, d2 → r2 ri là một biểu thức chính quy. dn → rn Ví dụ 2.5: Tập hợp các danh biểu trong Pascal là một tập hợp các chuỗi chữ cái và số, mở đầu bằng một chữ cái. Ðịnh nghĩa chính quy của tập đó là: letter → A | B | | Z | a | b | | z digit → 0 | 1 | | 9 id → letter (letter | digit)* Ví dụ 2.6 : Các số không dấu trong Pascal là các chuỗi 5280, 39.37, 6.336E4 hoặc 1.894E-4. Ðịnh nghĩa chính quy sau đặc tả tập các số này là : digit → 0 | 1 | | 9 digits → digit digit* optional_fraction → . digits | ε optional_exponent → ( E ( + | - | ε ) digits) | ε num → digits optional_fraction optional_exponent Trang 22
f. Ký hiệu viết tắt Người ta quy định các ký hiệu viết tắt cho thuận tiện trong việc biểu diễn như sau: 1. Một hoặc nhiều: dùng dấu + 2. Không hoặc một: dùng dấu ? Ví dụ 2.7 : r | ε được viết tắt là r ? Ví dụ 2.8 : Viết tắt cho định nghĩa chính quy tập hợp số num trong ví dụ 3.5 digit → 0 | 1 | | 9 digits → digit + optional_fraction → ( .digits ) ? optional_exponent → ( E ( + | - ) ? digits) ? num → digits optional_fraction optional_exponent 3. Lớp ký tự [abc] = a | b | c [a - z] = a | b | | z Sử dụng lớp ký hiệu chúng ta có thể mô tả danh biểu như là một chuỗi sinh ra bởi biểu thức chính quy : [A - Z a - z] [A - Z a - z 0 - 9]* 2.3.2. Nhận dạng token Trong suốt phần này, chúng ta sẽ dùng ngôn ngữ được tạo ra bởi văn phạm dưới đây làm thí dụ minh họa : stmt → if expr then stmt | if expr then stmt else stmt | ε expr → term relop term | term term → id | num Trong đó các ký hiệu kết thúc if, then, else, relop, id, num được cho bởi định nghĩa chính quy sau: if → if then → then else → else relop → | > | >= id → letter (letter | digit) * num → digit + ( . digit +) ? (E (+ | -) ? digit +) ? Ðịnh nghĩa chính quy của các khoảng trắng ws (white space) Trang 23
delim → blank | tab | newline ws → delim+ Mục đích của chúng ta là xây dựng một bộ phân tích từ vựng có thể định vị được từ tố cho các token kế tiếp trong vùng đệm và tạo ra output là một cặp token thích hợp và giá trị thuộc tính của nó bằng cách dùng mẫu biểu thức chính quy cho các token như sau: Biểu thức chính quy Token Trị thuộc tính ws - - if if - then then - else else - id id con trỏ trong bảng danh biểu num num giá trị số relop NE (Not Equal) > relop GT (Greater Than) >= relop GE (Greater Or Equal) Bảng 2.4. - Mẫu biểu thức chính quy cho một số token a. Sơ đồ dịch Ðể dễ dàng nhận dạng token, chúng ta xây dựng cho mỗi token một sơ đồ dịch (translation diagram). Sơ đồ dịch bao gồm các trạng thái (state) ký hiệu bởi vòng tròn và các cạnh mũi tên nối các trạng thái. Nói chung thường có nhiều sơ đồ dịch, mỗi sơ đồ đặc tả một nhóm token. Nếu xảy ra thất bại khi chúng ta đang đi theo một sơ đồ dịch thì chúng ta dịch lui con trỏ tới về nơi nó đã ở trong trạng thái khởi đầu của sơ đồ này rồi kích họat sơ đồ dịch tiếp theo. Do con trỏ đầu trị từ vựng và con trỏ tới cùng chỉ đến một vị trí trong trạng thái khởi đầu của sơ đồ, con trỏ tới sẽ được dịch lui lại để chỉ đến vị trí được con trỏ đầu trị từ vựng chỉ tới. Nếu xảy ra thất bại trong tất cả mọi sơ đồ dịch thì xem như một lỗi từ vựng đã được phát hiện và chúng ta sẽ khởi động một thủ tục khắc phục lỗi. Trang 24
Phần dưới đây trình bày một số sơ đồ dịch nhận dạng các token trong văn phạm ví dụ trên. Sơ đồ dịch nhận dạng cho token relop: return( relop, NE ) 3 2 ≠ return( relop, LT ) = 4 * 5 return( relop, EQ ) > = 6 7 return( relop, NE ) ≠ 8 * return( relop, GT ) Hình 2.4 - Sơ đồ dịch cho các toán tử quan hệ Chúng ta dùng ký hiệu * để chỉ ra những trạng thái mà chúng ta đã đọc quá một ký tự, cần phải quay lui con trỏ lại. Sơ đồ dịch nhận dạng token id: Letter or digit Start letter other 9 10 11 1 Hình 2.5 - Sơ đồ dịch cho các danh biểu và từ khóa Một kỹ thuật đơn giản để tách từ khóa ra khỏi các danh biểu là khởi tạo bảng danh biểu lưu trữ thông tin về danh biểu một cách thích hợp. Ðối với các token cần nhận dạng. Trong văn phạm này, chúng ta cần nhập các chuỗi if, then và else vào bảng danh biểu trước khi đọc các ký hiệu trong bộ đệm nguyên liệu. Ðồng thời ghi chú trong bảng danh biểu để trả về token đó khi một trong các chuỗi này được nhận ra. Sử dụng các hàm gettoken( ) và install_id( ) tương ứng để nhận token và các thuộc tính trả về. Sơ đồ dịch nhận dạng token num: Một số vấn đề sẽ nảy sinh khi chúng ta xây dựng bộ nhận dạng cho các số Trang 25
không dấu. Trị từ vựng cho một token num phải là trị từ vựng dài nhất có thể được. Do đó, việc thử nhận dạng số trên các sơ đồ dịch phải theo thứ tự từ sơ đồ nhận dạng số dài nhất. digit digit digit * start digit . digit E + or - digit other 12 13 14 15 16 17 18 19 2 digit digit start digit . digit other 20 21 22 23 24 * digit start digit other 25 26 27 * Hình 2.6 - Sơ đồ dịch cho các số không dấu trong Pascal Có nhiều cách để tránh các đối sánh dư thừa trong các sơ đồ dịch trên. Một cách là viết lại các sơ đồ dịch bằng cách tổ hợp chúng thành một - một công việc nói chung là không đơn giản lắm. Một cách khác là thay đổi cách đáp ứng với thất bại trong qua trình duyệt qua một sơ đồ. Phương pháp được sử dụng ở đây là cho phép ta vượt qua nhiều trạng thái kiểm nhận và quay trở lại trạng thái kiểm nhận cuối cùng đã đi qua khi thất bại xảy ra. Sơ đồ dịch nhận dạng khoảng trắng ws (white space): Việc xử lý các khoảng trắng ws không hoàn toàn giống như các mẫu nói trên bởi vì không có gì để trả về cho bộ phân tích cú pháp khi tìm thấy các khoảng trắng trong chuỗi nhập. Và do đó, thao tác đơn giản cho việc dò tìm trên sơ đồ dịch khi phát hiện khoảng trắng là trở lại trạng thái bắt đầu của sơ đồ dịch đầu tiên để tìm một mẫu khác. delim start delim other 28 29 30 * 7 2 Hình 2.7 - Sơ đồ dịch cho các khoảng trắng Trang 26
b. Cài đặt một sơ đồ dịch Dãy các sơ đồ dịch có thể được chuyển thành một chương trình để tìm kiếm token được đặc tả bằng các sơ đồ. Mỗi trạng thái tương ứng với một đoạn mã chương trình. Nếu có các cạnh đi ra từ trạng thái thì đọc một ký tự và tùy thuộc vào ký tự đó mà đi đến trạng thái khác. Ta dùng hàm nextchar( ) đọc một ký tự từ trong bộ đệm input và con trỏ p2 di chuyển sang phải một ký tự. Nếu không có một cạnh đi ra từ trạng thái hiện hành phù hợp với ký tự vừa đọc thì con trỏ p2 phải quay lại vị trí của p1 để chuyển sang sơ đồ dịch kế tiếp. Hàm fail( ) sẽ làm nhiệm vụ này. Nếu không có sơ đồ nào khác để thử, fail( ) sẽ gọi một thủ tục khắc phục lỗi. Ðể trả về các token, chúng ta dùng một biến tòan cục lexical_value. Nó được gán cho các con trỏ được các hàm install_id( ) và install_num( ) trả về, tương ứng khi tìm ra một danh biểu hoặc một số. Lớp token được trả về bởi thủ tục chính của bộ phân tích từ vựng có tên là nexttoken( ). int state = 0, start = 0; int lexical_value; /* để “trả về” thành phần thứ hai của token */ int fail ( ) { forward = token_beginning; switch (start) { case 0 : start = 9; break; case 9 : start = 12; break; case 12 : start = 20; break; case 20 : start = 25; break; case 25 : recover ( ); break; default : / * lỗi trình biên dịch */ } return start; } token nexttoken ( ) { while (1) { switch (state) { Trang 27
case 0 : c = nextchar ( ) ; / * c là ký hiệu đọc trước */ if ( c = = blank || c = = tab || c = = newline ) { state = 0; lexeme_beginning ++ ; / * dịch con trỏ đến đầu trị từ vựng */ } else if (c = = „ ‟) state = 6; else state = fail ( ) ; break ; / * các trường hợp 1- 8 ở đây */ case 9 : c = nextchar ( ) ; if (isletter (c)) state=10; else state = fail ( ) ; break ; case 10 : c = nextchar ( ) ; if (isletter (c)) state=10; else if (isdigit(c)) state = 10 ; else state = 11 ; break ; case 11 : retract (1) ; install_id ( ) ; return (gettoken ( )); / * các trường hợp 12 - 24 ở đây */ case 25 : c = nextchar ( ) ; if (isdigit (c)) state=26; else state = fail ( ) ; break ; case 26 : c = nextchar ( ) ; if (isdigit (c)) state=26; else state = 27 ; break ; case 27 : retract (1) ; install_num ( ) ; return (NUM); } } } Trang 28
2.4. Các bƣớc để xây dựng bộ phân tích từ vựng. Các bước tuần tự nên tiến hành để xây dựng được một bộ phân tích từ vựng tốt, hoạt động chính xác và dễ cải tiến, bảo hành, bảo trì. 1) Xác định các luật từ tố, các luật này được mô tả bằng lời. 2) Vẽ đồ thị chuyển cho từng mẫu một, trước đó có thể mô tả bằng biểu thức chính qui để tiện theo dõi và chỉnh sửa, và dễ dàng cho việc dựng đồ thị chuyển. 3) Kết hợp các luật này thành một đồ thị chuyển duy nhất. 4) Chuyển đồ thị chuyển thành bảng. 5) Xây dựng chương trình. 6) Bổ sung thêm phần báo lỗi để thành bộ phân tích từ vựng hoàn chỉnh. 2.5. Ngôn ngữ và đặc tả cho bộ phân tích từ vựng 2.5.1. Bộ sinh bộ phân tích từ vựng Có nhiều công cụ để xây dựng bộ phân tích từ vựng dựa vào các biểu thức chính quy. Lex là một công cụ được sử dụng rộng rãi để tạo bộ phân tích từ vựng. Trước hết đặc tả cho một bộ phân tích từ vựng được chuẩn bị bằng cách tạo ra một chương trình lex.l trong ngôn ngữ lex. Trình biên dịch Lex sẽ dịch lex.l thành một chương trình C là lex.yy.c. Chương trình này bao gồm các đặc tả về sơ đồ dịch được xây dựng từ các biểu thức chính quy của lex.l, kết hợp với các thủ tục chuẩn nhận dạng trị từ vựng. Các hành vi kết hợp với biểu thức chính quy trong lex.l là các đoạn chương trình C được chuyển sang lex.yy.c. Cuối cùng trình biên dịch C sẽ dịch lex.yy.c thành chương trình đối tượng a.out, đó là bộ phân tích từ vựng có thể chuyển dòng nhập thành chuỗi các token. Chương trình nguồn của lex: Lex Compiler Lex.yy.c lex.l C Compiler a.out a.out Chuỗi các Chuỗi nhập token Hình 2.8- Tạo ra bộ phân tích từ vựng bằng Lex Chú ý: Những điều ta nói trên là nói về lex trong UNIX. Ngày nay có nhiều version của lex như Lex cho Pascal hoặc Javalex. Trang 29
2.5.2. Ðặc tả lex Một chương trình lex bao gồm 3 thành phần: Khai báo %% Quy tắc dịch %% Các thủ tục phụ Phần khai báo bao gồm khai báo biến, hằng và các định nghĩa chính quy. Phần quy tắc dịch cho các lệnh có dạng: p1 {action 1 } p2 {action 2 } . . . pn {action n } Trong đó pi là các biểu thức chính quy, action i là đoạn chương trình mô tả hành động của bộ phân tích từ vựng thực hiện khi pi tương ứng phù hợp với trị từ vựng. Trong lex các đoạn chương trình này được viết bằng C nhưng nói chung có thể viết bằng bất cứ ngôn ngữ nào. Các thủ tục phụ là sự cài đặt các hành động trong phần 2. Ví dụ 3.8: Sau đây trình bày một chương trình Lex nhận dạng các token của văn phạm đã nêu ở phần trước và trả về token được tìm thấy. %{ /* định nghĩa các hằng LT, LE, EQ, NE, GT, GE, IF, THEN, ELSE, ID, NUMBER, RELOP */ }% /* định nghĩa chính quy */ delim [\t\n] ws {delim}+ letter [A - Za - z] digit [0 - 9] id {letter}({letter}| {digit})* number {digit}+(\.{digit}+)?(E[+\-]?{digit}+)? %% {ws} {/* Không có action, không có return */} if {return(IF); } then {return(THEN); } Trang 30
else {return(ELSE); } {id} {yylval = install_id( ); return(ID) } {number} {yylval = install_num( ); return(NUMBER) } “ “ {yylval = NE; return(RELOP) } “> “ {yylval = GT; return(RELOP) } “>= “ {yylval = GE; return(RELOP) } %% install_id ( ) { /* Thủ tục phụ cài id vào trong Bảng danh biểu */ } install_num ( ) { /* Thủ tục phụ cài một số vào trong Bảng danh biểu */ } Trang 31
BÀI TẬP CHƢƠNG II- PHÂN TÍCH TỪ VỰNG 2.1. Viết chỉ thị máy ảo kiểu Stack cho quá trình dịch các biểu thức sau sang dạng hậu tố: a) y := a + 2013 b3c b) t : = a div b + ( c -2012 * d ) mod 2013 / 3 c) t : = (a mod b) * 2010 - (2011 * c +2012 ) div 4 +2013 2.2. Cho văn phạm phi ngữ cảnh sau: T → T T + | T T * | a a) Viết các luật sinh dẫn ra câu nhập: a a + a * b) Xây dựng một cây phân tích cú pháp cho câu nhập trên. c) Văn phạm này sinh ra ngôn ngữ gì? Giải thích câu trả lời. Bài tập nâng cao- phần này mời quý bạn đọc xem thêm chương 2, chương 3 giáo trình chương trình dịch, tác giả Phạm Hồng Nguyên, NXB đại học Quốc Gia Hà Nội. 2.3. Xác định bộ chữ cái của các ngôn ngữ sau: a) Pascal b) C c) LISP 2.4. Viết một thủ tục phân tích từ vựng 2.5. Chuyển đổi từ SLANG sang VIM Trang 32
CHƢƠNG III. PHÂN TÍCH CÚ PHÁP Nội dung chính: Chương này giúp bạn đọc hiểu vai trò của bộ phân tích cú pháp, trái tim của trình biên dịch. Chỉ ra bằng cách nào trình biên dịch hiểu được và chuyển sang mã máy được các giải thuật của người lập trình trong mã nguồn một ứng dụng. Biên dịch một mã nguồn một ứng dụng không phải là việc biên dịch từ sang từ. Trong mã nguồn của người lập trình biên soạn phần lớn là các chỉ thị (lệnh) cho máy vi tính thực hiện. Bằng sự thỏa thuận giữa người lập trình và trình biên dịch, dù công việc tính toán (xử lý) phức tạp đến đâu thì người lập trình củng phải sử dụng những cấu trúc lệnh được quy định sẵn của ngôn ngữ lập trình đang được người lập trình sử dụng. Bộ phân tích cú pháp của trình biên dịch xem xét các từ tố mang chỉ thị của người sử dụng viết trong mã nguồn, phân rã nó ra và đưa vào các cấu trúc định sẵn này, việc thiết lập ra cấu trúc định sẵn này chính là nội dung Bộ phân tích cú pháp. Mục tiêu Giúp cho bạn đọc hiểu cách thiết kế ra cấu trúc định sẵn này chính là nội dung Bộ phân tích cú pháp. Yêu cầu chung Độc giả phải có các kiến thức cơ bản của các học phần như ngôn ngữ lập trình: hiểu và nhận dạng được trình biên dịch; cấu trúc máy tính: hiểu trình biên dịch chạy trên môi trường nào; lý thuyết ngôn ngữ: hiểu trình biên dịch minh họa cho cái gì, mục đích gì; cấu trúc dữ liệu: hiểu các dữ liệu cài đặt sẵn của 1 trình biên dịch; phân tích thiết kế giải thuật và công nghệ phần mềm: hiểu cách thức tạo ra một ứng dụng gọi là trình biên dịch một cách bài bản. TÀI LIỆU THAM KHẢO: [1] Dƣơng Tuấn Anh (1986), “Giáo trình trình biên dịch” - NXB Đại Học Bách Khoa TPHCM [2] Phạm Hồng Nguyên, “Giáo trình Chương trình Dịch” - NXB Đại Học Quốc Gia Hà Nội [3] Phan Thị Tƣơi (2011), “Trình Biên Dịch” - (Trường Ðại học kỹ thuật Tp.HCM) - NXB Giáo dục [4] Automata and Formal Language. An Introduction – Dean Kelley – Prentice Hall, Englewood Cliffs, New Jersey 07632. Trang 33
[5] Compilers : Principles, Technique and Tools - Alfred V.Aho, Jeffrey D.Ullman - Addison - Wesley Publishing Company, 1986. [6] Compiler Design – Reinhard Wilhelm, Dieter Maurer - Addison – Wesley Publishing Company, 1996. [7] Design of Compilers : Techniques of Programming Language Translation - Karen A. Lemone - CRC Press, Inc, 1992. [8] Modern Compiler Implementation in C - Andrew W. Appel – Cambridge University Press, 1997 Trang 34
3.1. Phƣơng pháp phân tích cú pháp 3.1.1. Vai trò của bộ phân tích cú pháp Phân tích cú pháp nhận đầu vào là danh sách các từ tố của chương trình nguồn thành các thành phần theo văn phạm và biểu diễn cấu trúc này bằng cây phân tích hoặc theo một cấu trúc nào đó tương đương với cây. Biểu Cây diễn Chương Lấy Phân trung trình từ tố Phân tích Phân tích tích Phân tích gian nguồn từ vựng cú pháp ngữ nghĩa từ tố Bảng ký hiệu Hình 3.1 - Vị trí của bộ phân tích cú pháp trong mô hình trình biên dịch 3.1.1.1. Xử lý lỗi cú pháp Chương trình nguồn có thể chứa các lỗi ở nhiều mức độ khác nhau: - Lỗi từ vựng như danh biểu, từ khóa, toán tử viết không đúng. - Lỗi cú pháp như ghi một biểu thức toán học với các dấu ngoặc đóng và mở không cân bằng. - Lỗi ngữ nghĩa như một toán tử áp dụng vào một toán hạng không tương thích. - Lỗi logic như thực hiện một lời gọi đệ qui không thể kết thúc. Phần lớn việc phát hiện và phục hồi lỗi trong một trình biện dịch tập trung vào giai đoạn phân tích cú pháp. Vì thế, bộ xử lý lỗi (error handler) trong quá trình phân tích cú pháp phải đạt mục đích sau: Ghi nhận và thông báo lỗi một cách rõ ràng và chính xác. Phục hồi lỗi một cách nhanh chóng để có thể xác định các lỗi tiếp theo. Không làm chậm tiến trình của một chương trình đúng. Trang 35
3.1.1.2. Các chiến lƣợc phục hồi lỗi Phục hồi lỗi là kỹ thuật vượt qua các lỗi để tiếp tục quá trình dịch. Nhiều chiến lược phục hồi lỗi có thể dùng trong bộ phân tích cú pháp. Mặc dù không có chiến lược nào được chấp nhận hoàn toàn, nhưng một số trong chúng đã được áp dụng rộng rãi. Ở đây, chúng ta giới thiệu một số chiến lược : a. Phƣơng thức "hoảng sợ" (panic mode recovery): Ðây là phương pháp đơn giản nhất cho cài đặt và có thể dùng cho hầu hết các phương pháp phân tích. Khi một lỗi được phát hiện thì bộ phân tích cú pháp bỏ qua từng ký hiệu một cho đến khi tìm thấy một tập hợp được chỉ định của các token đồng bộ (synchronizing tokens), các token đồng bộ thường là dấu chấm phẩy (;) hoặc end. b. Chiến lƣợc mức ngữ đoạn (phrase_level recovery): Khi phát hiện một lỗi, bộ phân tích cú pháp có thể thực hiện sự hiệu chỉnh cục bộ trên phần còn lại của dòng nhập. Cụ thể là thay thế phần đầu còn lại bằng một chuỗi ký tự có thể tiếp tục. Chẳng hạn, dấu phẩy (,) bởi dấu chấm phẩy (;), xóa một dấu phẩy lạ hoặc thêm vào một dấu chấm phẩy. c. Chiến lƣợc dùng các luật sinh sửa lỗi (error production): Thêm vào văn phạm của ngôn ngữ những luật sinh lỗi và sử dụng văn phạm này để xây dựng bộ phân tích cú pháp, chúng ta có thể sinh ra bộ đoán lỗi thích hợp để chỉ ra cấu trúc lỗi được nhận biết trong dòng nhập. d. Chiến lƣợc hiệu chỉnh toàn cục (global correction): Một cách lý tưởng là trình biên dịch tạo ra một số thay đổi trong khi xử lý một lỗi. Có những giải thuật để lựa chọn một số tối thiểu các thay đổi để đạt được một hiệu chỉnh có chi phí toàn cục nhỏ nhất. Cho một chuỗi nhập có lỗi x và một văn phạm G, các giải thuật này sẽ tìm được một cây phân tích cú pháp cho chuỗi y mà số lượng các thao tác chèn, xóa và thay đổi token cần thiết để chuyển x thành y là nhỏ nhất. Nói chung, hiện nay kỹ thuật này vẫn còn ở dạng nghiên cứu lý thuyết. 3.1.2. Văn phạm phi ngữ cảnh Nhiều ngôn ngữ lập trình có cấu trúc đệ quy mà nó có thể được định nghĩa các văn phạm phi ngữ cảnh (context-free grammar) G với 4 thành phần G (V, T, P, S), trong đó: Trang 36
• 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). Ví dụ 3.1: Văn phạm với các luật sinh sau cho phép định nghĩa các biểu thức số học đơn giản: E → E A E| (E) |- E | id A → + | - | * | / | ↑ 3.1.2.1. Cây phân tích cú pháp và dẫn xuất * Định nghĩa: Cây phân tích trong một văn phạm phi ngữ cảnh G = (V,T,P,S) là một cây thỏa mãn các điều kiện sau: 1) Mọi nút có một nhãn, là một ký hiệu trong (V  T  {ε}) 2) Nhãn của gốc là S 3) Nếu một nút có nhãn X là một nút trong thì X T 4) Nếu nút n có nhãn X và các nút con của nó theo thứ tự trái qua phải có nhãn Y1, Y2, . . ., Yk thì X->Y1Y2 . . . Yk sẽ là một sản xuất P 5) Nút lá có nhãn thuộc V hoặc là ε * Suy dẫn trái nhất (nói gọn là suy dẫn trái), nếu ở mỗi bước suy dẫn, biến được thay thế là biến nằm bên trái nhất trong dạng câu. * Suy dẫn phải nhất: (nói gọn là suy dẫn phải), nếu ở mỗi bước suy dẫn, biến được thay thế là biến nằm bên phải nhất trong dạng câu. Cây phân tích cú pháp có thể được xem như một dạng biểu diễn hình ảnh của dẫn xuất. Ta nói rằng αAβ dẫn xuất ra αγβ (ký hiệu: αAβ αγβ) nếu A → γ là 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. Ta có tính chất: 1. α * α với α 2. α * β và β * γ thì α * γ Cho một văn phạm G với ký hiệu bắt đầu S. Ta dùng quan hệ + để định nghĩa L(G) một ngôn ngữ được sinh ra bởi G. Chuỗi trong L(G) có thể chỉ chứa một ký Trang 37
hiệu kết thúc của G. Chuỗi các ký hiệu kết thúc w thuộc L(G) nếu và chỉ nếu S + w, chuỗi w được gọi là một câu của G. Một ngôn ngữ được sinh ra bởi một văn phạm gọi là ngôn ngữ phi ngữ cảnh. Nếu hai văn phạm cùng sinh ra cùng một ngôn ngữ thì chúng được gọi là hai văn phạm tương đương. Nếu S * α, trong đó α có thể chứa một ký hiệu chưa kết thúc thì ta nói rằng α là một dạng câu (sentential form) của G. Một câu là một dạng câu có chứa toàn các ký hiệu kết thúc. Một cây phân tích cú pháp có thể xem như một biểu diễn đồ thị cho một dẫn xuất. Ðể hiểu được bộ phân tích cú pháp làm việc ta cần xét dẫn xuất trong đó chỉ có ký hiệu chưa kết thúc trái nhất trong bất kỳ dạng câu nào được thay thế tại mỗi bước, dẫn xuất như vậy được gọi là trái nhất. Nếu α β trong đó ký hiệu chưa kết thúc trái nhất trong α được thay thế, ta viết α *lm β nếu S *lm α ta nói α là dạng câu trái của văn phạm. Tương tự, ta có dẫn xuất phải nhất - còn gọi là dẫn xuất chính tắc (canonical derivations). Ví dụ 3.2: Cây phân tích cú pháp cho chuỗi nhập : - (id + id) sinh từ văn phạm trong ví dụ 3.1 E E _ E ( ) | E + E | | id id Hình 3.2 - cây phân tích cú pháp Ðể thấy mối quan hệ giữa cây phân tích cú pháp và dẫn xuất, ta xét một dẫn xuất: α1 α2 αn trong đó αi là một ký hiệu chưa kết thúc A. Với mỗi αi ta xây dựng một cây phân tích cú pháp. Cụ thể với dẫn xuất: E -E - (E) - (E + E) - (id + E) - (id + id) Ta có quá trình xây dựng cây phân tích cú pháp như sau: Trang 38
E E E E E E - E - - | | ( ) E ( E ) | E + E E E - E - E | ( E ) ( E ) | E E | + E E | + id | | id id Hình 3.3 - Xây dựng cây phân tích cú pháp từ dẫn xuất 3.1.2.2. Khử sự mơ hồ Một văn phạm tạo ra nhiều hơn một cây phân tích cú pháp cho cùng một chuỗi nhập được gọi là văn phạm mơ hồ. Nếu một văn phạm là mơ hồ, ta không thể xác định được cây phân tích cú pháp nào sẽ được chọn. Vì thế, ta phải viết lại một văn phạm nhằm tránh sự mơ hồ của nó. Cụ thể loại bỏ sự mơ hồ trong văn phạm sau: Stmt → if expr then stmt | if expr then stmt else stmt | other Ðây là một văn phạm mơ hồ vì câu nhập if E1 then if E2 then S1 else S2 sẽ có hai cây phân tích cú pháp: Stmt If expr then Stmt | E1 1 If expr then Stmt elsem Stmt | | | E2 S1 S2 Trang 39
Stmt If expr then Stmt elsem Stmt | | E S 1 2 If expr then Stmt | | E2 S1 Hình 3.4 - Hai cây phân tích cú pháp cho một câu nhập Ðể tránh sự mơ hồ này ta đưa ra nguyên tắc " Khớp mỗi else với một then chưa khớp gần nhất trước đó". Với qui tắc này, ta viết lại văn phạm trên như sau : Stmt → matched_stmt | unmatched_stmt matched_stmt → if expr then matched_stmt else matched_stmt | other unmatched_stmt → if expr then Stmt | if expr then matched_stmt else unmatched_stmt Văn phạm tương đương này sinh ra tập chuỗi giống như văn phạm mơ hồ trên, nhưng nó chỉ có một cách dẫn xuất ra cây phân tích cú pháp cho từng chuỗi nhập. 3.1.2.3. Loại bỏ đệ qui Một văn phạm là đệ qui trái (left recursive) nếu nó có một ký hiệu chưa kết thúc A sao cho có một dẫn xuất A + Aα, với α là một chuỗi nào đó. Các phương pháp phân tích từ trên xuống không thể nào xử lý văn phạm đệ qui trái, do đó cần phải dùng một cơ chế biến đổi tương đương để loại bỏ các đệ qui trái. Ðệ qui trái có hai loại : Loại trực tiếp: Dạng A → Aα Loại gián tiếp: A i Aα với i ≥ 2 Xét văn phạm như sau: S → Aa | b A→ Ac | Sd | ε Biến S cũng là biến đệ qui trái vì S Aa Sda, nhưng đây không phải là đệ qui trái trực tiếp. . Với đệ qui trái trực tiếp: Luật sinh có dạng: Trang 40
A → Aα1 | Aα2 | | Aαm | β1 | β2 | | βn ' ' ' Sẽ thay thế bởi : A → β1 A | β2 A | | βn A ' ' ' ' A → α1A | α2A | | αm A | ε . Với đệ qui trái gián tiếp (và nói chung là đệ qui trái, ta sử dụng giải thuật sau) Giải thuật 3.1: Loại bỏ đệ qui Input: Văn phạm không tuần hoàn và không có các luật sinh ε (nghĩa là văn phạm không chứa các dạng A +A và A→ ε) Output: Văn phạm tương đương không đệ qui trái Phƣơng pháp: 1. Sắp xếp các ký hiệu không kết thúc theo thứ tự A1, A2, , An 2. For i:=1 to n do Begin for j:=1 to i -1 do Begin Thay luật sinh dạng Ai → Ajγ bởi luật sinh Ai→ δ1γ | δ2γ | | δkγ trong đó Aj → δ1 | δ2 | | δk là tất cả các Ai luật sinh hiện tại; End; Loại bỏ đệ qui trái trực tiếp trong số các Ai luật sinh; End; Ví dụ 3.3: Áp dụng thuật toán trên cho văn phạm: S → Aa | b A→ Ac | Sd | ε Về lý thuyết, thuật toán 3.1 không bảo đảm sẽ hoạt động được trong trường hợp văn phạm có chứa các luật sinh ε, nhưng trong trường hợp này luật sinh A → ε rõ ràng là "vô hại". 1. Sắp xếp các ký hiệu chưa kết thúc theo thứ tự S, A. 2. Với i = 1, không có đệ qui trái trực tiếp nên không có điều gì xảy ra. Với i = 2, thay các S - luật sinh vào A → Sd được: A→ Ac | Aad | bd | ε Loại bỏ đệ qui trái trực tiếp cho các A luật sinh, ta được : S→ Aa | b A→ bdA' A'→ cA' | adA | ε Trang 41
3.1.2.4. Tạo ra yếu tố trái Tạo ra yếu tố trái (left factoring) là một phép biến đổi văn phạm rất có ích để có được một văn phạm thuận tiện cho việc phân tích dự đoán. Ý tưởng cơ bản là khi không rõ luật sinh nào trong hai luật sinh để khai triển một ký hiệu chưa kết thúc A, chúng ta có thể viết lại các A - luật sinh nhằm "hoãn" lại việc quyết định cho đến khi thấy đủ nguyên liệu cho một lựa chọn đúng. Xét văn phạm cho câu lệnh if: stmt → if expr then stmt else stmt | if expr then stmt Khi gặp token if, chúng ta không thể quyết định ngay cần chọn luật sinh nào để triển khai cho stmt. Ðể giải quyết vấn đề này, một cách tổng quát, khi có luật sinh dạng A → αβ1 | αβ2, ta biến đổi luật sinh thành dạng: A → αA' A'→ β1 |β2 Giải thuật 3.2 : Tạo yếu tố trái cho văn phạm Input: Văn phạm G Output: Văn phạm tương đương với yếu tố trái. Phƣơng pháp: Với mỗi ký hiệu chưa kết thúc A, có các ký hiệu dẫn đầu các vế phải giống nhau, ta tìm một chuỗi α là chuỗi có độ dài lớn nhất chung cho tất cả các vế phải (α là yếu tố trái). Giả sử A → αβ1 | αβ2 | | αβn | γ, trong đó γ không có chuỗi dẫn đầu chung với các vế phải khác. Ta biến đổi luật sinh thành : A → αA' | γ ' A → β1 | β2 | | βn Với A' là ký hiệu chưa kết thúc mới. Áp dụng lặp đi lặp lại phép biến đổi này cho đến khi không còn hai khả triển nào cho một ký hiệu chưa kết thúc có một tiền tố chung. Ví dụ 3.4: Áp dụng thuật toán 3.2 cho văn phạm sau: S → i E t S | i E t S eS | α E → b Ta có văn phạm tương đương có chứa yếu tố trái như sau : S → i E t S S' | α S' → eS | ε E → b Trang 42
3.1.3. Các phƣơng pháp phân tích cú pháp 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 viết đúng phải tuân theo các luật mô tả này. Phân tích cú pháp là để tìm ra cấu trúc dựa trên văn phạm của một chương trình nguồn. - Thông thường có hai chiến lược phân tích: + Phân tích trên xuống (topdown): Cho một văn phạm PNC G = (V, T, P, S) và một câu cần phân tích w. Xuất phát 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 w. + Phân tích dưới lên (bottom-up): Cho một văn phạm PNC G = (V, T, P, S) và một câu cần phân tích w. Xuất phát từ câu w á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. Theo cách này thì phân tích Topdown và LL(k) là phân tích trên xuống, phân tích Bottom-up và phân tích LR(k) là phân tích dưới lên.  Điều kiện để thuật toán dừng: + Phân tích trên xuống dừng khi và chỉ khi G không có đệ quy trái. + Phân tích dưới lên dừng khi G không chứa suy dẫn A + A và sản xuất A .  Có các phương pháp phân tích. 1) Phương pháp phân tích topdown. 2) Phương pháp phân tích bottom up. 3) Phương pháp phân tích bảng CYK. 4) Phương pháp phân tích LL. 5) Phương pháp phân tích LR. 3.1.3.1. Phân tích cú pháp từ trên xuống Trong mục này, chúng ta giới thiệu các ý niệm cơ bản về phương pháp phân tích cú pháp từ trên xuống (Top Down Parsing) và trình bày một dạng không quay lui hiệu quả của phương pháp phân tích từ trên xuống, gọi là phương pháp phân tích dự đoán (predictive parser). Chúng ta định nghĩa một lớp văn phạm LL(1) (viết tắt của Left-to-right parse, Leftmost-derivation, 1-symbol lockahead ), trong đó phân tích dự đoán có thể xây dựng một cách tự động. a. Phân tích cú pháp đệ qui lùi (Recursive Descent Parsing) Phân tích cú pháp từ trên xuống có thể được xem như một nỗ lực tìm kiếm một dẫn xuất trái nhất cho chuỗi nhập. Nó cũng có thể xem như một nỗ lực xây dựng cây phân tích cú pháp bắt đầu từ nút gốc và phát sinh dần xuống lá. Một dạng tổng quát Trang 43
của kỹ thuật phân tích từ trên xuống, gọi là phân tích cú pháp đệ quy lùi, có thể quay lui để quét lại chuỗi nhập. Tuy nhiên, dạng này thường rất ít gặp. Lý do là với các kết cấu ngôn ngữ lập trình, chúng ta hiếm khi dùng đến nó. Ví dụ 3.5: Cho văn phạm S -> aSbS | aS | c Hãy phân tích xâu vào “aacbc” bằng thuật toán Top-down, vẽ cây phân tích trong quá trình phân tích quay lui. S S a S b S a S b S a S b S a S b S (1) (2) S S a* S a* b S S a S b a S b S S a S b S a S b S (4) c c a* S a* S b S (3) Trang 44
S S S a S b b S a S a S b S a S (6) c c* a* S b S (5) S S a S b S a S b S a S a S a* S b S (7) (8) c a* S S S a S b S a S b S a S a S c a* S 10 c (9) c Hình 3.5 cây phân tích trong quá trình phân tích quay lui Trang 45
b. Bộ phân tích cú pháp dự đoán (Predictive Parser) Trong nhiều trường hợp, bằng cách viết văn phạm một cách cẩn thận, loại bỏ đệ qui trái ra khỏi văn phạm rồi tạo ra yếu tố trái, chúng ta có thể thu được một văn phạm mà một bộ phân tích cú pháp đệ quy lùi phân tích được, nhưng không cần quay lui, gọi là phân tích cú pháp dự đoán. Xây dựng sơ đồ dịch cho bộ phân tích dự đoán: Ðể xây dựng sơ đồ dịch cho phương pháp phân tích xuống, trước hết loại bỏ đệ qui trái, tạo yếu tố trái cho văn phạm. Sau đó thực hiện các bước sau cho mỗi ký hiệu chưa kết thúc A : 1. Tạo một trạng thái khởi đầu và một trạng thái kết thúc. 2. Với mỗi luật sinh A → X1X2 Xn , tạo một đường đi từ trạng thái khởi đầu đến trạng thái kết thúc bằng các cạnh có nhãn X1X2 Xn Một cách cụ thể, sơ đồ dịch đƣợc vẽ theo các nguyên tắc sau: 1. Mỗi ký hiệu chưa kết thúc tương ứng với một sơ đồ dịch trong đó nhãn cho các cạnh là token hoặc ký hiệu chưa kết thúc. 2. Mỗi token tương ứng với việc đoán nhận token đó và đọc token kế tiếp x 3. Mỗi ký hiệu chưa kết thúc tương ứng với lời gọi thủ tục cho ký hiệu đó. A 4. Mỗi luật sinh có dạng A → α1 | α2 | | αn tương ứng với sơ đồ dịch α1 α2 αn 5. Mỗi luật sinh dạng A → α1 α2 αn tương ứng với sơ đồ dịch α1 α2 αn Trang 46
Ví dụ 3.6: Xét văn phạm sinh biểu thức toán học E → E + T | T T → T * F | F F → (E) | id Loại bỏ đệ quy trái trong văn phạm, ta được văn phạm tương đương sau : E → TE‟ E‟ → + TE‟ | ε T → FT ‟ T„ → * FT ‟ | ε F → (E) | id Một chương trình phân tích cú pháp dự đoán được thiết kế dựa trên sơ đồ dịch cho các ký hiệu chưa kết thúc trong văn phạm. Nó sẽ cố gắng so sánh các ký hiệu kết thúc với chuỗi nguyên liệu và đưa ra lời gọi đệ qui mỗi khi nó phải đi theo một cạnh có nhãn là ký hiệu chưa kết thúc. Các sơ đồ dịch tương ứng : T E’ + T E’ E 0 1 2 E’ 3 4 5 6 e ε F T’ * F T’ T 7 8 9 T’ 10 11 12 13 e 0 ε e ( F 14 E ) 15 16 17 4 4 id 4 4 Hình 3.6 - Các sơ đồ dịch cho các ký hiệu văn phạm Các sơ đồ dịch có thể được đơn giản hóa bằng cách thay sơ đồ này vào sơ đồ khác, những thay thế này tương tự như những phép biến đổi trên văn phạm. Trang 47
ε T + T + E’: 3 4 5 6 3 ⇒ E’: 4 6 ε ε T + T + T ε E: 0 3 4 6 ⇒ E: 0 3 6 ε * F ε ⇒ T: 7 8 13 ⇒ F: 14 15 16 17 ε Hình 3.7 - Rút gọn sơ đồ dịch Phân tích dự đoán không đệ qui Chúng ta có thể xây dựng bộ phân tích dự đoán không đệ qui bằng cách duy trì tường minh một Stack chứ không phải ngầm định qua các lời gọi đệ quy. Vấn đề chính trong quá trình phân tích dự đoán là việc xác định luật sinh sẽ được áp dụng cho một biến ở bước tiếp theo. Một bộ phân tích dự đoán sẽ làm việc theo mô hình sau: INPUT a + b $ STA CK X Y Chƣơng trình phân tích OUTPUT Z $ Bảng phân tích M Hình 3.8 - Mô hình bộ phân tích cú pháp dự đoán không đệ quy - INPUT là bộ đệm chứa chuỗi cần phân tích, kết thúc bởi ký hiệu $. - STACK chứa một chuỗi các ký hiệu văn phạm với ký hiệu $ nằm ở đáy Stack. - Bảng phân tích M là một mảng hai chiều dạng M[A,a], trong đó A là ký hiệu chưa kết thúc, a là ký hiệu kết thúc hoặc $. Trang 48
Bộ phân tích cú pháp được điều khiển bởi chương trình hoạt động như sau: Chương trình xét ký hiệu X trên đỉnh Stack và ký hiệu nhập hiện hành a. Hai ký hiệu này xác định hoạt động của bộ phân tích cú pháp như sau: 1. Nếu X = a = $ thì chương trình phân tích cú pháp kết thúc thành công. 2. Nếu X = a ≠ $, Pop X ra khỏi Stack và đọc ký hiệu nhập tiếp theo. 3. Nếu X là ký hiệu chưa kết thúc thì chương trình truy xuất đến phần tử M[X,a] trong bảng phân tích M: - Nếu M[X,a] là một luật sinh có dạng X → UVW thì Pop X ra khỏi đỉnh Stack và Push W, V, U vào Stack (với U trên đỉnh Stack), đồng thời bộ xuất sinh ra luật sinh X → UVW. - Nếu M[X,a] = error, gọi chương trình phục hồi lỗi. Giải thuật 3.3 : Phân tích cú pháp dự đoán không đệ quy. Input: Chuỗi nhập w và bảng phân tích cú pháp M cho văn phạm G. Output: Nếu w ∈ L (G), cho ra một dẫn xuất trái của w. Ngược lại, thông báo lỗi. Phƣơng pháp: Khởi đầu Stack chứa ký hiệu chưa kết thúc bắt đầu (S) trên đỉnh và bộ đệm chứa câu nhập dạng w$. Ðặt con trỏ ip trỏ tới ký hiệu đầu tiên của w$ ; Repeat Gọi X là ký hiệu trên đỉnh Stack và a là ký hiệu được trỏ bởi ip ; If X là ký hiệu kết thúc hoặc $ then If X = a then lấy X ra khỏi Stack và dịch chuyển ip else error ( ) Else // X là ký hiệu chưa kết thúc If M[X,a] = X → Y1 Y2 Yk then begin Lấy X ra khỏi Stack; Ðẩy Yk ,Yk-1, ,Y1 vào Stack; Xuất ra luật sinh X → Y1 Y2 Yk; end else error ( ) /* Stack rỗng */ Until X = $ Trang 49
Ví dụ 3.7: Xét văn phạm đã được khử đệ qui trái sinh biểu thức toán học E → TE‟ E‟ → + TE‟ | ε T → FT‟ T‟ → * FT‟ | ε F → (E) | id Bảng phân tích M của văn phạm được cho như sau : (ô trống tương ứng với lỗi) Ký hiệu Ký hiệu nhập chƣa kết thúc id + * ( ) $ E E → TE‟ E → TE‟ E' E → +TE‟ E→ ε E‟→ ε T T → FT„ T → FT‟ T' T‟→ ε T‟→ *FT‟ T‟→ ε T‟→ ε F F → id F → (E) Bảng 3.1 - Bảng phân tích cú pháp M cho văn phạm Quá trình phân tích cú pháp cho chuỗi nhập: id + id * id được trình bày trong bảng sau : Trang 50
STACK INPUT OUTPUT $ E id + id * id $ $ E' T id + id * id $ E → T E' $ E' T' F id + id * id $ T → F T' $ E' T' id id + id * id $ F → id $ E' T' + id * id $ $ E' + id * id $ T' → ε $ E' T + + id * id $ E' → + T E' $ E' T id * id $ $ E' T' F id * id $ T → F T' $ E' T' id id * id $ F → id $ E' T' * id $ $ E' T' F * * id $ T' → * F T' $ E' T' F id $ F → id $ E' T' id id $ $ E' T' $ T' → ε $ E' $ E' → ε $ $ Bảng 3.2. Quá trình phân tích cú pháp cho chuỗi nhập Cây phân tích cú pháp được hình thành từ output : E E‟ T F T‟ + T E‟ F T‟ ε id ε F T‟ id * id ε Hình 3.9 Cây phân tích cú pháp của ví dụ 3.6 Trang 51
Nhận xét: - Mỗi văn phạm có một bảng phân tích M tương ứng. - Chương trình không cần thay đổi cho các văn phạm khác nhau. c. Hàm FIRST và FOLLOW FIRST và FOLLOW là các tập hợp cho phép xây dựng bảng phân tích M và phục hồi lỗi theo chiến lược panic_mode. Ðịnh nghĩa FIRST(α): Giả sử α là một chuỗi các ký hiệu văn phạm, FIRST(α) là tập hợp các ký hiệu kết thúc mà nó bắt đầu một chuỗi dẫn xuất từ α. Nếu α ⇒* ε thì ε ∈ FIRST(α). Cách tính FIRST(X): Thực hiện các quy luật sau cho đến khi không còn có ký hiệu kết thúc nào hoặc ε có thể thêm vào tập FIRST(X) : 1. Nếu X là kí hiệu kết thúc thì FIRST(X) là {X} 2. Nếu X → ε là một luật sinh thì thêm ε vào FIRST(X). 3. Nếu X → Y1Y2Y3 Yk là một luật sinh thì thêm tất cả các ký hiệu kết thúc khác ε của FIRST(Y1) vào FIRST(X). Nếu ε ∈ FIRST(Y1) thì tiếp tục thêm vào FIRST(X) tất cả các ký hiệu kết thúc khác ε của FIRST(Y2). Nếu ε ∈ FIRST(Y1) ∩ FIRST(Y2) thì thêm tất cả các ký hiệu kết thúc khác ε ∈ k FIRST(Y3) Cuối cùng thêm ε vào FIRST(X) nếu   i 1 FIRST(Yi) Ví dụ 3.8: Với văn phạm sau: E → T E' E' → + T E' | ε T → F T' T' → * F T' | ε F → (E) | id Theo định nghĩa tập FIRST, ta có : Vì F ⇒ (E) | id ⇒ FIRST(F) = { (, id } Từ T → F T' và ε ∉ FIRST(F) ⇒ FIRST(T) = FIRST(F) Từ E → T E' và ε ∉ FIRST(T) ⇒ FIRST(E) = FIRST(T) Vì E' → ε ⇒ ε ∈ FIRST(E') Mặt khác do E' → + TE' mà FIRST(+) = {+} ⇒ FIRST(E') = {+, ε} Tương tự FIRST(T') = {*, ε } Vậy ta có : FIRST(E) = FIRST(T) = FIRST(F) = { (, id } Trang 52
FIRST(E') = {+, ε } FIRST(T') = {*, ε } Ðịnh nghĩa FOLLOW(A): (với A là một ký hiệu chưa kết thúc) là tập hợp các ký hiệu kết thúc a mà nó xuất hiện ngay sau A (bên phía phải của A) trong một dạng câu nào đó. Tức là tập hợp các ký hiệu kết thúc a, sao cho tồn tại một dẫn xuất dạng S ⇒* αAaβ. Chú ý rằng nếu A là ký hiệu phải nhất trong một dạng câu nào đó thì $ ∈ FOLLOW(A) ($ là ký hiệu kết thúc chuỗi nhập ). Cách tính FOLLOW(A): Áp dụng các quy tắc sau cho đến khi không thể thêm gì vào mọi tập FOLLOW được nữa. 1. Ðặt $ vào follow(S), trong đó S là ký hiệu bắt đầu của văn phạm và $ là ký hiệu kết thúc chuỗi nhập. 2. Nếu có một luật sinh A→ αBβ thì thêm mọi phần tử khác ε của FIRST(β)vào trong FOLLOW(B). 3. Nếu có luật sinh A→ αB hoặc A→ αBβ mà ε ∈ FIRST(β) thì thêm tất cả các phần tử trong FOLLOW(A) vào FOLLOW(B). Ví dụ 3.9: Với văn phạm trong ví dụ 3.7 nói trên: Áp dụng luật 2 cho luật sinh F→ (E) ⇒ ) ∈ FOLLOW(E) ⇒ FOLLOW(E) ={$, )} Áp dụng luật 3 cho E → TE' ⇒ ), $ ∈ FOLLOW(E') ⇒ FOLLOW(E') ={$, ) } Áp dụng luật 2 cho E → TE' ⇒ + ∈ FOLLOW(T). Áp dụng luật 3 cho E' → +TE' , E' → ε ⇒ FOLLOW(E') ⊂ FOLLOW(T) ⇒ FOLLOW(T) = { +, ), $ }. Áp dụng luật 3 cho T→ FT' thì FOLLOW(T') = FOLLOW(T) ={+, ), $ } Áp dụng luật 2 cho T→ FT' ⇒ * ∈ FOLLOW(F) Áp dụng luật 3 cho T' → * F T' , T'→ ε ⇒ FOLLOW(T') ⊂ FOLLOW(F) ⇒ FOLLOW(F) = {*, +, ), $ }. Vậy ta có: FOLLOW(E) = FOLLOW(E') = { $, ) } FOLLOW(T) = FOLLOW(T') = { +, ), $ } FOLLOW(F) = {*,+, ), $ } d. Xây dựng bảng phân tích M Giải thuật 3.4 : Xây dựng bảng phân tích cú pháp dự đoán Input: Văn phạm G. Output: Bảng phân tích cú pháp M. Phƣơng pháp: Trang 53
1. Với mỗi luật sinh A→ α của văn phạm, thực hiện hai bước 2 và 3. 2. Với mỗi ký hiệu kết thúc a ∈ FIRST(α), thêm A→ α vào M[A,a]. 3. Nếu ε ∈ FIRST(α) thì đưa luật sinh A→ α vào M[A,b] với mỗi ký hiệu kết thúc b ∈ FOLLOW(A). Nếu ε ∈ FIRST(α) và $ ∈ FOLLOW(A) thì đưa luật sinh A→ α vào M[A,$]. 4. Ô còn trống trong bảng tương ứng với lỗi (error). Ví dụ 3.10: Áp dụng thuật toán trên cho văn phạm trong ví dụ 3.7 Ta thấy: Luật sinh E → TE' : Tính FIRST(TE') = FIRST(T) = {(,id} ⇒ M[E,id] và M[E,( ] chứa luật sinh E → TE' Luật sinh E'→ + TE' : Tính FIRST(+TE') = FIRST(+) = {+} ⇒ M[E',+] chứa E' → +TE' Luật sinh E' → ε : Vì ε ∈ FIRST(E') và FOLLOW(E') = { ), $ } ⇒ E → ε nằm trong M[E',)] và M[E',$] Luật sinh T'→ * FT' : FIRST(* FT') = {* } ⇒ T' → * FT' nằm trong M[T',*] Luật sinh T' → ε: Vì ε ∈ FIRST(T') và FOLLOW(T') = {+, ), $} ⇒ T' → ε nằm trong M[T', +] , M[T', )] và M[T',$] Luật sinh F→ (E) ; FIRST((E)) = { ( } ⇒ F → ( E) nằm trong M[F, ( ] Luật sinh F → id ; FIRST(id) = {id} ⇒ F → id nằm trong M[F, id] Bảng phân tích cú pháp M của văn phạm được xây dựng như trong bảng 3.1. e. Văn phạm LL(1) Giải thuật 3.4 có thể áp dụng cho bất kỳ văn phạm G nào để sinh ra bảng phân tích M. Tuy nhiên, có những văn phạm (đệ quy trái hoặc mơ hồ) thì trong bảng phân tích M sẽ có thể có những ô đa trị (có chưá nhiều hơn 1 luật sinh). Ví dụ 3.11: Xét văn phạm sau: S → iE t S S' | a S' → eS | ε E → b Bảng phân tích cú pháp M của văn phạm như sau : Trang 54
Ký hiệu chƣa Ký hiệu kết thúc kết thúc a b e i T $ S S→ a S→ iEtSS' S → ε S' S'→ε S' → eS E E→b Bảng 3.3 - Bảng phân tích cú pháp M cho văn phạm ví dụ 3.10 Ðây là một văn phạm mơ hồ và sự mơ hồ này được thể hiện qua việc chọn luật sinh khi gặp ký hiệu e (else). Ô tại vị trí M [S', e] được gọi là ô đa trị. Một văn phạm mà bảng phân tích M không có các` ô đa trị được gọi là văn phạm LL(1) với ý nghĩa như sau : . L: Left-to-right parse (mô tả hành động quét chuỗi nhập từ trái sang phải) . L: Leftmost-derivation (biểu thị việc sinh ra một dẫn xuất trái cho chuỗi nhập) . 1: 1-symbol lookahead (tại mỗi một bước, đầu đọc chỉ đọc trước được một token để thực hiện các quyết định phân tích cú pháp) Văn phạm LL(1) có một số tính chất đặc biệt. Không có văn phạm mơ hồ hay đệ quy trái nào có thể là LL(1). Người ta đã chứng minh rằng một văn phạm G là LL(1) nếu và chỉ nếu mỗi khi A → α | β là 2 luật sinh phân biệt của G, các điều kiện sau đây sẽ đúng: 1. Không có một ký hiệu kết thúc a nào mà cả α và β đều dẫn xuất ra các chuỗi bắt đầu bằng a. 2. Tối đa chỉ có α hoặc chỉ có β có thể dẫn xuất ra chuỗi rỗng. 3. Nếu β ⇒* ε thì α không dẫn xuất được chuỗi nào bắt đầu bằng một ký hiệu kết thúc thuộc tập FOLLOW(A). Rõ ràng văn phạm trong ví dụ 3.6 cho các biểu thức số học là LL(1), nhưng văn phạm trong ví dụ 3.11 là văn phạm mô hình hóa câu lệnh if - then - else không phải là LL(1). Để giải quyết các ô đa trị thì một phương án khả thi là biến đổi văn phạm bằng cách loại bỏ mọi đệ quy trái, rồi tạo yếu tố trái khi có thể được với mong muốn sẽ sinh ra một văn phạm với bảng phân tích cú pháp không chứa ô đa trị nào. Nhưng cũng có một số văn phạm mà không có cách gì biến đổi thành văn phạm LL(1). Nói chung, không có quy tắc tổng quát nào để biến một ô đa trị thành ô đơn trị mà không làm ảnh Trang 55
hưởng đến ngôn ngữ đang được nhận dạng bởi bộ phân tích cú pháp. Khó khăn chính khi dùng một bộ phân tích cú pháp dự đoán là việc viết một văn phạm cho ngôn ngữ nguồn. Việc loại bỏ đệ quy trái và tạo yếu tố trái tuy dễ thực hiện nhưng chúng biến đổi văn phạm trở thành khó đọc và khó dùng cho các mục đích biên dịch. f. Phục hồi lỗi trong phân tích dự đoán Một lỗi sẽ được tìm thấy trong quá trình phân tích dự đoán khi: 1. Ký hiệu kết thúc trên đỉnh Stack không phù hợp với token kế tiếp trong dòng nhập. Hoặc : 2. Trên đỉnh Stack là ký hiệu chưa kết thúc A, token trong dòng nhập là a nhưng M[A,a] rỗng. Phục hồi lỗi theo phương pháp panic_mode là bỏ qua các ký hiệu trong dòng nhập cho đến khi gặp một phần tử trong tập hợp các token đồng bộ (synchronizing token). Tính hiệu quả của phương pháp này tùy thuộc vào cách chọn tập hợp các token đồng bộ. Một số heuristics có thể là: 1. Ta có thể đưa tất cả các ký hiệu trong FOLLOW(A) vào trong tập hợp token đồng bộ cho ký hiệu chưa kết thúc A. 2. FOLLOW(A) cũng chưa phải là một tập hợp các token đồng bộ cho A. Ví dụ, các lệnh của C kết thúc bởi ; (dấu chấm phẩy ). Nếu một lệnh thiếu dấu; thì từ khóa của lệnh kế tiếp sẽ bị bỏ qua. Thông thường ngôn ngữ có cấu trúc phân cấp, ví dụ biểu thức nằm trong một lệnh, lệnh nằm trong một khối lệnh, v.v. Chúng ta có thể thêm vào tập hợp đồng bộ của một cấu trúc những ký hiệu mà nó bắt đầu cho một cấu trúc cao hơn. Ví dụ, ta có thể thêm các từ khoá bắt đầu cho các lệnh vào tập đồng bộ cho ký hiệu chưa kết thúc sinh ra biểu thức. 3. Nếu chúng ta thêm các phần tử của FIRST(A) vào tập đồng bộ cho ký hiệu chưa kết thúc A thì quá trình phân tích có thể hòa hợp với A nếu một ký hiệu trong FIRST(A) xuất hiện trong dòng nhập. Ví dụ 3.12: Sử dụng các ký hiệu kết thúc trong tập FOLLOW làm token đồng bộ hóa hoạt động khá hữu hiệu khi phân tích cú pháp cho các biểu thức trong văn phạm ví dụ 3.6. Trang 56
FOLLOW(E) = FOLLOW(E') = { $, )} FOLLOW(T) = FOLLOW(T') = { +,$, )} FOLLOW(F) = {*,+, $, )} Bảng phân tích M cho văn phạm này được thêm vào các ký hiệu đồng bộ "synch", lấy từ tập FOLLOW của các ký hiệu chưa kết thúc - xác định các token đồng bộ : Ký hiệu chƣa Ký hiệu kết thúc kết thúc id + * ( ) $ E E→TE' E→TE' synch synch E' E'→ +TE' E'→ ε E'→ ε T T→ FT' synch T→ FT' synch synch T' T'→ ε T'→ *FT' T'→ ε T'→ ε F F→ id synch synch F→ (E) synch synch Bảng 3.4 - Bảng phân tích cú pháp M phục hồi lỗi Bảng này được sử dụng như sau: - Nếu M[A,a] là rỗng thì bỏ qua token a. - Nếu M[A,a] là "synch" thì lấy A ra khỏi Stack nhằm tái hoạt dộng quá trình phân tích. - Nếu một token trên đỉnh Stack không phù hợp với token trong dòng nhập thì lấy token ra khỏi Stack. Chẳng hạn, với chuỗi nhập : + id * + id, bộ phân tích cú pháp và cơ chế phục hồi lỗi thực hiện như sau : STACK INPUT OUTPUT $ E id + id * id $ $ E' T id + id * id $ E → T E' $ E' T' F id + id * id $ T → F T' $ E' T' id id + id * id $ F → id $ E' T' + id * id $ $ E' + id * id $ T' → ε $ E' T + + id * id $ E' → + T E' $ E' T id * id $ $ E' T' F id * id $ T → F T' Trang 57
$ E' T' id id * id $ F → id $ E' T' * id $ $ E' T' F * * id $ T' → * F T' $ E' T' F id $ F → id $ E' T' id id $ $ E' T' $ T' → ε $ E' $ E' → ε $ $ Hình 3.5 Bộ phân tích cú pháp và cơ chế phục hồi lỗi 3.1.3.1 Phân tích cú pháp từ dƣới lên Phần này sẽ giới thiệu một kiểu phân tích cú pháp từ dưới lên tổng quát gọi là phân tích cú pháp Shift -Reduce. Một dạng dễ cài đặt của nó gọi là phân tích cú pháp thứ bậc toán tử (Operator - Precedence parsing) cũng sẽ được trình bày và cuối cùng, một phương pháp tổng quát hơn của kỹ thuật Shift - Reduce là phân tích cú pháp LR (LR parsing) sẽ được thảo luận. a. Bộ phân tích cú pháp Shift – Reduce Phân tích cú pháp Shift - Reduce cố gắng xây dựng một cây phân tích cú pháp cho chuỗi nhập bắt đầu từ nút lá và đi lên hướng về nút gốc. Ðây có thể xem là quá trình thu gọn (reduce) một chuỗi w thành một ký hiệu bắt đầu của văn phạm. Tại mỗi bước thu gọn, một chuỗi con cụ thể đối sánh được với vế phải của một luật sinh nào đó thì chuỗi con này sẽ được thay thế bởi ký hiệu vế trái của luật sinh đó. Và nếu chuỗi con được chọn đúng tại mỗi bước, một dẫn xuất phải đảo ngược sẽ được xây dựng. Có 2 vấn đề: xác định handle và chọn luật sinh. * Cấu tạo: - 1 STACK để lưu các ký hiệu văn phạm. - 1 BUFFER INPUT để giữ chuỗi cần phân tích w. - Dùng $ để đánh dấu đáy stack và cuối chuỗi nhập. * Hoạt động: - Khởi đầu thì stack rỗng và w nằm trong input buffer. Bộ phân tích gạt lần lượt các ký hiệu đầu vào từ trái sang phải vào ngăn xếp đến khi nào đạt được một thu gọn thì thu gọn (thay thế vế phải xuất hiện trên đỉnh ngăn xếp bởi vế trái của sản xuất đó). Nếu có nhiều cách thu gọn tại một trạng thái thì lưu lại cho quá trình quay lui. Quá trình cứ tiếp tục, nếu dừng lại mà chưa đạt đến trạng thái kết thúc thì quay lại tại bước quay lui gần nhất. Trang 58
- Nếu quá trình đạt đến trạng thái ngăn xếp là $S và xâu vào là $ thì quá trình kết thúc và phân tích thành công. - Nếu đã xét hết tất cả các trường hợp, tức là không quay lui được nữa mà chưa đạt đến trạng thái kết thúc thì dừng lại và thông báo xâu vào không phân tích được bởi văn phạm đã cho. Ví dụ 3.13: S -> aABe; A -> Abc | b; B -> d; Phân tích câu vào “abbcde”.Quá trình phân tích Bottom-up như sau: Ngăn xếp Đầu vào Hành động $ abbcde$ gạt $a bbcde$ gạt $ab bcde$ thu gọn A -> b $aA bcde$ gạt $aAb cde$ thu gọn A -> b (2) $aAA cde$ gạt $aAAc de$ gạt $aAAcd e$ thu gọn B -> d (1) $aAAcB e$ gạt $aAAcBe $ dừng, quay lui 1 (gạt) $aAAcde $ dừng, quay lui 2 (gạt) $aAbc de$ thu gọn A -> Abc $aA de$ gạt $aAd e$ thu gọn B -> d $aAB e$ gạt $aABe $ thu gọn S -> aABe $S $ chấp nhận Bảng 3.6 Quá trình phân tích Bottom-up Trang 59
Vẽ cây cho quá trình phân tích, chúng ta có kết quả như sau: A* A A B A * a b b c d e a b b c d e Quá trình 2 Quá trình 1 S A A B a b b c d e Quá trình 3 Hình 3.10 Cây phân tích cho quá trình phân tích Bottom-up Quá trình suy dẫn cũng có thể được viết lại như sau: Abbcde => aAbcde (A -> b) => aAde (A -> Abc) => aABe (B -> d) => S (S -> aABe) Nếu viết ngược lại chúng ta sẽ được dẫn xuất phải nhất: S =>rm aABe =>rm aAde =>rm aAbcde =>rm abbcde - Quá trình phân tích Bottom-up là quá trình sinh dẫn suất phải nhất - Phân tích Bottom-up không phân tích đƣợc văn phạm có các sản xuất B-> hoặc có suy dẫn A =>+ A * Handle của một chuỗi Handle của một chuỗi là một chuỗi con của nó và là vế phải của một sản xuất trong phép thu gọn nó thành ký hiệu vế trái của 1 sản xuất. Trang 60
Ví dụ 3.14 Trong ví dụ trên. Ngăn Suy dẫn Tiền tố Đầu vào Hành động Handle xếp phải khả tồn $ abbcde$ gạt $a bbcde$ gạt abbcde a $ab bcde$ thu gọn A -> b b abbcde ab $aA bcde$ gạt aAbcde aA $aAb cde$ thu gọn A -> b (2) b aAbcde aAb $aAA cde$ gạt $aAAc de$ gạt $aAAcd e$ thu gọn B -> d (1) d không phải là handle do áp dụng thu gọn này là không thành công $aAAcB e$ gạt $aAAcBe $ dừng, quay lui 1 (gạt) $aAAcde $ dừng, quay lui 2 (gạt) $aAbc de$ thu gọn A -> Abc Abc AAbcde $aA de$ gạt $aAd e$ thu gọn B -> d d AAde $aAB e$ gạt $aABe $ thu gọn S -> aABe $S $ chấp nhận Bảng 3.7 Handle của một chuỗi Chú ý Handle là chuỗi mà chuỗi đó phải là một kết quả của suy dẫn phải từ S và phép thu gọn xảy ra trong suy dẫn đó. Trang 61
W ai ai+1 an $ Sản xuất A ->  Trên ngăn xếp chứa xâu y = ,  là vế phải của một sản xuất được bộ phân tích áp dụng để thu gọn và bước thu gọn này phải  dẫn đến quá trình phân tích thành công thì  là handle của chuỗi v (v là phần chuỗi còn lại trên input buffer). Stack Vậy nếu S =>*rm Aw =>rm w thì  là handle của suy dẫn phải w Trong việc sử dụng ngăn xếp để phân tích cú pháp gạt thu gọn, handle luôn luôn xuất hiện trên đỉnh của ngăn xếp. 3.1.3.3. Phân tích cú pháp thứ bậc toán tử Lớp văn phạm có tính chất không có luật sinh nào có vế phải là ε hoặc có hai ký hiệu chưa kết thúc nào nằm kế nhau có thể dễ dàng xây dựng bộ phân tích cú pháp Shift- Reduce hiệu quả theo lối thủ công. Một trong những kỹ thuật phân tích dễ cài đặt nhất gọi là phân tích cú pháp thứ bậc toán tử. a. Quan hệ thứ tự ƣu tiên Bảng định nghĩa 3 quan hệ thứ bậc được cho như sau : Quan hệ Ý nghĩa a có độ ưu tiên thấp hơn b a b a có độ ưu tiên cao hơn b Bảng 3.8 - Các quan hệ thứ bậc toán tử b. Sử dụng quan hệ thứ tự ƣu tiên của toán tử Các quan hệ ưu tiên này giúp việc xác định handle. Trước hết, ta dựa vào các quy tắc sau để xây dựng bảng quan hệ ưu tiên giữa các ký hiệu kết thúc. 1. Nếu toán tử θ1 có độ ưu tiên cao hơn θ2 thì θ1 •> θ2 và θ2 θ2 và θ2 •> θ1 nếu các toán tử là kết hợp trái. Trang 62
. θ1 + ; + •> - ; - •> - ; - •> + Phép toán ↑ kết hợp phải nên ↑ •> •> + * •> •> $ + * $ Chẳng hạn, đầu tiên (trong ví dụ 3.16 của chúng ta là •> sau id đầu tiên). 2. Sau đó, duyệt ngược lại (hướng sang trái), vượt qua các = (nếu có) cho đến khi gặp a đầu tiên và bên phải $ . Ðiều này chứng tỏ handle là E * E được thu gọn thành E. Vì các ký hiệu chưa kết thúc không ảnh hưởng gì đến việc phân tích cú pháp, nên chúng ta không cần phải phân biệt chúng. Trang 63
Giải thuật 3.5: Phân tích cú pháp thứ bậc toán tử Input: Chuỗi nhập w và bảng các quan hệ thứ bậc. Output: Nếu w là chuỗi chuẩn dạng đúng thì cho ra một cây phân tích cú pháp. Ngược lại, thông báo lỗi. Phƣơng pháp: Khởi đầu, Stack chứa ký hiệu $ và bộ đệm chứa câu nhập dạng w$. Ðặt con trỏ ip trỏ tới ký hiệu đầu tiên của w$ ; Repeat forever If $ nằm ở đỉnh Stack và ip chỉ đến $ then return Else begin If a b then /* thu gọn */ Repeat Lấy ký hiệu trên đỉnh Stack ra; Until Ký hiệu kết thúc trên đỉnh Stack có quan hệ <• với ký hiệu kết thúc vừa lấy ra; else error ( ) End 3.2.Các phƣơng pháp phân tích tất định 3.2.1. Bộ phân tích LR Phần này giới thiệu một kỹ thuật phân tích cú pháp từ dưới lên khá hiệu quả, có thể sử dụng để phân tích một lớp rộng các văn phạm phi ngữ cảnh. Kỹ thuật này được gọi là phân tích cú pháp LR(k). L (left - to - right): Duyệt chuỗi nhập từ trái sang phải. R (rightmost derivation): Xây dựng chuỗi dẫn xuất phải nhất đảo ngược. k : Số lượng ký hiệu nhập được xét tại mỗi thời điểm dùng để đưa ra quyết định phân tích. Khi không đề cập đến k, chúng ta hiểu ngầm là k = 1. Các ƣu điểm của bộ phân tích cú pháp LR - Bộ phân tích cú pháp LR có thể được xây dựng để nhận biết hầu như tất cả các ngôn ngữ lập trình được tạo ra bởi văn phạm phi ngữ cảnh. Trang 64
- Phương pháp phân tích cú pháp LR là phương pháp tổng quát của phương pháp chuyên thu gọn không quay lui. Nó có thể được cài đặt có hiệu quả như các phương pháp chuyên thu gọn khác. - Lớp văn phạm có thể dùng phương pháp LR là một lớp rộng lớn hơn lớp văn phạm có thể sử dụng phương pháp dự đoán. - Bộ phân tích cú pháp LR cũng có thể xác định lỗi cú pháp nhanh ngay trong khi duyệt dòng nhập từ trái sang phải. Nhược điểm chủ yếu của phương pháp này là cần phải thực hiện quá nhiều công việc để xây dựng được bộ phân tích cú pháp LR theo kiểu thủ công cho một văn phạm ngôn ngữ lập trình điển hình. 3.2.1.1. Thuật toán phân tích cú pháp LR INPUT a1 ai an $ STACK sm Chƣơng trình phân X m tích cú pháp LR OUTPUT sm-1 X m-1 action goto s0 Hình 3.11 - Mô hình bộ phân tích cú pháp LR • Stack lưu một chuỗi s0X1s1X2s2 Xmsm trong đó sm nằm trên đỉnh Stack. Xi là một ký hiệu văn phạm, si là một trạng thái tóm tắt thông tin chứa trong Stack bên dưới nó. • Bảng phân tích bao gồm 2 phần: hàm action và hàm goto.  action[sm, ai] có thể có một trong 4 giá trị : 1. shift s: đẩy s, trong đó s là một trạng thái. 2. reduce A→ β: thu gọn bằng luật sinh A→ β. 3. accept: Chấp nhận 4. error: Báo lỗi  Goto lấy 2 tham số là một trạng thái và một ký hiệu văn phạm, nó sinh ra một trạng thái. Trang 65
Cấu hình (configuration) của một bộ phân tích cú pháp LR là một cặp thành phần, trong đó thành phần đầu là nội dung của Stack, phần sau là chuỗi nhập chưa phân tích: (s0X1s1X2s2 Xmsm, ai ai+1 an $) Với sm là ký hiệu trên đỉnh Stack, ai là ký hiệu nhập hiện tại, cấu hình có được sau mỗi dạng bước đẩy sẽ như sau : 1. Nếu action[sm, ai] = Shift s : Thực hiện phép đẩy để được cấu hình mới: (s0X1s1X2s2 Xmsm ais, ai +1 an $) Phép đẩy làm cho s nằm trên đỉnh Stack, ai+1 trở thành ký hiệu hiện hành. 2. Nếu action [sm, ai] = Reduce(A → β) thì thực hiện phép thu gọn để được cấu hình: (s0X1s1X2s2 Xm - ism - i As, ai ai +1 an $) Trong đó, s = goto[sm - i, A] và r là chiều dài số lượng các ký hiệu của β. Ở đây, trước hết 2r phần tử của Stack sẽ bị lấy ra, sau đó đẩy vào A và s. 3. Nếu action[sm, ai] = accept: quá trình phân tích kết thúc. 4. Nếu action[sm, ai] = error: gọi thủ tục phục hồi lỗi. Giải thuật 3.6 : Phân tích cú pháp LR Input: Một chuỗi nhập w, một bảng phân tích LR với hàm action và goto cho văn phạm G. Output: Nếu w ∈ L(G), đưa ra một sự phân tích dưới lên cho w. Ngược lại, thông báo lỗi. Phƣơng pháp: Khởi tạo S0 là trạng thái khởi tạo nằm trong Stack và w$ nằm trong bộ đệm nhập. Ðặt ip vào ký hiệu đầu tiên của w$; Repeat forever begin Gọi s là trạng thái trên đỉnh Stack và a là ký hiệu được trỏ bởi ip; If action[s, a] = Shift s' then begin Ðẩy a và sau đó là s' vào Stack; Chuyển ip tới ký hiệu kế tiếp; end else if action[s, a] = Reduce (A → β) then begin Lấy 2 * | β| ký hiệu ra khỏi Stack; Gọi s' là trạng thái trên đỉnh Stack; Ðẩy A, sau đó đẩy goto[s', A] vào Stack; Xuất ra luật sinh A → β; Trang 66
end else if action[s, a] = accept then return else error ( ) end Ví dụ 3.17: Hình sau trình bày các hàm action và goto của bảng phân tích cú pháp LR cho văn phạm của các biểu thức số học dưới đây với các toán tử 2 ngôi + và * (1) E→ E + T Trạng Action Goto thái (2) E→ T id + * ( ) $ E T F (3) T → T * F 0 s5 s4 1 2 3 (4) T→ F 1 s6 acc (5) F → (E) 2 r2 s7 r2 r2 (6) F → id 3 r4 r4 r4 r4 4 s5 s4 8 2 3 5 r6 r6 r6 r6 Ý nghĩa: 6 s5 s4 9 3 si : chuyển trạng thái i 7 s5 s4 10 ri : thu gọn bởi luật 8 s6 s11 sinh i 9 r1 s7 r1 r1 acc: accept (chấp nhận) 10 r3 r3 r3 r3 error : khoảng trống 11 r5 r5 r5 r5 Bảng 3.10 - Bảng phân tích cú pháp LR Với chuỗi nhập id * id + id, các bước chuyển trạng thái trên Stack và nội dung bộ đệm nhập được trình bày như sau : Trang 67
STACK INPUT ACTION (1) 0 id * id + id $ Shift (2) 0 id 5 * id + id $ Reduce by F→ id (3) 0 F 3 * id + id $ Reduce by T → F (4) 0 T 2 * id + id $ Shift (5) 0 T 2 * 7 id + id $ Shift (6) 0 T 2 * 7 id 5 + id $ Reduce by F → id (7) 0 T 2 * 7 F 10 + id $ Reduce by T → T * F (8) 0 T 2 + id $ Reduce by E→ T (9) 0 E 1 + id $ Shift (10) 0 E 1 + 6 id $ Shift (11) 0 E 1 + 6 id 5 $ Reduce by F → id (12) 0 E 1 + 6 F 3 $ Reduce by T → F (13) 0 E 1 + 6 T 9 $ Reduce by E→ E + T (14) 0 E 1 $ Thành công Bảng 3.11 các bước chuyển trạng thái trên Stack của ví dụ 3.16 3.2.1.2. Văn phạm LR Một văn phạm có thể xây dựng được một bảng phân tích cú pháp cho nó được gọi là văn phạm LR. Có những văn phạm phi ngữ cảnh không thuộc lọai LR, nhưng nói chung là ta có thể tránh được những văn phạm này trong hầu hết các kết cấu ngôn ngữ lập trình điển hình. Có một sự khác biệt rất lớn giữa các văn phạm LL và LR. Ðể cho một văn phạm là LR(k), chúng ta phải có khả năng nhận diện được sự xuất hiện của vế phải của một luật sinh ứng với k ký hiệu đọc trước. Ðòi hỏi này ít khắt khe hơn so với các văn phạm LL(k). Vì vậy, các văn phạm LR có thể mô tả được nhiều ngôn ngữ hơn so với các văn phạm LL. Trang 68
3.2.1.3. Xây dựng bảng phân tích cú pháp SLR Phần này trình bày cách xây dựng một bảng phân tích cú pháp LR từ văn phạm. Chúng ta sẽ đưa ra 3 phương pháp khác nhau về tính hiệu quả cũng như tính dễ cài đặt. Phương pháp thứ nhất được gọi là "LR đơn giản" (Simple LR - SLR), là phương pháp "yếu" nhất nếu tính theo số lượng văn phạm có thể xây dựng thành công bằng phương pháp này, nhưng đây lại là phương pháp dễ cài đặt nhất. Ta gọi bảng phân tích cú pháp tạo ra bởi phương pháp này là bảng SLR và bộ phân tích cú pháp tương ứng là bộ phân tích cú pháp SLR, với văn phạm tương đương là văn phạm SLR. a. Mục (Item): Cho một văn phạm G, mục LR(0) văn phạm là một luật sinh của G với một dấu chấm mục tại vị trí nào đó trong vế phải. Ví dụ 3.18: Luật sinh A → XYZ có 4 mục như sau : A → •XYZ A → X•YZ A → XY•Z A → XYZ• Luật sinh A → ε chỉ tạo ra một mục A → • b. Văn phạm tăng cƣờng (Augmented Grammar) Giả sử G là một văn phạm với ký hiệu bắt đầu S, ta thêm một ký hiệu bắt đầu mới S' và luật sinh S' → S để được văn phạm mới G' gọi là văn phạm tăng cường. c. Phép toán bao đóng (Closure) Giả sử I là một tập các mục của văn phạm G thì bao đóng closure(I) là tập các mục được xây dựng từ I theo qui tắc sau: 1. Tất cả các mục của I được thêm cho closure(I). 2. Nếu A → α • Bβ ∈ closure(I) và B → γ là một luật sinh thì thêm B → • γ vào closure(I) nếu nó chưa có trong đó. Lặp lại bước này cho đến khi không thể thêm vào closure(I) được nữa. Ví dụ 3.19: Xét văn phạm tăng cường của biểu thức: E' → E E → E + T | T T → T * F | F F → (E) | id Nếu I là tập hợp chỉ gồm văn phạm { E'→ • E } thì closure(I) bao gồm: E' → • E (Luật 1) E → • E + T (Luật 2) Trang 69
E → • T (Luật 2) T → • T * F (Luật 2) T → • F (Luật 2) F → • (E) (Luật 2) F → • id (Luật 2) Chú ý rằng: Nếu một B - luật sinh được đưa vào closure(I) với dấu chấm mục nằm ở đầu vế phải thì tất cả các B - luật sinh đều được đưa vào. d. Phép toán Goto Goto(I, X), trong đó I là một tập các mục và X là một ký hiệu văn phạm là bao đóng của tập hợp các mục A → αX•β sao cho A → α•Xβ ∈ I. Cách tính goto(I, X): 1. Tạo một tập I' = ∅. 2. Nếu A → α•Xβ ∈ I thì đưa A→ αX•β vào I', tiếp tục quá trình này cho đến khi xét hết tập I. 3. Goto(I, X) = closure(I') Ví dụ 3.20: Giả sử I = { E' → E•, E → E • + T }. Tính goto (I, +) ? Ta có I' = { E→ E + • T } ( goto (I, +) = closure(I') bao gồm các mục : E → E + • T (Luật 1) T → • T * F (Luật 2) T → • F (Luật 2) F → • (E) (Luật 2) F → • id (Luật 2) e. Giải thuật xây dựng họ tập hợp các mục LR(0) của văn phạm G' Gọi C là họ tập hợp các mục LR(0) của văn phạm tăng cường G'. Ta có thủ tục xây dựng C như sau : Procedure Item (G') begin C := closure({ S' → •S}); Repeat For Với mỗi tập các mục I trong C và mỗi ký hiệu văn phạm X sao cho goto (I, X) ≠ ∅ và goto(I, X) ∉ C do Thêm goto(I, X) vào C; Until Không còn tập hợp mục nào có thể thêm vào C; end; Trang 70
Ví dụ 3.21: Với văn phạm tăng cường G' của biểu thức trong ví dụ 3.20 : Ta xây dựng họ tập hợp mục C của văn phạm như sau: Closure({E'→ E}): I0 : E'→ • E E → • E + T Goto (I0, id) I5: F → id • E → • T T → • T * F T → • F F → • (E) Goto (I1, +) I6: E → E + • T F → • id T → • T * F T → • F Goto (I0, E) I1: E'→ E • F → • (E) E → E • + T F → • id Goto (I0, T) I2: E → T • Goto (I2, *) I7: T → T* • F T → T • * F F → • (E) F → • id Goto (I0, F) I3: T → F • Goto (I0, ( ) I4: F → (• E) Goto (I , E) I : T → (E •) E → • E + T 4 8 E → • T E → E • + T T → • T * F T → • F F → • (E) F → • id Goto (I6,T) I9: E → E + T • T → T • * F Goto (I7,F) I10: T → T * F • Goto (I8,) ) I11: F → (E) • Trang 71
f. Thuật toán xây dựng bảng phân tích SLR Giải thuật 3.7: Xây dựng bảng phân tích SLR Input: Một văn phạm tăng cường G' Output: Bảng phân tích SLR với hàm action và goto Phƣơng pháp: 1. Xây dựng C = { I0, I1, , In }, họ tập hợp các mục LR(0) của G'. 2. Trạng thái i được xây dựng từ Ii .Các action tương ứng trạng thái i được xác định như sau: 2.1. Nếu A → α • aβ ∈ Ii và goto (Ii, a) = Ij thì action[i, a] = "shift j". Ở đây a là ký hiệu kết thúc. 2.2. Nếu A → α• ∈ Ii thì action[i, a] = "reduce (A → α)", ∀a ∈ FOLLOW(A). Ở đây A không phải là S' 2.3. Nếu S' → S• ∈ Ii thì action[i, $] = "accept". Nếu một action đụng độ được sinh ra bởi các luật trên, ta nói văn phạm không phải là SLR(1). Giải thuật sinh ra bộ phân tích cú pháp sẽ thất bại trong trường hợp này. 3. Với mọi ký hiệu chưa kết thúc A, nếu goto (Ii,A) = Ij thì goto [i, A] = j 4. Tất cả các ô không xác định được bởi 2 và 3 đều là “error” 5. Trạng thái khởi đầu của bộ phân tích cú pháp được xây dựng từ tập các mục chứa S‟→ • S Ví dụ 3.22: Ta xây dựng bảng phân tích cú pháp SLR cho văn phạm tăng cường G' trong ví dụ 3.19 trên. E' → E E → E + T | T T → T * F | F F → (E) | id (0) E'→ E (1) E → E + T (2) E → T (3) T → T * F (4) T → F Trang 72
(5) F → (E) (6) F → id1. 1. C = { I0, I1, I11 } 2. FOLLOW(E) = {+, ), $} FOLLOW(T) = {*, +, ), $} FOLLOW(F) = {*, +, ), $} Dựa vào họ tập hợp mục C đã được xây dựng trong ví dụ 3.21, ta thấy: Dựa vào họ tập hợp mục C đã được xây dựng trong ví dụ 3.21, ta thấy: Trước tiên xét tập mục I0 : Mục F → • (E) cho ra action[0, (] = "shift 4", và mục F → • id cho action[0, id] = "shift 5". Các mục khác trong I0 không sinh được hành động nào. Bây giờ xét I1 : Mục E'→ E • cho action[1, $] = "accept", mục E → E • + T cho action[1, +] = "shift 6". Kế đến xét I2 : E → T • T → T • * F Vì FOLLOW(E) = {+, ), $}, mục đầu tiên làm cho action[2, $] = action[2,+] = "reduce (E ( T)". Mục thứ hai làm cho action[2,*] = "shift 7". Tiếp tục theo cách này, ta thu được bảng phân tích cú pháp SLR đã trình bày trong bảng 3.10 Bảng phân tích xác định bởi giải thuật 3.7 gọi là bảng SLR(1) của văn phạm G, bộ phân tích LR sử dụng bảng SLR(1) gọi là bộ phân tích SLR(1) và văn phạm có một bảng SLR(1) gọi là văn phạm SLR(1).Mọi văn phạm SLR(1) đều không mơ hồ. Tuy nhiên có những văn phạm không mơ hồ nhưng không phải là SLR(1). Ví dụ 3.23: Xét văn phạm G với tập luật sinh như sau: S → L = R S → R L → * R L → id R → L Ðây là một văn phạm không mơ hồ nhưng không phải là văn phạm SLR(1). Họ tập hợp các mục C bao gồm: Trang 73
I0 : S' → • S R → • L S → • L = R L → • * R S → • R L → • id L → • * R I5 : L → id • L → • id I6 : S → L = • R R → • L R → • L I1 : S' → S • L → • * R I2 : S → L • = R L → • id R → L • I7 : L → * R• I3 : S → R • I8 : R → L• I4 : L → * • R I9 : S → L = R• 3.2.1.4. Xây dựng bảng phân tích cú pháp LR chính tắc (Canonical LR Parsing Table) a. Mục LR(1) của văn phạm G là một cặp dạng [A → α•β, a], trong đó A → αβ là luật sinh, a là một ký hiệu kết thúc hoặc $. b. Thuật toán xây dựng họ tập hợp mục LR(1) Giải thuật 3.8: Xây dựng họ tập hợp các mục LR(1) Input : Văn phạm tăng cường G‟ Output: Họ tập hợp các mục LR(1). Phƣơng pháp: Các thủ tục closure, goto và thủ tục chính Items như sau: Function Closure (I); begin Repeat For Mỗi mục [A → α•Bβ,a] trong I, mỗi luật sinh B → γ trong G' và mỗi ký hiệu kết thúc b ∈ FIRST (βa) sao cho [B → • γ, b] ∉ I do Thêm [B → •γ, b] vào I; Until Không còn mục nào có thể thêm cho I được nữa; return I; end; Function goto (I, X); begin Gọi J là tập hợp các mục [A → αX•β, a] sao cho [A → α•Xβ, a]∈ I; return Closure(J); Trang 74
end; Procedure Items (G'); begin C := Closure ({[S' → •S, $]}) Repeat For Mỗi tập các mục I trong C và mỗi ký hiệu văn phạm X sao cho goto(I, X) ≠ ∅ và goto(I, X) ∉ C do Thêm goto(I, X) vào C; Until Không còn tập các mục nào có thể thêm cho C; end; Ví dụ 3.24: Xây dựng bảng LR chính tắc cho văn phạm tăng cường G' có chứa các luật sinh như sau : S' → S (1) S → L = R (2) S → R (3) L → * R (4) L → id (5) R → L Trong đó: tập ký hiệu chưa kết thúc ={S, L, R} và tập ký hiệu kết thúc {=, *, id, $} I0 : S' → • S, $ Closure (S' → •S, $) S → • L = R, $ S → • R, $ L → • * R, = | $ L → • id, = | $ R → • L, $ Goto (I0,S) I1 : S' → S •, $ Goto (I0, L) I2 : S → L • = R, $ R → L •, $ Goto (I 0,R) I3: S → R •, $ Goto (I0,*) I4: L → * • R, = | $ R → • L, = | $ L → • * R, = | $ R → • id, = | $ Trang 75
Goto (I0,id) I5 : L → id •, = | $ Goto (I4,R) I7 : L → * R•, = | $ Goto (I4, L) I8 : R→ L•, = | $ Goto (I6,R) I9 : S → L = R•, $ Goto (I6,L) I10 : R → L•, $ Goto (I6,*) I11 : L → * • R, $ R → • L, $ L → • * R, $ R → • id, $ Goto (I6, id) I12 : L → id •, $ Goto (I11,R) I13 : R → * R•, $ Goto (I11,L) ≡ I10 Goto (I2,=) I6 : S → L = • R, $ R → • L, $ L → • * R, $ L → • id, $ Goto (I11,*) ≡ I11 Goto (I11,id) ≡ I12 c. Thuật toán xây dựng bảng phân tích cú pháp LR chính tắc Giải thuật 3.9: Xây dựng bảng phân tích LR chính tắc Input: Văn phạm tăng cường G' Output: Bảng LR với các hàm action và goto Phƣơng pháp: 1. Xây dựng C = { I0, I1, In } là họ tập hợp mục LR(1) 2. Trạng thái thứ i được xây dựng từ Ii. Các action tương ứng trạng thái i được xác định như sau: 2.1. Nếu [A → α • aβ,b] ∈ Ii và goto(Ii,a) = Ij thì action[i, a]= "shift j". Ở đây a phải là ký hiệu kết thúc. 2.2. Nếu [A → α •, a]∈ Ii , A ∈ S' thì action[i, a] = " reduce (A → α)" 2.3. Nếu [S' → S•,$] ∈ Ii thì action[i, $] = "accept". Nếu có một sự đụng độ giữa các luật nói trên thì ta nói văn phạm không phải là LR(1) và giải thuật sẽ thất bại. Trang 76
3. Nếu goto(Ii, A) = Ij thì goto[i,A] = j 4. Tất cả các ô không xác định được bởi 2 và 3 đều là "error" 5. Trạng thái khởi đầu của bộ phân tích cú pháp được xây dựng từ tập các mục chứa [S' → •S,$] Bảng phân tích xác định bởi giải thuật 3.9 gọi là bảng phân tích LR(1) chính tắc của văn phạm G, bộ phân tích LR sử dụng bảng LR(1) gọi là bộ phân tích LR(1) chính tắc và văn phạm có một bảng LR(1) không có các action đa trị thì được gọi là văn phạm LR(1). Ví dụ 3.25: Xây dựng bảng phân tích LR chính tắc cho văn phạm ở ví dụ trên Trạng Action Goto thái = * id $ S L R 0 s s 1 2 3 4 5 1 acc 2 s r 6 5 3 r 2 4 s s 8 7 4 5 5 r4 6 s11 s12 10 9 7 r3 8 r5 9 r1 10 r5 11 s11 s12 10 13 12 r4 13 r3 Bảng 3.12 - Bảng phân tích cú pháp LR chính tắc Mỗi văn phạm SLR(1) là một văn phạm LR(1), nhưng với một văn phạm SLR(1), bộ phân tích cú pháp LR chính tắc có thể có nhiều trạng thái hơn so với bộ phân tích cú pháp SLR cho văn phạm đó. 3.2.1.5 Xây dựng bảng phân tích cú pháp LALR Phần này giới thiệu phương pháp cuối cùng để xây dựng bộ phân tích cú pháp Trang 77