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

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: (s0X1s1X2s2 ... Xmsm , ai ai+1 ... an $)

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

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

until false

Ví dụ 3.24:

begin

writeln(„ thành công‟); halt; {kết thúc}

end

else error() ;

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

thái

Action						Goto
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

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

• 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
• Chương trình dịch - 20

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

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

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

id1 *

id2 +

id3

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:

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

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

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.