Chương trình dịch

Ðây là một văn phạm không nhập nhằng nhưng không phải là văn phạm SLR(1).

Họ tập hợp các mục C bao gồm:

I0 : S' → • S ;

S → • L = R ;

S → • R ; L → • * R ; L → • id ; R → • L

I1 : S' → S •

I2 : S → L • = R ;

R → L • ; I3 : S → R •

I4 : L → * • R ;

R → • L ; L → • * R ; L → • id

I5 : L → id •

I6 : S → L = • R ;

R → • L ; L → • * R ; L → • id

I7 : L → * R• I8 : R → L•

I9 : S → L = R•

Khi xây dựng bảng phân tích SLR cho văn phạm, khi xét tập mục I2 ta thấy mục đầu tiên trong tập này làm cho action[2, =] ="shift 6". Bởi vì =FOLLOW(R), nên mục thứ hai sẽ đặt action[2, =] ="reduce (R → L)"  Có sự đụng độ tại action[2, =]. Vậy văn phạm trên không là văn phạm SLR(1).

CÂU HỎI VÀ BÀI TẬP CHƯƠNG 3

3.1. Nêu vị trí, chức năng và nhiệm vụ của giai đoạn phân tích cú pháp.

3.2. Nêu khái niệm dẫn xuất, dẫn xuất trái nhất, cho ví dụ minh họa.

3.3. Nêu khái niệm cây phân tích cú pháp; phương pháp xây dựng cây phân tích cú pháp; cho ví dụ minh họa.

3.4. Nêu giải thuật thừa số hoá bên trái; chạy một ví dụ minh họa.

3.5. Nêu các phương pháp phân tích cú pháp.

3.6. Nêu các lỗi cú pháp thường gặp và phương pháp xử lý lỗi.

3.7. Nêu các chiến lược phục hồi lỗi.

3.8. Nêu khái niệm văn phạm nhập nhằng; kỹ thuật khử nhập nhằng; cho ví dụ.

3.9. Nêu khái niệm văn phạm phi ngữ cảnh đệ qui trái; phân loại, cho ví dụ minh họa.

3.10. Nêu giải thuật khử đệ qui trái; chạy một ví dụ minh họa.

3.11. Nêu phương pháp phân tích cú pháp từ trên xuống; ý tưởng của giải thuật phân tích cú pháp đệ qui xuống.

3.12. Nêu giải thuật phân tích cú pháp đệ qui xuống, chạy ví dụ minh họa.

3.13. Nêu ý tưởng của kỹ thuật phân tích cú pháp từ dưới lên; cho ví dụ.

3.14. Nêu ý tưởng của kỹ thuật phân tích cú pháp dự đoán; cho ví dụ.

3.15. Nêu cách xây dựng sơ đồ chuyển vị; cho ví dụ.

3.16. Nêu phương pháp phân tích cú pháp dự đoán dựa trên sơ đồ chuyển vị; chạy ví dụ minh họa.

3.17. Nêu giải thuật phân tích cú pháp dự đoán dựa vào ngăn xếp; chạy ví dụ minh họa. Viết lại lý thuyết phần này, dựa vào ngay ngôn ngữ Pascal: tên, số , biểu thức, câu lệnh ...

3.18. Nêu khái niệm và cách xác định hàm First; cho ví dụ.

3.19. Nêu khái niệm và cách xác định hàm Follow; cho ví dụ.

3.20. Nêu thuật toán sử dụng các hàm First và Follow để xây dựng bảng phân tích cú pháp; cho ví dụ minh họa.

3.21. Nêu các khái niệm phân tích đẩy – thu, từ thế, thay từ thế; cho ví dụ.

3.22. Nêu giải thuật phân tích cú pháp đẩy – thu; chạy ví dụ minh họa.

3.23. Nêu mô hình của bộ phân tích cú pháp LR.

3.24. Nêu giải thuật phân tích cú pháp LR.

3.25. Nêu các khái niệm: khả tiền tố, mục trong văn phạm, văn phạm tăng cường; cho ví dụ minh họa.

3.26. Nêu phép toán lấy bao đóng Closure(I) trên LR(0); cho ví dụ.

3.27. Nêu phép toán goto(I, X) trên LR(0); cho ví dụ.

3.28. Nêu kỹ thuật xây dựng tập mục LR(0); cho ví dụ.

3.29. Nêu giải thuật xây dựng bảng phân tích cú pháp SLR; cho ví dụ.

3.30. Cho văn phạm với các luật sinh sau: S  Sb | Aa | b;

A  Ab| Sd | a.

Hãy sử dụng giải thuật khử đệ quy trái cho văn phạm trên.

3.31. Sử dụng giải thuật khử đệ quy trái cho văn phạm có các luật sinh: S  Sc | Aa | Bb | a;

A  Ac | Bd | b; B  Bb | Sa | c.

3.32. Sử dụng giải thuật khử đệ quy trái cho văn phạm có các luật sinh: S  Sc | Aa | Bb | a;

A  Ac | Bd | b; B  Bb | Sa | c; C  a | c.

3.33. Cho văn phạm với các luật sinh:

S  aaaAab | aaaAbb | aaaBC | aaC | Bcd | cad; A  bbBa | bCc | ad;

B  ccC | ccca;

C  b | .

Hãy sử dụng giải thuật thừa số hoá bên trái cho văn phạm trên.

3.34. Cho văn phạm với các luật sinh:

B  ccbC | ccca | bB;

C  ab | ba | a | b.

Hãy sử dụng giải thuật thừa số hoá bên trái cho văn phạm trên.

3.35. Cho văn phạm với các luật sinh: S  bbABc;

A  ab  a  b;

B  bac  baa  ab ac c.

Hãy sử dụng giải thuật phân tích cú pháp đệ quy xuống phân tích các xâu:

a) w = bbabacc.

b) w = bbbbaac.

c) w = bbbabc.

d) w = bbabaac

3.36. Cho văn phạm với các luật sinh:

S  SAa  aB  a;

A  ab  a  b;

B  bac  bad  a b.

Hãy sử dụng giải thuật phân tích cú pháp đệ quy xuống phân tích các xâu:

a) w = aaba.

b) w = aaaba.

c) w = abac.

d) w = abbad.

3.37. Cho văn phạm sinh biểu thức toán học với các quy tắc E → E * T | T;

T → T + F | F;

F → (E) | id.

Hãy sử dụng giải thuật phân tích cú pháp đệ quy xuống phân tích các xâu:

+ w = id * (id + id).

+ w = (id * id)+ id).

+ w = (id + (id + id))* id.

+ w = (id + id) * (id + id).

+ w = id * ((id + id)* id).

3.38. Cho văn phạm sinh ra các biểu thức toán học với các quy tắc sinh: E → E * T | T;

T → T + F | F ;

F → (E) | id.

a) Hãy loại bỏ đệ quy trái trực tiếp trong văn phạm.

b) Hãy xây dựng sơ đồ chuyển cho văn phạm.

c) Sử dụng giải thuật phân tích cú pháp dự đoán dựa vào sơ đồ chuyển để phân tích xâu vào:

1) w = id * id + id

2) w = id + + id * id.

3) w = id + id + id.

4) w = id * (id + id.

5) w = (id + (id + id))* id.

6) w = (id + id) * (id + id).

7) w = id * ((id + id)* id).

3.39. Cho văn phạm sinh ra biểu thức nguyên trong ngôn ngữ lập trình Pascal với các luật sinh cho dưới dạng các định nghĩa chính quy:

1) expr  id | digits;

2) expr  expr matop expr | (expr); 3) digit  0 | 1 |...| 9;

4) digits  (digit)(digit)* ;

5) letter  A | B | ...| Z | a | b |...| z ;

6) id  (letter| _ ) (letter | digit | _ )* ; 7) matop → + | - | * | / .

a) Hãy loại bỏ đệ quy trái trực tiếp trong văn phạm.

b) Hãy xây dựng sơ đồ chuyển cho văn phạm.

c) Sử dụng giải thuật phân tích cú pháp dự đoán dựa vào sơ đồ chuyển để phân tích xâu vào:

1) A1 + 123 - bc2

2) b * a1b

3) 235 / bien1

4) 235 – 12* heso

3.40. Cho văn phạm sinh ra biểu thức toán học với các quy tắc sinh: E → E * T | T;

T → T + F | F ;

F → F / G | G ; G → G - B | B;

B → (E) | id .

a) Hãy loại bỏ đệ quy trái trực tiếp trong văn phạm;

b) Hãy xây dựng sơ đồ chuyển cho văn phạm.

c) Sử dụng giải thuật phân tích cú pháp dự đoán dựa vào sơ đồ chuyển để phân tích xâu vào:

1) w = id - (id + id).

2) w = (id + id)- id).

3) w = (id - (id + id))* id.

4) w = (id + id) / (id + id).

5) w = id * ((id - id) + id).

6) w = id * (id + id)/(id - id).

3.41. Cho văn phạm với các luật sinh:

E  TE‟; E‟  +TE‟; E‟ ;

T  FT‟; T‟  *FT‟; T‟ ;

F  (E); F  id.

Và có bảng phân tích cú pháp M:

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)