$ E' T‟) E‟T‟ | + id)$ | ||
13 | $ E' T‟) E‟ | + id)$ | T‟ |
14 | $ E' T‟) E‟T+ | + id)$ | E‟ +TE‟ |
15 | $ E' T‟) E‟T | id)$ | |
16 | $ E' T‟) E‟T‟F | id)$ | T FT‟ |
17 | $ E' T‟) E‟T‟id | id)$ | F id |
18 | $ E' T‟) E‟T‟ | )$ | |
19 | $ E' T‟) E‟ | )$ | T‟ |
20 | $ E' T‟) | )$ | E‟ |
21 | $ E' T‟ | $ | |
22 | $ E' | $ | T‟ |
23 | $ | $ | E‟ |
Có thể bạn quan tâm!
Xem toàn bộ 224 trang tài liệu này.
Bảng BT 3.41.1a Mô phỏng quá trình phân tích cú pháp dự đoán
X = a = $. Quá trình phân tích kết thúc thành công
b) Cây phân tích cú pháp được hình thành từ output :
E
T
E‟
F T‟ + T E‟
T‟
id * F
F T‟
( E )
id
* F T‟
T E‟
id
F T‟
id
Hình BT 3.41b. Cây phân tích cú pháp của xâu id * (id + id) được xây dựng từ trên xuống theo phương pháp dự đoán dựa vào bảng phân tích
2) w = id + id + id)
a) Quá trình phân tích cú pháp đượ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' | + id + id)$ | T‟ |
6 | $ E' T+ | + id + id)$ | E‟ +TE‟ |
7 | $ E' T | id + id)$ | |
8 | $ E' T‟F | id + id)$ | T FT‟ |
9 | $ E' T‟id | id + id)$ | |
10 | $ E' T‟ | + id)$ | |
11 | $ E' | + id)$ | T‟ |
12 | $ E' T+ | + id)$ | E‟ +TE‟ |
13 | $ E' T | id)$ | |
14 | $ E' T‟F | id)$ | T FT‟ |
15 | $ E' T‟id | id)$ | F id |
16 | $ E' T‟ | )$ | |
17 | $ E' | )$ | T‟ |
18 | $ | )$ | E‟ |
Bảng BT 3.41.2a Mô phỏng quá trình phân tích cú pháp dự đoán
X = $ a = ). Quá trình phân tích báo lỗi.
b) Không có cây phân tích cú pháp.
3) w = id + * id + id.
a) Quá trình phân tích cú pháp đượ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' | + * id + id$ | T‟ |
6 | $ E' T+ | + * id + id$ | E‟ +TE‟ |
7 | $ E' T | * id + id$ |
Bảng BT 3.41.3a Mô phỏng quá trình phân tích cú pháp dự đoán
Không tồn tại luật sinh tại ô M[T, *] của bảng phân tích cú pháp nên quá trình phân tích dừng để thông báo lỗi.
b) Không có cây phân tích cú pháp.
Các câu 4, 5, 6, 8) Tự làm, tương tự như trên.
3.42. 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 các luật sinh:
(1) | |
E1 * TE1; | (2) |
E1 | (3) |
T FT1 | (4) |
T1 +FT1; | (5) |
T1 ; | (6) |
F (E) | (7) |
F id | (8) |
b) FIRST và FOLLOW của các ký hiệu không kết thúc
1) FIRST
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(E1):
- Từ luật sinh (2), theo quy tắc 3 ta thêm được FIRST(*) = * (theo quy tắc1) vào FIRST(E1).
- Từ luật sinh (3), theo quy tắc 2 ta thêm được vào FIRST(E1).
- Không còn luật sinh nào có vế trái là E1nữa. Vì vậy, ta không thể thêm ký hiệu nào vào FIRST(E1) nữa FIRST(E1) = { * , }.
Tương tự FIRST(T1) = { +, }.
Từ luật sinh (4), theo quy tắc 3: T FT1 và FIRST(F) FIRST(T) = FIRST(F) = { (, id }
Tương tự từ E TE1 và FIRST(T) FIRST(E) = FIRST(T) = { (, id } Vậy ta có:
FIRST(E) = FIRST(T) = FIRST(F) = { (, id } FIRST(E1) = {* , }
FIRST(T1) = {+ , }
2) FOLLOW
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(E1):
- Áp dụng quy tắc 3 cho luật sinh (1): E TE1 ta thêm mọi ký hiệu của
FOLLOW(E) vào FOLLOW(E1) ), $ FOLLOW(E1)
- Không thêm được ký hiệu nào vào FOLLOW(E1) nữa
FOLLOW(E1) ={$, )}
- Áp dụng luật 2 cho luật sinh (1): E TE1 * FOLLOW(T).
- Áp dụng luật 3 cho luật sinh (2, 3): E1 *TE1 , E1
FOLLOW(E1) FOLLOW(T) FOLLOW(T) = { * , ) , $ }.
- Áp dụng quy tắc 3 cho luật sinh (4): T FT1 thì FOLLOW(T1) = FOLLOW(T) = {* , ) , $ }
Áp dụng quy tắc 2 cho luật sinh (4): T FT1 + FOLLOW(F) Áp dụng quy tắc 3 cho luật sinh (5, 6): T1 +FT1 ; T1
FOLLOW(T1) FOLLOW(F) FOLLOW(F) = {*, +, ), $ }. Vậy ta có: FOLLOW(E) = FOLLOW(E1) = { $, ) }
FOLLOW(T) = FOLLOW(T1) = { * , ) , $ }
FOLLOW(F) = {*, +, ), $ }
c) Xây dựng bảng phân tích cú pháp
Á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:
- Xét luật sinh E TE1:
Tính FIRST(TE1) = FIRST(T) = {( , id}
M[E, id] và M[E,( ] chứa luật sinh E TE1
- Xét luật sinh E1 *TE1 :
Tính FIRST(*TE1) = FIRST(*) = {*}
M[E1, *] chứa E1 *TE1
- Xét luật sinh E1 : Vì FIRST(E1) và FOLLOW(E1) = { ) , $ }
E nằm trong M[E1, )] và M[E1, $]
- Xét luật sinh T1 + FT' : Tính FIRST(+ FT') = {+ }
T1 + FT1 nằm trong M[T1, +]
- Xét luật sinh T1 : Vì FIRST(T1) và FOLLOW(T1) = {* , ) , $}
T' nằm trong M[T1, *] , M[T1, )] và M[T1, $]
- 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 sau:
id | * | + | ( | ) | $ | |
E | E TE1 | E TE1 | ||||
E1 | E1 *TE1 | E1 | E1 | |||
T | T FT1 | T FT1 | ||||
T1 | T1 | T1 +FT1 | T1 | T1 | ||
F | F id | F (E) |
Bảng BT 3.42 Bảng phân tích cú pháp
d) Tự làm, tương tự bài 3.41
3.43. Lời giải tóm tắt
a) Khử đệ quy trái trực tiếp, thu được:
(1) | |
E1 *TE1; | (2) |
E1 | (3) |
T FT1 | (4) |
T1 +FT1; | (5) |
T1 ; | (6) |
F GF1 ; | (7) |
F1 / GF1 ; | (8) |
F1 ; | (9) |
G BG1 ; | (10) |
G1 -BG1 ; | (11) |
G1 ; | (12) |
B (E) | (13) |
B id | (14) |
b) Tính FIRST và FOLLOW của các ký hiệu không kết thúc Tự làm, tương tự bài 4.43b.
c) Xây dựng bảng phân tích cú pháp Tự làm, tương tự bài 4.43c.
d) Tự làm, tương tự bài 3.42
3.44. Lời giải tóm tắt
1) w = id * (id + id)
- Áp dụng giải thuật phân tích cú pháp đẩy - thu, quá trình phân tích xâu được trình bày trong bảng sau:
Ngăn xếp | Xâu vào | Hành động | Kết quả | |
12 | $ | id * (id + id)$ | Đẩy | |
13 | $id | * (id + id)$ | Thu gọn | E id |
14 | $E | * (id + id)$ | Đẩy | |
15 | $E* | (id + id)$ | Đẩy | |
16 | $E*( | id + id)$ | Đẩy | |
17 | $E*(id | + id)$ | Thu gọn | E id |
18 | $E*(E | id)$ | Đẩy | |
19 | $E*(E+id | )$ | Thu gọn | E id |
20 | $E*(E+E | )$ | Thu gọn | E E+E |
21 | $E*(E | )$ | Đẩy | |
22 | $E*(E) | $ | Thu gọn | E (E) |
23 | $E*E | $ | Thu gọn | E E*E |
24 | $E | $ | Thành công |
Bảng 3.44.1. Mô phỏng quá trình phân tích đẩy - thu
- Xây dựng cây phân tích cú pháp
E
E
E
E
E
E
id * (
id + id )
Hình BT 3.44a. 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
2) w = id + id + id)
- Quá trình phân tích cú pháp đẩy - thu xâu được trình bày trong bảng sau:
Ngăn xếp | Xâu vào | Hành động | Kết quả | |
1 | $ | id + id + id)$ | Đẩy | |
2 | $id | + id + id)$ | Thu gọn | E id |
3 | $E | + id + id)$ | Đẩy | |
4 | $E+ | id + id)$ | Đẩy | |
5 | $E+id | + id)$ | Thu gọn | E id |
6 | $E+E | + id)$ | Thu gọn | E E+E |
7 | $E | + id)$ | Đẩy | |
8 | $E+ | id)$ | Đẩy | |
9 | $E+id | )$ | Thu gọn | E id |
10 | $E+E | )$ | Thu gọn | E E+E |
11 | $E | )$ | Đẩy | |
12 | $E) | $ | Báo lỗi |
Bảng 3.44.2. Mô phỏng quá trình phân tích đẩy - thu