a) w = abba b) w = aaaba
S S
a S2
a S2
B S1
b B1 A a S1
S1
a
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
0
T
1
E1
2
E:
Start
3
*
4 T
5
E1
6
E1:
Start
7
F
8
T1
9
T:
Start
10
+
11
F
12
T1
13
T1
Start
14
(
15 E
16
)
17
id
F:
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
14
(
15
16
)
17
id
F:
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 .
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$. 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
0
(
1
expr
2
)
3 expr1
4
id
expr:
Start
5 mato
6 expr
7
expr18
expr1:
Start
0,1,2,3,4,5,6,7,8,9
9
10
Digit:
Start
11
digit
12
digit
Digits:
Start
13
A,…,Z, a, …,z
14
Letter:
Start
15
letter
16
letter, digit
id:
Start
17
+ , - , *, /
18
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
T
E1
0
1
2
b)
E:
Start
3
*
4 T
5
E1
6
E1:
Start
7
F
8
T1
9
T:
Start
10
+
11
F
12
T1
13
T1
Start
14
G
15
F1
16
F:
Start
17
/
18
G
19
F1
20
F1
Start
21
B
22
G1
23
G:
Start
24
-
25
B
26 G1
27
G1:
Start
28
(
29
E
id
30
)
31
B:
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) |
Có thể bạn quan tâm!
-
Chương trình dịch - 23 -
Chương trình dịch - 24 -
Chương trình dịch - 25 -
Chương trình dịch - 27 -
Chương trình dịch - 28
Xem toàn bộ 224 trang tài liệu này.
Bảng BT 3.41
1) w = id * (id + id)
a) Áp dụng giải thuật phân tích cú pháp dự đoán dựa vào ngăn xếp, quá trình phân tích cú pháp cho xâu vào w = id * (id + id) được trình bày trong bảng sau:
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 |