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

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

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 <> $ and 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  β

- Đưa luật sinh X  β ra Buffer kết quả; End;

UNTIL a = $

If < Stack chỉ chứa ký tự bắt đầu> 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

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

• 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
• A. 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ương trình dịch - 18
• Chương trình dịch - 19

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

Bảng 3.7. Quá trình phân tích đẩy thu xâu id1 + id2* id3

Cây phân tích cú pháp tương ứng là:

E

E

E

E

E

id1 +

id2 *

id3

Chú ý:

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

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:

Quan hệ

Ý nghĩa
a <• b	a có độ ưu tiên thấp hơn b
a b	a có độ ưu tiên bằng b
a •> b	a có độ ưu tiên cao hơn b

Bảng 3.8. Các quan hệ thứ bậc toán tử

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à θ <• θ ;

1 2 1 2 2 1

(E + E * E + E thì handle là E * E).

2. Nếu toán tử θ có độ ưu tiên bằng θ thì:

1 2

+ θ •> θ và θ •> θ nếu các toán tử là kết hợp trái.

1 2 2 1

+ θ <• θ và θ <• θ nếu các toán tử là kết hợp phải.

1 2 2 1

Chẳng hạn:

Toán tử + và - có độ ưu tiên bằng nhau và kết hợp trái nên:

+ •> + ; + •> - ; - •> - ; - •> +

Phép toán ↑ kết hợp phải nên ↑ <• ↑ E - E + E  handle là E - E

E ↑ E ↑ E  handle là E ↑ E (phần cuối)

Ví dụ 3.23:

Với xâu vào w = id + id * id, ta có bảng quan hệ thứ bậc các toán tử như sau:

id	+	*	$
id		•>	•>	•>
+	<•	•>	<•	•>
*	<•	•>	•>	•>
$	<•	<•	<•

Bảng 3.9. Bảng quan hệ thứ bậc các toán tử

Sử dụng $ để đánh dấu cuối xâu và $ <• θ, θ.

Ta có xâu với các quan hệ thứ bậc được chèn vào là :

$ <• id •> + <• id •> * <• id •> $

Chẳng hạn, <• được chèn vào giữa $ bên trái và id bởi vì <• là mục ở hàng $ và cột id. Handle có thể tìm thấy thông qua quá trình sau :

1. Duyệt xâu từ trái sang phải cho đến khi gặp •> đầ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 <• (trong ví dụ, ta quét ngược về đến $).

3. Handle là xâu chứa mọi ký hiệu ở bên trái •> đầu tiên và bên phải <• được gặp trong bước (2), chứa luôn cả các ký hiệu chưa kết thúc xen giữa hoặc bao quanh (trong ví dụ, handle là id đầu tiên).

Với ví dụ trên, sau khi thu gọn id thành E ta được $ E + E * E $.

- Bỏ các ký hiệu chưa kết thúc E ta được $ + * $.

-  Thêm các quan hệ ưu tiên ta được $ <• + <• * •> $ . Ð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

Else begin

If a <• b hoặc a b then begin

end Else

Ðẩy b vào Stack;

Dịch ip chỉ đến ký hiệu tiếp theo;

End; Until false

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 ( )

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.

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

Sm

Xm

Sm-1

Xm-1

S0

Stack

Inuput

LR parsing program

a1

a2

...a2

...

an

$

Ouput

Action

goto

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 s0X1s1X2s2 ... Xmsm trong đó sm nằm trên đỉnh Stack. Xi là một ký hiệu văn phạm, si là một trạng thái tóm tắt thông tin chứa trong Stack bên dưới nó.

• Bảng phân tích bao gồm 2 phần: 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[sm, ai] có thể có một trong 4 giá trị :

1. shift s: đẩy s, trong đó s là một trạng thái.