1. Trang Chủ
  2. Kỹ thuật lập trình
  3. Bài giảng Chương trình dịch: Phần 2 - ĐH Sư phạm kỹ thuật Nam Định

Bài giảng Chương trình dịch: Phần 2 - ĐH Sư phạm kỹ thuật Nam Định

Tiếp nội dung phần 1, Bài giảng Chương trình dịch: Phần 2 cung cấp cho người học những kiến thức như: Trình bày các kiến thức cơ bản về: 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). Chƣơng 3.

Thể loại Tài liệu miễn phí Kỹ thuật lập trình

Số trang 143

Ngày tạo 10/2/2021 12:33:32 PM +00:00

Loại tệp PDF

Kích thước 1.09 M

Tên tệp

Tải Bài giảng Chương trình dịch: Phần 2 - ĐH Sư phạm k... (.pdf)

Xem mẫu

  1. 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
  2. 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 cú pháp Thẻ từ 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
  3. 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
  4. 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
  5. 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
  6. 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 α * β. lm Nếu S * α thì ta nói α là dạng câu trái nhất của văn phạm. lm 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
  7. 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
  8. 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
  9. 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 E1 if expr then sttm else sttm E2 S1 S2 a) sttm if expr then sttm else sttm E1 if expr then sttm S2 E2 S1 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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 d c d c d c A 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
  20. 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
nguon tai.lieu . vn
Tin học văn phòng Đồ họa - Thiết kế - Flash Quản trị Web Cơ sở dữ liệu Quản trị mạng Kỹ thuật lập trình Hệ điều hành Phần cứng An ninh - Bảo mật Chứng chỉ quốc tế Thủ thuật máy tính Điện - Điện tử Kinh tế học Hoá học Xã hội học Môi trường