Chương trình dịch

a) w = abba b) w = aaaba

S S

a S2

B S1

b B1 A a S1

A S1

b 

a A1 A

a S1

b 

c) d)

Hình BT 3.36. Cây phân tích cú pháp của các xâu

được xây dựng từ trên xuống theo phương pháp đệ quy xuống

3.37. Lời giải tóm tắt

a) Khử đệ quy trái, thu được văn phạm không đệ quy trái với tập các luật sinh: E  TE1 ; E1  * TE1| ;

T  FT1 và T1  +FT1 | ;

F  (E) | id.

b) Tự làm, tương tự bài 3.35, 3.36

3.38. Lời giải tóm tắt

a) Khử đệ quy trái trực tiếp, thu được: E  TE1 ; E1  *TE1| ;

T  FT1 và T1  +FT1 | ;

F  (E) | id.

b) Sơ đồ chuyển

Start

4 T



E1:

Start



Start

(

15 E

)

Hình BT 3.38b1. Sơ đồ chuyển

Biến đổi sơ đồ, thu được sơ đồ kết quả:

E: Start

0 T 3  6

T: Start

7 F 8  13

Start

(

)

Hình BT 3.38b2. Sơ đồ chuyển tổng hợp

c) Áp dụng giải thuật và sử dụng sơ đồ tổng hợp:

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

- Các xâu còn lại phân tích tương tự.

3.39. Lời giải tóm tắt

a) Loại bỏ đệ quy trái trực tiếp

- expr  (expr) expr1 | id expr1 | digits expr1

- expr1  matop expr expr1 | 

- digit  0 | 1 |...| 9 ;

- digits  digit digit* ;

- letter  A | B | ...| Z | a | b |...| z ;

- id  (letter| _ ) (letter | digit | _ )* ;

- matop → + | - | * | / ;

b) Sơ đồ chuyển của văn phạm.

digits

Start

(

expr

)

3 expr1

expr:

Start

5 mato

6 expr

expr18



expr1:

Start

0,1,2,3,4,5,6,7,8,9

Digit:

Start

digit

Digits:

Start

A,…,Z, a, …,z

Letter:

Start

letter

letter, digit

id:

Start

+ , - , *, /

Matop:

Hình BT 3.39b. Sơ đồ chuyển

c) Tự làm, tương tự bài 3.38

3.40. Lời giải tóm tắt

a) Khử đệ quy trái trực tiếp, thu được: E  TE1 ;

E1  * TE1| ;

T  FT1 ;

T1  +FT1 | ; F  GF1 ;

F1  /GF1 | ; G  BG1 ;

G1  -BG1 | ; B  (E) | id.

Start

4 T



E1:

Start



Start



Start



26 G1

G1:

Start

(

)

Hình BT 3.40b. Sơ đồ chuyển

c) Tự làm, tương tự bài 3.38

3.41. Lời giải tóm tắt

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)

STACK	INPUT	OUTPUT
Khởi tạo	$ E	id * (id + id)$
1	$ E' T	id * (id + id)$	E  TE‟
2	$ E' T‟F	id * (id + id)$	T  FT‟
3	$ E' T‟id	id * (id + id)$	F  id
4	$ E' T‟	* (id + id)$
5	$ E' T‟F*	* (id + id)$	T‟  *FT‟
6	$ E' T‟F	(id + id)$
7	$ E' T‟) E (	(id + id)$	F  (E)
8	$ E' T‟) E	id + id)$
9	$ E' T‟) E‟T	id + id)$	E  TE‟
10	$ E' T‟) E‟T‟F	id + id)$	T  FT‟
11	$ E' T‟) E‟T‟id	id + id)$	F  id