- r = (r ) + ; r = 0.
2 8 8
+ Xây dựng r
Start
0
0
1
- r = 0
3
Có thể bạn quan tâm!
-
Chương trình dịch - 21 -
Chương trình dịch - 22 -
Chương trình dịch - 23 -
Chương trình dịch - 25 -
Chương trình dịch - 26 -
Chương trình dịch - 27
Xem toàn bộ 224 trang tài liệu này.
Start
2
0
3
- r = 0
6
Start
4
1
5
- r = 1
7
- r = 0
Start
6
0
7
8
- r = r + r
5 6 7
0
ε 2 3 ε
Start 89
ε 4 1 5 ε
- r = (r )*
4 5
ε
0
ε
2
3
Start
10
ε
8
9
11
ε
4
1
5
ε
ε
- r = r r
1 3 4
ε
0
Start
0
0
1
ε
2
3
ε
8
9
11
ε
4
1
5
ε
ε
- r = (r ) +
2 8 ε
Start
12
6
0
7
13
- r = r r
1 2
ε
0
Start
0
0
1
ε
2
3
ε
8
9
11
ε
4
1
5
ε
ε
ε
6
ε
0
7
13
Hình BT 2.21a
*
b) r = ((0+ 1) 0(0 + 1))+
+ Phân tích r
+ *
- Ta có r = (r ) ; r = (0+ 1) 0(0 + 1)
1 1
*
- r = r
1 2
r ; r
3 2
= (0+ 1) 0; r
3
= (0 + 1)
- r = r
2 4
*
r ; r = (0+ 1)
5 4
*
; r = 0
5
- r = (r
4 6
) ; r
6
= 0 + 1
- r = r + r ; r = 0; r = 1
6 7 8 7 8
- r = r + r ; r = 0; r = 1
3 9 10 9 10
+ Xây dựng r
- Xây dựng r = 0; r = 0; r = 1; r = 0; r = 1
5 7 8 9 10
- Xây dựng r = r + r
6 7 8
*
- Xây dựng r
4
= (r )
6
- Xây dựng r2 = r4 r5
- Xây dựng r3 = r9 + r10
- Xây dựng r1 = r2 r3
- Xây dựng r = (r1)+ c) r = (1+ 0)00 (0* + 1+)
+ Phân tích r
- Ta có r = r1 r2; r1= (1+ 0)00; r2= (0* + 1+)
- r1 = r3 r4; r3 = (1+ 0)0; r4 = 0
- r3 = r5 r6 ; r5= 1+ 0; r6 = 0
- r5 = r7 + r8 ; r7 = 1; r8 = 0
- r2 = r9+ r10 ; r9 = 0*; r10 = 1+
- r9 = (r11) * ; r11 = 0
- r10 = (r12) +; r12 = 1
+ Xây dựng r
- Xây dựng r4 = 0; r6 = 0; r7 = 1; r8 = 0; r11 = 0; r12 = 1
- Xây dựng r5 = r7+ r8
- Xây dựng r3 = r5 r6
- Xây dựng r = r r
1 3 4
- Xây dựng r = (r ) *
9 11
- Xây dựng r = (r ) +
10 12
- Xây dựng r = r + r
2 9 10
- Xây dựng r = r r
1 2
*
d) r = (a + ba + aab) (ε + a)+
+ Phân tích r
* +
- Ta có r = r r ; r = (a + ba + aab) ; r = (ε + a)
0 2 0 2
- r0 = (r1) * ; r1= (a + ba + aab)
- r1 = r3 + r4; r3 = a + ba ; r4 = aab
- r3 = r5 + r6 ; r5= a; r6 = ba
- r6= r7 r8 ; r7 = b; r8 = a
- r4 = r9 r10 ; r9 = aa; r10 = b
- r9 = r11 r12 ; r11 = a; r12 = a
- r2 = (r13) +; r13 = ε + a
- r13 = r14 + r15; r14 = ε; r15 = a
+ Xây dựng r
- Xây dựng r5= a; r7 = b; r8 = a; r10 = b; r11 = a; r12 = a; r14 = ε; r15 = a
- Xây dựng r9= r11 r12
- Xây dựng r4 = r9 r10
- Xây dựng r6= r7 r8
- Xây dựng r3 = r5 + r6
- Xây dựng r1 = r3 + r4
- Xây dựng r0 = (r1) *
- Xây dựng r13 = r14 + r15
- Xây dựng r2 = (r13) +
2.23. Hướng dẫn
1) Tương tự bài 2.22
2) Tương tự bài 2.21
2.24. Lời giải tóm tắt
a) Sử dụng các giải thuật , kiểm tra các xâu sau là từ vị của token nào trong các token :
1) – Kiểm tra xâu 123
+ Token digits
Xuất phát từ trạng thái q2 của token digits. Con trỏ trỏ vào ký tự đầu tiên của xâu vào 123$ là 1. Trên sơ đồ chuyển đang ở nút q2 và cung đi ra có nhãn là digit đang nối với nút có nhãn là q3.
Vì digit là token, do đó quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong sơ đồ chuyển của token digit là q0. Trên sơ đồ chuyển đang ở nút q0 và cung đi ra có nhãn là 0 đang nối với nút có nhãn là q1, không trùng với ký tự 1 nên quá trình duyệt chuyển sang cung đi ra khỏi q0 tiếp theo mang nhãn là 1 trùng với ký tự kết thúc được trỏ bởi con trỏ trên xâu vào và đang nối với nút có nhãn là q1. Con trỏ trên xâu vào chuyển sang ký tự tiếp theo là 2, tức là ký tự đầu tiên của xâu 23$. Quá trình duyệt chuyển sang nút có nhãn là q1. Vì q1 là nút kết thúc của token digit nên quá trình duyệt chuyển sang nút có nhãn là q3 của sơ đồ chuyển digits.
Trên sơ đồ chuyển đang ở nút q3 và cung đi ra có nhãn là digit đang nối với nút có nhãn là q3.
Vì digit là token, do đó quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong sơ đồ chuyển của token digit là q0. Trên sơ đồ chuyển đang ở nút q0 và cung đi ra có nhãn là 0 đang nối với nút có nhãn là q1 , không trùng với ký tự 2 nên quá trình duyệt chuyển sang cung đi ra khỏi q0 tiếp theo mang nhãn là 1, không trùng với ký tự 2 nên quá trình duyệt chuyển sang cung đi ra khỏi q0 tiếp theo mang nhãn là 2 trùng với ký tự kết thúc được trỏ bởi con trỏ trên xâu vào và đang nối với nút có nhãn là q1. Con trỏ trên xâu vào chuyển sang ký tự tiếp theo là 3, tức là ký tự đầu tiên của xâu 3$. Quá trình duyệt chuyển sang nút có nhãn là q1. Vì q1 là nút kết thúc của token digit nên quá trình duyệt chuyến sang nút có nhãn là q3 của sơ đồ chuyển digits.
Trên sơ đồ chuyển đang ở nút q3 và cung đi ra có nhãn là digit đang nối với nút có nhãn là q3.
Vì digit là token, do đó quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong sơ đồ chuyển của token digit là q0 . Trên sơ đồ chuyển đang ở nút q0 và cung đi ra có nhãn là 0 đang nối với nút có nhãn là q1, không trùng với ký tự 3 nên quá trình duyệt chuyển sang cung đi ra khỏi q0 tiếp theo mang nhãn là 1, không trùng với ký tự 3 nên quá trình duyệt chuyển sang cung đi ra khỏi q0 tiếp theo mang nhãn là 2, không trùng với ký tự 3 nên quá trình duyệt chuyển sang cung đi ra khỏi q0 tiếp theo mang nhãn là 3 trùng với ký tự kết thúc được trỏ bởi con trỏ trên xâu vào và đang nối với nút có nhãn là q1. 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à q1. Vì q1 là nút kết thúc của token digit nên quá trình duyệt chuyến sang nút có nhãn là q3 của sơ đồ chuyển digits.
Quá trình duyệt đã duyệt hết xâu vào và quá trình duyệt đến được trạng thái kết thúc q3 của sơ đồ chuyển của token digits nên nó thông báo thành công và trả lại cho giai đoạn phân tích cú pháp token digits.
+ Token id
Xuất phát từ trạng thái q24 của token id. Con trỏ trỏ vào ký tự đầu tiên của xâu vào 123$ là 1. Trên sơ đồ chuyển đang ở nút q24 và cung đi ra có nhãn là letter đang nối với nút có nhãn là q25.
Vì letter là token, do đó quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong sơ đồ chuyển của token letter là q22. Trên sơ đồ chuyển đang ở nút q22 và cung đi ra có nhãn là A đang nối với nút có nhãn là q23, không trùng với ký tự 1 nên quá trình duyệt chuyển sang cung đi ra khỏi q22 tiếp theo mang nhãn là B, không trùng với ký tự 1 nên quá trình duyệt chuyển sang cung đi ra khỏi q22 tiếp theo mang nhãn là C, không trùng với ký tự kết thúc được trỏ bởi con trỏ trên xâu vào, ... Quá trình duyệt chuyển sang cung đi ra khỏi q22 cuối cùng mang nhãn là z, không trùng với ký tự kết thúc được trỏ bởi con trỏ trên xâu vào là 1.
Vì đã xét hết các cung đi ra khỏi nút q22 và quá trình duyệt không đến được trạng thái kết thúc của token letter nên quá trình duyệt dừng để thông báo lỗi.
– Kiểm tra xâu 123b
+ Token digits
Xuất phát từ trạng thái q2 của token digits. Con trỏ trỏ vào ký tự đầu tiên của xâu vào 123b$ là 1. Trên sơ đồ chuyển của digits đang ở nút q2 và cung đi ra có nhãn là digit đang nối với nút có nhãn là q3.
Vì digit là token, do đó quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong sơ đồ chuyển của token digit là q0. Trên sơ đồ chuyển của digit đang ở nút q0 và các cung đi ra có nhãn là 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 đang nối với nút có nhãn là q1, Chọn cung đi ra mang nhãn là 1 trùng với ký tự kết thúc được trỏ bởi con trỏ trên xâu vào và đang nối với nút có nhãn là q1. Con trỏ trên xâu vào chuyển sang ký tự tiếp theo là 2, tức là ký tự đầu tiên của xâu 23$. Quá trình duyệt chuyển sang nút có nhãn là q1. Vì q1 là nút kết thúc của token digit nên quá trình duyệt chuyến sang nút có nhãn là q3 của sơ đồ chuyển digits.
Trên sơ đồ chuyển của digits đang ở nút q3 và cung đi ra có nhãn là digit đang nối với nút có nhãn là q3.
Vì digit là token, do đó quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong sơ đồ chuyển của token digit là q0. Trên sơ đồ chuyển của digit đang ở nút q0 và các cung đi ra có nhãn là 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 đang nối với nút có nhãn là q1, Chọn cung đi ra mang nhãn là 2 trùng với ký tự kết thúc được trỏ bởi con trỏ trên xâu vào và đang nối với nút có nhãn là q1. Con trỏ trên xâu vào chuyển sang ký tự tiếp theo là 3, tức là ký tự đầu tiên của xâu 3$. Quá trình duyệt chuyển sang nút có nhãn là q1. Vì q1 là nút kết thúc của token digit nên quá trình duyệt chuyến sang nút có nhãn là q3 của sơ đồ chuyển digits.
Trên sơ đồ chuyển của digits đang ở nút q3 và cung đi ra có nhãn là digit đang nối với nút có nhãn là q3.
Vì digit là token, do đó quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong sơ đồ chuyển của token digit là q0. Trên sơ đồ chuyển của digit đang ở nút q0 và các cung đi ra có nhãn là 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 đang nối với nút có nhãn là q1, Chọn cung đi ra mang nhãn là 3 trùng với ký tự kết thúc được trỏ bởi con trỏ trên xâu vào và đang nối với nút có nhãn là q1. Con trỏ trên xâu vào chuyển sang ký tự tiếp theo là b, tức là ký tự đầu tiên của xâu b$.
Trên sơ đồ chuyển của digits đang ở nút q3 và cung đi ra có nhãn là digit đang nối với nút có nhãn là q3.
Vì digit là token, do đó quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong sơ đồ chuyển của token digit là q0. Trên sơ đồ chuyển của digit đang ở nút q0 và các cung đi ra có nhãn là 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 đang nối với nút có nhãn là q1, không có cung đi ra nào mang nhãn là b.
Vì đã xét hết các cung đi ra khỏi nút q0 và quá trình duyệt không đến được trạng thái kết thúc của token digit nên quá trình duyệt dừng để thông báo lỗi.
+ Các token khác làm tương tự
- Các trường hợp khác làm tương tự như trên.
2) – Kiểm tra xâu X1
+ Token digits
Xuất phát từ trạng thái q2 của token digits. Con trỏ trỏ vào ký tự đầu tiên của xâu vào X1$ là X. Trên sơ đồ chuyển của digits đang ở nút q2 và cung đi ra có nhãn là digit đang nối với nút có nhãn là q3.
Vì digit là token, do đó quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong sơ đồ chuyển của token digit là q0. Trên sơ đồ chuyển của digit đang ở nút q0 và cung đi ra có nhãn là 0 đang nối với nút có nhãn là q1, không trùng với ký tự 1 nên quá trình duyệt chuyển sang cung đi ra khỏi q0 tiếp theo mang nhãn là 1, không trùng với ký tự X nên quá trình duyệt chuyển sang cung đi ra khỏi q0 tiếp theo mang nhãn là 2, không trùng với ký tự kết thúc được trỏ bởi con trỏ trên xâu vào, ... Quá trình duyệt chuyển sang cung đi ra khỏi q0 cuối cùng mang nhãn là 9, không trùng với ký tự kết thúc được trỏ bởi con trỏ trên xâu vào là X.
Vì đã xét hết các cung đi ra khỏi nút q0 và quá trình duyệt không đến được trạng thái kết thúc của token digits nên quá trình duyệt dừng để thông báo lỗi báo lỗi.
+ Token id
Xuất phát từ trạng thái q24 của token id. Con trỏ trỏ vào ký tự đầu tiên của xâu vào X1$ là X. Trên sơ đồ chuyển của id đang ở nút q23 và cung đi ra có nhãn là letter đang nối với nút có nhãn là q24.
Vì letter là token, do đó quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong sơ đồ chuyển của token letter là q22 . Trên sơ đồ chuyển của letter đang ở nút