Phân Tích Cú Pháp Cho Xâu Vào + Id * + Id Phục Hồi Lỗi

- Xét luật sinh E  TE':

Tính FIRST(TE') = FIRST(T) = {(,id}

 M[E, id] và M[E,( ] chứa luật sinh E TE'

- Xét luật sinh E'  + TE' :

Tính FIRST(+TE') = FIRST(+) = {+}

 M[E', +] chứa E'  +TE'

- Xét luật sinh E' : Vì  FIRST(E') và FOLLOW(E') = { ), $ }

 E  nằm trong M[E', )] và M[E', $]

- Xét luật sinh T'  * FT' : Tính FIRST(* FT') = {* }

 T'  * FT' nằm trong M[T', *]

- Xét luật sinh T' ε: Vì ε  FIRST(T') và FOLLOW(T') = {+, ), $}

 T' ε nằm trong M[T', +] , M[T', )] và M[T', $]

- Xét luật sinh F  (E) ; FIRST((E)) = { ( }

 F  ( E) nằm trong M[F, (]

- Xét luật sinh F  id ; FIRST(id) = {id}

 F  id nằm trong M[F, id]

Kết quả bảng phân tích cú pháp M của văn phạm được xây dựng như trong bảng 3.3

id	+	*	(	)	$
E	E  TE‟			E  TE‟
E‟		E‟  +TE‟			E‟ 	E‟ 
T	T  FT‟			T  FT‟
T‟		T‟ 	T‟  *FT‟		T‟ 	T‟ 
F	F  id			F  (E)

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

• A, B, C. Mô Tả Quá Trình Phân Tích Xâu W = Cad
• 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
• 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
• 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

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

Bảng 3.3. Bảng phân tích cú pháp

3) Văn phạm LL(1)

Giải thuật xây dựng bảng phân tích cú pháp ở trên đây có thể áp dụng cho mọi loại văn phạm. Tuy nhiên có một số văn phạm (nhập nhằng hoặc đệ quy trái) có thể

xảy ra tình trạng ở mỗi vị trí M[A, a] có thể chứa nhiều luật sinh. Chẳng hạn khi G là văn phạm đệ quy trái hoặc là văn phạm nhập nhằng thì chắc chắn sẽ tồn tại ít nhất một ô trong bảng phân tích cú pháp M chứa nhiều luật sinh. Trong trường hợp như vậy kỹ thuật phân tích cú pháp dự đoán sẽ hạn chế hiệu quả, vì là dẫn đến tình trạng không biết sử dụng luật sinh nào trong số các luật sinh ghi ở vị trí M[A, a] cho phù hợp với phân tích từ vào. Ví dụ sau đây chỉ ra tình trạng trên.

Ví dụ 3.16:

Xét văn phạm:

S → i E t S | i E t S e S | a E → b

Sau khi thừa số hoá bên trái, ta có văn phạm tương đương: S  i E t S S‟| a ;

S‟  e S |  ; E  b.

Khi đó dựa vào giải thuật xây dựng bảng phân tích cú pháp cho văn phạm trên ta có bảng M.

a	b	e	i	t	$
S	S  a			S  i E t S S‟
S‟			S‟  S‟  e S			S‟ 
E		E  b

Bảng 3.4. Bảng phân tích cú pháp

a) Định nghĩa

Một văn phạm được gọi là văn phạm LL(1) nếu mọi ô trong bảng phân tích cú pháp của nó chỉ chứa không quá một luật sinh.

Ở đây ký tự “L” thứ nhất chỉ rằng quá trình dò đọc xâu vào được tiến hành từ bên trái (Left). Ký tự “L” thứ hai chỉ rằng quá trình phân tích cú pháp sẽ chỉ ra dẫn xuất trái nhất, cuối cùng chữ số “1” chỉ số ký tự cần biết để dự đoán cần phải chọn luật sinh nào cho thích hợp.

Người ta đã chứng minh được rằng nếu văn phạm G là văn phạm LL(1) thì sử dụng giải thuật xây dựng bảng phân tích cú pháp nêu trên có thể phân tích được mọi xâu vào của L(G).

b) Các tính chất của LL(1)

Văn phạm LL(1) có một số tính chất đặc biệt sau:

1. Nếu văn phạm G là LL(1) thì G không là văn phạm nhập nhằng.

2. Nếu văn phạm G là LL(1) thì G không là văn phạm đệ quy trái.

3. Văn phạm G là LL(1) khi và chỉ khi hai luật sinh khác nhau. A  và A  của G thoả mãn điều kiện sau:

- Không tồn tại a  T để * a và * a

- Chỉ có thể có tối đa một trong hai dẫn xuất * hoặc *

- Nếu * thì  không thể dẫn ra xâu bắt đầu bằng a  T và a  FOLLOW(A).

Chú ý:

- Nói chung không có quy tắc tổng quát để biến đổi một văn phạm về văn phạm LL(1).

- Một văn phạm có thể tiến hành khử nhập nhằng, khử đệ quy trái, thừa số hoá bên trái để được một văn phạm LL(1); song sẽ phải trả giá về sự phức tạp, cồng kềnh, thậm chí khó biên dịch hơn khi chưa biến đổi.

4) Phục hồi lỗi trong phân tích dự đoán

Một lỗi sẽ được tìm thấy trong quá trình phân tích dự đoán khi gặp một trong hai trường hợp sau:

1. Ký hiệu kết thúc trên đỉnh Stack không phù hợp với token kế tiếp trong xâu vào.

2. Trên đỉnh Stack là ký hiệu chưa kết thúc A, token trong xâu vào là a nhưng M[A,a] rỗng.

Phục hồi lỗi theo phương pháp panic_mode là bỏ qua các ký hiệu trong xâu vào cho đến khi gặp một phần tử trong tập hợp các token đồng bộ (synchronizing token).

Tính hiệu quả của phương pháp này tùy thuộc vào cách chọn tập hợp các token đồng bộ. Một số mẹo (heuristics) có thể là:

1. Ta có thể đưa tất cả các ký hiệu trong FOLLOW(A) vào trong tập hợp token đồng bộ cho ký hiệu chưa kết thúc A.

2. FOLLOW(A) cũng chưa phải là một tập hợp các token đồng bộ cho A. Ví dụ, các lệnh của C kết thúc bởi ; (dấu chấm phẩy ). Nếu một lệnh thiếu dấu ; thì từ khóa của lệnh kế tiếp sẽ bị bỏ qua. Thông thường ngôn ngữ có cấu trúc phân cấp, ví dụ biểu thức nằm trong một lệnh, lệnh nằm trong một khối lệnh, v.v. Có thể thêm vào tập hợp đồng bộ của một cấu trúc những ký hiệu mà nó bắt đầu cho một cấu trúc cao hơn. Ví dụ, ta có thể thêm các từ khoá bắt đầu cho các lệnh vào tập đồng bộ cho ký hiệu chưa kết thúc sinh ra biểu thức.

3. Nếu thêm các phần tử của FIRST(A) vào tập đồng bộ cho ký hiệu chưa kết thúc A thì quá trình phân tích có thể hòa hợp với A nếu một ký hiệu trong FIRST(A) xuất hiện trong xâu vào.

Ví dụ 3.17:

Sử dụng các ký hiệu kết thúc trong tập FOLLOW làm token đồng bộ hóa hoạt động khá hữu hiệu khi phân tích cú pháp cho các biểu thức trong văn phạm ở ví dụ 3.13.

FOLLOW(E) = FOLLOW(E') = { $, )}

FOLLOW(T) = FOLLOW(T') = { +,$, )}

FOLLOW(F) = {*, +, $, )}

Bảng phân tích M cho văn phạm này được thêm vào các ký hiệu đồng bộ "synch", lấy từ tập FOLLOW của các ký hiệu chưa kết thúc - xác định các token đồng bộ :

id	+	*	(	)	$
E	E  TE‟			E  TE‟	synch	synch
E‟		E‟  +TE‟			E‟ 	E‟ 
T	T  FT‟	synch		T  FT‟	synch	synch
T‟		T‟ 	T‟  *FT‟		T‟ 	T‟ 
F	F  id	synch	synch	F  (E)	synch	synch

Bảng 3.5. Bảng phân tích cú pháp M phục hồi lỗi

Bảng này được sử dụng như sau:

- Nếu M[A,a] là rỗng thì bỏ qua token a.

- Nếu M[A,a] là "synch" thì lấy A ra khỏi Stack nhằm tái hoạt động quá trình phân tích.

- Nếu một token trên đỉnh Stack không phù hợp với token trong xâu vào thì lấy token ra khỏi Stack.

Chẳng hạn, với xâu vào: w = + id * + id, bộ phân tích cú pháp và cơ chế phục hồi lỗi thực hiện như sau:

Bước

STACK	INPUT	OUTPUT
Khởi tạo	$ E	+ id * + id $	Error, nhảy qua +
1	$ E	id * + id $	E  T E'
2	$ E T'	id * + id $	T  F T'
3	$ E' T' F	id * + id $	F  id
4	$ E' T' id	id * + id $
5	$ E' T'	* + id $	T'  * F T'
6	$ E' T' F *	* + id $
7	$ E' T' F	+ id $	Error, M[F,+] = synch đẩy F
8	$ E' T'	+ id $	T' 
9	$ E'	+ id $	E'  + T E'
10	$ E T' +	+ id $
11	$ E' T'	id $
12	$ E' T' F	id $	T'  F T'
13	id T' E' $	id $	F  id
14	T' E' $	$
15	E' $	$	T'  ε
16	$	$	E'  ε

Bảng 3.6. Phân tích cú pháp cho xâu vào + id * + id phục hồi lỗi

3.4. Phân tích cú pháp từ dưới lên (Bottom - up parsing)

Phân tích cú pháp từ dưới lên thực chất là cách phân tích một xâu vào và tìm cách thay thế các xâu bằng các biến để rút gọn xâu về ký tự bắt đầu của văn phạm. Về mặt hình ảnh, phân tích cú pháp từ dưới lên được coi là quá trình phân tích bắt

đầu đi từ các nút lá hướng dần về gốc của cây. Người ta phân chia phương pháp phân tích từ dưới lên thành các phương pháp sau:

1. Phương pháp phân tích đẩy - thu (Shift – Reduce Parsing)

2. Phương pháp phân tích thứ bậc toán tử (Operator – Precedence parsing)

3. Phương pháp phân tích LR.

3.4.1. Phân tích đẩy thu ( Shift – Reduce parsing)

1) Khái niệm

Phương pháp phân tích đẩy – thu là phương pháp rút gọn xâu đã cho về ký hiệu bắt đầu của văn phạm. Trong quá trình thu gọn cố gắng tìm xâu con của các xâu trung gian trùng với vế phải của luật sinh nào đó rồi thay thế xâu con này bằng biến ở vế trái của luật sinh đó. Nếu xâu con được chọn đúng ở mỗi bước thì một dẫn xuất phải đảo ngược sẽ được xây dựng.

Ví dụ 3.18:

Xét văn phạm có các luật sinh sau:

1. S  aABe

2. A  Abc

3. A  b

4. B  d

Cho xâu w = abbcde, ta thấy xâu w có thể rút gọn về ký tự bắt đầu S theo các bước sau:

a b b c d e

 a A b c d e

 a A d e

a A B e

 S Hay

S 1 aABe 4 aAde 2 aAbcde 3 abbcde

Thực chất quá trình rút gọn này là quá trình thể hiện ngược lại của các bước trong dẫn xuất sau:

S 1 aABe 4 aAde 2 aAbcde 3 abbcde

2) Từ thế (Handle)

Một cách trực quan ta có thể hình dung từ thế như là xâu con trùng với vế phải của luật sinh . Quá trình phân tích đẩy – thu đòi hỏi phải tìm được các từ thế để thay thế nó bằng các biến ở vế trái của luật sinh có vế phải trùng với từ thế. Khó khăn ở đây là phải phát hiện từ thế thích hợp để có thể tiếp tục quá trình rút gọn về ký tự bắt đầu. Nếu chỉ ra từ thế không thích hợp có thể làm cho quá trình phân tích thất bại.

Ví dụ 3.19:

Xét văn phạm có các luật sinh sau:

1. S  aABc

2. A  Abc

3. A  b

4. B  d

Và xét xâu w = abbcde

Thử nhìn lại cách rút gọn ở vị trí trên với từ thế khác và không xem Abc là từ thế mà xem b là từ thế thì sẽ có:

? 4 aAAcde 3 aAbcde 3 abbcde

Trong trường hợp này không thể rút gọn tiếp về ký tự bắt đầu S. Vì lý do trên cần phải đưa ra khái niệm chặt chẽ hơn về từ thế.

Từ thế (Handle) của một xâu là một xâu con hợp với vế phải của luật sinh và nếu thu gọn nó thành vế trái của luật sinh đó thì có thể dẫn đến ký hiệu chưa kết thúc bắt đầu.

Một cách hình thức thì xâu  là từ thế của xâu w nếu có dẫn xuất phải nhất: S Rm *Aw Rm w và trong P có luật sinh A  P ở đây w  T*;  V*.

Dễ dàng nhận ra rằng từ thế là xâu con của xâu được sinh ra từ dẫn xuất phải

nhất (Rightmost derivation).

Chú ý:

Trong trường hợp văn phạm nhập nhằng thì ở mỗi bước, dẫn xuất phải có thể có lựa chọn một trong nhiều luật sinh để sử dụng vì vậy có thể có nhiều từ thế. Nếu văn phạm không nhập nhằng thì mỗi bước trong dẫn xuất phải nhất chỉ có một luật sinh được sử dụng và do đó chỉ có một từ thế mà thôi.

Ví dụ 3.20:

Xét văn phạm: E  E + E

E  E * E E  (E)

E  id

Xét dẫn xuất phải nhất E Rm E + E

Rm  E + E * E

Rm  E + E * id3 Rm  E + id2 * id3 Rm  id1 + id2 * id3

Các id1, id2, id3 là ký hiệu của từ thế của id trong dãy trên và .

Vì văn phạm trên là văn phạm nhập nhằng, nên nó có một dẫn xuất phải nhất khác cũng sinh ra xâu trên.

E Rm E * E

Rm  E * id3

Rm E + E * id3 Rm  E + id2 * id3 Rm  id1 + id2 * id3

3) Thay từ thế (Handle Pruning)

Thay từ thế (Handle pruning) là kỹ thuật dùng để tạo ra dẫn xuất phải nhất đảo ngược từ chuỗi ký hiệu kết thúc w mà ta muốn phân tích.

Nếu w là một xâu của văn phạm thì w = γ . Trong đó, γ là dạng câu phải thứ n

n n

của dẫn xuất phải nhất mà ta chưa biết.

S = γ

 γ

0 Rm

 γ

1 Rm

 …

2 Rm

 γ  γ = w

Rm n-1 Rm n

Ðể xây dựng dẫn xuất này theo thứ tự ngược lại, ta tìm từ thế (handle) βn trong γn và thay thế βn bởi An (An là vế trái của luật sinh An → βn) để được dạng câu phải