Mô Tả Hình Tổ Chức Dữ Liệu Của Kỹ Thuật Dự Đoán

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

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.

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

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.

Các sơ đồ chuyển tương ứng:

E‟

0 1 2

3 +

E‟



E‟:

T‟



T‟:

(

)

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.



E‟:



E‟:



E:

0 T 3 6

Tương tự ta có

T:

7 F 8 13

(

)

 F:

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

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

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 .

*, 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$

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

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.

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

Chương trình phân tích

- Một ngăn đệm dùng để chứa kết quả phân tích.