Trang 1
21/1/2010 Bài toán phân tích cú pháp Bài 6 Bài toán đặt ra Phân tích cú pháp Cho văn phạm phi ngữ cảnh G và xâu w t êtrên xuốống cóó quay l ilui w ∈ L(G)L(G) đđúúng hhay sai?i? Phân tích trên xuống (top down) S ⇒* w? 1 2 w đúng cú pháp ⇒cây cú pháp Phân tích trái E -> E + T E -> T Phân tích trái của α là dãy các sản xuất TT -> T> T * FF đượđượcc ssửử ddụụngng trongtrong suysuy ddẫẫnn tráitrái rara αα ttừừ SS T -> F F -> ( E ) Phân tích là danh sách các số từ 1 đến p F -> ident Biểu diễn cây cú pháp bằng cách nào? 3 4 goupee.com fb.com/groups/goupee 1
Trang 2
21/1/2010 Ví dụ Giải thuật phân tích top down quay lui Xét văn phạm G, các sản xuất được đánh số như sau Tư tưởng chủ yếu của giải thuật là xây 1.E → T+E dựng cây phân tích cú pháp (cây suy dẫn) 2.E → T cho xâu w 3.T → F* T 4.T → F Đánh số thứ tự các sản xuất có cùng vế 5.F → (E) phải, như vậy, các A - sản xuất của văn 6.F → a phạm sẽ được xếp thứ tự Phân tích trái của xâu a*(a+a) là 23645124646 A → α1 | α2 | . . . .| αn 5 6 Mô tả giải thuật Nút hoạt động là ký hiệu không kết thúc A Bắt đầu từ nút gốc S 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 S được coi là nút hoạt động NútNút hohoạạtt độđộngng làlà nútnút nhãnnhãn XX11. Nếu k = 0, (sản xuất A → ε) thì nút hoạt động sẽ là nút Tạo ra các nút con một cách đệ quy bên phải (ngay sau) A khi duyệt cây theo thứ tự trái 7 8 goupee.com fb.com/groups/goupee 2
Trang 3
21/1/2010 Nút được xét có nhãn là ký hiệu Điều kiện để thực hiện giải thuật kết thúc a So sánh với ký hiệu đang xét.
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 bên phải.
NNếếuu aa khôngkhông trùngtrùng vvớớii kýký hihiệệuu đđangang xétxét thìthì quayquay VVăănn phphạạmm GG ccầầnn thothoảả đđiiềềuu kikiệệnn lui tới nút mà tại đó đã sử dụng sản xuất trước không đệ quy trái để tránh rơi vào (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). chu trình
Chuyển đầu đọc sang trái (nếu cần) và thử với lựa chọn tiếp theo. Nếu không còn lựa chọn nào khác thì quay lui tới bước trước đó Nếu đã quay lui tới S và không còn lựa chọn khác:câu sai cú pháp 9 10 Ví dụ Dựng cây phân tích cú pháp Cho văn phạm S → aSb | c Các sCác sảản xun xuấất st sẽ đượẽ đượcc đđánh sánh sốố ttừừ 11 đếđếnn 22. Xét xâu vào aacbb 11 12 goupee.com fb.com/groups/goupee 3
Trang 4
21/1/2010 Thử lựa chọn khác 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 MMộộtt phâhân tí h t áitích trái chho w((nếếu có)ó) Thông báo lỗi nếu ngược lại 13 14 Phương pháp (1) (Xây dựng 2 stack D1 và D2. ∀ A ∈ N , giả sử có các A-sản xuất A → α1 | α2 | . . . .| αn D2 biểu diễn dạạngg câu trái hiệện tạại có đượợc bằngg Coi các sCoi các sảản xun xuấấtt trên làtrên là cách thay thế các ký hiệu không kết thúc bởi vế phải tương ứng A1 → α1 D ghi lại lịch sử những lựa chọn đã sử dụng và . . . . 1 những ký hiệu vào trên đó đầu đọc đã đổi vị trí An → αn 15 16 goupee.com fb.com/groups/goupee 4
Trang 5
21/1/2010 Hình trạng của giải thuật Thực hiện giải thuật Bộ bốn (s, i, α, β) Bắt đầu từ hình trạng đầu, tính liên tiếp s ∈ Q: Trạng thái hiện thời các hình trạng tiếp theo cho đến khi q: Trạng thái bình thường khôngg tính đượợc nữa. bb: QQuay l ilui t: Kết thúc i : Vị trí đầu đọc (Băng vào có dấu hiệu kết thúc #) Nếu hình trạng cuối là (t,n+1,γ,ε), đưa α: Nội dung stack thứ nhất ra h(γ) và dừng. Ngược lại đưa ra thông β: Nội dung stack thứ hai báo sai 17 18 Ví dụ Đánh số lại các sản xuất Xét xâu vào aacbb và văn phạm G với các sản xuất S → aSb 1. 1 22. SS2 →→ cc S → aSb S → c 19 20 goupee.com fb.com/groups/goupee 5
Trang 6
21/1/2010 Quá trình thay đổi hình trạng Tìm phân tích trái (q,1, ε, S#) h(a) = ε ∀a là ký hiệu kết thúc |⎯ (q, 1, S , aSb#) 1 h(A)= p , |⎯ (q, 2, S a, Sb#) i 1 |⎯ (q, 2, S aS ,aSbb#) p là số hiệu của sản xuất liên hệ với sản 1 1 → γ γ |⎯ (q, 3, S aS a, Sbb#) xuất A với là lựa chọn thứ i của A 1 1 ||⎯ ((q, 3 S3, S1aSS1aSS1,aSbbb#)Sbbb#) VVăăn phn phạạmm |⎯ (b, 3, S1aS1aS1,aSbbb#) S → aSb |⎯ (q, 3, S aS aS , cbb#) 1. 1 1 1 2 |⎯ (q, 4, S1aS1aS2c,bb#) 2. S2 → c |⎯ (q, 5, S1aS1aS2cb,b#) aS aS cbb)=112 |⎯ (q, 6, S aS aS cbb,#) h(S1 1 2 1 1 2 |⎯ (t, 6, S1aS1aS2cbb, ε ) 21 22 Thử phân tích quay lui với KPL Chuyển sơ đồ cú pháp thành luật Phân tích từ vựng và mã hóa từ tố <program >::= program ident ; <block>. Tập sản xuất của văn phạm <block>::= <const<block>::= <const-decl><typedecl><type-decl>decl> <proc-decl><func-decl><var-decl> begin <statement-list> end 23 24 goupee.com fb.com/groups/goupee 6
Trang 7
21/1/2010 Mã hóa ký hiệu không kết thúc Mã hóa từ tố: tên, số, hằng ký tự // ident; //specific symbol if(str=="<program>") return 1; if (str == "<para-list>") return 13; if(str == "ident") return 25; if(str=="<block>") return 2; if (str == "<para-one>") return 14; if (str =="lparen") return 35; if(str=="<const-decl>") return 3; if(str=="<func-decl>") return 15; //const if (str == "rparen") return 36; if (str == "<const-assign-list>") return if(str=="<statement-list>") return 16; if(str == "number")return 26; if (str == "comma") return 37; 4; if(str=="<statement>" ) return 17; if ((str == "charcon")) return 27;; if (str ==if (str == "<constant><constant> )") return 5;return 5; if ( tif (str == ""<conditidition>")") retturn 1818; if (str ==if (str == "semicolonsemicolon )") return 38;return 38; if(str=="<type-decl>") return 6; if (str == "<relation>") return 19; //operator if (str == "period") return 39; if (str =="<type-assign-list>") return 7; if(str=="<expression>") return 20; if(str == "plus")return 28; if (str == "<type>") return 8; if (str == "<adding-op>") return 21; if (str == "becomes") return 40; if (str == "<basictype>") return 9; if (str == "minus") return 29; if (str == "lbrace") return 41; if(str=="<term>") return 22 if (str == "times") return 30; if(str=="<var-decl>") return 10; if(str=="<multiplying-op>") return 23; if (str == "rbrace") return 42; if (str == "<ident-list>") return 11; if (str == "<factor>") return 24; if (str == "slash") return 31; if(str=="<proc-decl>") return 12; if (str == "lbrack") return 43; if (str == "oddsym") return 32; if (str == "rbrack") return 44; if (str == "assign") return 33; if (str == "leq") return 34; 25 26 Mã hóa từ tố: từ khóa Mã hóa từ tố: phép toán quan hệ //relations if (str == "beginsym") return 45; if (str == "varsym") return 53; if (str == "eql") return 61; if (str == "endsym") return 46; if (str == "progsym") return 54; if (str == "funcsym") return 55; if (str == "leq") return 62; if (str == "ifsym") return 47; if (str == "thensym") return 48; if (str == "typesym") return 56;if (str == "typesym") return 56; if (str == "neq") return 63;if (str == "neq") return 63; if (str == "whilesym") return 49; if (str == "arraysym") return 57; if (str == "lss") return 64; if (str == "dosym") return 50; if (str == "ofsym") return 58; if (str == "intsym") return 59; if (str == "gtr") return 65; if (str == "callsym") return 51; if (str == "constsym") return 52; if (str == "charsym") return 60; if (str == "geq") return 66; 27 28 goupee.com fb.com/groups/goupee 7
Trang 8
21/1/2010 Mã hóa sản xuất Nhận xét <program >::= program ident ; <block>. Cài đặt phức tạp setlaw[1,1]="54 25 38 2 39 "; Chi phí thời gian quá lớn nếu chương trình phphảải phân tích gi phân tích gồồmm nhinhiềềuu ký hiký hiệệuu (t(từừ ttốố)) <block>::= <const-decl><type-decl> <proc-decl><func-decl><var-decl> begin <statement-list> end Không thể thông báo lỗi chi tiết setlaw[2,1]=" 3 6 12 15 10 45 16 46 "; 29 30 goupee.com fb.com/groups/goupee 8
Hiển thị 8 trang đầu. Tải tài liệu để xem đầy đủ.
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!