A, B, C. Mô Tả Quá Trình Phân Tích Xâu W = Cad

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.

Có thể bạn quan tâm!

• Automat Đoán Nhận R=(A  B) * Abb
• Vị Trí, Chức Năng, Nhiệm Vụ Của Giai Đoạn Phân Tích Cú Pháp
• Minh Họa Một Cây Phân Tích Cú Pháp
• Mô Tả Hình Tổ Chức Dữ Liệu Của Kỹ Thuật Dự Đoán
• 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
• Phân Tích Cú Pháp Cho Xâu Vào + Id * + Id Phục Hồi Lỗi

Xem toàn bộ 224 trang tài liệu này.

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ì

+ 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

- 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:

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

- 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.

Cần xây dựng cây phân tích cú pháp cho từ w = cad.

S SS

c

c d A d 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:

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.

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