Tập đề cương bài giảng Chương trình dịch (Phần 2)

143 trang Gia Huy 17/05/2022 2500

Download

Bạn đang xem 20 trang mẫu của tài liệu "Tập đề cương bài giảng Chương trình dịch (Phần 2)", để 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:

tap_de_cuong_bai_giang_chuong_trinh_dich_phan_2.pdf

Nội dung text: Tập đề cương bài giảng Chương trình dịch (Phần 2)

Chƣơng 3. Phân tích cúa pháp Chƣơng 3 PHÂN TÍCH CÚ PHÁP Mục tiêu: Giúp sinh viên có khả năng: - Biết đƣợc vị trí, nhiệm vụ của giai đoạn phân tích cú pháp - Biết đƣợc các phƣơng pháp phân tích cú pháp. - Hiểu đƣợc các kỹ thuật biến đổi văn phạm. - Hiểu đƣợc các kỹ thuật trong phƣơng pháp phân tích top - down. - Hiểu đƣợc các kỹ thuật trong phƣơng pháp phân tích bottom - up . - Vận dụng các kỹ thuật vào phân tích cú cho một số văn phạm đơn giản Nội dung chính: - Vị trí, nhiệm vụ của giai đoạn phân tích cú pháp và các phƣơng pháp phân tích cú pháp. - Các kỹ thuật biến đổi văn phạm: khử đệ quy trái, thừa số hoá bên trái, khử nhập nhằng. - Phƣơng pháp phân tích top – down: phân tích cú pháp đệ quy xuống, phân tích cú pháp dự đoán. - Phƣơng pháp phân tích bottom – up: phân tích cú pháp đẩy thu, phân tích cú pháp LR(k). 3.1. Giai đoạn phân tích cú pháp 3.1.1. Vị trí, chức năng, nhiệm vụ của giai đoạn phân tích cú pháp Giai đoạn phân tích cú pháp là giai đoạn tiếp theo của giai đoạn phân tích từ vựng và trƣớc giai đoạn phân tích ngữ nghĩa. Chức năng của giai đoạn phân tích cú pháp là phân tích chƣơng trình nguồn về mặt cú pháp: Xây dụng cây phân tích cú pháp hoặc báo lỗi. Nhiệm vụ chính của giai đoạn này là nhận vào dòng các thẻ từ (token) có đƣợc từ giai đoạn phân tích từ vựng và xác nhận rằng nó có thể đƣợc sinh ra từ văn phạm của ngôn ngữ nguồn bằng cách tạo ra cây phân tích cú pháp cho dòng thẻ từ này và đầu ra của nó là cây phân tích cú pháp (parsing tree). Ngoài ra, bộ phân tích cú pháp còn có cơ chế ghi nhận các lỗi cú pháp theo một phƣơng thức linh hoạt và có khả năng phục hồi đƣợc 76
Chƣơng 3. Phân tích cúa pháp các lỗi thƣờng gặp để có thể tiếp tục xử lý phần còn lại của xâu vào. Có thể chỉ ra vị trí của giai đoạn này với các giai đoạn liên quan ở hình 3.1. Cây phân tích Chƣơng Thẻ từ cú pháp trình ngu ồn Bộ phân tích Bộ phân tích (Parsing tree) Phần còn lại từ vựng cú pháp của front end Yêu cầu Thẻ từ mới Bảng ký hiệu Hình 3.1. Vị trí của bộ phân tích cú pháp 3.1.2. 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ƣ tên, 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, thiếu dấu chấm phảy (;), thiếu từ khoá. - 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, sai kiểu dữ liệu. - Lỗi logic: nhƣ thực hiện một lời gọi đệ quy 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 chƣơng chƣơng 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 đƣợc 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. 3.1.3. 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 sẽ giới thiệu một số chiến lƣợc: 1) Phương thức "hoảng sợ" (panic mode recovery) 77
Chƣơng 3. Phân tích cúa pháp Đâ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. 2) 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 xâu vào. 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. 3) 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, giúp 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 xâu vào. 4) Chiến lược hiệu chỉnh toàn cục (global correction) Một cách lý tƣởng là chƣơng 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 xâu vào 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 xâu 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.4. Các phƣơng pháp phân tích cú pháp Hiện tại có nhiều phƣơng pháp phân tích cú pháp khác nhau; tuy nhiên, ngƣời ta có thể phân chúng thành 3 loại: phƣơng pháp phân tích tổng hợp, phƣơng pháp phân tích top – down và phƣơng pháp phân tích bottom – up. 1) Phương pháp phân tích tổng hợp (Universal parsing) Tiêu biểu cho phƣơng pháp phân tích tổng hợp là giải thuật Cooke – Young Kasami và giải thuật Earley; Ngƣời ta gọi chúng là giải thuật tổng hợp hay giải thuật vạn năng vì chúng phân tích cú pháp cho văn phạm bất kỳ. Tuy nhiên do tính vạn năng của chúng cho nên nói chung phƣơng pháp này không hiệu quả với một 78
Chƣơng 3. Phân tích cúa pháp văn phạm cụ thể; vì lý do trên, ngƣời ta ít sử dụng chúng để viết các chƣơng trình dịch (Compiler). 2) Phương pháp phân tích Top – Down Về mặt trực giác có thể coi phƣơng pháp phân tích Top – Down là phƣơng pháp xây dựng cây phân tích cú pháp từ trên xuống hay 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á (Root – Leaves). 3) Phương pháp phân tích Bottom – Up Về mặt trực giác có thể coi phƣơng pháp phân tích Bottom – Up là xây dựng cây phân tích cú pháp từ dƣới lên trên hay hay 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ừ các nút lá và thu gọn dần về gốc (Leaves – root). 3.2. Biến Ðổi 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 bằng các văn phạm phi ngữ cảnh (context-free grammar) G với 4 thành phần G = (N, T, P, S), trong đó: - N : 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) với N T = . - P : là tập luật sinh của văn phạm (productions) có dạng: A với A N và V* = (NT)* - S N: là ký hiệu bắt đầu của văn phạm (start symbol). Ví dụ: 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 (với E là một biểu thức - expression) : E → EAE | (E) | - E | id ; A → + | - | * | / | ↑ . 3.2.1. Cây phân tích cú pháp (Parsing tree) và dẫn xuất Ta nói rằng αAβ dẫn xuất ra αγβ (ký hiệu: αAβ αγβ) nếu A → γ là một luật sinh, α và β là các chuỗi tùy ý các ký hiệu văn phạm. Nếu α α α ta nói α dẫn xuất ra (suy ra) α 1 2 n 1 n Ký hiệu : dẫn xuất ra qua 1 bƣớc 79
Chƣơng 3. Phân tích cúa pháp * : dẫn xuất ra qua 0, 1 hoặc nhiều bƣớc. + : dẫn xuất ra qua 1 hoặc nhiều bƣớc. i : dẫn xuất ra qua i 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. Xâu các ký hiệu kết thúc w thuộc + L(G) nếu và chỉ nếu S w và xâu 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 phi ngữ cảnh 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 chứa toàn các ký hiệu kết thúc. Cây phân tích cú pháp là hình ảnh minh họa cho ký hiệu bắt đầu của một văn phạm dẫn đến một xâu trong ngôn ngữ. Nếu ký hiệu chƣa kết thúc A có luật sinh A XYZ thì cây phân tích cú pháp có thể có một nút trong có nhãn A và có 3 nút con có nhãn tƣơng ứng từ trái qua phải là X, Y, Z. A X Y Z Hình 3.2. Minh họa một cây phân tích cú pháp Một cách hình thức, cho một văn phạm phi ngữ cảnh thì cây phân tích cú pháp là một cây có các tính chất sau đây: 1. Nút gốc có nhãn là ký hiệu bắt đầu. 80
Chƣơng 3. Phân tích cúa pháp 2. Mỗi một lá có nhãn là một ký hiệu kết thúc hoặc ε. 3. Mỗi nút trong có nhãn là một ký hiệu chƣa kết thúc. 4. Nếu A là một ký hiệu chƣa kết thúc đƣợc dùng làm nhãn cho một nút trong nào đó và X1, , Xn là nhãn của các con của nó theo thứ tự từ trái sang phải thì A → X1X2 Xn là một luật sinh. Ở đây X1, , Xn có thể là ký hiệu kết thúc hoặc chƣa kết thúc. Ðặc biệt, nếu A → ε thì nút có nhãn A có thể có một con có nhãn ε. Một cây phân tích cú pháp có thể xem nhƣ một biểu diễn 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à dẫn xuất 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 α * β . l m Nếu S * α thì ta nói α là dạng câu trái nhất của văn phạm. l 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.1: Cho văn phạm G = ( N, T, P, S); Tập P gồm các quy tắc: E E + E; E E * E; E (E); E - E; E id Khi đó cây phân tích cú pháp cho xâu - (id + id) có dạng ở hình 3.2 E E - ( ) E E E + id id Hình 3.3. Minh họa một 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 Với mỗi α ta xây dựng một cây phân tích cú pháp. Ví dụ với dẫn xuất: i 81
Chƣơng 3. Phân tích cúa pháp E -E - (E) - (E + E) - (id + E) - (id + id) Quá trình xây dựng cây phân tích cú pháp nhƣ sau: E E E E - E - ( ) E E E E E - - ) ( ( ) E E E E E E + + E id E - ( ) E E E + id id Hình 3.4. Xây dựng cây phân tích cú pháp từ dẫn xuất 3.2.2. Ngôn ngữ nhập nhằng (Ambiguity) Trong lý thuyết ngôn ngữ hình thức đã đề cập đến tính nhập nhằng của văn phạm; để tiện cho việc trình bày, ta đƣa ra khái niệm tƣơng tự về văn phạm nhập nhằng. Văn phạm đƣợc gọi là nhập nhằng nếu tồn tại một xâu có hai cây phân tích cú pháp khác nhau. Nói cách khác văn phạm đƣợc gọi là nhập nhằng nếu tồn tại một xâu có nhiều hơn một cây phân tích cú pháp cho dẫn xuất trái nhất hay phải nhất. Ngôn ngữ đƣợc sinh bởi văn phạm nhập nhằng gọi là ngôn ngữ nhập nhằng. 82
Chƣơng 3. Phân tích cúa pháp Ví dụ 3.2: Cho văn phạm: G = ( N, T, P, E) Tập P gồm các quy tắc: E E + E; E E * E; E (E); E - E; E id Xét xâu id + id * id, xâu này có hai dẫn xuất trái nhất là: a) E E + E id + E id + E * E id + id * E id + id * id b) E E * E E + E * E id + E * E id + id * E id + id * id Hình 3.5a và 3.5b là hai cây phân tích cú pháp của xâu trên. E E E + E E E * E E E id * E + id id id id id a) b) Hình 3.5. Hai cây phân tích cú pháp của xâu id + id * id Vậy văn phạm trên là văn phạm nhập nhằng. 3.2.3. Kỹ thuật khử nhập nhằng Nếu một văn phạm là nhập nhằng thì khi gặp một xâu có nhiều hơn một cây phân tích cú pháp; ta không thể xác định đƣợc cây phân tích cú pháp nào sẽ đƣợc chọn. Vì vậy, ta phải viết lại văn phạm nhằm loại bỏ sự nhập nhằng của nó. Chẳng hạn, xét văn phạm với các luật sinh : IF THEN IF THEN ELSE Other Các luật sinh trên định nghĩa câu lện IF, ở đây ứng với biến chỉ câu lệnh; - biến chỉ biểu thức; other chỉ câu lệnh khác. Ký hiệu E là biểu thức; S là câu lệnh và xét câu lệnh sau: IF E1 THEN IF E2 THEN S1 ELSE S2 83
Chƣơng 3. Phân tích cúa pháp Văn phạm trên là văn phạm nhập nhằng vì câu lệnh trên có hai cây phân tích cú pháp trái nhất ở hình 3.6a và hình 3.6b sttm if expr then sttm sttm E1 if expr then sttm else E2 S1 S2 a) sttm if expr then sttm else sttm E1 if expr then sttm S 2 E S 2 1 b ) Hình 3.6. Hai cây phân tích cú pháp của cùng một xâu Để khử tính nhập nhằng của văn phạm nêu trên, ngƣời ta thƣờng khắc phục bằng cách cho mỗi ELSE ứng với THEN gần nhất trƣớc đó. Theo nguyên tắc này, ta sửa lại các luật sinh nhƣ sau: IF THEN ELSE other IF THEN IF THEN ELSE 3.2.4. Kỹ thuật khử đệ quy trái Trong lý thuyết ngôn ngữ hình thức, khi xét dạng chuẩn Greibach đã đề cập đến các A - luật sinh. Các A - luật sinh thƣờng làm cho văn phạm trở thành đệ quy 84
Chƣơng 3. Phân tích cúa pháp trái. Ở đây, ta sẽ nhắc lại khái niệm và kỹ thuật khử đệ quy trái đã nêu trong các bổ đề của Greibach. 1) Khái niệm Một văn phạm phi ngữ cảnh đƣợc gọi là đệ quy trái nếu tồn tại một dẫn xuất dạng: A + A với A N; V+ = (NT)+ Phƣơng pháp phân tích Top – Down không khắc phục đƣợc trƣờng hợp văn phạm đệ quy trái. Vì vậy, để có thể sử dụng đƣợc phƣơng pháp phân tích Top – Down cần phải khử tính đệ quy trái của văn phạm. Ðệ quy trái có hai loại : - Trực tiếp: Dạng A Aα ; i - Gián tiếp: A Aα với i ≥ 2. Ví dụ 3.3: Xét văn phạm nhƣ sau: S → Aa | b; A→ Ac | Sd | a. Biến A là biến đệ quy trái (trực tiếp) vì A Ac nhờ áp dụng luật sinh A→ Ac Biến S, A cũng là các biến đệ quy trái (gián tiếp); Vì S Aa Sda nhờ áp dụng các luật sinh S → Aa; A→ Sd và A Sd Aad nhờ áp dụng các luật sinh A→ Sd; S → Aa . 2) Kỹ thuật khử đệ quy trái a) Khử đệ quy trái trực tiếp Nếu luật sinh có dạng: A → Aα1 | Aα2 | | Aαm | β1 | β2 | | βn thì thêm vào một biến mới A‟ và thay luật sinh đó bởi các luật sinh: A → β1A‟ | β2A‟ | | βnA‟ Và A‟ → α1A‟| α2A‟ | | αm A‟ | ε Ví dụ 3.4: - Xét văn phạm sinh ra biểu thức số học có các luật sinh sau: E E + T; E T ; T T*F; T F ; F (E); F id. 85
Chƣơng 3. Phân tích cúa pháp Áp dụng kỹ thuật nêu trên, ta có: + Với các luật sinh E E + T; E T có thể viết lại là E E + T | T và nó đƣợc thay thế bằng các luật sinh E TE1 và E1 + TE1| . + Với các luật sinh T T*F; T F có thể viết lại là T T*F | F và nó đƣợc thay thế bằng các luật sinh T FT1 và T1 *FT1 | . Sau khi khử đệ quy trái, ta thu đƣợc văn phạm không đệ quy trái với tập các luật sinh: E TE1 ; E1 + TE1| ; T FT1 và T1 *FT1 | ; F (E) | id. - Xét văn phạm S → Aa | b; A→ Ac | Sd | a Ta có A Ac | Sd | a; nên nó sẽ đƣợc thay thế bằng các luật sinh A SdA‟ | aA‟ ; A‟ cA'| . b) Khử đệ quy trái gián tiếp - Ý tƣởng Với mỗi biến đệ quy trái gián tiếp: + Biến đổi và thay thế để đƣa nó về đệ quy trái trực tiếp. + Khử đệ quy trái trực tiếp. - Giải thuật loại bỏ đệ quy trái gián tiếp 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ẫn xuất dạng A + A và A ) Output: Văn phạm tƣơng đƣơng không đệ quy trái Process: 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 if  luật sinh Ai Aj then 86
Chƣơng 3. Phân tích cúa pháp begin + Tìm các luật sinh dạng Aj δ1 | δ2 | | δk ; + Thay luật sinh dạng Ai Aj bởi luật sinh Ai δ1 | δ2 | | δk; {Trong đó các A - luật sinh và A - luật sinh là các luật sinh hiện tại} i j end; - Loại bỏ đệ quy trái trực tiếp trong số các Ai - luật sinh; End; Ví dụ 3.5: a) Khử đệ quy trái cho văn phạm có các luật sinh S → Aa | b; A→ Ac | Sd | a. Áp dụng giải thuật trên 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: + j = 0 nên vòng lặp theo j bị bỏ qua; + Không có đệ quy trái trực tiếp nên không có điều gì xảy ra. - Với i = 2: + j = 1: Có luật sinh A Sd và tìm đƣợc S Aa | b nên phải thay thế luật sinh này và sau khi thay ta thu đƣợc: A Ac | Aad | bd | a. + Loại bỏ đệ quy trái trực tiếp cho các A luật sinh, ta đƣợc: A bdA' | aA'; A' cA' | adA' | ε b) Khử đệ quy trái cho văn phạm có các luật sinh: S Sc| Aa| b; A Ac| Bd| b; B Bb| Sa| d 1. Sắp xếp các ký hiệu chƣa kết thúc theo thứ tự S, A, B. 2. - Với i = 1: + j = 0 nên vòng lặp theo j bị bỏ qua; + Khử đệ quy trái trực tiếp cho S- luật sinh: 87
Chƣơng 3. Phân tích cúa pháp Bổ sung thêm biến S‟; Thay S Sc| Aa| b bằng S AaS‟| bS‟ ; S‟ cS‟| . -Với i = 2: + j =1: Không tồn tại luật sinh dạng Ai Aj nên việc thay thế bị bỏ qua. + Khử đệ quy trái trực tiếp cho A - luật sinh: Bổ sung thêm biến A‟; Thay A Ac| Bd| b bằng A BdA‟ | bA‟ ; A‟ cA‟| . - Với i = 3; ta có: + j =1: Tồn tại luật sinh B Sa và tìm đƣợc S AaS‟| bS‟ nên sau khi thay thế ta thu đƣợc: B Bb| AaS‟a | bS‟a | d. + j = 2: Tồn tại luật sinh B AaS‟a và tìm đƣợc A BdA‟ | bA‟ nên sau khi thay thế ta thu đƣợc: B Bb| BdA‟aS‟a | bA‟aS‟a | bS‟a | d. + Loại bỏ đệ quy trái trực tiếp cho các B - luật sinh: Bổ sung thêm B‟; Thay luật sinh B Bb| BdA‟aS‟a | bA‟aS‟a | bS‟a | d bằng B bA‟aS‟a B‟| bS‟aB‟ | dB‟ và B‟ bB‟| dA‟aS‟aB‟| . Vậy sau khi khử đệ quy trái ta thu đƣợc văn phạm với các luật sinh sau: S AaS‟| bS‟; S‟ cS‟| ; A BdA‟ | bA‟ ; A‟ cA‟| ; B bA‟aS‟a B‟| bS‟aB‟ | dB‟; B‟ bB‟| dA‟aS‟aB‟| . 3.2.5. Kỹ thuật thừa số hoá bên trái Trong quá trình phân tích từ trên xuống (Top – Down); ta có thể thay một biến ở vế trái bằng một xâu ở vế phải. Vấn đề nảy sinh là ở mỗi bƣớc phân tích trong tập P có thể có nhiều luật sinh có thể sử dụng đƣợc nhƣng ta không biết chọn luật sinh nào là thích hợp cho các bƣớc tiếp theo. Để khắc phục tình trạng trên, ngƣời ta sử dụng kỹ thuật thừa số hoá bên trái. 88
Chƣơng 3. Phân tích cúa pháp 1) Ý tưởng Ý tƣởng cơ bản của kỹ thuật này là viết lại các A – luật sinh của văn phạm nhằm “hoãn” lại việc quyết định cho đến khi đủ thông tin cho một lựa chọn đúng với quá trình phân tích. Ví dụ 3.6: Xét văn phạm có các luật sinh sau cho câu lệnh IF: IF THEN ELSE IF THEN Khi nhận ra từ IF thì không biết sử dụng luật sinh nào trong hai luật sinh trên. Một cách tổng quát, khi có các A - luật sinh dạng: A 1; A 2 Ta đƣa thêm vào biến A‟ và thay các A - luật sinh trên về dạng: A A‟; A‟ 1 ; A‟ 2 Quá trình thêm biến và thay thế các A - luật sinh nhƣ trên gọi là quá trình thừa số hoá bên trái. Quá trình thừa số hoá bên trái cho phép ta nhận đƣợc văn phạm mới tƣơng đƣơng với văn phạm đã cho. Rõ ràng nhờ quá trình thừa số hoá giúp cho ta nhận biết luật sinh cần sử dụng chính xác và nhanh chóng hơn. 2) Giải thuật thừa số hoá bên trái Input: Văn phạm G Output: Văn phạm tƣơng đƣơng đã thừa số hoá bên trái Process: Bƣớc 1: Với mỗi biến A thực hiện - Tìm tiền tố  chung dài nhất cho tất cả các vế phải của các luật sinh có vế trái là A; - Nếu tìm thấy A 1| 2 | | n |  ; trong đó:  là các vế phải không có tiền tố chung với các vế phải khác thì 89
Chƣơng 3. Phân tích cúa pháp + Bổ sung vào một biến mới A‟; + Thay tập luật sinh tìm đƣợc bằng A A‟|  và A‟ 1| 2| | n . Bƣớc 2: Với mỗi biến A‟ mới bổ sung thực hiện bƣớc 1 cho đến khi không còn một biến có hai luật sinh có chung một tiền tố  Ví dụ 3.7: a) Xét văn phạm với các luật sinh sau: IF THEN IF THEN ELSE . Nếu ký hiệu = IF THEN khi đó ta có: | ELSE Sau khi thừa số hoá bên trái ta có: A1 A1 ELSE |  b) Cho văn phạm với các luật sinh: S aaaAcBd | aaaAcDE | aaaFe | bbS| cD; A bbCd | bbb; B bbD; C abc; D aba; E dbaa; F e | . Áp dụng giải thuật trên: 1. -Với biến S, ta thay S aaaAcBd | aaaAcDE | aaaFe | bbS| cD bằng S aaaS1 | bbS| cD; S1 AcBd | AcDE | Fe 90
Chƣơng 3. Phân tích cúa pháp - Với biến A, ta thay A bbCd | bbb bằng A bbA1 và A1 Cd | b - Với các biến B, C, D, E, F: không có tiền tố chung 2. - Với biến S1, ta thay S1 AcBd | AcDE | Fe bằng S1 AcS2 | Fe; S2 Bd | DE . - Với biến A1: không có tiền tố chung 3. Với biến S2: Không có tiền tố chung Kết quả ta thu đƣợc văn phạm tƣơng đƣơng với tập các luật sinh: S aaaS1 | bbS| cD; S1 AcS2 | Fe; S2 Bd | DE; A bbA1 ; A1 Cd | b; B bbD; C abc; D aba; E dbaa; F e | . c) Cho văn phạm với các luật sinh: S aaaAcBd | aaaAcde | bbbBe | bbS| cC; A aba; B bba; C abc. Áp dụng giải thuật trên: 1. Với biến S, thay S aaaAcBd | aaaAcde | bbbBe | bbSdd| cD bằng S aaaAcS‟| bbS‟‟| cC; S‟ Bd| de; S‟‟ Be| Sdd. Kết quả ta thu đƣợc văn phạm tƣơng đƣơng với tập các luật sinh: 91
Chƣơng 3. Phân tích cúa pháp S aaaAcS‟| bbS‟‟| cC; S‟ Bd| de; S‟‟ Be| Sdd. A aba; B bba; C abc. Ta có thể viết lại giải thuật trên nhƣ sau: Với mỗi biến A thực hiện Bƣớc 1: - Tìm tiền tố  chung dài nhất cho tất cả các vế phải của các luật sinh có vế trái là A; - Nếu tìm thấy A 1| 2 | | n |  ; trong đó:  là các vế phải không có tiền tố chung với các vế phải khác thì + Bổ sung vào một biến mới A‟; + Thay tập luật sinh tìm đƣợc bằng A A‟|  và A‟ 1| 2| | n Bƣớc 2: Với mỗi biến A‟ mới bổ sung thực hiện bƣớc 1 cho đến khi không còn một biến có hai luật sinh có chung một tiền tố  . Khi đó thừa số hoá bên trái cho văn phạm trong ví dụ 3.7b có thể trình bày lại nhƣ sau: Áp dụng giải thuật trên: -Với biến S, ta thay S aaaAcBd | aaaAcDE | aaaFe | bbS| cD bằng S aaaS1 | bbS| cD; S1 AcBd | AcDE | Fe - Với biến S1, ta thay S1 AcBd | AcDE | Fe bằng S1 AcS2 | Fe; S2 Bd | DE - Với biến S2: không có tiền tố chung - Với biến A, ta thay A bbCd | bbb bằng A bbA1 và A1 Cd | b - Với biến A1: không có tiền tố chung 92
Chƣơng 3. Phân tích cúa pháp - Với các biến B, C, D, E, F: không có tiền tố chung. Kết quả ta thu đƣợc văn phạm tƣơng đƣơng với tập các luật sinh: S aaaS1 | bbS| cD; S1 AcS2 | Fe; S2 Bd | DE; A bbA1 ; A1 Cd | b; B bbD; C abc; D aba; E dbaa; F e | . 3.3. Phân tích cú pháp từ trên xuống Kỹ thuật phân tích cú pháp từ trên xuống dựa vào ý tƣởng cơ bản là cố gắng tìm một dẫn xuất trái nhất cho xâu vào, xuất phát từ ký tự bắt đầu của văn phạm. Hay nói một cách khác là xây dựng một cây phân tích cho xâu vào, bắt đầu từ nút gốc phát sinh dần xuống nút lá. Kỹ thuật phân tích cú pháp từ trên xuống đƣợc chia thành hai loại: - Phân tích cú pháp từ trên xuống có quay lui - gọi là phân tích cú pháp đệ quy xuống. - Phân tích cú pháp từ trên xuống theo nguyên tắc dự đoán (Preditive parse) 3.3.1. Phân tích cú pháp đệ quy xuống 1) Ý tưởng Ý tƣởng của kỹ thuật này đƣợc minh hoạ qua ví dụ cụ thể sau: Cho văn phạm với các luật sinh: 1. S cAd. 2. A ab. 3. A a. 93
Chƣơng 3. Phân tích cúa pháp Cần xây dựng cây phân tích cú pháp cho từ w = cad. S S S c d c d A c d A A a b a a) b) c) Hình 3.7 a, b, c. Mô tả quá trình phân tích xâu w = cad Bắt đầu với gốc có nhãn S, con trỏ trỏ vào ký tự đầu tiên của xâu w là c; áp dụng luật sinh 1 ta đƣợc cây ở hình a). Đối chiếu với lá của cây trong hình a) từ bên trái ta thấy nhãn của nút lá trái nhất là c trùng với ký tự mà con trỏ đang trỏ trên xâu vào; Vì vậy, con trỏ trỏ đến ký tự thứ 2 là a. Xét nút lá thứ 2 cây a), nút có nhãn A, sử dụng luật sinh thứ 2 ta đƣợc cây b). So sánh nhãn nút lá cực trái của cây con này với ký tự mà con trỏ trỏ trên xâu w; chúng giống nhau, đó là ký tự a. Con trỏ trên xâu w trỏ sang ký tự d. So sánh nhãn của nút lá tiếp theo của cây con gốc A với ký tự mà con trỏ đang trỏ trên xâu w; ta thấy chúng khác nhau. Việc sử dụng luật sinh 2 coi nhƣ thất bại; ta cần phải quay lui lại nút gốc có nhãn A và con trỏ trên xâu w cũng lui lại ký tự thứ 2 là a. Bây giờ, ta lại thử sử dụng luật sinh 3; kết quả ta có cây dẫn xuất hình 3.7c. So sánh nhãn của nút lá trong cây gốc A với ký tự con trỏ đang trỏ, chúng trùng nhau. Khi đó con trỏ trên w dịch đến ký tự thứ 3 và việc so sánh lại đƣợc tiến hành với nút lá có nhãn d. Kết quả ta xây dựng xong cây phân tích cho w; giải thuật kết thúc. 2) Giải thuật phân tích cú pháp đệ quy xuống Trƣớc tiên, để đảm bảo có thể phân tích cú pháp đệ quy xuống; ta cần thực hiện các bƣớc chuẩn bị sau: - Loại bỏ đệ quy trái; - thực hiện thừa số hoá bên trái Input: Văn phạm đã loại bỏ đệ quy trái, thừa số hoá bên trái, Xâu vào Output: Cây phân tích cú pháp Process: 94
Chƣơng 3. Phân tích cúa pháp Bƣớc 1: - Sử dụng một con trỏ trỏ đến xâu vào. Ký hiệu trên xâu vào đang đƣợc con trỏ chỉ đến gọi là ký hiệu vào hiện tại. Ví trí đầu tiên của con trỏ là ký hiệu bên trái nhất của xâu vào. - Khởi tạo cây với nút gốc là ký tự khởi đầu S của văn phạm; nút đang xét là S. Bƣớc 2: Nếu nút đang xét là: - Ký hiệu không kết thúc A thì tìm luật sinh đầu tiên có vế trái là A. Giả sử là A X1X2 Xk thì bổ sung vào cây các nút X1, X2, , Xk làm con của A và lấy X1 làm nút đang xét. Trƣờng hợp k = 0 tức là A  thì bổ sung nút có nhãn là  làm con của A và lấy nút ngay bên phải A làm nút đang xét. - Ký hiệu kết thúc a thì so sánh a với ký hiệu vào hiện tại + Nếu trùng nhau thì lấy nút bên phải a làm nút đang xét và dịch chuyển con trỏ trên xâu vào sang ký tự tiếp theo. + Nếu khác nhau thì quay lại nút do luật sinh ngay trƣớc đó tạo ra; điều chỉnh lại con trỏ trên xâu vào và lựa chọn luật sinh tiếp theo. Nếu không còn lựa chọn nào nữa thì quay lui. Bƣớc 3: Nếu đã duyệt hết xâu vào và cây không còn nút nào chƣa xét thì ta thu đƣợc cây phân tích cú pháp. Ngƣợc lại, nếu đã quay lui lại tất cả các trƣờng hợp mà không thu đƣợc cây phân tích cú pháp thì thông báo lỗi. Chú ý: Phƣơng pháp này thƣờng rất ít gặp. Lý do là với kết cấu các ngôn ngữ lập trình hiếm khi dùng đến nó. Ví dụ 3.8: Cho văn phạm với các luật sinh: S cAd  bbABd; A ab  a  b; B bac  bad. Hãy phân tích cú pháp cho các xâu: a) w = bbabacd. b) w = bbbbad. 95
Chƣơng 3. Phân tích cúa pháp 3.3.2. Phân tích cú pháp dự đoán (phân tích LL(1)) Kỹ thuật phân tích cú pháp đệ quy xuống đã xem xét ở trên có đặc điểm là trong quá trình phân tích, khi gặp “thất bại” công việc phải quay lui trở lại nút gốc của cây con gần nhất. Kỹ thuật trên có một số nhƣợc điểm sau: - Tốn thời gian, trong nhiều trƣờng hợp làm cho chƣơng trình dịch làm việc chậm do “sa lầy” vào vòng lặp đệ quy. - Thiếu không gian nhớ nếu mức lồng đệ quy lớn. Khi xem xét nhiều văn phạm ngƣời ta nhận thấy rằng: bằng cách viết văn phạm cẩn thận, khử đệ quy trái, thừa số hoá bên trái giúp có thể thu đƣợc văn phạm mới mà quá trình phân tích không cần phải quay lui. Ta xét một kỹ thuật phân tích từ trên xuống nhƣng không quay lui và đƣợc gọi là kỹ thuật phân tích dự đoán (Preditive paser). 1) Ý tưởng Ý tƣởng của kỹ thuật phân tích dự đoán là giả sử cho trƣớc xâu vào w = x1x2 xn; con trỏ hiện đang trỏ vào ký tự xi và quá trình xây dựng cây phân tích đang ở nút có nhãn là biến A . Vấn đề đặt ra là cần phải sử dụng luật sinh nào trong số m các A - luật sinh có thể sử dụng A i với i = 1, 2, , m để dẫn ra cây phân tích thích hợp của từ w. Rõ ràng, nếu trong m các A - luật sinh chỉ có một luật sinh A ik là thích hợp nhất trong trƣờng hợp này. Phân tích dự đoán còn gọi là phân tích LL đƣa ra cách thức chọn luật sinh để triển khai. Cho các luật sinh A i với i = 1, 2, , m thoả mãn tính chất các xâu i với i = 1, 2, , m suy dẫn ra các xâu có ký hiệu đầu tiên là các ký hiệu kết thúc khác nhau. Khi đó chỉ cần nhìn vào ký tự tiếp theo trên xâu vào thì sẽ xác định đƣợc cần triển khai A theo i nào. Một văn phạm thỏ mãn điều này gọi là văn phạm LL(1). Ví dụ 3.9: Xét văn phạm sinh ra các câu lệnh trong ngôn ngữ lập trình Pascal: IF THEN ELSE WHILE DO BEGIN END 96
Chƣơng 3. Phân tích cúa pháp Trong ví dụ này, rõ ràng là nếu đang ở nút của cây phân tích có nhãn và con trỏ đang trỏ vào ký tự „I‟ hoặc „W‟ hoặc „B‟ trên xâu vào thì có thể xác định đƣợc ngay cần sử dụng luật sinh nào trong 3 luật sinh trên. 2) Phân tích dự đoán dựa trên sơ đồ chuyển Sơ đồ chuyển đƣợc sử dụng nhƣ một công cụ để thể hiện giải thuật phân tích cú pháp dự đoán. Trƣớc hết, hãy xét cách xây dựng sơ đồ chuyển cho bộ phân tích cú pháp dự đoán. a) Xây dựng sơ đồ chuyển cho bộ phân tích dự đoán Giả sử cho văn phạm G, trƣớc hết ta thực hiện: - Khử tính nhập nhằng của văn phạm; - Khử đệ quy trái; - Thừa số hoá bên trái; Sau đó, với mỗi biến hay Nonterminal A ta xây dựng một sơ đồ chuyển cho A - luật sinh dạng A x1x2 xn nhƣ sau: - Tạo một trạng thái bắt đầu và một trạng thái kết thúc. - Tạo một đƣờng đi từ trạng thái bắt đầu đến trạng thái kết thúc bằng các cung có hƣớng mang nhãn xi với i = 1, 2, , n nhƣ hình 3.8 x1 x2 xn 0 1 2 n Hình 3.8. Sơ đồ chuyển của một biến Một cách cụ thể, sơ đồ chuyển đƣợc xây dựng 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ơ đồ chuyển trong đó nhãn cho các cung là token hoặc ký hiệu kết thúc hoặc chƣa kết thúc. 2. Mỗi token hoặc ký hiệu kết thúc tƣơng ứng với việc đoán nhận token hoặc ký hiệu kết thúc đó và đọc t tiếp theo. 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 đó. A8 - 8 97
Chƣơng 3. Phân tích cúa pháp 4. Mỗi luật sinh có dạng A → α | α | | α tƣơng ứng với sơ đồ chuyển 1 2 n α1 α2 αn 5. Mỗi luật sinh dạng A → α α α tƣơng ứng với sơ đồ chuyển 1 2 n α1 α2 αn Ví dụ 3.10: 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. Sau khi loại bỏ đệ quy trái trong văn phạm, ta đƣợc văn phạm tƣơng đƣơng với các luật sinh 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ơ đồ chuyển 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. 98
Chƣơng 3. Phân tích cúa pháp Các sơ đồ chuyển tƣơng ứng: T E‟ E: 0 1 2 + T E‟ E‟: 3 4 5 6  F T: T‟ 7 8 9 * F T‟ T‟: 10 11 12 13 ‟: ‟:  : : ( E ) F: 14 15 16 17 ‟: id : : Hình 3.9. Sơ đồ chuyển cho các biến Các sơ đồ chuyển 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.  + T E‟: 3 4 5 6  T + E‟: 3 4 6  T T E: 0 3 + 4 6  +  T E: 0 3 6 99
Chƣơng 3. Phân tích cúa pháp Tƣơng tự ta có *  F T: 7 8 13 ( F ) F: 14 15 16 17 id Hình 3.10. Sơ đồ chuyển rút gọn b) Giải thuật phân tích dự đoán dựa vào sơ đồ chuyển Quá trình phân tích cú pháp từ trên xuống theo phƣơng pháp dự đoán dựa vào sơ đồ chuyển đƣợc tiến hành nhƣ sau: Input: Sơ đồ chuyển và xâu vào w$ Output: phân tích đƣợc xâu vào? Process: Bƣớc 1: Xuất phát từ trạng thái bắt đầu của ký tự khởi đầu trong tập N, con trỏ trỏ vào ký tự đầu tiên của xâu vào w. Bƣớc 2: Nếu trên sơ đồ chuyển đang ở nút i và cung đi ra đầu tiên có nhãn là  đang nối với nút j thì khi đó: - Nếu  là ký tự kết thúc (Terminal) và ký tự mà con trỏ đang trỏ trong w cũng là  thì con trỏ trỏ đến ký tự tiếp theo của xâu w; quá trình duyệt chuyển sang nút j. - Nếu  là biến (Nonterminal) thì quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong sơ đồ chuyển của biến . + Nếu quá trình duyệt đến đƣợc trạng thái kết thúc của biến  thì quá trình duyệt quay trở lại nút j. + Ngƣợc lại * Nếu ở nút i còn cung đi ra thì chọn cung đi ra tiếp theo và quay lại bƣớc 2. * Nếu đã xét hết các cung đi ra khỏi nút i và quá trình duyệt không đến đƣợc trạng thái kết thúc của biến  thì báo lỗi. - Nếu từ nút i đến nút j có cung mang nhãn , thì quá trình duyệt chuyển thẳng đến nút j và con trỏ trỏ vào ký tự trên xâu vào w đứng yên. Bƣớc 3: Nếu quá trình duyệt đã duyệt hết xâu vào và: 100
Chƣơng 3. Phân tích cúa pháp - Nếu quá trình duyệt đến đƣợc trạng thái kết thúc của một sơ đồ chuyển thì thông báo thành công. - Ngƣợc lại, nếu không đến đƣợc trạng thái kết thúc của một sơ đồ chuyển thì thông báo lỗi. Ví dụ 2.11: Cho văn phạm có sơ đồ chuyển hình 3.10. Hãy phân tích các xâu vào: - w = id + id * id$ Xuất phát từ trạng thái 0 của ký hiệu khởi đầu E của văn phạm. Con trỏ trỏ vào ký tự đầu tiên của xâu vào id + id * id$ là id. Trên sơ đồ chuyển đang ở nút 0 và cung đi ra có nhãn là T đang nối với nút có nhãn là 3. Vì T là biến, do đó quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong sơ đồ chuyển của T là 7 . Trên sơ đồ chuyển của T đang ở nút 7 và cung đi ra có nhãn là F đang nối với nút có nhãn là 8. Vì F là biến, do đó quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong sơ đồ chuyển của F là 14 . Trên sơ đồ chuyển của F đang ở nút 14 và có 2 cung đi ra có nhãn là id và ( đang nối với nút có nhãn là 17 và 15. Chọn cung đi ra có nhãn là id, trùng với token đƣợc trỏ bởi con trỏ trên xâu vào. Con trỏ trên xâu vào chuyển sang ký tự tiếp theo là +, tức là ký tự đầu tiên của xâu + id * id$. Quá trình duyệt chuyển sang nút có nhãn là 17. Vì 17 là nút kết thúc của F nên quá trình duyệt chuyến sang nút có nhãn là 8 trong sơ đồ chuyển của T. Trên sơ đồ chuyển của T đang ở nút 8 và có 2 cung đi ra có nhãn là * và  đang nối với nút có nhãn là 7 và 13. Chọn cung đi ra có nhãn là . Vì nhãn là , do đó quá trình duyệt chuyển sang duyệt nút 13. Vì 13 là nút kết thúc của T nên quá trình duyệt chuyến sang nút có nhãn là 3 trong sơ đồ chuyển của E. Trên sơ đồ chuyển của E đang ở nút 3 và có 2 cung đi ra có nhãn là + và  đang nối với nút có nhãn là 0 và 6. Chọn cung đi ra có nhãn là +, trùng với token đƣợc trỏ bởi con trỏ trên xâu vào. Con trỏ trên xâu vào chuyển sang ký tự tiếp theo là id, tức là ký tự đầu tiên của xâu id * id$. Quá trình duyệt chuyển sang nút có nhãn là 0. 101
Chƣơng 3. Phân tích cúa pháp Trên sơ đồ chuyển của E đang ở nút 0 và cung đi ra có nhãn là T đang nối với nút có nhãn là 3. Vì T là biến, do đó quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong sơ đồ chuyển của T là 7 . Trên sơ đồ chuyển của T đang ở nút 7 và cung đi ra có nhãn là F đang nối với nút có nhãn là 8 trong sơ đồ chuyển của T. Vì F là biến, do đó quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong sơ đồ chuyển của F là 14 . Trên sơ đồ chuyển của F đang ở nút 14 và có 2 cung đi ra có nhãn là id và ( đang nối với nút có nhãn là 17 và 15. Chọn cung đi ra có nhãn là id, trùng với token đƣợc trỏ bởi con trỏ trên xâu vào. Con trỏ trên xâu vào chuyển sang ký tự tiếp theo là *, tức là ký tự đầu tiên của xâu * id$. Quá trình duyệt chuyển sang nút có nhãn là 17. Vì 17 là nút kết thúc của F nên quá trình duyệt chuyến sang nút có nhãn là 8 trong sơ đồ chuyển của T. Trên sơ đồ chuyển của T đang ở nút 8 và có 2 cung đi ra có nhãn là * và  đang nối với nút có nhãn là 7 và 13. Chọn cung đi ra có nhãn là *, trùng với ký tự đƣợc trỏ bởi con trỏ trên xâu vào. Con trỏ trên xâu vào chuyển sang ký tự tiếp theo là id, tức là ký tự đầu tiên của xâu id$. Quá trình duyệt chuyển sang nút có nhãn là 7 của sơ đồ chuyển của T. Trên sơ đồ chuyển của T đang ở nút 7 và cung đi ra có nhãn là F đang nối với nút có nhãn là 8. Vì F là biến, do đó quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong sơ đồ chuyển của F là 14 . Trên sơ đồ chuyển của F đang ở nút 14 và có 2 cung đi ra có nhãn là id và ( đang nối với nút có nhãn là 17 và 15. Chọn cung đi ra có nhãn là id, trùng với token đƣợc trỏ bởi con trỏ trên xâu vào. Con trỏ trên xâu vào chuyển sang ký tự tiếp theo là $, tức là ký tự kết thúc xâu. Quá trình duyệt chuyển sang nút có nhãn là 17. Vì 17 là nút kết thúc trong sơ đồ chuyển của F và đã duyệt hết xâu vào nên quá trình duyệt kết thúc và thông báo thành công. - w = id + * id + id$ 102
Chƣơng 3. Phân tích cúa pháp Xuất phát từ trạng thái 0 của ký hiệu khởi đầu E của văn phạm. Con trỏ trỏ vào ký tự đầu tiên của xâu vào id + * id + id$ là id. Trên sơ đồ chuyển của E đang ở nút 0 và cung đi ra có nhãn là T đang nối với nút có nhãn là 3. Vì T là biến, do đó quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong sơ đồ chuyển của T là 7 . Trên sơ đồ chuyển của T đang ở nút 7 và cung đi ra có nhãn là F đang nối với nút có nhãn là 8. Vì F là biến, do đó quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong sơ đồ chuyển của F là 14 . Trên sơ đồ chuyển của F đang ở nút 14 và có 2 cung đi ra có nhãn là id và ( đang nối với nút có nhãn là 17 và 15. Chọn cung đi ra có nhãn là id, trùng với token đƣợc trỏ bởi con trỏ trên xâu vào. Con trỏ trên xâu vào chuyển sang ký tự tiếp theo là +, tức là ký tự đầu tiên của xâu + * id + id$. Quá trình duyệt chuyển sang nút có nhãn là 17 của sơ đồ F. Vì 17 là nút kết thúc của F nên quá trình duyệt chuyến sang nút có nhãn là 8 trong sơ đồ chuyển của T. Trên sơ đồ chuyển của T đang ở nút 8 và có 2 cung đi ra có nhãn là * và  đang nối với nút có nhãn là 7 và 13. Chọn cung đi ra có nhãn là . Vì nhãn là , do đó quá trình duyệt chuyển sang duyệt nút 13. Vì 13 là nút kết thúc của T nên quá trình duyệt chuyến sang nút có nhãn là 3 trong sơ đồ chuyển của E. Trên sơ đồ chuyển của E đang ở nút 3 và có 2 cung đi ra có nhãn là + và  đang nối với nút có nhãn là 0 và 6. Chọn cung đi ra có nhãn là +, trùng với token đƣợc trỏ bởi con trỏ trên xâu vào. Con trỏ trên xâu vào chuyển sang ký tự tiếp theo là *, tức là ký tự đầu tiên của xâu * id + id$. Quá trình duyệt chuyển sang nút có nhãn là 0. Trên sơ đồ chuyển của E đang ở nút 0 và cung đi ra có nhãn là T đang nối với nút có nhãn là 3. Vì T là biến, do đó quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong sơ đồ chuyển của T là 7 . Trên sơ đồ chuyển của T đang ở nút 7 và cung đi ra có nhãn là F đang nối với nút có nhãn là 8 trong sơ đồ chuyển của T. 103
Chƣơng 3. Phân tích cúa pháp Vì F là biến, do đó quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong sơ đồ chuyển của F là 14 . Trên sơ đồ chuyển của F đang ở nút 14 và có 2 cung đi ra có nhãn là id và ( đang nối với nút có nhãn là 17 và 15. Các nhãn này là token id và ký tự kết thúc ( đều không trùng với ký hiệu kết thúc * đang đƣợc trỏ bởi con trỏ trên xâu vào. Vì đã xét hết các cung đi ra khỏi các nút 14, 7 và 0 và quá trình duyệt không đến đƣợc trạng thái kết thúc của một sơ đồ chuyển nào nên quá trình duyệt dừng để thông báo lỗi . 2) Phân tích dự đoán dựa vào ngăn xếp (không đệ quy ) Trong phƣơng pháp phân tích cú pháp Top - Down cả hai kỹ thuật nêu trên đều sử dụng thủ tục đệ quy. Với phƣơng pháp phân tích dự đoán sử dụng ngăn xếp (Stack), ta có thể tránh đƣợc thủ tục đệ quy. a) Ý tưởng Mô hình tổ chức dữ liệu cho kỹ thuật này gồm các khối sau: - Một ngăn đệm (Buffer) dùng để chứa xâu vào w, với việc bổ sung ký hiệu hết xâu $. - Một ngăn xếp (Stack) với ký hiệu $ chỉ đáy ngăn xếp và có bổ sung ký hiệu khởi đầu S vào ngăn xếp. - Một bộ chƣơng trình điều khiển quá trình phân tích. - Một bảng phân tích cú pháp M[A, a], bảng này chứa các A - luật sinh dạng A ; (NT)+. - Một ngăn đệm dùng để chứa kết quả phân tích. b + a * c $ Chƣơng trình Dòng X phân tích kết quả Y Z $ Bảng phân tích cú pháp Hình 3.11. Mô tả hình tổ chức dữ liệu của kỹ thuật dự đoán 104
Chƣơng 3. Phân tích cúa pháp Chƣơng trình phân tích hoạt động theo nguyên tắc sau: - Con trỏ ip trỏ vào ký tự a trên xâu vào w. - Xét ký tự X trên đỉnh ngăn xếp, khi đó chƣơng trình hành động nhƣ sau: + Nếu X = a = $ chƣơng trình dừng, đƣa ra thông báo quá trình phân tích kết thúc thành công. + Nếu X = a $ thì đẩy X ra khỏi đỉnh Stack, con trỏ trên w dịch sang vị trí tiếp theo. + Nếu X là biến (Nonterminal), chƣơng trình dò tìm luật sinh X trên bảng M tại M[X , a], nếu có luật sinh này thì đƣợc đƣa vào ngăn xếp và quay lại bƣớc 1, nếu không có, chƣơng trình báo lỗi. b) Giải thuật phân tích cú pháp dự đoán dựa vào ngăn xếp Input: G - CFG, xâu vào w$ Output: Dẫn xuất trái nhất của w hoặc thông báo lỗi. Process: 1. Khởi tạo: + Bổ sung ký tự $ vào Stack chỉ đáy ngăn xếp; + Đƣa ký hiệu chƣa kết thúc bắt đầu S vào đỉnhStack; + Đƣa vào ngăn đệm xâu vào w$; + Con trỏ ip trỏ tới ký hiệu đầu tiên của xâu w$ ; 2. REPEAT - X là ký hiệu nằm trên đỉnh Stack; - ip đang trỏ vào ký tự a của xâu vào w$; IF (X T) OR (X = $) THEN IF X = a THEN Begin - Đẩy X ra khỏi Stack; - ip := ip +1; end ELSE witeln(„Thông báo lỗi‟) ELSE {X N} IF M[X, a] = X Y1 Y2 .Yk THEN 105
Chƣơng 3. Phân tích cúa pháp begin - Đẩy X ra khỏi Stack; - Đẩy Yk , Y2, , Y1 vào Stack { Y1 ở đỉnh}; - Đƣa luật sinh X Y1 Y2 .Yk ra Buffer kết quả; end ELSE witeln(„Thông báo lỗi‟) UNTIL X = $ Ví dụ 3.12: Xét văn phạm sau: E TE‟; E‟ +TE‟; E‟ ; T FT‟; T‟ *FT‟; T‟ ; F (E); F id. Bảng phân tích cú pháp M cho văn phạm trên ở bảng 3.1. Cần chú ý rằng, các luật sinh ghi trong bảng M theo nguyên tắc nào, ta chƣa biết và ta sẽ đề cập đến vấn đề này sau. 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 Quá trình phân tích cú pháp cho xâu vào id + id * id đƣợc trình bày trong bảng sau: 106
Chƣơng 3. Phân tích cúa pháp Bƣớc STACK INPUT OUTPUT Khởi tạo $ E id + id * id $ 1 $ E' T id + id * id $ E T E' 2 $ E' T F' id + id * id $ T F T' 3 $ E' T' id id + id * id $ F id 4 $ E' T' + id * id $ 5 $ E' + id * id $ T'  6 $ E' T + + id * id $ E' + T E' 7 $ E' T id * id $ 8 $ E' T' F id * id $ T F T' 9 $ E' T' id id * id $ F id 10 $ E' T' * id $ T' * F T' 11 $ E' T' F * * id $ 12 $ E' T' F id $ 13 $ E' T' id id $ F id 14 $ E' T' $ 15 E' $ $ T'  16 $ $ E'  Bảng 3.2. Phân tích cú pháp cho xâu vào id + id * id Cây phân tích cú pháp đƣợc hình thành từ output : E T E‟ F T‟ + T E‟   id F T‟ * F T‟ id id  Hình 3.12. Cây phân tích cú pháp cho xâu vào id + id * id được xây dựng từ dưới lên 107
Chƣơng 3. Phân tích cúa pháp 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) Xây dựng bảng phân tích cú pháp Với mục đích hỗ trợ cho giải thuật xây dựng bảng phân tích cú pháp M và phục hồi lỗi theo chiến lƣợc panic_mode; ta xét cách xác định hai hàm FIRST và FOLLOW. . Hàm FIRST - Định nghĩa Cho văn phạm G = (N, T, P, S); giả sử là xâu các ký hiệu văn phạm, tức là (N T)*. FIRST(α) là tập hợp các ký hiệu kết thúc a mà a là ký hiệu bắt đầu của một xâu đƣợc dẫn xuất từ α. * * FIRST( ) = a T a;  (NT)  * Nếu trong P có  thì  cũng thuộc FIRST ( ). FIRST( ) cho ta biết xâu có thể dẫn xuất đến tận cùng thành một xâu bắt đầu bằng một ký hiệu kết thúc nào. - Cách xác định hàm FIRST(X) với X là một ký hiệu văn phạm 1. Nếu X là ký tự kết thúc thì FIRST(X) = {X} 2. Nếu X  là một luật sinh thì thêm  vào FIRST(X) 3. Nếu X Y1Y2 Yk là một luật sinh thì thêm FIRST(Y1) trừ  vào FIRST(X). Nếu  FIRST(Y1) thì tiếp tục thêm FIRST(Y2) trừ  vào FIRST(X). Nếu  FIRST(Y1)  FIRST(Y2) thì tiếp tục thêm FIRST(Y3) trừ  vào FIRST(X). Nếu  FIRST(Yt) với mọi t = 1, 2, , i và i < k thì tiếp tục thêm FIRST(Yi+1) trừ  k vào FIRST(X). Cuối cùng thêm  vào FIRST(X) nếu  i 1 FIRST(Yi). Để tính FIRST của các ký tự không kết thúc trong một văn phạm, ta lần lƣợt xét tất cả các luật sinh. Tại mỗi luật sinh, áp dụng các quy tắc trên để thêm các ký tự vào các tập FIRST. Quá trình này đƣợc tiếp tục cho đến khi gặp một lƣợt duyệt mà không bổ sung thêm đƣợc bất kỳ một ký tự kết thúc nào hoặc  vào các tập FIRST thì kết thúc. 108
Chƣơng 3. Phân tích cúa pháp Ví dụ 3.13: Cho văn phạm có các luật sinh sau: E TE' (1) E' + TE' (2) E'  (3) T FT' (4) T' * FT' (5) T'  (6) F (E) (7) F id (8) Tính FIRST(F): - Từ luật sinh (7), theo quy tắc 3 ta thêm đƣợc FIRST(„(‟) = „(‟ (theo quy tắc1) vào FIRST(F). - Từ luật sinh (8), theo quy tắc 3 ta thêm đƣợc FIRST(id) = „id‟ (theo quy tắc1) vào FIRST(F). - Không còn luật sinh nào có vế trái là F nữa. Vì vậy, ta không thể thêm ký hiệu nào vào FIRST(F) nữa FIRST(F) = { (, id }. - Tính FIRST(E' ): - Từ luật sinh (2), theo quy tắc 3 ta thêm đƣợc FIRST(+) = + (theo quy tắc1) vào FIRST(E'). - Từ luật sinh (3), theo quy tắc 2 ta thêm đƣợc  vào FIRST(E'). - Không còn luật sinh nào có vế trái là E' nữa. Vì vậy, ta không thể thêm ký hiệu nào vào FIRST(E') nữa FIRST(E') = { +, }. Tƣơng tự FIRST(T') = { *, }. Từ luật sinh (4), theo quy tắc 3: T FT' và  FIRST(F) FIRST(T) = FIRST(F) = { (, id } Tƣơng tự từ E TE' và  FIRST(T) FIRST(E) = FIRST(T) = { (, id } Vậy ta có: FIRST(E) = FIRST(T) = FIRST(F) = { (, id } FIRST(E') = {+,  } FIRST(T') = {*,  } 109
Chƣơng 3. Phân tích cúa pháp Ta cũng có thể tính FIRST của một xâu nhƣ sau: Giả sử = Y1Y2 .Yk . Trong trƣờng hợp này, ta tính FIRST( ) nhƣ quy tắc 3 ở trên: 1. thêm FIRST(Y1) trừ  vào FIRST( ). 2. Nếu  FIRST(Y1) thì tiếp tục thêm FIRST(Y2) trừ  vào FIRST( ). Nếu  FIRST(Y1)  FIRST(Y2) thì tiếp tục thêm FIRST(Y3) trừ  vào FIRST( ). Nếu  FIRST(Yt) với mọi t = 1, 2, , i và i < k thì tiếp tục thêm FIRST(Yi+1) trừ  vào k FIRST( ). Cuối cùng thêm  vào FIRST( ) nếu  i 1 FIRST(Yi). . Hàm FOLLOW - Ðịnh nghĩa Cho văn phạm G = (N, T, P, S); A là một ký hiệu chƣa kết thúc. FOLLOW(A) 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 bên phải nhất trong một dạng câu nào đó thì $ FOLLOW(A) ($ là ký hiệu kết thúc xâu vào). * * FOLLOW(A) = a T S Aa; ,  (N  T)  * $ FOLLOW(A) S A . Nói một cách khác FOLLOW(A) là tập các ký tự vào hay các kết thúc xuất hiện ngay sau biến A về bên phải trong một dẫn xuất nào đó. - Cách xác định hàm FOLLOW(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 thêm vào để đánh dấu kết thúc chuỗi nhập. 2. Nếu có một luật sinh B A thì thêm mọi phần tử khác  của FIRST() vào trong FOLLOW(A) tức là FOLLOW(A) = FOLLOW(A) FIRST() \  3. Nếu có luật sinh B A, hoặc B A mà  FIRST() thì thêm tất cả các phần tử trong FOLLOW(B) vào FOLLOW(A) tức là FOLLOW(A) = FOLLOW(A)  FOLLOW(B). 110
Chƣơng 3. Phân tích cúa pháp Để tính FOLLOW của các ký tự không kết thúc trong một văn phạm, ta lần lƣợt xét tất cả các luật sinh. Tại mỗi luật sinh, áp dụng các quy tắc trên để thêm các ký tự vào các tập FOLLOW. Quá trình này đƣợc tiếp tục cho đến khi gặp một lƣợt duyệt mà không bổ sung thêm đƣợc bất kỳ một ký tự kết thúc nào vào các tập FOLLOW thì kết thúc. Ví dụ 3.14: Cho văn phạm có các luật sinh sau: E TE' (1) E' + TE' (2) E'  (3) T FT' (4) T' * FT' (5) T'  (6) F (E) (7) F id (8) Tính FOLLOW(E): - Vì E là ký hiệu khởi đầu, theo quy tắc 1 ta thêm $ vào FOLLOW(E) . - Áp dụng quy tắc 2 cho luật sinh (7): F (E) ) FOLLOW(E) FOLLOW(E) ={$, )} - Không còn áp dụng đƣợc quy tắc nào cho E nữa. Vậy FOLLOW(E) ={$, )} . Tính FOLLOW(E'): - Áp dụng quy tắc 3 cho luật sinh (1): E TE' ta thêm mọi ký hiệu của FOLLOW(E) vào FOLLOW(E') ), $ FOLLOW(E‟) - Không thêm đƣợc ký hiệu nào vào FOLLOW(E') nữa FOLLOW(E') ={$, )} - Áp dụng luật 2 cho luật sinh (1): E TE' + FOLLOW(T). - Áp dụng luật 3 cho luật sinh (2, 3): E‟ +TE' , E'  FOLLOW(E')  FOLLOW(T) FOLLOW(T) = { +, ), $ }. - Áp dụng quy tắc 3 cho luật sinh (4): T FT' thì FOLLOW(T') = FOLLOW(T) = {+, ), $ } 111
Chƣơng 3. Phân tích cúa pháp Áp dụng quy tắc 2 cho luật sinh (4): T FT' * FOLLOW(F) Áp dụng quy tắc 3 cho luật sinh (5, 6): T' *FT' ; T'  FOLLOW(T')  FOLLOW(F) FOLLOW(F) = {*, +, ), $ }. Vậy ta có: FOLLOW(E) = FOLLOW(E') = { $, ) } FOLLOW(T) = FOLLOW(T') = { +, ), $ } FOLLOW(F) = {*, +, ), $ } . Giải thuật xây dựng bảng phân tích cú pháp Sử dụng các hàm FIRST , FOLLOW có thể đƣa ra giải thuật xây dựng bảng phân tích cú pháp cho một văn phạm phi ngữ cảnh nhƣ sau: Input: Văn phạm phi ngữ cảnh Output: Bảng phân tích cú pháp M Process: Bƣớc 1: Với mỗi luật sinh A P thực hiện bƣớc 2, 3. Bƣớc 2: Với mỗi a FIRST( ) thì M[A, a]:= “A ” (đƣa luật sinh A vào vị trí M[A, a] Bƣớc 3: Nếu  FIRST ( ) thì M[A, b]:= “A ” với mọi b Follou (A). Bƣớc 4: Các vị trí M[A, a] chƣa xác định sau khi thực hiện các bƣớc 2, 3 coi là lỗi (ERROR). Ví dụ 3.15: Cho văn phạm có các luật sinh sau: E TE'; E' + TE'; E'  T FT' T' * FT' ; T'  ; F (E) ; F id Áp dụng giải thuật xây dựng bảng phân tích cú pháp dự đoán cho văn phạm trong ví dụ trên: 112
Chƣơng 3. Phân tích cúa pháp - Xét 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' - Xét luật sinh E' + TE' : Tính FIRST(+TE') = FIRST(+) = {+} M[E', +] chứa E' +TE' - Xét luật sinh E' : Vì  FIRST(E') và FOLLOW(E') = { ), $ } E  nằm trong M[E', )] và M[E', $] - Xét luật sinh T' * FT' : Tính FIRST(* FT') = {* } T' * FT' nằm trong M[T', *] - Xét luật sinh T' ε: Vì ε FIRST(T') và FOLLOW(T') = {+, ), $} T' ε nằm trong M[T', +] , M[T', )] và M[T', $] - Xét luật sinh F (E) ; FIRST((E)) = { ( } F ( E) nằm trong M[F, (] - Xét luật sinh F id ; FIRST(id) = {id} F id nằm trong M[F, id] Kết quả 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.3 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.3. Bảng phân tích cú pháp 3) Văn phạm LL(1) Giải thuật xây dựng bảng phân tích cú pháp ở trên đây có thể áp dụng cho mọi loại văn phạm. Tuy nhiên có một số văn phạm (nhập nhằng hoặc đệ quy trái) có thể 113
Chƣơng 3. Phân tích cúa pháp xảy ra tình trạng ở mỗi vị trí M[A, a] có thể chứa nhiều luật sinh. Chẳng hạn khi G là văn phạm đệ quy trái hoặc là văn phạm nhập nhằng thì chắc chắn sẽ tồn tại ít nhất một ô trong bảng phân tích cú pháp M chứa nhiều luật sinh. Trong trƣờng hợp nhƣ vậy kỹ thuật phân tích cú pháp dự đoán sẽ hạn chế hiệu quả, vì là dẫn đến tình trạng không biết sử dụng luật sinh nào trong số các luật sinh ghi ở vị trí M[A, a] cho phù hợp với phân tích từ vào. Ví dụ sau đây chỉ ra tình trạng trên. Ví dụ 3.16: Xét văn phạm: S → i E t S | i E t S e S | a E → b Sau khi thừa số hoá bên trái, ta có văn phạm tƣơng đƣơng: S i E t S S‟| a ; S‟ e S |  ; E b. Khi đó dựa vào giải thuật xây dựng bảng phân tích cú pháp cho văn phạm trên ta có bảng M. a b e i t $ S S a S i E t S S‟ S‟  S‟ S‟  S‟ e S E E b Bảng 3.4. Bảng phân tích cú pháp a) Định nghĩa Một văn phạm đƣợc gọi là văn phạm LL(1) nếu mọi ô trong bảng phân tích cú pháp của nó chỉ chứa không quá một luật sinh. Ở đây ký tự “L” thứ nhất chỉ rằng quá trình dò đọc xâu vào đƣợc tiến hành từ bên trái (Left). Ký tự “L” thứ hai chỉ rằng quá trình phân tích cú pháp sẽ chỉ ra dẫn xuất trái nhất, cuối cùng chữ số “1” chỉ số ký tự cần biết để dự đoán cần phải chọn luật sinh nào cho thích hợp. 114
Chƣơng 3. Phân tích cúa pháp Ngƣời ta đã chứng minh đƣợc rằng nếu văn phạm G là văn phạm LL(1) thì sử dụng giải thuật xây dựng bảng phân tích cú pháp nêu trên có thể phân tích đƣợc mọi xâu vào của L(G). b) Các tính chất của LL(1) Văn phạm LL(1) có một số tính chất đặc biệt sau: 1. Nếu văn phạm G là LL(1) thì G không là văn phạm nhập nhằng. 2. Nếu văn phạm G là LL(1) thì G không là văn phạm đệ quy trái. 3. Văn phạm G là LL(1) khi và chỉ khi hai luật sinh khác nhau. A và A  của G thoả mãn điều kiện sau: * * - Không tồn tại a T để a và  a * * - Chỉ có thể có tối đa một trong hai dẫn xuất  hoặc   * - Nếu   thì không thể dẫn ra xâu bắt đầu bằng a T và a FOLLOW(A). Chú ý: - Nói chung không có quy tắc tổng quát để biến đổi một văn phạm về văn phạm LL(1). - Một văn phạm có thể tiến hành khử nhập nhằng, khử đệ quy trái, thừa số hoá bên trái để đƣợc một văn phạm LL(1); song sẽ phải trả giá về sự phức tạp, cồng kềnh, thậm chí khó biên dịch hơn khi chƣa biến đổi. 4) 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 gặp một trong hai trƣờng hợp sau: 1. Ký hiệu kết thúc trên đỉnh Stack không phù hợp với token kế tiếp trong xâu vào. 2. Trên đỉnh Stack là ký hiệu chƣa kết thúc A, token trong xâu vào 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 xâu vào 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ố mẹo (heuristics) có thể là: 115
Chƣơng 3. Phân tích cúa pháp 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. 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 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 xâu vào. Ví dụ 3.17: 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.13. 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ộ : 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.5. 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. 116
Chƣơng 3. Phân tích cúa pháp - Nếu M[A,a] là "synch" thì lấy A ra khỏi Stack nhằm tái hoạt độ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 xâu vào thì lấy token ra khỏi Stack. Chẳng hạn, với xâu vào: w = + 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: Bƣớc STACK INPUT OUTPUT Khởi tạo $ E + id * + id $ Error, nhảy qua + 1 $ E id * + id $ E T E' 2 $ E T' id * + id $ T F T' 3 $ E' T' F id * + id $ F id 4 $ E' T' id id * + id $ 5 $ E' T' * + id $ T' * F T' 6 $ E' T' F * * + id $ 7 $ E' T' F + id $ Error, M[F,+] = synch đẩy F 8 $ E' T' + id $ T'  9 $ E' + id $ E' + T E' 10 $ E T' + + id $ 11 $ E' T' id $ 12 $ E' T' F id $ T' F T' 13 id T' E' $ id $ F id 14 T' E' $ $ 15 E' $ $ T' ε 16 $ $ E' ε Bảng 3.6. Phân tích cú pháp cho xâu vào + id * + id phục hồi lỗi 3.4. Phân tích cú pháp từ dƣới lên (Bottom - up parsing) Phân tích cú pháp từ dƣới lên thực chất là cách phân tích một xâu vào và tìm cách thay thế các xâu bằng các biến để rút gọn xâu về ký tự bắt đầu của văn phạm. Về mặt hình ảnh, phân tích cú pháp từ dƣới lên đƣợc coi là quá trình phân tích bắt 117
Chƣơng 3. Phân tích cúa pháp đầu đi từ các nút lá hƣớng dần về gốc của cây. Ngƣời ta phân chia phƣơng pháp phân tích từ dƣới lên thành các phƣơng pháp sau: 1. Phƣơng pháp phân tích đẩy - thu (Shift – Reduce Parsing) 2. Phƣơng pháp phân tích thứ bậc toán tử (Operator – Precedence parsing) 3. Phƣơng pháp phân tích LR. 3.4.1. Phân tích đẩy thu ( Shift – Reduce parsing) 1) Khái niệm Phƣơng pháp phân tích đẩy – thu là phƣơng pháp rút gọn xâu đã cho về ký hiệu bắt đầu của văn phạm. Trong quá trình thu gọn cố gắng tìm xâu con của các xâu trung gian trùng với vế phải của luật sinh nào đó rồi thay thế xâu con này bằng biến ở vế trái của luật sinh đó. Nếu xâu con đƣợc chọn đúng ở mỗi bƣớc thì một dẫn xuất phải đảo ngƣợc sẽ đƣợc xây dựng. Ví dụ 3.18: Xét văn phạm có các luật sinh sau: 1. S aABe 2. A Abc 3. A b 4. B d Cho xâu w = abbcde, ta thấy xâu w có thể rút gọn về ký tự bắt đầu S theo các bƣớc sau: a b b c d e  a A b c d e  a A d e  a A B e  S Hay S 1 aABe 4 aAde 2 aAbcde 3 abbcde Thực chất quá trình rút gọn này là quá trình thể hiện ngƣợc lại của các bƣớc trong dẫn xuất sau: S 1 aABe 4 aAde 2 aAbcde 3 abbcde 118
Chƣơng 3. Phân tích cúa pháp 2) Từ thế (Handle) Một cách trực quan ta có thể hình dung từ thế nhƣ là xâu con trùng với vế phải của luật sinh . Quá trình phân tích đẩy – thu đòi hỏi phải tìm đƣợc các từ thế để thay thế nó bằng các biến ở vế trái của luật sinh có vế phải trùng với từ thế. Khó khăn ở đây là phải phát hiện từ thế thích hợp để có thể tiếp tục quá trình rút gọn về ký tự bắt đầu. Nếu chỉ ra từ thế không thích hợp có thể làm cho quá trình phân tích thất bại. Ví dụ 3.19: Xét văn phạm có các luật sinh sau: 1. S aABc 2. A Abc 3. A b 4. B d Và xét xâu w = abbcde Thử nhìn lại cách rút gọn ở vị trí trên với từ thế khác và không xem Abc là từ thế mà xem b là từ thế thì sẽ có: ? 4 aAAcde 3 aAbcde 3 abbcde Trong trƣờng hợp này không thể rút gọn tiếp về ký tự bắt đầu S. Vì lý do trên cần phải đƣa ra khái niệm chặt chẽ hơn về từ thế. Từ thế (Handle) của một xâu là một xâu con hợp với vế phải của luật sinh và nếu thu gọn nó thành vế trái của luật sinh đó thì có thể dẫn đến ký hiệu chƣa kết thúc bắt đầu. Một cách hình thức thì xâu  là từ thế của xâu w nếu có dẫn xuất phải nhất: * * * S Rm Aw Rm w và trong P có luật sinh A  P ở đây w T ; V . Dễ dàng nhận ra rằng từ thế là xâu con của xâu đƣợc sinh ra từ dẫn xuất phải nhất (Rightmost derivation). Chú ý: Trong trƣờng hợp văn phạm nhập nhằng thì ở mỗi bƣớc, dẫn xuất phải có thể có lựa chọn một trong nhiều luật sinh để sử dụng vì vậy có thể có nhiều từ thế. Nếu văn phạm không nhập nhằng thì mỗi bƣớc trong dẫn xuất phải nhất chỉ có một luật sinh đƣợc sử dụng và do đó chỉ có một từ thế mà thôi. 119
Chƣơng 3. Phân tích cúa pháp Ví dụ 3.20: Xét văn phạm: E E + E E E * E E (E) E id Xét dẫn xuất phải nhất E Rm E + E Rm E + E * E Rm E + E * id3 Rm E + id2 * id3 Rm id1 + id2 * id3 Các id1, id2, id3 là ký hiệu của từ thế của id trong dãy trên và . Vì văn phạm trên là văn phạm nhập nhằng, nên nó có một dẫn xuất phải nhất khác cũng sinh ra xâu trên. E Rm E * E Rm E * id3 Rm E + E * id3 Rm E + id2 * id3 Rm id1 + id2 * id3 3) Thay từ thế (Handle Pruning) Thay từ thế (Handle pruning) là kỹ thuật dùng để tạo ra dẫn xuất phải nhất đảo ngƣợc từ chuỗi ký hiệu kết thúc w mà ta muốn phân tích. Nếu w là một xâu của văn phạm thì w = γ . Trong đó, γ là dạng câu phải thứ n n n của dẫn xuất phải nhất mà ta chƣa biết. S = γ γ γ γ γ = w 0 Rm 1 Rm 2 Rm Rm n-1 Rm n Ðể xây dựng dẫn xuất này theo thứ tự ngƣợc lại, ta tìm từ thế (handle) β trong n γ và thay thế β bởi An (A là vế trái của luật sinh A → β ) để đƣợc dạng câu phải n n n n n 120
Chƣơng 3. Phân tích cúa pháp thứ n -1 là γ . Quy luật trên cứ tiếp tục. Nếu ta có một dạng câu phải γ = S thì sự n-1 0 phân tích thành công. Ví dụ 3.21: Cho văn phạm: E → E + E | E * E | (E) | id Và xâu vào w = id1 + id2 * id3 , ta có các bƣớc thu gọn xâu vào thành ký hiệu bắt đầu E nhƣ sau: w = id1 + id2 * id3  E + id2 * id3  E + E * id3  E * id3  E * E  E 4) Kỹ thuật phân tích đẩy - thu Khi phân tích cú pháp bằng phƣơng pháp đẩy thu cần phải thực hiện quá trình thu gọn. Quá trình thu gọn đặt ra hai vấn đề cần giải quyết: - Cần phát hiện ra từ thế? - Tìm luật sinh nào để thay từ thế? a) Ý tưởng Kỹ thuật dùng ngăn xếp cho phân tích đẩy - thu đƣợc mô tả trong hình 3.13 Xâu vào w a1 a2 a3 an $ Stack Chƣơng trình điều khiển a2 a1 $ Hình 3.13. Mô hình phân tích đẩy – thu 121
Chƣơng 3. Phân tích cúa pháp Trong kỹ thuật này sử dụng: - Một ngăn đệm (Buffer) dùng để chứa xâu vào w cùng với ký hiệu hết xâu $; một con trỏ ip dò đọc xâu vào từ trái sang phải. - Một ngăn xếp (Stack) chứa các ký hiệu của văn phạm, đầu tiên ngăn xếp rỗng, ký hiệu $ ở đỉnh Stack. - Một chƣơng trình phân tích và điều khiển quá trình đẩy và thu các ký hiệu của văn phạm trên Stack. Chƣơng trình phân tích thực hiện 3 thao tác cơ bản sau: 1. Đẩy các ký hiệu của xâu vào w vào ngăn xếp cho đến khi hết xâu hoặc một từ thế (handle) β nằm trên đỉnh Stack. 2. Thu gọn từ thế β trên đỉnh Stack bằng một biến là vế trái của một luật sinh nào đó cho đến khi hết từ thế. 3. Lặp lại các thao tác 1 và 2 cho đến khi gặp một lỗi hoặc Stack chứa ký hiệu bắt đầu và bộ đệm rỗng (thông báo kết thúc thành công). b) Giải thuật phân tích đẩy - thu Input: G - CFG, xâu vào w$ Output: Thông báo thành công (Dẫn xuất trái nhất của w) hoặc thông báo lỗi. Process: 1. Khởi tạo: - Bổ sung ký hiệu kết thúc xâu $ đỉnh Stack; - Đƣa xâu vào w$ vào ngăn đệm; - Con trỏ ip trỏ tới ký hiệu đầu tiên của w$; 2. REPEAT ip đang trỏ vào ký tự a của xâu vào w$; While a Do Begin - Đẩy a vào Stack; - ip := ip +1; End; While Do Begin - Thu gọn từ thế bằng biến X sao cho X β 122
Chƣơng 3. Phân tích cúa pháp - Đƣa luật sinh X β ra Buffer kết quả; End; UNTIL a = $ If Then witeln(„Thông báo thành công‟) Else witeln(„Thông báo lỗi‟) Ví dụ 3.22: Xét văn phạm sau: E E + E; E E * E; E (E); E id. Áp dụng giải thuật trên, quá trình phân tích đẩy - thu của xâu w = id1+ id2 * id3 đƣợc trình bày trong bảng 3.7. Bƣớc Ngăn xếp Xâu vào Hành động Kết quả 1 $ id1 + id2* id3 $ đẩy 2 $id1 + id2 * id3$ Thu gọn E id 3 $E + id2 * id3$ đẩy 4 $E+ id2 * id3$ đẩy 5 $E+id2 * id3 $ Thu gọn E id 6 $E+E * id3 $ Thu gọn E E + E 7 $E * id3 $ đẩy 8 $E* id3 $ đẩy 9 $E*id3 $ Thu gọn E id 10 $E*E $ Thu gọn E E*E 11 $E $ Kết thúc thành công Bảng 3.7. Quá trình phân tích đẩy thu xâu id1 + id2* id3 123
Chƣơng 3. Phân tích cúa pháp Cây phân tích cú pháp tƣơng ứng là: E E E E E id1 + id2 * id3 Hình 3.13a. Cây phân tích cú pháp của xâu id+id*id được xây dựng từ dưới lên theo phương pháp đẩy-thu Chú ý: 1. Trong quá trình phân tích cú pháp đẩy - thu, từ thế luôn nằm trên phần đỉnh của Stack, không bao giờ từ thế nằm bên trong Stack. 2. Có một số văn phạm phi ngữ cảnh không sử dụng đƣợc kỹ thuật này, bởi vì có thể xảy ra tình huống biết hết xâu trong Stack và ký hiệu sắp đọc vào tiếp theo trên xâu vào nhƣng vẫn không thể quyết định đƣợc cần thu hay cần đẩy, hoặc có thể xảy ra không biết sử dụng luật sinh nào để thu, một khi có nhiều luật sinh lựa chọn. Chẳng hạn nhƣ với văn phạm: sttm IF expr THEN sttm sttm IF expr THEN sttm ELSE sttm sttm orther và hình trạng phân tích đang ở dạng: Ngăn xếp Xâu vào Hành động $ IF expr THEN sttm ELSE . $ ??? 3.4.2. 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 liền 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ử. 1) Quan hệ thứ tự ưu tiên Bảng định nghĩa 3 quan hệ thứ bậc đƣợc cho nhƣ sau: 124
Chƣơng 3. Phân tích cúa pháp Quan hệ Ý nghĩa 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ử 2) 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ử θ có độ ƣu tiên cao hơn θ thì θ •> θ và θ θ và θ •> θ nếu các toán tử là kết hợp trái. 1 2 2 1 + θ + ; + •> - ; - •> - ; - •> + Phép toán ↑ kết hợp phải nên ↑ •> •> + * •> •> $ <• <• <• Bảng 3.9. Bảng quan hệ thứ bậc các toán tử 125
Chƣơng 3. Phân tích cúa pháp Sử dụng $ để đánh dấu cuối xâu và $ + * $ Chẳng hạn, đầu tiên (trong ví dụ trên 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 không cần phải phân biệt chúng. 3) Giải thuật phân tích cú pháp thứ bậc toán tử Input: Xâu nhập w và bảng các quan hệ thứ bậc. Output: Nếu w là xâu 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. Process: 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 If $ nằm ở đỉnh Stack và ip chỉ đến $ then Begin writeln („thành công‟); Halt; End 126
Chƣơng 3. Phân tích cúa pháp 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; Until false 3.4.3. Phân tích LR(K) 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 xâu vào từ trái sang phải. R (rightmost derivation): Xây dựng dãy dẫn xuất phải nhất đảo ngƣợc. k : Số lƣợng ký hiệu vào đƣợ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 thì ngầm định là k = 1. Có ba phƣơng pháp phân tích LR là SLR (simple LR), LR và LALR (lookahead LR). Bộ phân tích cú pháp LR có các ƣu điểm: - 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. - 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 đẩy - thu 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. 127
Chƣơng 3. Phân tích cúa pháp - 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 xâu vào từ trái sang phải. Nhƣợc điểm chủ yếu 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 của ngôn ngữ lập trình điển hình. 3.4.4. Giải thuật phân tích LR 1) Ý tưởng Mô hình bộ phân tích cú pháp LR đƣợc chỉ ra ở hình 3.14 gồm: Inuput Stack a1 a2 a2 an $ Sm Xm Ouput LR parsing program Sm-1 Xm-1 Action goto S0 Hình 3.14. Mô hình bộ phân tích cú pháp LR Kênh vào (input) chứa xâu vào, kênh ra (output) chứa kết quả phân tích, một ngăn xếp (Stack) phục vụ cho thao tác đẩy - thu, một chƣơng trình điều khiển (Driver program) và một bảng phân tích cú pháp. • Ngăn xếp (Stack) lƣu một xâu dạng s X s X s X s trong đó sm nằm 0 1 1 2 2 m 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: Phần hành động (hàm action) xác định hành động đẩy hay thu gọn và phần chuyển đi (hàm goto) xác định và di chuyển đến trạng thái tiếp theo. - Hàm action[s , a ] có thể có một trong 4 giá trị : m i 1. shift s: đẩy s, trong đó s là một trạng thái. 128
Chƣơng 3. Phân tích cúa pháp 2. reduce A→ β: thu gọn bằng luật sinh A→ β. 3. accept: Chấp nhận 4. error: Báo lỗi - Hàm 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. Trong kỹ thuật này về cơ bản chƣơng trình điều khiển giống nhau ở mọi bộ phân tích LR, chỉ có phần bảng phân tích là khác nhau với các phƣơng pháp phân tích khác nhau. Hoạt động của bộ phân tích cú pháp LR đƣợc xác định bằng ký hiệu ai trên xâu vào w, trạng thái sm trên đỉnh Stack và thông tin trong mục Action sm, ai trong bảng phân tích cú pháp. Cụ thể hoạt động của nó nhƣ sau: Cấu hình (configuration) hay hình trạng 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, thành phần sau là phần xâu vào chƣa phân tích: (s X s X s X s , a a a $) 0 1 1 2 2 m m i i+1 n Với sm là ký hiệu trên đỉnh Stack, ai là ký hiệu vào hiện tại, cấu hình có đƣợc sau mỗi bƣớc đẩy - thu sẽ nhƣ sau : 1. Nếu Action sm, ai = shift s bộ phân tích thực hiện một động tác đẩy ai và trạng thái s lấy từ Action sm, ai vào ngăn xếp. Bộ phân tích chuyển sang hình trạng mới: (s0 X1 s1 X2 s2 Xm smais , ai+1 an $). Ký tự ai+1 trên xâu vào trở thành ký tự hiện thời. 2. Nếu Action sm, ai = “reduce by A ” thì bộ phân tích cú pháp thực hiện động tác thu gọn và chuyển sang hình trạng mới: (s0 X1 s1 X2 s2 Xm -r sm-rA s, ai ai+1 an $) Ở đây s là trạng thái đƣợc xác định bởi s = gotosm-r, ai; r là độ dài xâu ; bộ phân tích cú pháp sẽ đẩy ra khỏi ngăn xếp 2*r ký hiệu, trong đó gồm r ký hiệu chỉ trạng thái và r ký hiệu của xâu vào. Khi đó trong Stack còn lại m - r ký hiệu trạng thái và m - r ký tự của xâu vào. Động tác tiếp theo, bộ phân tích sẽ đẩy biến A trong luật sinh A  và trạng thái s trong mục gotoA, s vào Stack. Con trỏ trên xâu vào không thay đổi vị trí. 129
Chƣơng 3. Phân tích cúa pháp 3. Nếu Action sm, ai = “accept” bộ phân tích thông báo không có lỗi trong xâu và kết thúc. 4. Nếu Action sm, ai = “error” bộ phân tích thông báo có lỗi và gọi thủ tục khắc phục lỗi. 2)Giải thuật phân tích LR - Input: Xâu vào w và bảng phân tích cú pháp LR - Output: Đƣa ra dạng phân tích cú pháp của w nếu w L(G) trên kênh ra, ngƣợc lại đƣa thông báo báo lỗi. - Process: Khởi tạo s0 - trạng thái khởi đầu nằm trong ngăn xếp - đỉnh ngăn xếp, xâu vào w$ nằm trên ngăn đệm vào (kênh vào), con trỏ ip trỏ vào ký tự đầu tiên a của xâu vào. Repeat s := đỉnh ngăn xếp; a := ký tự mà ip trỏ đến trên xâu vào; If action s, a = shift s‟ then Begin Đẩy a , rồi sau đó s‟ vào ngăn xếp; ip: = ký tự tiếp theo; end Else If action s, a = reduce bởi A  then Begin Lấy 2* ký hiệu ra khỏi ngăn xếp; s‟:= đỉnh ngăn xếp; Đẩy A, rồi sau đó đẩy gotos‟, A vào ngăn xếp; Đƣa luật sinh A → β ra bộ đệm ra; end else if actions, a = accept then 130
Chƣơng 3. Phân tích cúa pháp begin writeln(„ thành công‟); halt; {kết thúc} end else error() ; until false Ví dụ 3.24: Cho văn phạm có các luật sinh sau: 1. E E+T 2. E T 3.T T*F 4.T F 5. F (E) 6. F id Ta sử dụng các ký hiệu sau cho hàm action: - si có nghĩa là shift i - rj có nghĩa là thu gọn theo luật sinh thứ j. - acc có nghĩa là chấp nhận. - Ký tự trắng có nghĩa là lỗi. Bảng phân tích cú pháp của văn phạm trên là bảng 3.10 Trạng Action Goto thái id + * ( ) $ E T F 0 s5 s4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 3 r4 r4 r4 r4 4 s5 s4 8 2 3 5 r6 r6 r6 r6 6 s5 s4 9 3 7 s5 s4 10 131
Chƣơng 3. Phân tích cúa pháp 8 s6 s11 9 r1 s7 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 Bảng 3.10. Bảng phân tích cú pháp Bảng 3.11 minh họa các bƣớc hoạt động của giải thuật phân tích từ vào w = id * id + id. STT Ngăn xếp Xâu vào Hành động Kết quả 1 0 id*id+id$ đẩy 2 0 id 5 *id+id$ thu gọn theo F id F id 3 0 F 3 *id+id$ thu gọn theo T F T F 4 0 T 2 *id+id$ đẩy 5 0 T 2 * 7 Id+id$ đẩy 6 0 T 2 * 7 id 5 +id$ thu gọn theo F id F id 7 0 T 2 * 7 F 10 +id$ thu gọn theo T T*F T T*F 8 0 T 2 +id$ thu gọn theo ET ET 9 0 E 1 +id$ đẩy 10 0 E 1 + 6 id$ đẩy 11 0 E 1 + 6 id 5 $ thu gọn theo F id F id 12 0 E 1 + 6 F 3 $ thu gọn theo T F T F 13 0 E 1 + 6 T 9 $ thu gọn theo EE+T EE+T 14 0 E 1 $ accept Bảng 3.11. Quá trình phân tích xâu id*id+id Trong bảng 3.9 dòng 1 chỉ rằng bộ phân tích đang ở trạng thái 0, con trỏ chỉ vào ký tự đầu tiên trên xâu vào là id, khi đó action0, id trong bảng phân tích cú pháp là s5, nghĩa là đẩy ký hiệu hiện thời trên xâu vào là id và trạng thái 5 vào Stack, kết quả ghi ở cột 2 dòng 2. ở dòng 2: ký tự * trở thành ký tự hiện thời trên xâu vào, và trạng thái 5 ở đỉnh Stack, action5, * trong bảng phân tích chỉ ra là r6, nghĩa là thu gọn theo luật 132
Chƣơng 3. Phân tích cúa pháp sinh 6 (F id), khi đó trạng thái 0 trở thành nằm trên đỉnh của Stack, hàm goto0, F trên bảng phân tích là 3. Vì vậy F và 3 đƣợc đẩy vào Stack, kết quả bộ phân tích có hình trạng ở hàng 3 cột 2. Làm tƣơng tự ta có các dòng tiếp theo. E E T T T F F F id id1 * id2 + 3 Hình 3.14a. Cây phân tích cú pháp của xâu id * id + id được xây dựng từ dưới lên theo phương pháp đẩy-thu 3.4.5. Xây dựng bảng phân tích cú pháp 1) Văn phạm LR ở trên đã đề cập đến giải thuật phân tích LR rất hiệu quả, tuy nhiên toàn bộ ý tƣởng của giải thuật lại dựa vào bảng phân tích cú pháp với hai phần action và goto. Ta gọi văn phạm mà ta có thể xây dựng đƣợc bảng phân tích cú pháp nhƣ vậy là văn phạm LR. Có hai câu hỏi đặt ra ở đây là: - Văn phạm nào có thể đƣa về văn phạm LR. - Làm thế nào để có thể xây dựng đƣợc bảng phân tích cú pháp cho văn phạm LR? Ngƣời ta đã chứng minh đƣợc rằng không phải mọi văn phạm phi ngữ cảnh đều là văn phạm LR. Song ngƣời ta cũng chỉ ra đƣợc rằng có thể tìm đƣợc các văn phạm phi ngữ cảnh là LR đáp ứng các yêu cầu của ngôn ngữ lập trình. Qúa trình làm việc của giải thuật phân tích LR, có thể rút ra các nhận xét sau về văn phạm LR: 133
Chƣơng 3. Phân tích cúa pháp a) Để văn phạm là LR thì điều kiện quan trọng là bộ phân tích cú pháp đẩy - thu từ trái qua phải, phải có khả năng nhận diện ra các từ thế khi chúng xuất hiện trên ngăn xếp. Tuy nhiên cần chú ý rằng để nhận diện ra từ thế, bộ phân tích không cần phải dò tìm trên toàn bộ ngăn xếp, nhờ ký hiệu trạng thái trên đỉnh ngăn xếp bộ phân tích đã có mọi thông tin cần thiết. b) Một nguồn cung cấp thông tin khác là các ký hiệu trên xâu vào, hành động đẩy hay thu phụ thuộc không chỉ vào trạng thái trên đỉnh ngăn xếp mà còn phụ thuộc vào k ký hiệu trên xâu vào, trong giải thuật trên chỉ mới xét k 1. Trong thực tế thƣờng gặp k = 0 hoặc bằng 1. Một văn phạm phân tích đƣợc bằng bộ phân tích cú pháp LR khi biết trƣớc k ký hiệu trên xâu vào trong mỗi bƣớc phân tích gọi là văn phạm LR(k). 2) Xây dựng bảng phân tích cú pháp SLR Để xây dựng bảng phân tích cú pháp LR, ngƣời ta đã đƣa ra nhiều phƣơng pháp khác nhau, trong phần này ta tìm hiểu phƣơng pháp đơn giản nhất, đó là phƣơng pháp SLR (Simple LR). Một văn phạm có thể xây dựng bảng phân tích cú pháp SLR gọi là văn phạm SLR. Để tiện cho việc trình bày, trƣớc tiên ta làm quen với một số khái niệm: a) Khả tiền tố Ta gọi dãy các ký hiệu trong stack tại mỗi thời điểm của một quá trình phân tích đẩy – thu là một khả tiền tố. Nhƣ vậy, khả tiền tố là một tiền tố của một dạng xâu dẫn xuất phải nhất có tính chất là nó không đƣợc vƣợt quá từ thế (handle) bên phải nhất của nó vì nếu gặp một từ thế thì nó phải đƣợc thu gọn. Chẳng hạn, tại một thời điểm trong stack có  và xâu vào còn lại là w thì w là một dạng xâu dẫn xuất phải và  là khả tiền tố. Ví dụ 3.25: Với quá trình phân tích đẩy – thu đƣợc mô tả nhƣ sau: Bƣớc Ngăn xếp Xâu vào Hành động 1 $ id1 + id2* id3 $ đẩy 2 $id1 + id2 * id3$ Thu gọn theo E id 3 $E id2 * id3$ đẩy 134
Chƣơng 3. Phân tích cúa pháp 4 $E+ id2 * id3$ đẩy 5 $E+id2 * id3 $ Thu gọn E id 6 $E+E * id3 $ Thu gọn E E + E Bảng 3.12. Mô phỏng giải thuật đoán nhận xâu id1 + id2* id3 Ta có: id1 là khả tiền tố của dạng xâu id1 + id2* id3 E là khả tiền tố của dạng xâu E + id2* id3 E+ là khả tiền tố của dạng xâu E + id2* id3 E+id2 là khả tiền tố của dạng xâu E + id2* id3 E+E là khả tiền tố của dạng xâu E + E * id3 b) Mục trong văn phạm Cho văn phạm G, ta gọi một luật sinh của G có thêm dấu chấm (•) ở vị trí nào đó trong xâu ở vế phải là một mục (item) của G. Ví dụ 3.26: Xét luật sinh A XYZ của văn phạm G: Khi đó sẽ có các mục sau: A •XYZ A X•YZ A AY•Z A XYZ• Chú ý rằng nếu luật sinh A  thuộc G thì luật sinh này chỉ có một mục sinh ra từ nó là A •. Mục A x•y cho ta biết quá trình suy dẫn sử dụng luật sinh A xy và suy dẫn đến hết phần x trong luật sinh. Quá trình suy dẫn tiếp theo đối với phần xâu vào còn lại sẽ bắt đầu từ y. Ta gọi tập tất cả các mục của văn phạm G là bộ chính tắc LR (0) (Canoncial LR (0) collection). 135
Chƣơng 3. Phân tích cúa pháp c) Văn phạm gia tố (tăng cường) Cho G là văn phạm phi ngữ cảnh G = (N, T, P, S) khi đó ta gọi văn phạm G‟ là văn phạm G có bổ sung thêm ký tự bắt đầu S‟ và luật sinh S‟ S là văn phạm gia tố (Augmented Grammar) của văn phạm G. Từ đây trở đi ta luôn coi G là văn phạm gia tố của văn phạm nào đó Một cách hình thức văn phạm gia tố của G có thể viết dƣới dạng: G‟ = (N‟, T, P‟, S‟) Trong đó N‟ = N S‟ P‟ = P  S‟ S Ví dụ 3.27: Cho văn phạm G có các luật sinh S aSb a thì văn phạm tăng cƣờng của nó là G‟ có các luật sinh S‟ S; S aSba với S‟ là ký hiệu bắt đầu. Mục đích của việc bổ sung thêm luật sinh S‟ S để báo hiệu cho bộ phân tích cú pháp biết quá trình phân tích khi nào cần phải dừng. d) Ý tưởng giải thuật xây dựng bảng cú pháp SLR Ý tƣởng của giải thuật xây dựng bảng phân tích cú pháp SLR là xây dựng Automat hữu hạn đơn định đoán nhận tất cả các khả tiền tố của G. Sau đó ta nhóm các mục thành tập mục, tập này tạo ra trạng thái của bộ phân tích cú pháp LR. Các mục của văn phạm có thể coi nhƣ các trạng thái của Automat hữu hạn nhận biết các khả tiền tố. Ta sử dụng hai phép toán: Tính bao đóng closure(I) của một tập mục I và phép sinh ra tập các mục goto (I, X) cho các khả tiền tố mới. e) Phép toán lấy bao đóng trên LR(0) Cho văn phạm phi ngữ cảnh G = (N, T, P, S). Giả sử I là một tập nào đó trên họ các mục LR(0), ta gọi phép toán lấy bao đóng của tập I là tập Closure(I) đƣợc xây dựng theo các quy tắc sau: 1. Đƣa tập I vào tập Closure(I). 2. Nếu A •B Closure(I) và B  P thì đƣa B • vào tập Closure(I) nếu Closure(I) chƣa có luật sinh này. 3. Lặp lại bƣớc 2 cho đến khi không nhận đƣợc thêm mục mới. 136
Chƣơng 3. Phân tích cúa pháp Về mặt trực quan có thể giải thích cho việc làm ở luật sinh 2 nhƣ sau: Khi luật sinh A •B Closure(I), điều này có thể dẫn đến trong quá trình phân tích, bộ phân tích có thể gặp xâu con B. Nếu B  P thì hy vọng có thể gặp xâu con dẫn đƣợc từ , vì vậy ta đƣa luật sinh B • vào Closure(I). Ví dụ 3.28: Xét văn phạm: E‟ E; E E+T; E T ; T T*F ; T F ; F (E) ; F id Nếu I là tập chỉ có một mục I = E‟ •E, khi đó Closure sẽ gồm các mục sau: E‟ •E E •E+T E •T T •T*F T •F F •(E) F •id Dƣới đây sẽ đƣa ra giải thuật tính Closure(I) ở dạng hàm nhƣ sau: Function Closure(I) Begin J:= I; Repeat J‟:= J; For mỗi A •B J Do IF (B  P) AND (B • J) THEN J:= J  B •; 137
Chƣơng 3. Phân tích cúa pháp Until J = J‟ End; Chú ý: Nếu một B – luật sinh đƣợc thêm vào Closure(I) với dấu chấm ở cận trái thì tất cả các B – luật sinh sẽ đƣợc thêm vào Closure(I). Vì vậy nói chung không cần liệt kê các B - mục dạng B • đƣợc thêm vào Closure(I) mà chỉ cần có một danh sách biến B và các luật sinh sẽ đƣợc bổ sung là đủ. Với nhận xét trên, rõ ràng có thể chia tập các mục đó thành hai lớp: 1. Tập mục hạt nhân (Kernel item) gồm mục S‟ •S và các mục có dấu chấm không nằm ở cận trái. 2. Tập mục không phải là hạt nhân (Nonkernel) là các mục còn lại. Với mỗi tập khi cần sử dụng, ta có thể lấy bao đóng từ các tập mục hạt nhân thuộc nó. f) Phép toán goto Giả sử I là tập các mục trên họ mục LR(0) và X V khi đó goto(I, X) là bao đóng của tập tất cả các mục A X• sao cho A •X I goto(I, X) = closure( A X• A •X I) Về mặt trực quan, nếu tập I gồm các mục với một khả tiền tố  nào đó thì goto(I, X) sẽ chứa các mục có khả tiền tố X. 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.29: Xét văn phạm: E‟ E E E+T E T T T*F 138
Chƣơng 3. Phân tích cúa pháp F F F (E) F id Giả sử I là tập chỉ có hai mục 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) g) Kỹ thuật xây dựng tập mục LR(0) Ở trên đã nói đến tập các mục LR(0), song làm thế nào để có nó chƣa đƣợc đề cập đến. Sau đây sẽ mô tả ngắn gọn giải thuật xây dựng tập LR(0). Gọi C là họ tập hợp các mục LR(0) của văn phạm gia tố G = (N, T, P, S). Procedure Item (G) Begin I := S‟ •S; C:= Closure(I); Repeat C1:= C; For I  C AND X V Do IF goto(I, X)  AND goto(I, X) C then C:= C  goto(I, X); until C1 = C end; Chú ý: - Thủ tục trên cho ta tập kết quả C, đó chính là tập LR(0). Thủ tục đƣợc bắt đầu với tập có một mục S‟ •S, mục này đƣợc đƣa vào LR(0), quá trình xây dựng 139
Chƣơng 3. Phân tích cúa pháp LR(0) là quá trình bổ sung dần bằng tập mới khác rỗng goto (I, X) cho đến khi nào không nhận thêm đƣợc mục mới. - Có thể hình dung rằng có một Automat hữu hạn không đơn định N có các trạng thái là các mục của văn phạm. Automat N sẽ chuyển trạng thái từ trạng thái A •X sang trạng thái A X• khi đọc X và từ trạng thái A •B sang trạng thái A • khi đọc từ rỗng . Khi đó một tập I các mục cũng chính là tập I các trạng thái của Automat N. Do vậy việc tính Closure(I) cũng chính là việc tính - Closure(I) khi chuyển Automat không đơn định về Automat đơn định. Cũng vì lý do trên nên goto(I,X) thực chất là phép chuyển trạng thái của Automat đơn định bằng cách xây dựng tập con từ Automat không đơn định N. Với cách nhìn này thì thủ tục item(G) chỉ là phép dựng tập con áp dụng cho Automat không đơn định N mà Automat này đƣợc xây dựng từ văn phạm gia tố G. Ví dụ 3.30: Xét văn phạm tăng cƣờng E‟ E; E E+T ; E T ; T T*F ; T F ; F id. Ta xây dựng họ tập hợp mục LR(0) của văn phạm nhƣ sau: Closure({E'→ •E}): I : E'→ • E 0 E → • E + T E → • T T → • T * F T → • F F → • (E) F → • id Goto (I , E) I : E'→ E • 0 1 140
Chƣơng 3. Phân tích cúa pháp E → E • + T Goto (I , T) I : E → T • 0 2 T → T • * F Goto (I , F) I : T → F • 0 3 Goto (I , ( ) I : F → (• E) 0 4 E → • E + T E → • T T → • T * F T → • F F → • (E) F → • id Goto (I , id) I : F → id • 0 5 Goto (I , +) I : E → E + • T 1 6 T → • T * F T → • F F → • (E) F → • id Goto (I , *) I : T → T* • F 2 7 F → • (E) F → • id Goto (I , E) I : T → (E •) 4 8 E → E • + T Goto (I , T) I : E → E + T • 6 9 T → T • * F Goto (I , F) I : T → T * F • 7 10 Goto (I , ) ) I : F → (E) • 8 11 Hàm goto của các mục đƣợc biểu diễn ở dạng sơ đồ chuyển trạng thái của một Automat đơn định cho ở hình 3.15. 141
Chƣơng 3. Phân tích cúa pháp E + T * I0 I1 I6 I9 To I7 To I3 To I4 To I5 T * F I1 I7 I10 F To I4 I ( 3 To I 5 ( E ) I4 I8 I11 + To I6 T To I2 id F To I3 id I5 Hình 3.15. Sơ đồ chuyển h) Giải thuật xây dựng bảng phân tích cú pháp SLR Bây giờ ta giới thiệu kỹ thuật xây dựng các hàm action và hàm goto cho bảng phân tích cú pháp SLR. Kỹ thuật xây dựng đƣợc mô tả bởi giải thuật sau: - Input: Văn phạm tăng cƣờng (gia tố) G. - Output: Hàm action và hàm Goto cho bảng phân tích SLR - Process: 1. Xây dựng C = { I , I , , I }, họ tập hợp các mục LR(0) của G'. 0 1 n 2. Trạng thái i đƣợc xây dựng từ Ii. Các action tƣơng ứng với trạng thái i đƣợc xác định nhƣ sau: 2.1. Nếu A → α • aβ I và goto (I , a) = Ij thì action[i, a] = "shift j". i i Ở đâ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• I thì action[i, $] = "accept". i 142
Chƣơng 3. Phân tích cúa pháp 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. 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 (I ,A) = I thì goto[i, A] = j i 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.31: Xây dựng bảng phân tích cú pháp SLR cho văn phạm gia tố G: E' → E; E → E + T | T; T → T * F | F; F → (E) | id. Ta có các luật sinh: (0) E'→ E; (1) E → E + T; (2) E → T; (3) T → T * F; (4) T → F; (5) F → (E); (6) F → id. 1. C = { I , I , I } 0 1 11 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.28, ta thấy: Trƣớc tiên xét tập mục I : Mục F → • (E) cho action[0, ( ] = "shift 4", và mục 0 F → • id cho action[0, id] = "shift 5". Các mục khác trong I không sinh đƣợc hành 0 động nào. 143
Chƣơng 3. Phân tích cúa pháp Bây giờ xét I : Mục E'→ E • cho action[1, $] = "accept", mục E → E • + T cho 1 action[1, +] = "shift 6". Tiếp theo xét I : E → T • ; T → T • * F 2 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.13. Trạng Action Goto thái id + * ( ) $ E T F 0 s5 s4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 3 r4 r4 r4 r4 4 s5 s4 8 2 3 5 r6 r6 r6 r6 6 s5 s4 9 3 7 s5 s4 10 8 s6 s11 9 r1 s7 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 Bảng 3.13. Bảng phân tích cú pháp LR(1) Bảng phân tích xác định bởi giải thuật trên 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.32: 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 . 144
Chƣơng 3. Phân tích cúa pháp Ðây là một văn phạm không nhập nhằng 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: I : S' → • S ; 0 S → • L = R ; S → • R ; L → • * R ; L → • id ; R → • L I : S' → S • 1 I : S → L • = R ; 2 R → L • ; I : S → R • 3 I : L → * • R ; 4 R → • L ; L → • * R ; L → • id I : L → id • 5 I : S → L = • R ; 6 R → • L ; L → • * R ; L → • id I : L → * R• 7 I : R → L• 8 I : S → L = R• 9 Khi xây dựng bảng phân tích SLR cho văn phạm, khi xét tập mục I ta thấy 2 mục đầu tiên trong tập này làm cho action[2, =] = "shift 6". Bởi vì = FOLLOW(R), nên mục thứ hai sẽ đặt action[2, =] = "reduce (R → L)" Có sự đụng độ tại action[2, =]. Vậy văn phạm trên không là văn phạm SLR(1). 145
Chƣơng 3. Phân tích cúa pháp CÂU HỎI VÀ BÀI TẬP CHƢƠNG 3 3.1. Nêu vị trí, chức năng và nhiệm vụ của giai đoạn phân tích cú pháp. 3.2. Nêu khái niệm dẫn xuất, dẫn xuất trái nhất, cho ví dụ minh họa. 3.3. Nêu khái niệm cây phân tích cú pháp; phƣơng pháp xây dựng cây phân tích cú pháp; cho ví dụ minh họa. 3.4. Nêu giải thuật thừa số hoá bên trái; chạy một ví dụ minh họa. 3.5. Nêu các phƣơng pháp phân tích cú pháp. 3.6. Nêu các lỗi cú pháp thƣờng gặp và phƣơng pháp xử lý lỗi. 3.7. Nêu các chiến lƣợc phục hồi lỗi. 3.8. Nêu khái niệm văn phạm nhập nhằng; kỹ thuật khử nhập nhằng; cho ví dụ. 3.9. Nêu khái niệm văn phạm phi ngữ cảnh đệ qui trái; phân loại, cho ví dụ minh họa. 3.10. Nêu giải thuật khử đệ qui trái; chạy một ví dụ minh họa. 3.11. Nêu phƣơng pháp phân tích cú pháp từ trên xuống; ý tƣởng của giải thuật phân tích cú pháp đệ qui xuống. 3.12. Nêu giải thuật phân tích cú pháp đệ qui xuống, chạy ví dụ minh họa. 3.13. Nêu ý tƣởng của kỹ thuật phân tích cú pháp từ dƣới lên; cho ví dụ. 3.14. Nêu ý tƣởng của kỹ thuật phân tích cú pháp dự đoán; cho ví dụ. 3.15. Nêu cách xây dựng sơ đồ chuyển vị; cho ví dụ. 3.16. Nêu phƣơng pháp phân tích cú pháp dự đoán dựa trên sơ đồ chuyển vị; chạy ví dụ minh họa. 3.17. Nêu giải thuật phân tích cú pháp dự đoán dựa vào ngăn xếp; chạy ví dụ minh họa. Viết lại lý thuyết phần này, dựa vào ngay ngôn ngữ Pascal: tên, số , biểu thức, câu lệnh 3.18. Nêu khái niệm và cách xác định hàm First; cho ví dụ. 3.19. Nêu khái niệm và cách xác định hàm Follow; cho ví dụ. 3.20. Nêu thuật toán sử dụng các hàm First và Follow để xây dựng bảng phân tích cú pháp; cho ví dụ minh họa. 3.21. Nêu các khái niệm phân tích đẩy – thu, từ thế, thay từ thế; cho ví dụ. 3.22. Nêu giải thuật phân tích cú pháp đẩy – thu; chạy ví dụ minh họa. 3.23. Nêu mô hình của bộ phân tích cú pháp LR. 146
Chƣơng 3. Phân tích cúa pháp 3.24. Nêu giải thuật phân tích cú pháp LR. 3.25. Nêu các khái niệm: khả tiền tố, mục trong văn phạm, văn phạm tăng cƣờng; cho ví dụ minh họa. 3.26. Nêu phép toán lấy bao đóng Closure(I) trên LR(0); cho ví dụ. 3.27. Nêu phép toán goto(I, X) trên LR(0); cho ví dụ. 3.28. Nêu kỹ thuật xây dựng tập mục LR(0); cho ví dụ. 3.29. Nêu giải thuật xây dựng bảng phân tích cú pháp SLR; cho ví dụ. 3.30. Cho văn phạm với các luật sinh sau: S Sb | Aa | b; A Ab| Sd | a. Hãy sử dụng giải thuật khử đệ quy trái cho văn phạm trên. 3.31. Sử dụng giải thuật khử đệ quy trái cho văn phạm có các luật sinh: S Sc | Aa | Bb | a; A Ac | Bd | b; B Bb | Sa | c. 3.32. Sử dụng giải thuật khử đệ quy trái cho văn phạm có các luật sinh: S Sc | Aa | Bb | a; A Ac | Bd | b; B Bb | Sa | c; C a | c. 3.33. Cho văn phạm với các luật sinh: S aaaAab | aaaAbb | aaaBC | aaC | Bcd | cad; A bbBa | bCc | ad; B ccC | ccca; C b | . Hãy sử dụng giải thuật thừa số hoá bên trái cho văn phạm trên. 3.34. Cho văn phạm với các luật sinh: S aaaAab | aaaAbb | aacBC | bbaC | bbBcd | cad; A bbBa | bbCc | abAd| aaC | c; B ccbC | ccca | bB; 147
Chƣơng 3. Phân tích cúa pháp C ab | ba | a | b. Hãy sử dụng giải thuật thừa số hoá bên trái cho văn phạm trên. 3.35. Cho văn phạm với các luật sinh: S bbABc; A ab  a  b; B bac  baa  ab ac c. Hãy sử dụng giải thuật phân tích cú pháp đệ quy xuống phân tích các xâu: a) w = bbabacc. b) w = bbbbaac. c) w = bbbabc. d) w = bbabaac 3.36. Cho văn phạm với các luật sinh: S SAa  aB  a; A ab  a  b; B bac  bad  a b . Hãy sử dụng giải thuật phân tích cú pháp đệ quy xuống phân tích các xâu: a) w = aaba. b) w = aaaba. c) w = abac. d) w = abbad. 3.37. Cho văn phạm sinh biểu thức toán học với các quy tắc E → E * T | T; T → T + F | F; F → (E) | id. Hãy sử dụng giải thuật phân tích cú pháp đệ quy xuống phân tích các xâu: + w = id * (id + id). + w = (id * id)+ id). + w = (id + (id + id))* id. + w = (id + id) * (id + id). + w = id * ((id + id)* id). 148
Chƣơng 3. Phân tích cúa pháp 3.38. Cho văn phạm sinh ra các biểu thức toán học với các quy tắc sinh: E → E * T | T; T → T + F | F ; F → (E) | id. a) Hãy loại bỏ đệ quy trái trực tiếp trong văn phạm. b) Hãy xây dựng sơ đồ chuyển cho văn phạm. c) Sử dụng giải thuật phân tích cú pháp dự đoán dựa vào sơ đồ chuyển để phân tích xâu vào: 1) w = id * id + id 2) w = id + + id * id. 3) w = id + id + id. 4) w = id * (id + id. 5) w = (id + (id + id))* id. 6) w = (id + id) * (id + id). 7) w = id * ((id + id)* id). 3.39. Cho văn phạm sinh ra biểu thức nguyên trong ngôn ngữ lập trình Pascal với các luật sinh cho dƣới dạng các định nghĩa chính quy: 1) expr id | digits; 2) expr expr matop expr | (expr); 3) digit 0 | 1 | | 9; * 4) digits (digit)(digit) ; 5) letter A | B | | Z | a | b | | z ; * 6) id (letter| _ ) (letter | digit | _ ) ; 7) matop → + | - | * | / . a) Hãy loại bỏ đệ quy trái trực tiếp trong văn phạm. b) Hãy xây dựng sơ đồ chuyển cho văn phạm. c) Sử dụng giải thuật phân tích cú pháp dự đoán dựa vào sơ đồ chuyển để phân tích xâu vào: 1) A1 + 123 - bc2 2) b * a1b 149
Chƣơng 3. Phân tích cúa pháp 3) 235 / bien1 4) 235 – 12* heso 3.40. Cho văn phạm sinh ra biểu thức toán học với các quy tắc sinh: E → E * T | T; T → T + F | F ; F → F / G | G ; G → G - B | B; B → (E) | id . a) Hãy loại bỏ đệ quy trái trực tiếp trong văn phạm; b) Hãy xây dựng sơ đồ chuyển cho văn phạm. c) Sử dụng giải thuật phân tích cú pháp dự đoán dựa vào sơ đồ chuyển để phân tích xâu vào: 1) w = id - (id + id). 2) w = (id + id)- id). 3) w = (id - (id + id))* id. 4) w = (id + id) / (id + id). 5) w = id * ((id - id) + id). 6) w = id * (id + id)/(id - id). 3.41. Cho văn phạm với các luật sinh: E TE‟; E‟ +TE‟; E‟ ; T FT‟; T‟ *FT‟; T‟ ; F (E); F id. 150
Chƣơng 3. Phân tích cúa pháp Và có bảng phân tích cú pháp M: 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 BT 3.41 Sử dụng giải thuật phân tích cú pháp dự đoán dựa vào ngăn xếp để phân tích xâu vào w; sau đó dựng cây phân tích cú pháp nếu có: 1) w = id * (id + id). 2) w = id + id + id). 3) w = id + * id + id. 4) w = id + (id + id). 5) w = (id + (id + id))* id. 6) w = (id + id) * (id + id). 7) w = id * ((id + id)* id). 3.42. Cho văn phạm sinh biểu thức toán học với các quy tắc E → E * T | T; T → T + F | F; F → (E) | id. a) Hãy loại bỏ đệ quy trái trong văn phạm. b) Tính FIRST và FOLLOW của các ký hiệu không kết thúc của văn phạm. c) Hãy xây dựng bảng phân tích cú pháp theo phƣơng pháp dự đoán. d) Sử dụng giải thuật phân tích cú pháp dự đoán dựa vào ngăn xếp để phân tích xâu vào w; sau đó dựng cây phân tích cú pháp nếu có: 1) w = id * (id + id). 2) w = id + id + id). 3) w = id + * id + id. 4) w = id + (id + id). 5) w = (id + (id + id))* id. 151
Chƣơng 3. Phân tích cúa pháp 6) w = (id + id) * (id + id). 7) w = id * ((id + id)* id). 3.43. Cho văn phạm sinh ra các biểu thức toán học với các luật sinh: E → E * T | T; T → T + F | F; F → F / G | G; G → G - B | B; B → (E) | id. a) Hãy loại bỏ đệ quy trái trực tiếp trong văn phạm. b) Tính FIRST và FOLLOW của các ký hiệu không kết thúc của văn phạm. c) Hãy xây dựng bảng phân tích cú pháp theo phƣơng pháp dự đoán. d) Sử dụng giải thuật phân tích cú pháp dự đoán dựa vào ngăn xếp để phân tích các xâu vào và xây dựng cây phân tích cú pháp tƣơng ứng nếu có: 1) w = id * (id - id). 2) w = (id + * id - id). 3) w = (id - (id + id))* id. 4) w = (id + id / (id + id). 5)w = id * ((id - id) + id). 6) w = id * (id + id)/(id - id). 3.44. Cho văn phạm có các luật sinh: E E + E | E * E | (E) | id. Hãy sử dụng giải thuật phân tích cú pháp đẩy – thu để phân tích mỗi xâu vào w; sau đó xây dựng cây phân tích cú pháp của nó nếu có: 1) w = id * (id + id). 2) w = id + id + id). 3) w = id + * id + id. 4) w = id + (id + id). 5) w = (id + (id + id))* id. 6) w = (id + id) * (id + id). 7) w = id * ((id + id)* id). 3.45. Cho văn phạm có các luật sinh: E E + E; E E * E; E E - E; E E / E; E (E); E id. 152
Chƣơng 3. Phân tích cúa pháp Hãy sử dụng giải thuật phân tích cú pháp đẩy – thu để phân tích mỗi xâu vào w; sau đó xây dựng cây phân tích cú pháp của nó nếu có: 1) w = id - (id + id). 2) w = (id + id) / id. 3) w = (id + id)- (id. 4) w = id + * (id - id) / id. 5) w = (id + id) / (id + id). 6) w = id * id - id) + id. 7) w = id * (id + id)/(id - id). 3.46. Cho văn phạm có các luật sinh sau: 1. E E+T ; 2. E T ; 3.T T*F ; 4.T F ; 5. F (E) ; 6. F id. Với bảng phân tích cú pháp là: Trạng Action Goto thái id + * ( ) $ E T F 0 s5 s4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 3 r4 r4 r4 r4 4 s5 s4 8 2 3 5 r6 r6 r6 r6 6 s5 s4 9 3 7 s5 s4 10 8 s6 s11 9 r1 s7 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 Bảng BT 3.464.6 Bảng phân tích cú pháp SLR 153
Chƣơng 3. Phân tích cúa pháp Hãy sử dụng giải thuật phân tích cú pháp LR để phân tích xâu vào: 1) w = id * (id + id). 2) w = id + id + id). 3) w = id + * id + id. 4) w = id + (id + id). 5) w = (id + (id + id))* id. 6) w = (id + id) * (id + id). 7) w = id * ((id + id)* id). 3.47. Cho văn phạm sinh biểu thức toán học với các quy tắc sinh: E → E * T | T; T → T + F | F ; F → F / G | G ; G → G - B | B; B → (E) | id . 1) Xây dựng họ tập hợp mục LR(0) của văn phạm. 2) Xây dựng các hàm action và hàm goto cho bảng phân tích cú pháp SLR của văn phạm. 3) Xây dựng bảng phân tích cú pháp SLR cho văn phạm. 4) Sử dụng giải thuật phân tích cú pháp để phân tích xâu vào: 1) w = id - (id + id). 2) w = (id + id) / id. 3) w = (id + id) - (id. 4) w = id + * (id - id) / id. 5) w = (id + id) / (id + id). 6) w = id * id - id) + id. 7) w = id * (id + id)/(id - id). 154
Lời giải tóm tắt hoặc hƣớng dẫn LỜI GIẢI TÓM TẮT HOẶC HƢỚNG DẪN CHƢƠNG 1 1.9. Lời giải tóm tắt 1. digit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Thì: + digit là thẻ từ (token); + 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 là mẫu từ vựng (pattern) của thẻ từ digit; + Mỗi chữ số: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 là một từ vị (lexeme) của thẻ từ digit. 2. digits digit(digit)* Thì: + digits là thẻ từ (token); + Biểu thức chính quy digit(digit)* là mẫu từ vựng (pattern) của thẻ từ digits; + Mỗi số: 0, 1, 20, 135, là một từ vị (lexeme) của thẻ từ digits. 3. optional_fraction . digits | ε Thì: + optional_fraction là thẻ từ (token); + Biểu thức chính quy . digits | ε là mẫu từ vựng (pattern) của thẻ từ optional_fraction; + Mỗi: ε, .0, .5, .21, .135, là một từ vị (lexeme) của thẻ từ optional_fraction. 4. optional_exponent ( E ( + | - | ε ) digits) | ε Thì: + optional_exponent là thẻ từ (token); + Biểu thức chính quy ( E ( + | - | ε ) digits) | ε là mẫu từ vựng (pattern) của thẻ từ optional_exponent; + Mỗi: ε, E-1, E5, E+2, E135, là một từ vị (lexeme) của thẻ từ optional_exponent. 5. nums digits optional_fraction optional_exponent Thì: + nums là thẻ từ (token); 155
Lời giải tóm tắt hoặc hƣớng dẫn + Biểu thức chính quy: digits optional_fraction optional_exponent là mẫu từ vựng (pattern) của thẻ từ num; + Mỗi: 1, 126, 572E-1, 329.22 E5, 143.0 E+2, là một từ vị (lexeme) của thẻ từ nums. 1.10. Lời giải tóm tắt a) Với ngôn ngữ lập trình bậc cao Pascal 1. Kiểu dữ liệu - Số nguyên (integer) digit 0 | 1 | | 9 ; sign  + | - | ε ; * digits (sign)(digit)(digit) - Số nguyên ngắn (sortint) - Số nguyên dài (longint) - Số thực (real) + Số thực dấu phảy tĩnh optional_fraction . digits | ε ; number (sign)(digits)(optional_fraction) + Số thực dấu phảy động optional_exponent ( E ( + | - | ε ) digits) | ε; nums digits optional_fraction optional_exponent. - Ký tự (Char) – bảng chữ cái Char A | B | | Z | a | b | | z | 0 | 1| | 9| ( | ) | [ | ] | { | }| ?| | >= | <> 3. Phép toán số học (operator) 156
Lời giải tóm tắt hoặc hƣớng dẫn Operator +-*/ 4. Phép gán (Assign) Assign := 5. Tên (Identifer) letter A | B | | Z | a | b | | z ; digit 0 | 1 | | 9 ; * id (letter| _ ) (letter | digit | _ ) 6. Tên chuẩn (standard identifer) Integer Integer; Shortint Shortint; longint longint;  real  real;  Char Char; String String;  Boolean Boolean;  pi 3.141 ; Ngoài ra còn nhiều tên chuẩn khác nhƣ: sqr, sqrt, copy, val, max, min,  7. Từ khóa (Keyword) If if; then then; else else; while while; do do; to to; for for; repeat repeat; until until; program program; label label; 157