Bài 6 Phân tích cú pháp trên xuống có quay lui
1
Bài toán phân tích cú pháp
Bài toán đặt ra
Cho văn phạm phi ngữ cảnh G và xâu w w Î L(G) đúng hay sai?
Phân tích trên xuống (top down)
2
S Þ* w?
w đúng cú pháp Þcây PT cú pháp
Biểu diễn cây PT cú pháp bằng cách nào?
3
E -> E + T E -> T T -> T * F T -> F F -> ( E ) F -> ident
Phân tích trái
• Phân tích trái của a là dãy các sản xuất được sử dụng
trong suy dẫn trái ra a từ S
• Phân tích phải của a là nghịch đảo của dãy các sản
xuất được sử dụng trong suy dẫn phải ra a từ S
4
• Phân tích là danh sách các số từ 1 đến p
Ví dụ Xét văn phạm G, các sản xuất được đánh số như sau
1. E T+E 2. E T 3. T F* T 4. T F 5. F (E) 6. F a
Suy dẫn trái: E Þ T Þ F*T Þ a*T Þ a* F Þ a*(E) Þ a* (T+ E) Þ a * (F + E) Þ a* (a + E) Þ a* (a+T) Þ a* (a + F) Þ a* (a+a) • •
Phân tích trái của xâu a*(a+a) là 23645146246 Phân tích phải của xâu a*(a+a) là 66464215432
5
Giải thuật phân tích top down quay lui
• Tư tưởng chủ yếu của giải thuật là xây dựng cây
phân tích cú pháp (cây suy dẫn) cho xâu w
6
• Đánh số thứ tự các sản xuất có cùng vế phải, như vậy, các A - sản xuất của văn phạm sẽ được xếp thứ tự A a1 | a2 | . . . .| an
Mô tả giải thuật
• Bắt đầu từ nút gốc S • Nút S được coi là nút hoạt động • Tạo ra các nút con một cách đệ quy
7
Nút hoạt động là ký hiệu không kết thúc A
• Chọn vế phải đầu tiên của A- sản xuất : X1X2. . . .Xk. • Tạo k nút con trực tiếp của A với nhãn X1, X2, . . . .Xk. • Nút hoạt động là nút nhãn X1. • Nếu k = 0, (sản xuất A e) thì nút hoạt động sẽ là nút ngay sau A khi
duyệt cây theo thứ tự trái
8
Nút hoạt động là ký hiệu kết thúc a
• Nếu trùng với ký hiệu đang xét thì chuyển đầu đọc sang phải 1
ô, chuyển sang xét nút tiếp theo.
• Nếu a không trùng với ký hiệu đang xét thì quay lui tới nút mà tại đó đã sử dụng sản xuất trước (Thay thế một ký hiệu không kết thúc - chẳng hạn A - bằng vế phải một sản xuất).
• Chuyển đầu đọc sang trái (nếu cần) và thử với lựa chọn tiếp theo của A. Nếu không còn lựa chọn nào khác thì quay lui tới bước trước đó
9
• So sánh với ký hiệu đang xét trên xâu vào.
Nếu đã quay lui tới S và không còn lựa chọn khác: câu sai cú pháp
10
Điều kiện để thực hiện giải thuật
• Văn phạm G cần thoả điều kiện không đệ quy trái để tránh rơi vào chu trình vô hạn
11
Ví dụ
12
• Quay lại văn phạm 1. S ® aSb 2. S ® c Các sản xuất được đánh số từ 1 đến 2. • Xét xâu vào aacbb
Dựng cây phân tích cú pháp
13
Thử lựa chọn khác
14
Giải thuật phân tích cú pháp quay lui
• Vào
Văn phạm G phi ngữ cảnh không đệ quy trái, xâu w = a1. . . .an, n 0 Các sản xuất của G được đánh số 1,. . . . q
• Ra
Một phân tích trái cho w(nếu có) Thông báo lỗi nếu ngược lại
15
Phương pháp
• Bộ phân tích cú pháp sử dụng 2 stack D1 và D2.
16
D2 biểu diễn dạng câu trái hiện tại có được bằng cách thay thế các ký hiệu không kết thúc bởi vế phải tương ứng D1 ghi lại lịch sử những lựa chọn đã sử dụng và những ký hiệu vào trên đó đầu đọc đã đổi vị trí
Đánh số các sản xuất có cùng vế trái • A N , giả sử có các A-sản xuất
A a1 | a2 | . . . .| an
Coi các sản xuất trên là
17
A1 a1 . . . . An an
Hình trạng của giải thuật
• q: Trạng thái bình thường • b: Quay lui • t: Kết thúc
Bộ bốn (s, i, a, b) • s Q: Trạng thái hiện thời
• i : Vị trí đầu đọc (Băng vào có dấu hiệu kết thúc $)
18
a: Nội dung stack thứ nhất b: Nội dung stack thứ hai
Thực hiện giải thuật
• Bắt đầu từ hình trạng đầu, tính liên tiếp các hình trạng tiếp theo cho đến khi không tính được nữa.
• Nếu hình trạng cuối là (t,n+1,g,e), đưa ra h(g) và
19
dừng. Ngược lại đưa ra thông báo sai
Ví dụ
• Xét xâu vào aacbb và văn phạm G với các sản xuất
20
S aSb S c
Đánh số lại các sản xuất
21
1. S1 aSb 2. S2 c
Quá trình thay đổi hình trạng
(q,1, e, S#) |¾ (q, 1, S1, aSb#) |¾ (q, 2, S1a, Sb#) |¾ (q, 2, S1aS1,aSbb#) |¾ (q, 3, S1aS1a, Sbb#) |¾ (q, 3, S1aS1aS1,aSbbb#) |¾ (b, 3, S1aS1aS1,aSbbb#) |¾ (q, 3, S1aS1aS2, cbb#) |¾ (q, 4, S1aS1aS2c,bb#) |¾ (q, 5, S1aS1aS2cb,b#) |¾ (q, 6, S1aS1aS2cbb,#) |¾ (t, 6, S1aS1aS2cbb, e )
22
Tìm phân tích trái
•
h(a) = ea là ký hiệu kết thúc h(Ai)= p , p là số hiệu của sản xuất liên hệ với sản xuất
A®g với glà lựa chọn thứ i của A
• Văn phạm
1. S1 aSb 2. S2 c h(S1aS1aS2cbb)=112
23
•
Thử phân tích quay lui với KPL
24
• Phân tích từ vựng và mã hóa từ tố • Tập sản xuất của văn phạm
Chuyển sơ đồ cú pháp thành luật
25 list> end if (str == " if(str==" 26 //specific symbol
if (str =="lparen") return 35;
if (str == "rparen") return 36;
if (str == "comma") return 37;
if (str == "semicolon") return 38;
if (str == "period") return 39;
if (str == "becomes") return 40;
if (str == "lbrace") return 41;
if (str == "rbrace") return 42;
if (str == "lbrack") return 43;
if (str == "rbrack") return 44; // ident;
if(str == "ident") return 25;
//const
if(str == "number")return 26;
if (str == "charcon") return 27;
//operator
if(str == "plus")return 28;
if (str == "minus") return 29;
if (str == "times") return 30;
if (str == "slash") return 31;
if (str == "oddsym") return 32;
if (str == "assign") return 33;
if (str == "leq") return 34; 27 if (str == "varsym") return 53;
if (str == "progsym") return 54;
if (str == "funcsym") return 55;
if (str == "typesym") return 56;
if (str == "arraysym") return 57;
if (str == "ofsym") return 58;
if (str == "intsym") return 59;
if (str == "charsym") return 60; if (str == "beginsym") return 45;
if (str == "endsym") return 46;
if (str == "ifsym") return 47;
if (str == "thensym") return 48;
if (str == "whilesym") return 49;
if (str == "dosym") return 50;
if (str == "callsym") return 51;
if (str == "constsym") return 52; 28 29 //relations
if (str == "eql") return 61;
if (str == "leq") return 62;
if (str == "neq") return 63;
if (str == "lss") return 64;
if (str == "gtr") return 65;
if (str == "geq") return 66; setlaw[1,1]="54 25 38 2 39 "; setlaw[2,1]=" 3 6 12 15 10 45 16 46 "; 30 • Cài đặt phức tạp
• Độ phức tạp tính toán hàm mũ theo độ dài xâu vào.
Do vậy chi phí thời gian quá lớn nếu chương trình
phải phân tích gồm nhiều ký hiệu (từ tố) 31 • Không thể thông báo lỗi chi tiếtMã hóa ký hiệu không kết thúc
Mã hóa từ tố: tên, số, hằng ký tự
Mã hóa từ tố: từ khóa
Mã hóa từ tố: phép toán quan hệ
Mã hóa sản xuất
Nhận xét
