Kĩ thuật lập trình - Chương 3: Văn phạm phi ngữ cảnh

Chương 3Văn phạm phi ngữ cảnhNội dungSuy dẫn phi ngữ cảnhCây suy dẫn và sự nhập nhằngGiản lược văn phạm phi ngữ cảnhDạng chuẩn ChomskySuy dẫn phi ngữ cảnhVăn phạm phi ngữ cảnh: là văn phạm trong đó các sản xuất có dạng: A với A;  ()*Suy dẫn phi ngữ cảnh: tại mỗi bước chỉ áp dụng sản xuất phi ngữ cảnh Một số ví dụ về suy dẫn phi ngữ cảnhVí dụ 1: Trong ngôn ngữ lập trình|| A|B|C||Z0|1|2|3|4|5|6|7|8|9Kí hiệu không kết thúc: , , Kí hiệu kết thúc: A, B, C, , Z, 0, 1, 2, , 9Một số ví dụ về suy dẫn phi ngữ cảnhVí dụ 2: Trong văn phạm tiếng Việt có các quy tắc:|bò|mèo|tôi|nó|ăn|nằm|Kí hiệu không kết thúc: , , , , , Kí hiệu kết thúc: “bò”, “mèo”, “tôi”, “nó”, “ăn”, “nằm” là các từ tiếng ViệtSuy dẫn phi ngữ cảnhĐịnh lý III.1 (định lý phân dã suy dẫn) Cho G=(, , P, S) là văn phạm phi ngữ cảnh, đặt V= . Nếu trong G có suy dẫn u1u2un=>kG v trong đó ui, vV* thì tồn tại viV*và kiN (i=1, 2,, n) sao cho: ui=>ki vi Với mọi i=1, 2, , n v=v1v2 vn k1+k2++kn=k(Chứng minh: lý thuyết ngôn ngữ và tính toán – Nguyễn Văn Ba)Cây suy dẫn và sự nhập nhằngĐịnh nghĩa cây suy dẫn: Trong văn phạm phi ngữ cảnh G=(,,P,S), Cây suy dẫn là cây mà mỗi đỉnh được gắn một nhãn là một phần tử thuộc tập {} và thỏa các điều kiện: i. Nhãn của gốc là kí hiệu đầu S. ii. Nhãn của mỗi đỉnh trong là kí hiệu không kết thúc. Nhãn của mỗi lá là kí hiệu kết thúc hoặc . iii. Với mỗi đỉnh trong có nhãn A và các con có nhãn là X1, X2 Xk thì A X1X2Xk là một sản xuất trong G. iv. Nếu một lá có nhãn là  thì lá đó là con duy nhất của cha nóCây suy dẫn (tiếp)Cây con là một cây tạo thành bởi một đỉnh và mọi hậu duệ của nó cùng với các nhãn và cung liên kết chúng. Gốc cây con có nhãn là A ta gọi cây con đó là A-câyBiên (kết quả) của một cây suy dẫn hay của một A-cây là xâu tạo thành bằng cách ghép tiếp các lá của cây theo trật tự từ trái qua phải ta được một câu gọi là kết quả.Ví dụ về cây suy dẫnVí dụ: xét văn phạm G({S, A}, {a, b}, P, S}, với P gồm: S  aAS | a A  SbA | SS | baMột dẫn xuất của G: S => aAS => aSbAS => aabAS => aabbaS => aabbaa1361025947811SAbbaSaSAaaCây suy dẫn (tiếp)Định lý III.2: Cho G là văn phạm phi ngữ cảnh có một xâu w được sản sinh bởi G (S=>*Gw ) khi và chỉ khi có một cây suy dẫn của văn phạm đó mà biên của nó là w.Chứng minh:Giả sử có cây suy dẫn biên là w thì có suy dẫn S=>*w.Giả sử có suy dẫn S=>*w thì có cây suy dẫn biên là w.Suy dẫn trái và suy dẫn phảiSuy dẫn trái: là suy dẫn mà trong đó, ở mỗi bước, kí hiệu được thay thế luôn luôn là kí hiệu không kết thúc nằm bên trái nhất trong dạng câu.Suy dẫn phải:là suy dẫn mà trong đó, ở mỗi bước, kí hiệu được thay thế luôn luôn là kí hiệu không kết thúc nằm bên phải nhất trong dạng câu.Suy dẫn trái và suy dẫn phải (tiếp)Ví dụ: Cho văn phạm G với các sản xuất: S AB A  aA|a B  bB|bCác dẫn xuất khác nhau cho từ aaabb: 1. S =>AB => aAB => aaAB => aaaB => aaabB => aaabb 2. S => AB => AbB => Abb => aAbb => aaAbb => aaabb 3. S => AB => aAB => aAbB => aAbb => aaAbb => aaabb 4. S => AB => aAB => aaAB => aaAbB => aaabB => aaabbDẫn xuất (1) là dẫn xuất trái nhất, (2) là dẫn xuất phải nhấtCác dẫn xuất tuy khác nhau, nhưng có cùng một cây dẫn xuấtVăn phạm nhập nhằng Khái niệm: một văn phạm phi ngữ cảnh G được gọi là văn phạm nhập nhằng (ambiguity) nếu nó có nhiều hơn một cây dẫn xuất cho cùng một chuỗi w.Văn phạm nhập nhằng (tiếp)Một ngôn ngữ có thể được sinh ra từ văn phạm nhập nhằng hoặc văn phạm không nhập nhằngNgôn ngữ được gọi là nhập nhằng (nhập nhằng cố hữu – không nghiên cứu) nếu mọi văn phạm sinh ra nó đều nhập nhằng Văn phạm nhập nhằng (tiếp)Để giản trừ nhập nhằng: ta đưa vào một số kí hiệu kết thúc phụ và một vài sản xuất trung gian:Quy định rằng các phép cộng và nhân luôn được thực hiện theo thứ tự từ trái sang phải (trừ khi gặp ngoặc đơn) E  E + T | E * T | T T  (E) | a Quy định rằng khi không có dấu ngoặc đơn ngăn cách thì phép nhân luôn được thực hiện ưu tiên hơn phép cộng E  E + T | T T  T * F | F F  (E) | aBiến đổi văn phạm phi ngữ cảnhLoại bỏ các kí hiệu vô íchLoại bỏ các sản xuất Loại bỏ các sản xuất đơnLoại bỏ kí hiệu vô íchĐịnh nghĩa: Cho văn phạm G=(,,P,S), đặt V=. XV là có ích nếu tồn tại suy dẫn: S=>*Xβ=>*w (, βV*; w* ). Nếu không thì nó là kí hiệu vô íchVậy kí hiệu có ích X là:Kí hiệu hữu sinh, nghĩa là tồn tại một xâu x* mà X=>*xKí hiệu đến được, nghĩa là tồn tại hai xâu , β V* sao cho S=>* Xβ Loại bỏ kí hiệu vô sinhBổ đề III.1 (Loại bỏ các kí hiệu vô sinh) Tồn tại một thuật toán cho phép, với mọi văn phạm phi ngữ cảnh G mà L(G)≠, thành lập một văn phạm phi ngữ cảnh tương đương G’ chỉ có các kí hiệu hữu sinhThuật toán: Thành lập tập các kí hiệu hữu sinh W:W0=; Wi=Wi-1{A|ƎWi-1*: AP} (với i>0)W=  Wi (i≥0) Quá trình bổ sung sẽ dừng vì tập W  Thành lập văn phạm G’=(, ’, P’,S):’=W ;P’={AuP|A’, u( ’)*}Loại bỏ kí hiệu vô sinhVí dụ: Cho G=(, , P, S) trong đó:={a, b}; ={S, A, B, C}P={SaA| bAB| abA AaB| bA| a BaB| bB CaA| bS| a } Tìm văn phạm G’ tương đương không còn kí hiệu vô sinhLoại bỏ kí hiệu vô sinhLời giải:W0={a, b}W1=W0{A, C} (vì có các sản xuất Aa, Ca)W2=W1{S} (vì có sản xuất SaA)W3=W2W={a, b, A, C, S}; G’={, ’, P’, S} trong đó: ’={S, A, C} P’={SaA| abA, AbA| a, CaA| bS| a}Loại bỏ các kí hiệu không đến đượcBổ đề III.2 (Loại bỏ các kí hiệu không đến được) Tồn tại một thuật toán cho phép với mọi văn phạm phi ngữ cảnh G thành lập một văn phạm phi ngữ cảnh tương đương G’ chỉ có các kí hiệu đến được. Thuật toán:Thành lập tập hợp các kí hiệu đến được:W0={S}; U0=Wi=Wi-1{A| ƎBWi-1, Ǝu1, u2()*: Bu1Au2P}Ui=Ui-1 {a| ƎBWi-1, Ǝu1, u2()*: Bu1au2P}W=Wi; U= Ui (i≥0)Thành lập văn phạm G’=(U, W, P’, S) trong đó:P’={AuP|AW và u(U  W)*}Loại bỏ các kí hiệu không đến đượcVí dụ: Cho G’ ở ví dụ trên, tìm văn phạm G’’ chỉ gồm các kí hiệu đến được:W0={S}; U0=W1= W0{A}; U1=U0 {a, b}W2=W1; U2=U1W={S, A}; U={a, b}Văn phạm G’’=({a, b}, {S, A}, P’’, S) trong đó: P’’={SaA| abA AbA|a}Loại bỏ -sản xuất-sản xuất:-sản xuất là các sản xuất có dạng AKhi xâu  thuộc ngôn ngữ thì văn phạm phải chứa ít nhất một -sản xuất (thường là S ), ngoài ra các -sản xuất đều là thừa và có thể loại bỏĐịnh lý III.4: Cho văn phạm G=(, , P, S) là một văn phạm phi ngữ cảnh. Ta có thể thành lập một văn phạm phi ngữ cảnh G’=(, , P’, S) không có -sản xuất mà: L(G’)=L(G)-{}Loại bỏ -sản xuấtThuật toán:Thành lập tập hợp các kí hiệu không kết thúc sinh ra xâu rỗng:Đặt E0={A|AP}Ei=Ei-1{A| ƎuEi-1*: AuP} (i>0)E= Ei (i≥0)Thành lập các sản xuất P’:Với mỗi sản xuất AX1X2Xn P ta đưa vào P’ tất cả các sản xuất có dạng A12n trong đó: (1) Nếu XiE thì i=Xi (2) Nếu XiE thì i=Xi hoặc i= Loại bỏ tất cả các -sản xuấtLoại bỏ -sản xuấtVí dụ: Cho văn phạm: SABC, ABB|, BCC|a, CAA|b Loại bỏ các -sản xuất của văn phạm trên.Lời giải:E={A, C, B, S}Văn phạm G’ tương đương là:SABC| AB| BC| AC| A| B| CABB| BB CC| C| aC AA| A| bLoại bỏ các sản xuất đơnSản xuất đơn:Sản xuất đơn là sản xuất có dạng AB (A, B)Sản xuất đơn thường làm kéo dài các suy dẫn nên ta cần loại bỏLoại bỏ các sản xuất đơnĐịnh lý III.6 Cho một văn phạm phi ngữ cảnh G=(, , P, S). Ta có thể thành lập một văn phạm tương đương G’=(, , P’, S) không có các sản xuất đơn.Thuật toán: Thành lập G’Cho R là quan hệ trên  được định nghĩa là: ARB khi và chỉ khi ABPĐặt: P’={A| ƎBP, với   và AR*B}(R* là bao đóng phản xạ, bắc cầu của R)Loại bỏ các sản xuất đơnVí dụ: Cho văn phạm G:EE+T| TTT*F| FF(E)| aTìm văn phạm G’ không còn sản xuất đơnLoại bỏ các sản xuất đơnTa có: R={(E, T), (T, F)}R*={(E, E), (T, T), (F, F), (E, T), (T, F), (E, F)}Có EE+T mà E+T, có (E, E)R* suy ra có sản xuất: EE+TCó T T*F mà T*F, có (T,T), (E,T) R* suy ra có sản xuất: TT*F và ET*FCó F(E) mà (E), có (F, F), (T, F), (E, F)R* suy ra có sản xuất: F(E) và T(E) và E(E)Có Fa mà a, có (F,F), (T,F), (E,F) R* suy ra có sản xuất: Fa và Ta và EaLoại bỏ các sản xuất đơnVăn phạm tương đương không có sản xuất đơn:EE+T| T*F| (E)| aTT*F|(E)| aF(E)|aDạng chuẩn ChomskyDạng chuẩn Chomsky: Văn phạm phi ngữ cảnh ở dạng chuẩn Chomsky là văn phạm mà các sản xuất của nó ở một trong hai dạng:ABCAaTrong đó: A, B, C, a Định lý III.9 Cho văn phạm phi ngữ cảnh G. Ta có thể thành lập một văn phạm G’ ở dạng chuẩn Chomsky sao cho L(G’)=L(G)Đưa văn phạm về dạng chuẩn ChomskyThuật toán: dựng G’=(, ’, P’, S) tương đương với GNhặt các sản xuất trong P ở dạng chuẩn Chomsky đưa vào P’Các sản xuất còn lại đưa về dạng chuẩn Chomsky:Nếu có sản xuất AY1Y2Yk (k>2) thì thay sản xuất đó bằng hai sản xuất AY1A’ và A’Y2Yk. Lặp lại cho tới khi độ dài vế phải các sản xuất không lớn hơn 2Nếu có sản xuất mà vế phải độ dài có chứa kí hiệu kết thúc a, ta thêm một kí hiệu không kết thúc Ca, thay sự xuất hiện của a trong sản xuất bằng Ca và thêm sản xuất CaaĐưa văn phạm về dạng chuẩn ChomskyVí dụ: Đưa văn phạm trên về dạng chuẩn Chomsky SaAB| BBBA ABAB| a B AS| bLời giải: B1: Các sản xuất đã ở dạng chuẩn Chomsky Aa BAS| b B2: Đưa các sản xuất còn lại về dạng chuẩn Chomsky SaAB được thay bằng SCAB và Ca SCAB được thay bằng SCD và DAB SBBBA được thay bằng SBE và EBBA EBBA được thay bằng EBF và FBA ABAB được thay bằng ABT và TABĐưa văn phạm về dạng chuẩn ChomskyTa thu được văn phạm G’=(, ’, P’, S) trong đó: ’={S, A, B, C, D, E, F, T} P’={ SCD| BE Ca DAB EBE FBA ABT| a TAB BAS| b}