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

Chương trình phân tích hoạt động theo nguyên tắc sau:

- Con trỏ ip trỏ vào ký tự a trên xâu vào w.

- Xét ký tự X trên đỉnh ngăn xếp, khi đó chương trình hành động như sau:

+ Nếu X = a = $ chương trình dừng, đưa ra thông báo quá trình phân tích kết thúc thành công.

+ Nếu X = a  $ thì đẩy X ra khỏi đỉnh Stack, con trỏ trên w dịch sang vị trí tiếp theo.

+ Nếu X là biến (Nonterminal), chương trình dò tìm luật sinh X  trên bảng M tại M[X , a], nếu có luật sinh này thì  được đưa vào ngăn xếp và quay lại bước 1, nếu không có, chương trình báo lỗi.

b) Giải thuật phân tích cú pháp dự đoán dựa vào ngăn xếp

Input: G - CFG, xâu vào w$

Output: 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ý tự $ vào Stack chỉ đáy ngăn xếp;

+ Đưa ký hiệu chưa kết thúc bắt đầu S vào đỉnhStack;

+ Đưa vào ngăn đệm xâu vào w$;

+ Con trỏ ip trỏ tới ký hiệu đầu tiên của xâu w$ ;

2. REPEAT

- X là ký hiệu nằm trên đỉnh Stack;

- ip đang trỏ vào ký tự a của xâu vào w$; IF (X  T) OR (X = $) THEN

IF X = a THEN

Begin

- Đẩy X ra khỏi Stack;

- ip := ip +1; end

ELSE witeln(„Thông báo lỗi‟) ELSE {X  N}

IF M[X, a] = X  Y1 Y2….Yk THEN

begin

- Đẩy X ra khỏi Stack;

- Đẩy Yk , Y2, …, Y1 vào Stack { Y1 ở đỉnh};

- Đưa luật sinh X  Y1 Y2….Yk ra Buffer kết quả; end

ELSE witeln(„Thông báo lỗi‟)

UNTIL X = $

Ví dụ 3.12:

Xét văn phạm sau: E  TE‟;

E‟  +TE‟;

E‟ ;

T  FT‟;

T‟  *FT‟;

T‟ ; F  (E);

F  id.

Bảng phân tích cú pháp M cho văn phạm trên ở bảng 3.1. Cần chú ý rằng, các luật sinh ghi trong bảng M theo nguyên tắc nào, ta chưa biết và ta sẽ đề cập đến vấn đề này sau.

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!

• Minh Họa Một Cây Phân Tích Cú Pháp
• 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
• 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
• 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

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

sau:

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

Quá trình phân tích cú pháp cho xâu vào id + id * id được trình bày trong bảng

Bước

STACK	INPUT	OUTPUT
Khởi tạo	$ E	id + id * id $
1	$ E' T	id + id * id $	E  T E'
2	$ E' T F'	id + id * id $	T  F T'
3	$ E' T' id	id + id * id $	F  id
4	$ E' T'	+ id * id $
5	$ E'	+ id * id $	T' 
6	$ E' T +	+ id * id $	E'  + T E'
7	$ E' T	id * id $
8	$ E' T' F	id * id $	T  F T'
9	$ E' T' id	id * id $	F  id
10	$ E' T'	* id $	T'  * F T'
11	$ E' T' F *	* id $
12	$ E' T' F	id $
13	$ E' T' id	id $	F  id
14	$ E' T'	$
15	E' $	$	T' 
16	$	$	E' 

Bảng 3.2. Phân tích cú pháp cho xâu vào id + id * id

Cây phân tích cú pháp được hình thành từ output :

T

E

E‟

F T‟ + T E‟

id 



F T‟

id * F T‟

id 

Hình 3.12. 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

Nhận xét:

- Mỗi văn phạm có một bảng phân tích M tương ứng.

- Chương trình không cần thay đổi cho các văn phạm khác nhau.

c) Xây dựng bảng phân tích cú pháp

Với mục đích hỗ trợ cho giải thuật xây dựng bảng phân tích cú pháp M và phục hồi lỗi theo chiến lược panic_mode; ta xét cách xác định hai hàm FIRST và FOLLOW.

Hàm FIRST

- Định nghĩa

Cho văn phạm G = (N, T, P, S); giả sử  là xâu các ký hiệu văn phạm, tức là

(N T)*. FIRST(α) là tập hợp các ký hiệu kết thúc a mà a là ký hiệu bắt đầu của một xâu được dẫn xuất từ α.

FIRST() = a  T* a;  (NT)*

Nếu trong P có * thì  cũng thuộc FIRST ().

FIRST() cho ta biết xâu  có thể dẫn xuất đến tận cùng thành một xâu bắt đầu bằng một ký hiệu kết thúc nào.

- Cách xác định hàm FIRST(X) với X là một ký hiệu văn phạm

1. Nếu X là ký tự kết thúc thì FIRST(X) = {X}

2. Nếu X  là một luật sinh thì thêm  vào FIRST(X)

3. Nếu X  Y1Y2…Yk là một luật sinh thì thêm FIRST(Y1) trừ  vào FIRST(X). Nếu  FIRST(Y1) thì tiếp tục thêm FIRST(Y2) trừ  vào FIRST(X). Nếu  FIRST(Y1)  FIRST(Y2) thì tiếp tục thêm FIRST(Y3) trừ  vào FIRST(X). Nếu  FIRST(Yt) với mọi t = 1, 2, ..., i và i < k thì tiếp tục thêm FIRST(Yi+1) trừ 

i 1

vào FIRST(X). Cuối cùng thêm  vào FIRST(X) nếu k FIRST(Yi).

Để tính FIRST của các ký tự không kết thúc trong một văn phạm, ta lần lượt xét tất cả các luật sinh. Tại mỗi luật sinh, áp dụng các quy tắc trên để thêm các ký tự vào các tập FIRST. Quá trình này được tiếp tục cho đến khi gặp một lượt duyệt mà không bổ sung thêm được bất kỳ một ký tự kết thúc nào hoặc  vào các tập FIRST thì kết thúc.

Ví dụ 3.13:

Cho văn phạm có các luật sinh sau: E  TE' (1)

E'  + TE' (2)

E'  (3)

T  FT' (4)

T' * FT' (5)

T' (6)

F  (E) (7)

F  id (8)

Tính FIRST(F):

- Từ luật sinh (7), theo quy tắc 3 ta thêm được FIRST(„(‟) = „(‟ (theo quy tắc1) vào FIRST(F).

- Từ luật sinh (8), theo quy tắc 3 ta thêm được FIRST(id) = „id‟ (theo quy tắc1) vào FIRST(F).

- Không còn luật sinh nào có vế trái là F nữa. Vì vậy, ta không thể thêm ký hiệu nào vào FIRST(F) nữa  FIRST(F) = { (, id }.

- Tính FIRST(E' ):

- Từ luật sinh (2), theo quy tắc 3 ta thêm được FIRST(+) = + (theo quy tắc1) vào FIRST(E').

- Từ luật sinh (3), theo quy tắc 2 ta thêm được  vào FIRST(E').

- Không còn luật sinh nào có vế trái là E' nữa. Vì vậy, ta không thể thêm ký hiệu nào vào FIRST(E') nữa  FIRST(E') = { +, }.

Tương tự FIRST(T') = { *, }.

Từ luật sinh (4), theo quy tắc 3: T  FT' và  FIRST(F)  FIRST(T) = FIRST(F) = { (, id }

Tương tự từ E  TE' và  FIRST(T)  FIRST(E) = FIRST(T) = { (, id } Vậy ta có:

FIRST(E) = FIRST(T) = FIRST(F) = { (, id } FIRST(E') = {+,  }

FIRST(T') = {*,  }

Ta cũng có thể tính FIRST của một xâu  như sau:

Giả sử  = Y1Y2….Yk . Trong trường hợp này, ta tính FIRST() như quy tắc 3 ở trên:

1. thêm FIRST(Y1) trừ  vào FIRST().

2. Nếu  FIRST(Y1) thì tiếp tục thêm FIRST(Y2) trừ  vào FIRST(). Nếu 

 FIRST(Y1)  FIRST(Y2) thì tiếp tục thêm FIRST(Y3) trừ  vào FIRST(). Nếu 

 FIRST(Yt) với mọi t = 1, 2, ..., i và i < k thì tiếp tục thêm FIRST(Yi+1) trừ  vào

i 1

FIRST(). Cuối cùng thêm  vào FIRST() nếu k FIRST(Yi).

Hàm FOLLOW

- Ðịnh nghĩa

Cho văn phạm G = (N, T, P, S); A là một ký hiệu chưa kết thúc. FOLLOW(A) là tập hợp các ký hiệu kết thúc a mà nó xuất hiện ngay sau A (bên phía phải của A) trong một dạng câu nào đó. Tức là tập hợp các ký hiệu kết thúc a, sao cho tồn tại một dẫn xuất dạng S * αAaβ. Chú ý rằng nếu A là ký hiệu bên phải nhất trong một dạng câu nào đó thì $  FOLLOW(A) ($ là ký hiệu kết thúc xâu vào).

FOLLOW(A) = a  T S *Aa; , (N  T)*

$  FOLLOW(A)  S *A .

Nói một cách khác FOLLOW(A) là tập các ký tự vào hay các kết thúc xuất hiện ngay sau biến A về bên phải trong một dẫn xuất nào đó.

- Cách xác định hàm FOLLOW(A)

1. Đặt $ vào FOLLOW(S), trong đó S là ký hiệu bắt đầu của văn phạm và $ là ký hiệu thêm vào để đánh dấu kết thúc chuỗi nhập.

2. Nếu có một luật sinh B A thì thêm mọi phần tử khác  của FIRST() vào trong FOLLOW(A) tức là FOLLOW(A) = FOLLOW(A) FIRST() 

3. Nếu có luật sinh B A,

hoặc B A mà  FIRST() thì thêm tất cả các phần tử trong FOLLOW(B) vào FOLLOW(A) tức là FOLLOW(A) = FOLLOW(A)  FOLLOW(B).

Để tính FOLLOW của các ký tự không kết thúc trong một văn phạm, ta lần lượt xét tất cả các luật sinh. Tại mỗi luật sinh, áp dụng các quy tắc trên để thêm các ký tự vào các tập FOLLOW. Quá trình này được tiếp tục cho đến khi gặp một lượt duyệt mà không bổ sung thêm được bất kỳ một ký tự kết thúc nào vào các tập FOLLOW thì kết thúc.

Ví dụ 3.14:

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

E  TE'

(1)
E'  + TE'	(2)
E' 	(3)
T  FT'	(4)
T' * FT'	(5)
T'	(6)
F  (E)	(7)
F  id	(8)

Tính FOLLOW(E):

- Vì E là ký hiệu khởi đầu, theo quy tắc 1 ta thêm $ vào FOLLOW(E) .

- Áp dụng quy tắc 2 cho luật sinh (7):

F  (E)  ) FOLLOW(E)  FOLLOW(E) ={$, )}

- Không còn áp dụng được quy tắc nào cho E nữa. Vậy FOLLOW(E) ={$, )} . Tính FOLLOW(E'):

- Áp dụng quy tắc 3 cho luật sinh (1): E  TE' ta thêm mọi ký hiệu của FOLLOW(E) vào FOLLOW(E')  ), $  FOLLOW(E‟)

- Không thêm được ký hiệu nào vào FOLLOW(E') nữa

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

- Áp dụng luật 2 cho luật sinh (1): E  TE'  +  FOLLOW(T).

- Áp dụng luật 3 cho luật sinh (2, 3): E‟  +TE' , E' 

 FOLLOW(E')  FOLLOW(T)  FOLLOW(T) = { +, ), $ }.

- Áp dụng quy tắc 3 cho luật sinh (4): T  FT' thì FOLLOW(T') = FOLLOW(T) = {+, ), $ }

Áp dụng quy tắc 2 cho luật sinh (4): T  FT'  *  FOLLOW(F) Áp dụng quy tắc 3 cho luật sinh (5, 6): T'  *FT' ; T'

 FOLLOW(T')  FOLLOW(F)  FOLLOW(F) = {*, +, ), $ }. Vậy ta có: FOLLOW(E) = FOLLOW(E') = { $, ) } FOLLOW(T) = FOLLOW(T') = { +, ), $ }

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

Giải thuật xây dựng bảng phân tích cú pháp

Sử dụng các hàm FIRST , FOLLOW có thể đưa ra giải thuật xây dựng bảng phân tích cú pháp cho một văn phạm phi ngữ cảnh như sau:

Input: Văn phạm phi ngữ cảnh Output: Bảng phân tích cú pháp M Process:

Bước 1: Với mỗi luật sinh A  P thực hiện bước 2, 3.

Bước 2: Với mỗi a  FIRST() thì M[A, a]:= “A ” (đưa luật sinh A 

vào vị trí M[A, a]

Bước 3: Nếu  FIRST () thì M[A, b]:= “A ” với mọi b Follou (A).

Bước 4: Các vị trí M[A, a] chưa xác định sau khi thực hiện các bước 2, 3 coi là lỗi (ERROR).

Ví dụ 3.15:

Cho văn phạm có các luật sinh sau: E  TE';

E'  + TE';

E' 

T  FT' T' * FT' ;

T' ;

F  (E) ;

F  id

Áp dụng giải thuật xây dựng bảng phân tích cú pháp dự đoán cho văn phạm trong ví dụ trên: