Đề tài Mô phỏng lại hoạt động của các giải thuật trong phần ngôn ngữ phi ngữ cảnh đặc biệt là các giải thuật phân tích cú pháp Earley và CYK

LÔØI NOÙI ÑAÀU Moân hoïc ngoân ngöõ hình thöùc vaø automata coù raát nhieàu öùng duïng trong lónh vöïc khoa hoïc maùy tính nhö xaây döïng caùc trình bieân dòch, nhaän daïng vaø chuyeån ñoåi giöõa caùc ngoân ngöõ khaùc nhau… Do ñoù maø moân hoïc naøy laø moät moân hoïc baét buoäc cho caùc sinh vieân ngaønh CNTT trong caùc tröôøng ñaïi hoïc. Ñeå giuùp cho caùc sinh vieân coù ñieàu kieän hoïc toát vaø thöïc haønh caùc baøi taäp cuûa moân hoïc naøy, luaän vaên naøy ñi saâu vaøo vieäc moâ phoûng laïi hoaït ñoäng cuûa caùc giaûi thuaät trong phaàn ngoân ngöõ phi ngöõ caûnh ñaëc bieät laø caùc giaûi thuaät phaân tích cuù phaùp Earley vaø CYK. Sinh vieân coù theå khai thaùc cô sôû lyù thuyeát cuûa moân hoïc thoâng qua heä thoáng Help cuûa chöông trình. Xin caùm ôn thaày Hoà Vaên Quaân ñaõ taän tình höôùng daãn vaø giuùp ñôõ toâi hoaøn thaønh baûn luaän vaên toát nghieäp nhö yeâu caàu cuûa ñeà baøi. Sinh Vieân Thöïc Hieän Thaùi Thuaàn Thaïch PHAÀN 1 GIÔÙI THIEÄU 1. GIÔÙI THIEÄU ÑEÀ TAØI Yeâu caàu cuûa ñeà taøi laø : “Xaây döïng boä coâng cuï thöïc hieän moät soá giaûi thuaät trong moân hoïc ngoân ngöõ hình thöùc vaø Automata.” Ngoaøi caùc giaûi thuaät bieán ñoåi vaên phaïm, taäp trung vaøo nghieân cöùu vaø hieän thöïc hai giaûi thuaät phaân tích cuù phaùp CYK vaø Earley, Ñaùnh giaù soá böôùc phaân tích cuûa moãi giaûi thuaät. Aùp duïng nhaän daïng moät caâu nhaäp thuoäc ngoân ngöõ töï nhieân (Tieáng Anh) 2. MUÏC ÑÍCH & YÙ NGHÓA Hieän nay, ôû nöôùc ta vieäc aùp duïng giaûng daïy caùc moân hoïc thoâng qua caùc moâ hình giaûng daïy thieát keá treân maùy tính coøn gaëp nhieàu khoù khaên, moät trong nhöõng nguyeân nhaân laø thieáu caùc phaàn meàm hoã trôï vieäc hoïc vaø giaûng daïy. Luaän vaên naøy ra ñôøi khoâng naèm ngoaøi muïc ñích giuùp sinh vieân nghaønh CNTT coù moät coâng cuï ñeå hoã trôï theâm cho vieäc hoïc moân hoïc “Ngoân Ngöõ Hình Thöùc & Automata” . Boä coâng cuï naøy cho pheùp sinh thaáy roõ caùch thöùc hoaït ñoäng cuûa moät soá giaûi thuaät cuûa phaàn ngoân ngöõ phi ngöõ caûnh, cuõng nhö thaáy ñöôïc öùng duïng cuûa caùc giaûi thuaät phaân tích cuù phaùp. 3. NOÄI DUNG CHÍNH CUÛA LUAÄN VAÊN TOÁT NGHIEÄP Noäi dung cuûa luaän vaên ñöôïc chia laøm 8 phaàn, cuï theå nhö sau: Phaàn 1 : Laø phaàn giôùi thieäu veà ñeà taøi, cuøng yù nghóa vaø taàm quan troïng cuûa noù. Phaàn 2 : Ñaây laø phaàn tìm hieåu veà cô sôû lyù thuyeát coù lieân quan, trong phaàn 2 naøy ñöôïc chia laøm 4 chöông vôùi caùc chuû ñeà tìm hieåu khaùc nhau cuï theå laø : Chöông 1 : Moät soá khaùi nieäm cô baûn cuûa moân hoïc Muïc ñích cuûa chöông naøy laø giuùp cho ngöôøi ñoïc laøm quen vôùi moät soá khaùi nieäm veà Ngoân ngöõ Hình thöùc & Automat nhö chuoãi, ngoân ngöõ vaø vaên phaïm chính qui, ngoân ngöõ vaø vaên phaïm PNC, caây daãn xuaát… ñeå coù theå deã daøng ñoïc tieáp nhöõng phaàn sau.Tuy nhieân, ngöôøi ñoïc coù theå boû qua chöông naøy neáu ñaõ naém ñöôïc caùc khaùi nieäm treân. Chöông 2 :Caùc giaûi thuaät bieán ñoåi vaên phaïm PNC & caùc daïng chuaån Trong chöông naøy taäp trung tìm hieåu caùc giaûi thuaät bieán ñoåi vaên phaïm PNC nhö : Loaïi boû caùc luaät sinh roãng, ñôn vò, voâ duïng cuõng nhö chuyeån ñoåi moät vaên phaïm PNC baát kyø veà hai daïng chuaån Chomsky vaø Greibach, ñaây laø phaàn lyù thueát cô baûn laøm neàn taûng cho vieäc thöïc hieän giaûi thuaät phaân tích cuù phaùp CYK sau naøy. Chöông 3 : Trình baøy Moät soá giaûi thuaät vaø coâng cuï phaân tích cuù phaùp thoâng duïng bao goàm phöông phaùp töø treân xuoáng (top -down) vaø töø döôùi leân (bootom -up) muïc ñích laø giuùp cho ngöôøi ñoïc coù sô sôû ñeå so saùnh vôùi hai giaûi thuaät phaân tích cuù phaùp toång quaùt CYK vaø Earley Chuông 4 : Giaûi thuaät phaân tích cuù phaùp Earley vaø CYK, ñaây laø phaàn chính cuûa luaän vaên, trong chöông naøy chuù troïng ñeán vieäc tìm hieåu veà giaûi thuaät ñeå phaân tích cuù phaùp vaø taïo chuoãi daãn xuaát cho caâu nhaäp, cuõng nhö so saùnh ñoä phöùc taïp cuûa hai giaûi thuaät naøy vôùi caùc giaûi thuaät ôû chöông 3. Phaàn 3 : Tìm hieåu lyù thuyeát veà phaàn meàm hoã trôï hoïc taäp vaø giaûng daïy, caùch thöùc ñeå thieát keá vaø löïa choïn moâ hình giaûng daïy toát. Phaàn 4 : Taäp trung phaân tích vaø thieát keá cho moâ hình vöøa choïn, phaàn naøy döïa treân caùc lyù thuyeát ñaõ tìm hieåu ôû phaàn 2 vaø moâ hình giaûng daïy ñeå ñöa ra Löïa choïn ngoân ngöõ laäp trình Caáu truùc döõ lieäu cho caùc giaûi thuaät söû duïng trong chöông trình Caùch thöùc nhaäp lieäu, caáu truùc file löu tröõ Caùch trình baøy döõ lieäu xuaát Caùc löu ñoà thuaät toaùn, tính toaùn ñoä phöùc taïp… … Phaàn 5 : So saùnh ñoä phöùc taïp giöõa hai giaûi thuaät phaân tích cuù phaùp CYK vaø Earley, trong phaàn naøy ñöa ra caùc giaû thieát ñeå thöïc hieän tính ñoä phöùc taïp cho hai giaûi thuaät treân baèng chöông trình cuõng nhö ñöa ra nhöõng minh hoïa baèng ví duï thöïc teá (vôùi caùc ñoà thò minh hoïa) Phaàn 6 : Aùp duïng nhaän daïng ngoân ngöõ töï nhieân, trong phaàn naøy seõ trình baøy caùc vaán ñeà lieân quan ñeán vieäc nhaän daïng moät caâu nhaäp (Tieáng Anh) vaø caùch thöùc xaây döïng boä töø ñieån token. Phaàn 7 : Thieát keá Help : ñaây cuõng laø moät phaàn quan troïng cuûa moät chöông trình trôï giuùp hoïc taäp, trong phaàn naøy chuù troïng tìm hieåu thieát keá moät heä thoáng Help. Ñaëc bieät laø thieát keá heä thoáng Help cho chöông trình thoâng qua coâng cuï Windows Help Designer Pro (down load töø Phaàn 8 : Giôùi thieäu chuông trình keát quaû. Phaàn 9 : Phuï luïc - Maõ chöông trình Phaàn 10 : Giôùi thieäu caùc taøi lieäu tham khaûo PHAÀN 2 : CÔ SÔÛ LYÙ THUYEÁT LIEÂN QUAN CHÖÔNG 1 MOÄT SOÁ KHAÙI NIEÄM CÔ BAÛN Trong chöông naøy chuùng ta seõ tìm hieåu moät soá khaùi nieäm vaø ñònh nghóa cô baûn lieân quan ñeán moân hoïc nhö : baûng chöõ caùi, chuoãi, ngoân ngöõ, vaên phaïm, caây daãn xuaát…, tuy nhieân sinh vieân coù theå boû qua chöông naøy neáu ñaõ naém baét ñöôïc caùc khaùi nieäm treân. 1. BAÛNG CHÖÕ CAÙI Laø moät taäp höõu haïn khoâng troáng caùc kyù hieäu (symbol) taäp naøy thöôøng ñöôïc kyù hieäu baèng S Ví duï : {A,B,C,...,Z} : Baûng chöõ caùi chöõ La Tinh {0,1,2,....9} : Baûng chöõ soá thaäp phaân 2. CHUOÃI Cho S laø baûng chöõ caùi (alphabet), moät töø w treân S laø moät chuoãi höõu haïn caùc chöõ caùi. Ví duï: w=aabba, v=aaabbb laø caùc töø treân baûng chöõ caùi S={a,b} Chuoãi roãng cuõng laø moät töø treân baûng chöõ caùi S kyù hieäu laø l Keát noái chuoãi (concatenation) : Cho hai chuoãi u,v treân baûng chöõ caùi S, keát noái giöõa hai chuoãi u,v kyù hieäu laø uv laø moät töø treân baûng chöõ caùi S bao goàm caùc kyù hieäu thuoäc u theo sau laø caùc kyù hieäu thuoäc v. Ví duï: S ={a,b,1,2} u=aabb v=1122 uv=aabb1122 Ñaûo moät chuoãi : laø chuoãi nhaän ñöôïc baèng caùch vieát caùc kyù hieäu theo thöù töï ngöôïc laïi. Ví duï : v=1122 thì vR=2211 Tieáp ñaàu ngöõ (prefix) vaø tieáp vó ngöõ (suffix) cuûa moät chuoãi : Neâu w=uv thì u ñöôïc goïi laø tieáp ñaàu ngöõ vaø v ñöôïc goïi laø tieáp vó ngöõ cuûa w Chieàu daøi cuûa moät chuoãi : Chieàu daøi cuûa moät chuoãi w ñöôïc kyù hieäu laø |w| hay laø l(w) laø soá kyù hieäu coù trong chuoãi. Vôùi moïi chuoãi u,v treân S ta coù: |uv|=|u|+|v| |uv|=|vu| Luõy thöøa cuûa moät chuoãi: neâu w laø moät chuoãi thì wn laø moät chuoãi coù ñöôïc baèng caùch keát noái chuoãi w vôùi chính noù n laàn, tröôøng hôïp ñaëc bieät w0=l S* : Neáu S laø moät baûng chöõ caùi thì taäp taát caû caùc chuoãi treân S keå caû chuôûi troáng ñöôïc goïi laø S* S+: Neáu S laø moät baûng chöõ caùi thì taäp taát caû caùc chuoãi treân S khoâng keå chuôûi troáng ñöôïc goïi laø S+ 3. NGOÂN NGÖÕ Baát kyø moät taäp L naøo treân baûng chöõ caùi S, hay taäp con L cuûa S* ñöôïc goïi laø moät ngoân ngöõ. Ví duï : Cho S={a,b} thì S*={l,a,b,aa,ab,ba,aaa,aab,...} Taäp {a,aa,aab} laø moät ngoân ngöõ treân å Taäp L={anbn : n³0} cuõng laø moät ngoân ngöõ treân taäp å Vì ngoân ngöõ laø moät taäp hôïp caùc chuoãi neân hoäi (union), giao (intersection) vaø hieäu (diference) cuûa hai ngoân ngöõ deã daøng xaùc ñònh ngay laäp töùc. Buø cuûa moät ngoân ngöõ : Buø cuûa moät ngoân ngöõ L treân baûng chöõ caùi å ñöôïc kyù hieäu laø L =å*-L Cho L1 vaø L2 laø hai ngoân ngöõ treân baûng chöõ caùi å: + L1L2 : Laø moät ngoân ngöõ treân å chöùa caùc chuoãi coù ñöôïc baèng caùch noái baát kyø moät chuoãi cuûa ngoân ngöõ L1 vôùi moät chuoãi baát kyø cuûa ngoân ngöõ thuoäc L2 L1L2={w: w=uv, uÎL1, vÎL2} + Ln : Luõy thöøa cuûa moät ngoân ngöõ bao goàm L noái vôùi chính n laàn vôùi tröôøng hôïp ñaëc bieät : L0={l} Ln=Ln-1L vôùi n³0 Bao ñoùng -sao cuûa moät ngoân ngöõ L ñöôïc kyù hieäu laø L* vôùi : L*=L0ÈL1ÈL2... Bao ñoùng -döông cuûa moät ngoân ngöõ L ñöôïc kyù hieäu laø L+ vôùi : L+=L1ÈL2... 4.VAÊN PHAÏM CHÍNH QUI VAØ NGOÂN NGÖÕ CHÍNH QUI 4.1- Vaên phaïm Chính Qui Ñeå nguyeân cöùu moät ngoân ngöõ, chuùng ta caàn moät cô cheá ñeå moâ taû noù. Ngoân ngöõ haøng ngaøy thöôøng khoâng chính xaùc (vì coù theå hieåu theo nhieàu nghóa tuøy vaøo hoaøn caûnh cuûa töøng ngöôøi vaø boái caûnh saûy ra), cuù phaùp thì nhaäp nhaèng khoâng roõ raøng (caâu coù theå khoâng xaùc ñònh ñöôïc yù nghóa chính xaùc), vì vaäy chuùng ta seõ tìm hieåu moät vaøi cô cheá ñònh nghóa ngoân ngöõ raát hieäu quaû trong caùc tröôøng hôïp khaùc nhau ñoù laø ñònh nghóa ngoân ngöõ thoâng qua vaên phaïm. Ñònh Nghóa Moät vaên phaïm G ñöôïc xaùc ñònh nhö laø moät boä boán : G=(V,T,S,P) Trong ñoù: + V laø moät taäp höõu haïn caùc ñoái töôïng ñöôïc goïi laø caùc bieán (variable) + T laø moät taäp höõu haïn caùc ñoái töôïng ñöôïc goïi laø caùc kyù hieäu keát thuùc (terminal symbol) + SÎ V laø moät kyù hieäu ñaët bieät ñöôïc goïi laø bieán khôûi ñaàu. + P laø taäp höõu haïn caùc luaät sinh (Production) Vaên phaïm tuyeán tính Phaûi vaø Traùi + Moät vaên phaïm G=(V,T,S,P) ñöôïc goïi laø tuyeán tính - phaûi neáu taát caû caùc luaät sinh coù daïng : X à xB, Xà x Trong ñoù : A,B Î V, x Î T* . + Moätvaên phaïm ñöôïc goïi laø tuyeán tính traùi neáu taát caû caùc luaät sinh coù daïng : Xà Bx, Xà x + Moät vaên phaïm goïi laø chính qui laø vaên phaïm maø hoaëc laø tuyeán tính traùi hoaëc tuyeán tính phaûi. Caùc luaät sinh laø traùi tim cuûa vaên phaïm, chuùng chæ ra laøm theá naøo vaên phaïm bieán ñoåi moät chuoãi thaønh moät chuoãi khaùc, vaø thoâng qua caùch naøy chuùng (caùc luaät sinh) ñònh nghóa moät ngoân ngöõ lieân keát vôùi vaên phaïm. Chuùng ta noùi raèng w daãn xuaát ra z kyù hieäu w=*>z hay z ñöôïc daãn xuaát ra töø w. Caùc chuoãi laàn löôït ñöôïc daãn xuaát baèng caùch aùp duïng caùc luaät sinh cuûa vaên phaïm trong moät thöù töï tuøy yù neáu : w1=>w2=>...=>wn chuùng ta noùi w1 daãn xuaát ra wn vaø vieát w1=*> w2. Daáu * chæ ra raèng moät soá böôùc baát kyø naøo ñoù (keå caû khoâng) coù theå ñöôïc aùp duïng ñeå daãn xuaát ra wn töø w1 Ñeå chæ ra ít nhaát moät luaät sinh aùp duïng chuùng ta phaûi vieát : w1=+>wn 4.2- Ngoân Ngöõ Chính Qui Moät ngoân ngöõ goïi laø chính qui neáu toàn taïi moät automat höõu haïn chaáp nhaän noù. Vì vaäy moãi ngoân ngöõ chính qui coù theå ñöôïc moâ taû baèng moät dfa hay moät nfa naøo ñoù, nhö vaäy ñeå trình baøy moät ngoân ngöõ chính qui coù theå moâ taû noù nhö laø moät dfa hay nfa. Ngoân ngöõ L laø chính qui neáu vaø chæ neáu toàn taïi moät vaên phaïm chính qui G sao cho L=L(G). 4.3- Bieåu Thöùc Chính Qui Moät caùch ñeå bieåu dieãn ngoân ngöõ chính qui laø thoâng qua khaùi nieän bieåu thöùc chính qui. Khaùi nieäm veà bieåu thöùc chính qui bao goàm söï keát hôïp caùc chuoãi kí hieäu cuûa moät baûng chöõ caùc å naøo ñoù, caùc daáu ngoaëc ( ) vaø caùc pheùp toaùn + , . vaø *. Ví duï r=(a|b)*a Ñònh nghóa Cho å laø moät baûng chöõ caùi. Thì: + Æ,l vaø aÎå taát caû ñeàu laø nhöõng bieåu thöùc chính qui. Nhöõng caùi naøy ñöôïc goïi laø nhöõng bieåu thöùc chính qui nguyeân thuûy. + Neáu r1 vaø r2 laø nhöõng bieåu thöùc chính qui, thì r1+r2, r1.r2, vaø(r1) cuõng vaäy. + Moäät chuoãi laø moät bieåu thöùc chính quy neáu vaø chæ neáu noù coù theå ñöôïc daãn xuaát töø caùc bieåu thöùc chính qui nguyeân thuûy baèng moät soá laàn höõu haïn aùp duïng caùc qui taéc trong (2). Ngoân ngöõ L(r) ñöôïc bieåu thò bôõi bieåu thöùc chính qui baát kyø vaø ñöôïc ñònh nghóa bôûi caùc qui taéc sau: + Æ laø moät bieåu thöùc chính qui bieåu thò taäp troáng. + l laø moät bieåu thöùc chính qui bieåu thò taäp {l} + Ñoái vôùi moïi a Îå, a laø bieåu thöùc chính qui bieåu thò cho ngoân ngöõ {a}. Neáu r1 vaø r2 nhöõng bieåu thöùc chính qui thì : + L(r1+r2) = L(r1) ÈL(r2) + L(r1.r2) = L(r1).L(r2) + L((r1)) = L(r1) + L(r1*) = (L(r1))* 5. NGOÂN NGÖÕ PHI NGÖÕ CAÛNH Trong thöïc teá haøng ngaøy khoâng phaûi taát caû caùc ngoân ngöõ ñieàu laø chính qui. Trong khi ngoân ngöõ chính qui hieäu quaû trong vieäc moâ taû moät vaøi maãu ñôn giaûn do ñoù ngöôøi ta khoâng caàn chuù yù quaù nhieàu ñeán caùc ngoân ngöõ chính qui vì coù nhieàu söï haïn cheá cuûa noù ñoái vôùi ngoân ngöõ laäp trình. Ví duï: Neáu trong L={anbn : n³0}, chuùng ta thay theá daáu ngoaëc traùi cho a vaø daáu ngoaëc phaûi cho b thì chuoãi caùc daáu ngoaëc chaúng haïn nhö (( )) vaø ((( ))) laø thuoäc L nhöng (( ) thì khoâng maø trong moät ngoân ngöõ laäp trình thì thöôøng xuyeân gaëp nhöõng caáu truùc loàng nhau nhö vaäy. Do ñoù ta thaáy moät vaøi thuoäc tính cuûa ngoân ngöõ laäp trình yeâu caàu moät caùi gì ñoù beân ngoaøi ngoân ngöõ chính qui, ñeå bao truøm nhöõng vaán ñeà naøy ta phaûi môû roäng ngoân ngöõ daãn ñeán vieäc nguyeân cöùu ngoân ngöõ vaø vaên phaïm phi ngöõ caûnh. 5.1- Vaên Phaïm Phi Ngöõ Caûnh Caùc luaät sinh trong vaên phaïm chính qui thì bò giôùi haïn theo 2 caùch : Veá phaûi laø moät bieán ñôn, trong khi ñoù veá phaûi coù moät daïng ñaëc bieät. Ñeå taïo ra vaên phaïm maïnh hôn, chuùng ta phaûi nôùi loûng moät vaøi giôùi haïn nhö vaäy, baèng caùch duy trì giôùi haïn treân veá traùi nhöng cho pheùp baát kyø caùi gì treân veá phaûi khi ñoù chuùng ta nhaän ñöôïc moät vaên phaïm phi ngöõ caûnh. Ñònh Nghóa Moät vaên phaïm G =(V,T,S,P) ñöôïc goïi laø phi ngöõ caûnh neáu moïi luaät sinh trong P coù daïng : A-->x trong ñoù AÎV coøn xÎ (VÈT)*. Moät ngoân ngöõ ñöôïc goïi laø phi ngöõ caûnh neáu vaø chæ neáu coù moät vaên phaïm phi ngöõ caûnh G sao cho L= L(G). 5.2- Daãn Xuaát Traùi Nhaát Vaø Phaûi Nhaát Trong vaên phaïm phi ngöõ caûnh maø khoâng tuyeán tính, moät daãn xuaát coù theå bao goàm nhieàu daïng caâu vôùi nhieàu hôn moät bieán, trong tröôøng hôïp nhö vaäy chuùng coù coù moät söï choïn löïa veà thöù töï bieán naøo ñöôïc thay theá. Moät daãn xuaát ñöôïc goïi laø traùi nhaát neáu trong moãi böôùc bieán beân traùi nhaát ñöôïc thay theá. neáu trong moãi böôùc bieán beân phaûi nhaát ñöôïc thay theá thì goïi daãn xuaát traùi nhaát. 5.3 - Caây Daãn Xuaát Moät caùch thöù hai ñeå trình baøy caùc daãn xuaát, ñoäc laäp vôùi thöù töï trong ñoù caùc luaät sinh ñöôïc aùp duïng laø baèng caây daãn xuaát. Moät caây daãn xuaát laø moät caây coù thöù töï trong ñoù caùc noát ñöôïc gaùn nhaõn vôùi veá traùi cuûa luaät sinh coøn caùc con cuûa caùc noát bieåu dieãn baèng veá phaûi töông öùng cuûa noù Ví duï : A--> abABc thì caây daãn xuaát laø : A B A c b a Ñònh Nghóa Cho G=(V,T,S,P) laø moät vaên phaïm phi ngöõ caûnh. Moät caây coù thöù töï laø moät caây daãn xuaát cho G neáu vaø chæ neáu coù caùc tính chaát sau: + Goác ñöôïc gaùn nhaõn laø S + Moãi laù coù moät nhaõn laáy töø taäp (TÈ{l}) + Moãi noát beân trong khoâng phaûi laø laù coù moät nhaõn laáy töø V. + Neáu noãi noát coù nhaõn AÎV, vaø caùc con cuûa noù ñöôïc gaùn nhaõn (töø traùi sang phaûi) a1, a2.... an thì P phaûi chöùa moät luaät sinh coù daïng A--> a1, a2.... an + Moät laù ñöôïc gaùn nhaõn l khoâng coù anh chò e, töùc laø moät noát vôùi moät con ñöôïc gaùn nhaõn l coù theå khoâng coù con naøo khaùc. Ngoaøi ra coøn coù moät soá khaùi nieäm khaùc chöa ñöôïc neâu ra ôû ñaây, caùc baïn coù theå tìm hieåu theâm trong “An Introduction To Formal Languages And Automata” cuûa Peter Linz CHUÔNG 2 MOÄT SOÁ GIAÛI THUAÄT BIEÁN ÑOÅI VAÊN PHAÏM PNC VAØ CAÙC DAÏNG CHUAÅN Trong phaàn naøy, chuùng ta ñi saâu vaøo vieäc tìm hieåu moät soá giaûi thuaät bieán ñoåi vaên phaïm phi ngöõ caûnh nhö : + Loaïi boû caùc luaät sinh roãng + Loaïi boû caùc luaät sinh voâ duïng + Loaïi boû caùc luaät sinh ñôn vò + Chuyeån vaên phaïm baát kyø veà daïng chuaån Chomsky + Chuyeån vaên phaïm baát kyø veà daïng chuaån Greibach Vieäc loaïi boû caùc luaät sinh treân raát quang troïng laøm tieàn ñeà ñeå coù theå bieán ñoåi taäp vaên phaïm cuûa ngoân ngöõ phi ngöõ caûnh veà caùc daïng chuaån quan troïng nhö daïng chuaån Chomsky, daïng chuaån Greibach. Töø ñoù giuùp cho vieäc thöïc hieän moät giaûi thuaät phaân tích cuù phaùp nhö CYK. I- CAÙC GIAÛI THUAÄT BIEÁN ÑOÅI VAÊN PHAÏM 1) LOAÏI BOÛ CAÙC LUAÄT SINH ROÃNG (l) Baát kyø luaät sinh naøo cuûa vaên phaïm phi ngöõ caûnh coù daïng A --> l ñöôïc goïi laø luaät sinh l, vaø baát kyø bieán A naøo maø ñoái vôùi noù daãn xuaát A--*> l laø coù theå thì A goïi laø khaû troáng. Nhaäp : - Moät vaên phaïm phi ngöõ caûnh G =(V,T,S,P) vôùi : + V : Caùc kí hieäu khoâng keát thuùc. + T : Caùc kí hieäu keát thuùc. + S : Bieán khôûi ñaàu + P : Taäp caùc luaät sinh Xuaát : - Moät vaên phaïm G^=( V,T,S,P^) vôùi taäp luaät sinh P^ khoâng coù taäp luaät sinh roãng. Giaûi Thuaät Böôùc 1: Duyeät qua taát caû caùc luaät sinh trong P, neáu coù luaät sinh naøo coù daïng A->l thì cho A vaøo taäp Vn Böôùc 2 : Laëp laïi böôùc sau cho ñeán khi naøo khoâng theâm ñöôïc bieán vaøo Vn ñöôïc nöõa : + Neáu trong P coù toàn taïi : B---> A1 A2 A3... An vôùi A1 A2 A3... An Î Vn thì cho B vaøo Vn Böôùc 3: Sau khi ñaõ coù taäp Vn, xeùt moïi luaät sinh trong P coù daïng : A---> x1 x2... xm vôùi m³1 vaø xi Î (VÈ T) Ñoái vôùi moãi luaät sinh nhö vaäy cuûa P, ñaët vaøo P^ luaät sinh ñoù cuõng nhö nhöõng luaät sinh baèng caùch thay theá caùc bieán khaû troáng (Î Vn) baèng l trong moïi toå hôïp coù theå coù, ngoaïi tröø taát caû xi (i=1,2...) laø khaû troáng thì khoâng ñaët luaät sinh A->l vaøo trong P^ Ví duï: Cho vaên phaïm G =({S,A,B,C,D},{a, b,d,l},{S},P) vaø caùc luaät sinh trong P nhö sau : S ---> ABaC A ---> BC B ---> b | l C ---> D | l D ---> d AÙp duïng giaûi thuaät treân ta coù : - Ñaàu tieân Vn={} Böôùc 1: Caùc luaät sinh tröïc tieáp sinh B--->l, C--->l do ñoù Vn={B,C} Böôùc 2: Caùc luaät sinh giaùn tieáp daãn xuaát ra roãng laø A--->BC do ñoù theâm A vaøo taäp Vn => Vn={B,C,A} Böôùc 3 : Xaây döïng caùc toå hôïp cho moãi luaät sinh baèng caùch thay theá l cho nhöõng bieán ôû veá phaûi thuoäc Vn, ta ñöôïc luaät P^: S ---> ABaC | BaC | AaC | ABa | aC | Ba | Aa | a B ---> b C ---> D A ---> BC | C | B 2) LOAÏI BOÛ CAÙC LUAÄT SINH ÑÔN VÒ Baát kyø luaät sinh cuûa vaên phaïm phi ngöõ caûnh coù daïng A ---> B trong ñoù A,B thuoäc V thì ñöôïc goïi laø luaät sinh ñôn vò. Nhaäp : - Moät vaên phaïm phi ngöõ caûnh G =(V,T,S,P) vôùi : + V : Caùc kí hieäu khoâng keát thuùc. + T : Caùc kí hieäu keát thuùc. + S : Bieán khôûi ñaàu + P : Taäp caùc luaät sinh Xuaát : - Moät vaên phaïm G^=( V,T,S,P^) vôùi taäp luaät sinh P^ khoâng coù taäp luaät sinh ñôn vò. Giaûi Thuaät Böôùc 1 : Ñaët vaøo P^ caùc luaät sinh khoâng ñôn vò cuûa P Böôùc 2 : Ñoái vôùi moãi luaät sinh trong P coù daïng A---> B (A ¹ B), thì ñoái vôùi moãi bieán A tìm taát caû caùc bieán B sao cho A--*> B Ñieàu naøy coù theå thöïc hieän ñöôïc baèng caùch veõ ñoà thò phuï thuoäc cho G. Böôùc 3 : Xeùt taát caû caùc bieán A vaø B thoûa maõn ôû böôùc 2 , chuùng ta seõ theâm vaøo P^ caùc luaät sinh sau : A ---> y1 | y2 | y3| ...|yn Trong ñoù B ---> y1 | y2 | y3| ...|yn laø caùc luaät sinh khoâng ñôn vò cuûa B. Hay noùi caùch khaùc ñaët caùc veá phaûi cuûa caùc luaät sinh khoâng ñôn vò cuûa B ôû trong P vaøo laøm caùc veá phaûi cuûa caùc luaät sinh cuûa A trong p^ Keát quaû G^ seõ töông ñöông vôùi G maø P^ khoâng chöùa caùc luaät sinh ñôn vò Ghi chuù : Neáu muoán trong P^ khoâng chöùa luaät sinh roãng l thì tröôùc tieân ta phaûi loaïi boû luaät sinh l tröôùc. Ví duï: Cho vaên phaïm G =({S,A,B},{a,b,c},{S},P) vaø caùc luaät sinh trong P nhö sau : S ---> Aa | B B ---> A | bb A ---> a | bc | B AÙp duïng giaûi thuaät treân ta coù : - Böôùc 1: Ñaët vaøo P^ caùc luaät sinh khoâng ñôn vò : S ---> Aa B ---> bb A ---> a | bc - Böôùc 2: Töø caùc taäp luaät sinh ñôn vò treân tìm ra ñöôïc caùc taäp luaät sinh daãn xuaát A--*>B nhö sau : S ---> B S ---> A A ---> B B ---> A + Ñoà thò phuï thuoäc: B A S - Böôùc 3 : Xeùt taát caû caùc luaät sinh thoõa maõn böôùc 2 ta theâm vaøo caùc luaät sinh sau vaøo P^ S ---> B S ---> bb S ---> A S ---> a | bc A ---> B A ---> bb B ---> A S ---> a | bc Vaäy trong P^ : S ---> Aa | bb | a | bc B ---> bb | a | bc A ---> a | bc | bb Khoâng coù luaät sinh ñôn vò naøo 3) LOAÏI BOÛ CAÙC LUAÄT SINH VOÂ DUÏNG Moät mong muoán coá ñònh laø loaïi boû ra khoûi vaên phaïm nhöõng luaät sinh maø khoâng bao giôø ñoùng goùp gì trong baát kyø daãn xuaát naøo. Chaúng haïn trong vaên phaïm sau toaøn boä taäp luaät sinh cuûa noù laø : S ---> aSb | l | A A ---> aA Luaät sinh S ---> A roõ raøng khoâng ñoùng moät vai troø naøo, vì A khoâng theå ñöôïc bieán ñoåi thaønh caùc kyù hieäu keát thuùc. Trong khi A coù theå xuaát hieän trong moät chuoãi ñöôïc daãn xuaát töø S, caùi naøy coù theå khoâng bao giôø daãn ñeán caâu. Vieäc loaïi boû luaät sinh naøy khoâng laøm aûnh höôûng ñeán ngoân ngöõ vaø laø moät söï ñôn giaûn hoùa theo baát kyø ñònh nghóa naøo. Nhaäp : - Moät vaên phaïm phi ngöõ caûnh G =(V,T,S,P) vôùi : + V : Caùc kí hieäu khoâng keát thuùc. + T : Caùc kí hieäu keát thuùc. + S : Bieán khôûi ñaàu + P : Taäp caùc luaät sinh Xuaát : - Moät vaên phaïm G^=(V^,T^,S,P^) vôùi taäp luaät sinh P^ khoâng coù taäp luaät sinh voâ duïng. Giaûi Thuaät Böôùc 1 : Loaïi boû luaät sinh voâ duïng loaïi 1: + Khôûi taïo V1={ } + Laëp laïi caùc böôùc sau cho ñeán khi khoâng coøn bieán naøo ñöôïc theâm vaøo V1. Ñoái vôùi moãi AÎ V maø coù luaät sinh A--> x1x2...xn vôùi xi Î T* È V1 thi theân A vaøo V1 + laáy P1 laø taát caû caùc luaät trong P maø coù caùc kí hieäu thuoäc (V È T)* Böôùc 2 : Ñeå loaïi boû caùc luaät sinh voâ duïng loaïi 2 ta döïa vaøo vaên phaïm G1 (coù taäp luaät sinh P1) vöøa coù ôû treân vaø veõ ñoà thò phuï thuoäc cho noù, sau ñoù tìm caùc bieán maø khoâng ñaït tôùi ñöôïc töø S. Loaïi boû caùc bieán naøy vaø caùc luaät sinh lieân quan ñeán noù ra khoûi G1 ta ñöôïc vaên phaïm keát quaû G^ II- CAÙC DAÏNG CHUAÅN 1) DAÏNG CHUAÅN CHOMSKY Moät VPPNC laø thuoäc daïng chuaån Chomsky neáu moïi luaät sinh coù daïng A-->BC hoaëc A-->a vôùi A,B,C Î V, coøn aÎ T Ñònh lyù : Baát kyø VPPNC naøo G=(V,T,S,P) vôùi l Ï L(G) ñieàu coù moät vaên phaïm töông ñöông G^=(V^,T,S,P^) trong daïng chuaån Chom sky Nhaäp : - Moät vaên phaïm phi ngöõ caûnh G =(V,T,S,P) vôùi : + V : Caùc kí hieäu khoâng keát thuùc. + T : Caùc kí hieäu keát thuùc. + S : Bieán khôûi ñaàu + P : Taäp caùc luaät sinh Xuaát : - Moät vaên phaïm G^=( V^,T^,S^,P^) vôùi taäp luaät sinh P^ thuoäc daïng chuaån Chomsky Giaûi Thuaät Böôùc 1: Loaïi boû caùc luaät sinh: - Roãng - Ñôn Vò - Voâ duïng Böôùc 2: Ñaët caùc luaät sinh A-->a vaøo trong P^ Böôùc 3: Ñoái vôùi caùc luaät sinh A-->x1x2...xn vôùi n ³ 2, xi Î (VÈT) thì thay caùc kí hieäu keát thuùc, chaúng haïn xk=a, baèng caùc bieán ñaïi dieän môùi Ba taïo thaønh caùc luaät sinh trung gia A--> C1C2...Cn. Böôùc 4: Öùng vôùi moãi bieán Ba ñaët vaøo trong P ^ caùc luaät sinh Ba-->a. Böôùc 5: Sau khi thöïc hieän xong böôùc 3, öùng vôùi moãi luaät sinh A--> C1C2...Cn. maø n=2 thì ñaët noù vaøo trong P^. Ngöôïc laïi öùng vôùi n ³ 2 ta giôùi thieäu caùc bieán môùi D1, D2,.... vaø ñöa vaøo P caùc luaät sinh sau: A --> C1D1 D2--> D1 D2 . . . . Dn-2---> Cn-1Cn Ví duï : Haõy bieán ñoåi vaên phaïm sau sang daïng chuaån Chomsky Sà a | Aba Aà aab Bà b | Ac - Theo böôùc 1, ta ñaët caùc luaät sinh sau vaøo trong P^ Sà a, Bà b - Theo böôùc 2, ta ñöa ra caùc bieán môùi vaø thay theá caùc luaät sinh coøn laïi trôû thaønh nhö sau: Sà ABBa Aà BaBaBb Bà Abc Baà a Bbà b Bc à c - Theo böôùc 3 & 4, ta ñaët vaøo P^ caùc luaät sinh sau: Bà Abc Baà a Bbà b Bcà c - Coøn ñoái vôùi caùc luaät sinh Sà ABBa Aà BaBaBb ta bieán ñoåi vaø ñöa vaøo P^ caùc luaät sinh töông öùng sau: Sà AD1 D1à Bba Aà BaD2 D2à BaBb - Toùm laïi ta ñöôïc vaên phaïm ôû daïng chuaån Chomsky töông ñöông nhö sau: Sà a | AD1 D1à Bba Aà BaD2 D2à BaBb Bà b | Abc Baà a Bbà b Bcà c 2) DAÏNG CHUAÅN GREIBACH Moät VPPNC laø thuoäc daïng chuaån Greibach neáu moïi luaät sinh coù daïng A-->ax trong ñoù xÎ V*, coøn aÎ T Ñònh lyù : Baát kyø VPPNC naøo G=(V,T,S,P) vôùi l Ï L(G) ñieàu coù moät vaên phaïm töông ñöông G^=(V^,T,S,P^) trong daïng chuaån Greibach. Nhaäp : - Moät vaên phaïm phi ngöõ caûnh G =(V,T,S,P) vôùi : + V : Caùc kí hieäu khoâng keát thuùc. + T : Caùc kí hieäu keát thuùc. + S : Bieán khôûi ñaàu + P : Taäp caùc luaät sinh Xuaát : + Moät vaên phaïm G^=( V^,T,S,P^) vôùi taäp luaät sinh P^ thuoäc daïng chuaån Greibach Giaûi Thuaät Böôùc 1: Loaïi boû caùc luaät sinh: - Roãng - Ñôn Vò - Voâ duïng Böôùc 2: Ñaùnh soá thöù töï caùc bieán chaúng haïn laø A1, A2... Böôùc 3:Vieát laïi vaên phaïm sao cho taát caû caùc luaät sinh coù moät trong caùc daïng sau: Ai ---> Ajxj vôùi j > i Zi ---> Ajxj vôùi j ³ i Ai ---> axi Trong ñoù aÎ T vaø xi Î (V È T)*, coøn Zi laø caùc bieán môùi khi söû duïng khi loaïi boû ñeä qui traùi. Böôùc 4: sau khi thöïc hieän böôùc 3 taát caû caùc luaät sinh cuûa An phaûi coù daïng An ---> axn Thay theá An vaøo trong caùc xuaát hieän cuûa noù ôû vò trí ñaàu tieân treân caùc veá phaûi cuûa luaät sinh An-1 baèng caùc veá phaûi cuûa noù. Deã daøng thaáy luaät sinh An-1 coù daïng An-1 ---> axn-1 töông töï laøm theo kieåu naøy thay theá An vaø An-1 vaøo caùc xuaát hieän cuûa chuùng ôû vò trí ñaàu tieân treân caùc veá phaûi cuûa luaät sinh An-2 baèng caùc veá phaûi töông öùng cuûa chuùng. Thöïc hieän laàn löôït cho ñeán A1 Böôùc 5: Thay theá A1A2 ...An trong caùc xuaát hieän cuûa noù ôû vò trí ñaàu tieân caùc veá phaûi cuûa caùc luaät sinh Zn (neáu coù) baèng caùc veá phaûi töông öùng cuûa chuùng. Böôùc 6: Thay theá caùc kyù hieäu keát thuùc, chaúng haïn a, naèm beân veá phaûi cuûa caùc luaät sinh maø khoâng ôû vò trí ñaàu tieân baèng caùc bieán ñaïi dieän, chaúng haïn Ba ñoàng thôøi theâm vaøo caùc luaät sinh môùi Ba ---> a. Ví duï: Bieán ñoåi vaên phaïm sau thaønh daïng chuaån Greibach Sà SBb |Ab Aà Sb | Ba Bà Sa | b - Ñaàu tieân, ta aùp duïng böôùc 1 ñaùnh soá thöù töï cho caùc bieán, chaúng haïn theo thöù töï laø S, A, B ta coù ñöôïc vaên phaïm sau : S0à S0B2b | A1b A1à S0b | B2a B2à S0a | b - Tieáp tuïc thöïc hieän böôùc 2, xeùt caùc luaät sinh cuûa S0 ta thaáy luaät sinh S0 à S0A1b chöa thoûa maõn böôùc 2. Loaïi boû ñeä qui traùi cho S0, ta coù : S0à S0B2b | A1b ó S0 à A1b | A1bZ1 (1) Z1à B2b | B2bZ1 (2) Ñeán ñaây caùc luaät sinh cuûa S0 ñaõ thoûa maõn böôùc 2 - Xeùt tieáp caùc luaät sinh cuûa A1, ta thaáy luaät sinh A1à S0b laø chöa thoûa maõn. Thöïc hieän thay theá S0 töø (1), ta coù : A1à S0b | B2a A1à A1bb | A1bZ1b | B2a - Ñeán ñaây xuaát hieän ñeä qui traùi cuûa A1, thöïc hieän vieäc loaïi boû ñeä qui traùi, ta coù : A1à A1bb | A1bZ1b | B2a A1à B2a | B2aZ2 (3) Z2 à bb | bZ1b | bbZ2 | bZ1bZ2 (4) Ñeán ñaây taát caû caùc luaät sinh cuûa A1 ñaõ thoûa maõn böôùc 2. - Xeùt tieáp caùc luaät sinh cuûa B2, ta thaáy luaät sinh B2 à S0a laø chöa thoûa maõn böôùc 2, thöïc hieän töông töï nhö treân, ta coù quaù trình thöïc hieän nhö sau : B2à S0a | b (thay theá S0 töø (1) ) ó B2 à A1ba | A1bZ1a | b (thay theá A1 töø (3) ) B2 à B2aba | B2aZ2ba | B2abZ1a | B2aZ2bZ1a | b (loaïi boû ñeä qui traùi) B2 à b | bZ3 (5) Z3 à aba | aZ2ba | abZ1a | aZ2bZ1a | abaZ3 | aZ2baZ3 | abZ1aZ3 | aZ2bZ1aZ3 (6) Ñeán ñaây caùc luaät sinh cuûa caùc bieán S0, A1, B2 ñieàu thoûa maõn böôùc 2, vaø caùc kyù hieäu ñi ñaàu caùc veá phaûi cuûa caùc luaät sinh B2 ñeàu laø kyù töï keát thuùc. Aùp duïng böôùc 3 thay ngöôïc trôû laïi B2 vaøo caùc luaät sinh cuûa A1 (neáu coù) vaø thay B2, A1 vaøo caùc luaät sinh cuûa S0 (neáu coù) ta coù : A1à B2a | B2aZ2 (thay theá B2 töø (5) ) ó A1 à ba | bZ3a | baZ2 | bZ3aZ2 (7) Töông töï : S0 à A1b | A1bZ1 (thay theá A1 töø (7) ) ó S0 à bab | bZ3ab | baZ2b | bZ3aZ2b | babZ1 | bZ3abZ1 | baZ2bZ1 | bZ3aZ2bZ1 (8) Ñeán ñaây caùc kyù hieäu ñi ñaàu cuûa caùc luaät sinh cuûa S0, A1, B2 ñeàu laø kyù töï keát thuùc, vì theá caùc luaät sinh naøy ñaõ gaàn coù daïng chuaån Greibach. - Aùp duïng böôùc 4, thay theá S0, A1, B2 vaøo caùc luaät sinh cuûa Zi ta coù : Z1 à B2b | B2bZ1 (thay theá B2 töø (5) ) ó Z1 à bb | bZ3b | bbZ1 | bZ3bZ1 (9) Ñeán ñaây ta coù vaên phaïm “gaàn” coù daïng Greibach töông töông vôùi vaên phaïm ban ñaàu nhö sau : S0 à bab | bZ3ab | baZ2b | bZ3aZ2b | babZ1 | bZ3abZ1 | baZ2bZ1 | bZ3aZ2bZ1 (8) Z1 à bb | bZ3b | bbZ1 | bZ3bZ1 (9) A1 à ba | bZ3a | baZ2 | bZ3aZ2 (7) Z2 à bb | bZ1b | bbZ2 | bZ1bZ2 (4) B2 à b | bZ3 (5) Z3 à aba | aZ2ba | abZ1a | aZ2bZ1a | abaZ3 | aZ2baZ3 | abZ1aZ3 | aZ2bZ1aZ3 (6) - Aùp duïng böôùc 5, bieán ñoåi vaên phaïm naøy thaønh vaên phaïm coù daïng chuaån Greibach töông ñöông nhö sau : S0 à bXY | bZ3XY | bXZ2Y | bZ3XZ2Y | bXYZ1 | bZ3XYZ1 | bXZ2YZ1 | bZ3XZ2YZ1 Z1 à bY | bZ3Y | bYZ1 | bZ3YZ1 A1 à bX | bZ3X | bXZ2 | bZ3XZ2 Z2 à bY | bZ1Y | bYZ2 | bZ1YZ2 B2 à b | bZ3 Z3 à aYX | aZ2YX | aYZ1X | aZ2YZ1X | aYXZ3 | aZ2YXZ3 | aYZ1aXZ3 | aZ2YZ1XZ3 X à a Y à b Ñeán ñaây ñeå ñôn giaûn ta coù theå loaïi boû caùc chæ soá cuûa caùc bieán S0, A1, B2 vaø saép xeáp laïi thöù töï cuûa caùc luaät sinh ta ñöôïc vaên phaïm keát quaû cuoái cuøng nhö sau : S à bXY | bZ3XY | bXZ2Y | bZ3XZ2Y | bXYZ1 | bZ3XYZ1 | bXZ2YZ1 | bZ3XZ2YZ1 A à bX | bZ3X | bXZ2 | bZ3XZ2 B2 à b | bZ3 Z1 à bY | bZ3Y | bYZ1 | bZ3YZ1 Z2 à bY | bZ1Y | bYZ2 | bZ1YZ2 Z3 à aYX | aZ2YX | aYZ1X | aZ2YZ1X | aYXZ3 | aZ2YXZ3 | aYZ1aXZ3 | aZ2YZ1XZ3 X à a Y à b CHÖÔNG 3 CAÙC GIAÛI THUAÄT VAØ COÂNG CUÏ PHAÂN TÍCH CUÙ PHAÙP THOÂNG DUÏNG I- GIÔÙI THIEÄU Hieän nay, ñaõ coù nhieàu coâng cuï vaø giaûi thuaät phaân tích cuù phaùp, caùc giaûi thuaät naøy coù theå theo phöông phaùp töø treân xuoáng hay töø döôùi leân vaø coù theå xöû lyù ñöôïc lôùp vaên phaïm phi ngöõ caûnh toång quaùt hay laø lôùp con cuûa noù (moät taäp vaên phaïm nhoû cuûa taäp vaên phaïm phi ngöõ caûnh toång quaùt). Vieäc tìm hieåu caùc giaûi thuaät vaø coâng cuï hieän coù giuùp chuùng ta coù moät caùi nhìn toång theå veà vieäc phaân tích cuù phaùp cuõng nhö coù ñieàu kieän ñeå so saùnh öu nhöôïc ñieån cuûa töøng giaûi thuaät, hôn nöõa noù giuùp tìm ra nhöõng caùch giaûi quyeát thích hôïp trong vaán ñeà phaân tích cuù phaùp. Sau ñaây chuùng ta seõ ñi vaøo tìm hieåu moät soá giaûi thuaät vaø coâng cuï phaân tích cuù phaùp thoâng duïng. II- CAÙC GIAÛI THUAÄT Trong phaàn naøy taäp trung tìm hieåu caùc giaûi thuaät phaân tích cuù phaùp sau : - Giaûi thuaät phaân tích cuù phaùp LL. - Giaûi thuaät phaân tích cuù phaùp LR. - Giaûi thuaät Chart Parsing. 1- Giaûi Thuaät Phaân Tích Cuù Phaùp LL Giaûi thuaät naøy laø tieâu bieåu cho phöông phaùp phaân tích cuù phaùp töø treân xuoáng, giaûi thuaät chæ aùp duïng cho moät taäp caùc vaên phaïm haïn cheá coù tính chaát ñaët bieät goïi laø LL. sau ñaây laø caáu truùc döõ lieäu chính vaø hoaït ñoäng cuûa giaûi thuaät : Caáu truùc döõ lieäu goàm : + Boä ñeäm nhaäp chöùa chuoãi nhaäp caàn phaân tích. + Parser : Ñieàu khieån caùc haønh vi cuûa boä phaân tích. + Stack : Chöùa caùc kyù hieäu vaên phaïm trong quaù trình phaân tích. + Baûng phaân tích LL Baûng phaân tích LL Parser Chuoãi nhaäp Xuaát keát quaû Stack Hình 1 : Hoaït ñoäng cuûa boä phaân tích cuù phaùp LL Nhaäp : - Vaên phaïm G - Chuoãi nhaäp w Xuaát : - Neáu G laø vaên phaïm LL vaø w thuoäc L(G) thì taïo ra daãn xuaát traùi cuûa w, ngöôïc laïi seõ baùo loãi. Giaûi Thuaät : Goïi S laø kyù hieäu muïc tieâu cuûa G, $ laø kyù hieäu keát thuùc chuoãi nhaäp vaø ñaùnh daáu stack roãng. Ñaàu tieân xaây döïng baûng phaân tích M cho vaên phaïm G, noù coù daïng laø moät ma traän M. Trò cuûa phaàn töû M[A,a] coù theå laø moät luaät sinh maø A laø veá traùi, hoaëc trò cuûa phaàn töû naøy laø error. Trong ñoù A laø kyù hieäu khoâng keát thuùc, a laø kyù hieäu keát thuùc hay kyù hieäu ñaùnh daáu keát thuùc chuoãi nhaäp $. Khi boä phaân tích baét ñaàu hoaït ñoäng, stack chæ chöùa kyù hieäu ñaùnh daáu stack roãng $ ôû ñaùy stack vaø kyù hieäu muïc tieâu S treân ñænh. Goïi X laø kyù hieäu treân ñænh stack, a laø kyù hieäu trong chuoãi nhaäp ñöôïc ñoïc hieän taïi thi haønh vi cuûa boä phaân tích hoaït ñoäng nhö sau: Neáu X=a=$, nghóa laø stack roãng vaø chuoãi nhaäp ñöôïc duyeät heát, thì giaûi thuaät keát thuùc vaø parser thoâng baùo quaù trình phaân tích chuoãi nhaäp thaønh coâng. Neáu X=a vaø a khaùc $ thì boä phaân tích seõ ñaåy X ra khoûi stack, dòch ñaàu ñoïc ñeán kyù hieäu nhaäp keá tieáp. Neáu X laø moät kyù hieäu khoâng keát thuùc, thì boä phaân tích seõ xeùt phaàn töû M[X,a] trong baûng phaân tích M. Trò cuûa phaàn töû naøy coù theå laø moät luaät sinh maø X laø veá traùi hoaëc trò cuûa phaàn töû naøy error. neáu M[X,a] = luaät sinh X-->a thì giaûi thuaät seõ ñaåy X ra khoûi stack vaø theâm a vaøo stack sao cho kyù hieäu ñaàu tieân cuûa a naèm treân ñænh stack. Luaät sinh X --> a ñöôïc xuaát ra nhö moät phaàn cuûa caây daãn xuaát maø boä phaân tích tìm thaáy. Tröôøng hôïp M[X,a] laø error thì boä phaân tích seõ goïi moät thuû tuïc xöû lyù loãi thích hôïp. Khi ñoù chuoãi nhaäp khoâng phaûi laø caâu hôïp leä cuûa vaên phaïm. Ñoái vôùi vaên phaïm phi ngöõ caûnh baát kyø thì moät phaàn töû cuûa baûng phaân tích coù theå laø ña trò. Giaûi thuaät parsing LL chæ coù theå aùp duïng ñöôïc vôùi nhöõng vaên phaïm phi ngöõ caûnh naøo maø phaàn töû cuûa baûng phaân tích töông öùng laø ñôn trò. ñoù chính laø vaên phaïm LL ñaõ ñeà caäp ôû treân. Deã daøng moät vaên phaïm vi phaïm ñieàu kieän 1 vaø ñieàu kieän 2 thì khoâng phaûi laø vaên phaïm LL , do ñoù giaøi thuaät parsing LL khoâng theå aùp duïng cho loaïi vaên phaïm treân. Caùch thöùc xaây döïng baûng phaân tích M coù theå tham khaûo theâm trong (Compilers - trang 190) 2- Giaûi Thuaät Phaân Tích Cuù Phaùp LR Giaûi thuaät naøy laø tieâu bieåu cho hoï giaûi tthuaät phaân tích cuù phaùp töø döôùi leân. Giaûi thuaät aùp duïng ñöôïc treân caùc taäp vaên phaïm haïn cheá coù tính chaát ñaëc bieät goïi laø vaên phaïm LR. Sau ñaây laø caáu truùc döõ lieäu chính vaø hoaït ñoäng cuûa giaûi thuaät : Baûng Action - Goto Parser Chuoãi nhaäp Xuaát keát quaû Stack Hình 2 : Hoaït ñoäng cuûa boä phaân tích LR Boä ñeäm nhaäp chöùa chuoãi nhaäp caàn phaân tích vôùi $ laø kyù hieäu ñaùnh daáu keát thuùc chuoãi nhaäp. Parser : ñieàu khieån caùc haønh vi cuûa boä phaân tích. Stack chöùa caùc kyù hieäu vaên phaïm vaø caùc traïng thaùi xuaát hieän trong quaù trình phaân tích, noäi dung cuûa noù coù daïng : s0X1 s1X2 s2... Xmsm vôùi sm naèm treân ñænh stack. Xi ñöôïc goïi laø kyù hieäu vaên phaïm, si laø traïng thaùi. Baûng Action-Goto cuûa giaûi thuaät phaân tích cuù phaùp LR, noù coù daïng laø moät ma traän vôùi hai phaàn rieâng bieät action vaø goto. Phaàn töø action[sm,a] coù theå chöùa moät trong 4 giaù trò sau : + Shift s, vôùi s laø traïng thaùi. + Reduce a, vôùi a laø veá phaûi cuûa luaät sinh A --> a + Accept + Error Phaàn töû goto[sm,X] : coù giaù trò laø moät traïng thaùi si naøo ñoù, trong ñoù X laø kyù hieäu khoâng keát thuùc. Hoaït ñoäng cuûa Giaûi thuaät Nhaäp : Vaên phaïm G vaø chuoãi nhaäp w Xuaát : Neáu G laø vaên phaïm LR vaø chuoãi thuoäc L(G) thì taïo ra daãn xuaát cho w, ngöôïc laïi thì baùo loãi. Giaûi thuaät Ñaàu tieân xaây döïng baûng action - goto cuûa vaên phaïm. Khi giaûi thuaät baét ñaàu hoaït ñoäng, stack chæ chöùa traïng thaùi s0, boä ñeäm nhaäp chöùa chuoãi w $ (vôùi $ naèm ôû cuoái boä ñeäm). Goïi s laø traïng thaùi treân ñænh stack vaø a laø kyù hieäu nhaäp ñang xeùt. Hoaït ñoäng cuûa giaûi thuaät tuøy thuoäc vaøo giaù trò cuûa action[s,a] nhö sau : Neáu action[s,a] = shift si : Ñaåy a vaøo stack, sau ñoù laø si, chuyeån kyù hieäu keá tieáp trong chuoãi nhaäp thaønh kyù nhaäp seõ xeùt. Neáu action[s,a] = reduce A à a , ñaët | a | laø chieàu daøi cuûa a, ñaåy 2*|a | kyù hieäu ra khoûi stack, ñaåy A vaøo stack vaø sau ñoù ñaåy traïng thaùi cho bôõi goto[si,A] vaøo trong stack. Luaät sinh A à a ñöôïc xuaát ra nhö moät phaàn cuûa caây daãn xuaát. Neáu action[s,a] =accept : Keát thuùc giaûi thuaät vaø quaù trình phaân tích chuoãi nhaäp ñaõ thaønh coâng. Neáu action[s,a] = error : Boä phaân tích seõ goïi moät thuû tuïc xöû lyù loãi thích hôïp. khi ñoù chuoãi nhaäp khoâng phaûi laø caâu hôïp leä cuûa vaên phaïm. Ñoái vôùi moät vaên phaïm phi ngöõ caûnh toång quaùt thì moät phaàn töû cuûa baûng action coù theå laø ña trò . Giaûi thuaät phaân tích LR chæ coù theå aùp duïng ñöôïc vôùi nhöõng taäp vaên phaïm phi ngöõ caûnh naøo maø moät phaàn töû cuûa baûng action-goto laø ñôn trò. Ñoù laø vaên phaïm LR ñaõ ñeà caäp ôû treân. Caùch thöùc xaây döïng baûng action - goto xin xem theâm trong (Compilers - trang 221) Veà hieäu quaû cuûa giaûi thuaät phaân tích cuù phaùp LR : deã daøng thaáy ñoä phöùc taïp cuûa giaûi thuaät tuyeán tính theo kích thöôùc chuoãi nhaäp. Thoâng thöôøng khoù xaùc ñònh giaûi thuaät phaân tích cuù phaùp LL hay LR aùp duïng ñöôïc vôùi lôùp vaên phaïm lôùn hôn, nhöng theo (Compilers-V. Aho) thì lôùp vaên phaïm coù theå phaân tích baèng giaûi thuaät LR chöùa lôùp vaên phaïm coù theå phaân tích baèng giaûi thuaät LL. Ta cuõng nhaän xeùt taïi moät thôøi ñieåm trong quaù trình phaân tích thì giaûi thuaät phaân tích cuù phaùp LL chæ laøm vieäc vôùi moät luaät sinh maø thoâi, coøn giaûi thuaät phaân tích cuù phaùp LR coù theå laøm vieäc vôùi nhieàu luaät sinh cuøng moät luùc. Chính vì vaäy maø giaûi thuaät LR coù khaû naêng phaân tích taäp vaên phaïm phöùc taïp hôn giaûi thuaät LL. 3- Giaûi Thuaät Chart Pasing Char pasing laø moät giaûi thuaät phaân tích cuù phaùp treân taäp vaên phaïm phi ngöõ caûnh toång quaùt. Noù coù tính chaát raát ñaëc bieät : trung hoøa giöõa phöông phaùp phaân tích töø treân xuoáng vaø phöông phaùp töø döôùi leân. Ñieàu ñoù coù nghóa laø noù vöøa coù khaû phaân tích cuù phaùp töø treân xuoáng vaø vöøa coù khaû naêng phaân tích cuù phaùp töø döôùi leân. sau ñaây laø moâ taû hoaït ñoäng cuûa giaûi thuaät: Goïi chieàu daøi cuûa chuoãi nhaäp laø n, ta xeùt vieäc xaây döïng caây daãn xuaát cho chuoãi nhaäp treân moät sô ñoà (chart) Vôùi chuoãi nhaäp coù chieàu daøi n thì sô ñoà coù n+1 ñænh (vertex). Caùc ñænh ñöôïc ñaùnh soá töø 0 ñeán n. Giöõa hai ñænh baát kyø coù theå coù nhieàu cung (edge), moãi cung ñöôïc bieåu dieãn baèng moät boä : (, , ) trong ñoù : + : Moät soá töï nhieân chæ ra ñænh baét ñaàu cuûa cung. + : Moät soá töï nhieân chæ ra ñænh keát thuùc cuûa cung. + : Ñoù laø moät luaät coù daáu chaám (dotted-rule). Luaät coù daáu chaám laø luaät sinh cuûa vaên phaïm coù theâm daáu chaám trong luaät taïi moät vò trí naøo ñoù. Ví duï : A--> XYZ ==> A-->.XYZ A-->X.YZ A-->XY.Z A-->XYZ. Ví duï : (1,1, S--> .AB) laø moät cung baét ñaàu töø ñænh 1, keát thuùc cuõng ñænh 1 vaø luaät sinh coù daáu chaám töông öùng laø S--> .AB 1 S --> .AB Hình veõ cung (1,1, S-->.AB) Ta goïi moät cung maø luaät sinh coù daáu chaám cuoái cuøng laø moät cung cheát (inactive-edge), ngöôïc laïi ta coù moät cung soáng (active-adge). Chart Parsing thöïc hieän tuaân theo caùc qui taéc sau : Quy taéc cô baûn (Fundamental rule) Neáu sô ñoà chöùa hai cung (i,j,A-->w1.Bw2) vaø (j, k, B--> w3.) trong ñoù A,B laø caùc kyù hieäu khoâng keát thuùc , w1, w2, w3 laø chuoãi caùc kyù hieäu keát thuùc vaø khoâng keát thuùc (cuõng coù theå laø roãng) thì ta theâm cung (i,k, A--> w1B.w2) vaøo trong sô ñoà. Khôûi taïo (Initialization) Khôûi taïo laø quaù trình taïo ra caùc cung maø luaät sinh coù daáu chaám daïng : A--> a. Trong ñoù A laø kyù hieäu khoâng keát thuùc coøn a laø kyù hieäu keát thuùc. Vôùi moïi i > 0 , i£ n thì khi khôõi taïo ta phaûi tìm moät cung coù =i-1, =i vaø luaät sinh coù daáu chaám laø A --> a. vôùi a laø kyù hieäu thöù i trong chuoãi nhaäp, ngöôïc laïi chaéc chaén chuoãi nhaäp khoâng phaûi laø moät caâu hôïp leä cuûa vaên phaïm ñang xeùt. Qui taéc töø döôùi leân cho chart parsing (bottom-up rule) Neáu theâm cung (i,j,C--> w1.) vaøo sô ñoà thì vôùi moãi luaät sinh B --> Cw2 ta phaûi theâm cung (i,i, B-->.Cw2) vaøo sô ñoà. Qui taéc töø treân xuoáng cho chart parsing (top-down rule) - Khi khôõi taïo : vôùi moãi luaät sinh S --> a theâm cung (0,0,S-->.a) vaøo sô ñoà, trong ñoù S laø kyù hieäu muïc tieâu cuûa vaên phaïm. - Neáu theâm cung (i,j, C--> w1.Bw2) vaøo sô ñoà thì vôùi moãi luaät sinh B --> w, phaûi theâm cung (j,j, B --> .w) vaøo sô ñoà. Ví duï: Minh hoïa cho qui taéc khôõi taïo cuûa giaûi thuaät chart parsing, chuùng ta xeùt vaên phaïm sau : S à NP VP VP à IV VP à IV PP VP à TV NP VP à TV NP VP VP à TN NP PP NP à Det N NP à Det N PP PP à P NP vôùi caùc töø vöïng sau : Töø Vöïng Töø Loaïi the Det her Det her NP they NP on P see TV report N report IV nurses NP nurses N Xeùt chuoãi nhaäp :” they see her report on the nurses”. Aùp duïng qui taéc khôõi taïo cho keát quaû laø sô ñoà sau : N à nurses. N à nurses. Det à the. P à on. N à report. IV à report. N à her. Det à her. TV à see. NP à they. COÂNG CUÏ PHAÂN TÍCH CUÙ PHAÙP YACC 1- Toång Quan Trong phaàn naøy chuùng ta seõ trình baøy moät boä sinh phaân tích cuù phaùp LARL ñöôïc goïi laø Yacc. Yacc sinh ra maõ ñích döôùi daïng ngoân ngöõ C töø ñoù xaây döïng baûng phaân tích LARL vaø phaân tích moät chuoãi nhaäp theo vaên phaïm LR(1). Yacc thöôøng ñöôïc söû duïng ñeå xaây döïng caùc boä phaân tích cuù phaùp cho caùc ngoân ngöõ laäp trình vaø hieän nay Yacc laø moät leänh cuûa heä ñieàu haønh UNIX. 2- Moâ Taû Boä Phaân Tích Cuù Phaùp Yacc a.out C Compiler Yacc Compiler Taäp tin ñaëc taû Yacc.translate.y y.tab.c Chuoãi Token Daãn xuaát a.out y.tab.c Döôùi ñaây laø sô ñoà moâ taû quaù trình xaây döïng boä phaân tích cuù phaùp töø file ñaëc taû Yacc : Taäp tin nhaäp cho Yacc laø translate.y laø söï ñaëc taû vaên phaïm trong ngoân ngöõ Yacc. Sau khi chuùng ta taïo ra taäp tin translate.y, chuùng ta seõ duøng Yacc compiler ñeå chuyeån file translate.y sang taäp tin y.tab.c (ñaây laø taäp tin vôùi maõ nguoàn laø ngoân ngöõ C). Ñaây chính laø boä phaân tích cuù phaùp cuøng vôùi moät soá haøm maø ngöôøi söû duïng ñònh nghóa trong taäp tin ñaëc taû. Sau khi coù taäp tin y.tab.c seõ ñöôïc bieân dòch ñeå taïo ra file thöïc thi a.out. 3- Caáu Truùc File Ñaëc Taû Yacc File ñaëc taû coù daïng toång quaùt nhö sau : Declarations %% Translation rules %% C-routine codes Phaàn khai baùo : Khai baùo caùc kyù hieäu ñeå söû duïng trong phaàn thöù 2 vaø thöù 3, coù hai daïng khai baùo + Khai baùo daïng C ñöôïc boïc giöõa hai kyù hieäu %{ vaø %}. Caùc khai baùo trong phaàn naøy ñöôïc ñöa nguyeân vaøo trong paser ñöôïc sinh ra. + Caùc khai baùo cuûa Yacc duøng ñeå khai baùo caùc token ñöôïc söû duïng trong file vaên phaïm hoaëc khai baùo ñoä öu tieân, keát hôïp traùi, phaûi cuûa caùc token. Phaàn caùc luaät sinh : Moãi luaät sinh trong Yacc laø moät luaät sinh keát hôïp vôùi caùc haønh ñoäng ngöõ nghóa. Caùc haønh ñoäng ngöõ nghóa phaûi ñeå ôû cuoái luaät, moãi luaät sinh cuûa Yacc coù daïng toång quaùt nhö sau : : {semantic action 1} | {semantic action 2} ……………………… | {semantic action n} Moãi haønh ñoäng ngöõ nghóa laø caùc phaùt bieåu C. Haønh ñoäng ngöõ nghóa cuûa luaät seõ ñöôïc thöïc thi khi taùc vuï reduce ñöôïc thöïc hieän treân luaät ñoù. Do Yacc xaây döïng boä phaân tích cuù phaùp theo vaên phaïm LR(1) neân caùc haønh ñoäng ngöõ nghóa phaûi ñeå cuoái luaät sinh. Phaàn C-routine codes : Phaàn naøy bao goàm caùc ñoaïn maõ chöông trình C maø chuùng ta coù theå khai baùo caùc ñoaïn chöông trình con ñeå xaây döïng boä xöû lyù loãi, boä phaân tích töø vöïng (Yac khoâng xaây döïng boä phaân tích töø vöïng) hay caùc ñoaïn chöông trình maø chuùng ta coù theå söû duïng trong caùc haønh ñoäng ngöõ nghóa. 4- Söû Duïng Yacc Vôùi Caùc Vaên Phaïm Khoâng Töôøng Minh Ñoái vôùi vaên phaïm khoâng töôøng minh thì boä phaân tích seõ taïo ra baûng phaân tích vôùi caùc oâ coù nhieàu giaù trò (multiple entry). Do ñoù trong quaù trình phaân tích seõ coù sö ñuïng ñoä. Yacc seõ baùo caùo caùc ñuïng ñoä naøy khi noù saûy ra. Ngoaøi ra, Yacc coøn coù khaû naêng giaûi quyeát moät soá ñuïng ñoä baèng caùch söû duïng hai qui taéc sau : + Ñuïng ñoä do moät phaàn töû trong baûng coù 2 giaù trò laø reduce (reduce /reduce) ñöôïc giaûi quyeát baèng caùch thöïc hieän taùc vuï reduce treân luaät sinh ñöôïc lieät keâ tröôùc trong file ñaëc taû vaên phaïm. + Ñuïng ñoä do moät phaàn töû trong baûng coù hai giaù trò, moät laø reduce vaø moät laø shift ñöôïc giaûi quyeát baèng caùch höïc thi taùc vuï shift. Quy taéc naøy xöû lyù toát trong tröôøng hôïp khoâng töôøng minh trong caáu truùc if -then -else / if then : if_stmt : IF expr THEN stmt | IF expr THEN stmt ELSE stmt Vì caùc qui taéc treân coù theå khoâng phaûi luoân luoân laø ñieàu maø ngöôøi söû duïng mong muoán, cho neân Yacc cung caáp moät cô cheá toång quaùt ñeå giaûi quyeát ñuïng ñoä shift/reduce baèng caùch cho pheùp ngöôøi söû duïng coù theå gaùn ñoä öu tieân vaø keát hôïp traùi/phaûi hoaëc khoâng coù keát hôïp trong phaàn khai baùo. Khaéc Vuï Loãi Trong Yacc Khaéc phuïc loãi trong Yacc coù theå ñöôïc thöïc hieän baèng caùch söû duïng caùc luaät sinh khaéc phuïc loãi. Tröôùc tieân, ngöôøi söû duïng phaûi choïn nhöõng kyù hieäu khoâng keát thuùc chính yeáu (major nonterminal) naøo seõ coù thuû tuïc khaéc phuïc loãi keøm theo. Sau ñoù ngöôøi söû duïng phaûi theâm vaøo vaên phaïm caùc luaät sinh khaéc phuïc loãi, caùc luaät sinh naøy coù daïng A à error a vôùi A laø kyù hieäu khoâng keát thuùc chính yeáu, error laø moät token ñöôïc hoã trôï saün trong Yacc vaø a laø chuoãi caùc kyù hieäu vaên phaïm. Yacc seõ sinh ra boä phaân tích cuù phaùp döôùi daïng ñaëc taû nhö vaäy vaø xöû lyù caùc luaät sinh treân nhö caùc luaät sinh thoâng thöôøng. CHÖÔNG 4 GIAÛI THUAÄT PHAÂN TÍCH CUÙ PHAÙP EARLEY VAØ CYK GIAÛI THUAÄT PHAÂN TÍCH CUÙ PHAÙP EARLEY 1.1 Giôùi Thieäu Vaên phaïm phi ngöõ caûnh ñöôïc söû duïng roäng raõi trong vieäc moâ taû cuù phaùp cuûa ngoân ngöõ laäp trình vaø ngoân ngöõ töï nhieân. Caùc giaûi thuaät phaân tích cuù phaùp cho caùc vaên phaïm phi ngöõ caûnh ñaõ vaø ñang ñoùng moät vai troø raát lôùn trong vieäc thöïc hieän caùc chöông trình dòch cho ngoân ngöõ laäp trình vaø caùc chöông trình xöû lyù ngoân ngöõ töï nhieân. Earley ñaõ ñöa ra moät giaøi thuaät phaân tích cuù phaùp cho vaên phaïm phi ngöõ caûnh. Ñaây laø moät giaûi thuaät thuoäc loaïi phaân tích cuù phaùp töø treân xuoáng vaø xaây döïng caùc daãn xuaát traùi nhaát cuûa chuoãi kyù hieäu nhaäp, giaûi thuaät naøy hieäu quaû hôn giaûi thuaät CYK vaø chuùng ta cuõng khoâng ñöa vaên phaïm veà moät daïng chuaån naøo nhö giaûi thuaät CYK. 1.2 Moâ Taû Sô Löôït Giaûi Thuaät Earley YÙ töôûng cô baûn cuûa giaûi thuaät nhö sau : Cho G=(N,å, P,S) laø moät vaên phaïm phi ngöõ caûnh. w=a1a2 … an laø moät chuoåi nhaäp treân å* Moät thöïc theå cuûa vaên phaïm G laø luaät sinh cuûa G coù daïng : [Aà X1X2 … Xk . Xk+1 … Xm , i] Daáu chaám naèm giöõa Xk vaø Xk+1 laø moät kyù hieäu khoâng coù trong N vaø å vaø i ñaïi dieän cho taäp thöïc theå chöùa luaät treân Vôùi moãi soá nguyeân j (0 £ j £ n), chuùng ta seõ xaây döïng moät danh saùch caùc taäp thöïc theå Ij maø moãi Ij chöùa caùc thöïc theå : [Aà a . b , i] laø ôû trong Ij (0 £ i £ j) neáu vaø chæ neáu toàn taïi g vaø d sao cho chuùng ta coù S =*> gAd vaø g =*> a1…ai vaø a =*> ai+1 … aj . YÙ nghóa cuûa thöïc theå treân laø : chuùng ta ñaõ nhìn thaáy chuoãi nhaäp daãn xuaát töø a ñeán vò trí j vaø ñang chôø chuoåi tieáp theo ñöôïc daãn xuaát töø b. Neáu Aà Î thì thöïc theå cuûa noù laø [Aà . ,i] Sau khi hình thaønh danh saùch I0, I1, … In cho chuoåi nhaäp w, chuùng ta keát luaän w laø moät chuoãi thuoäc ngoân ngöõ L(G) neáu vaø chæ neáu trong In coù chöùa ít nhaát moät thöïc theå coù daïng [Sà a . ,0] 1.3 Giaûi Thuaät Phaân Tích Cuù Phaùp Cuûa Earley Nhaäp :Vaên phaïm phi ngöõ caûnh G=(N,å,P,S) vaø chuoåi nhaäp w= a1a2 … an thuoäc å* Xuaát : Danh saùch caùc taäp thöïc theå : I0, I1, … In Giaûi Thuaät : Ñaàu tieân chuùng ta xaây döïng taäp I0 nhö sau : Neáu Sà a laø moät luaät sinh trong P thì ta cho [Sà.a , 0] vaøo trong I0, sau ñoù thöïc hieän böôùc (2) vaø (3) cho ñeán khi naøo khoâng theå theâm taäp thöïc theå môùi vaøo trong I0 ñöôïc nöõa. Neáu [Bà g . , 0] thuoäc I0 (chuù yù : g coù theå laø Î) thì cho vaøo I0 [Aà aB . b , 0] cho taát caû caùc thöïc theå coù daïng [Aà a . Bb , 0] coù trong I0 Neáu [Aà a . Bb ,0] laø moät thöïc theå trong I0 thì ta cho vaøo I0 taát caû caùc luaät sinh trong P coù daïng Bà g caùc thöïc theå [Bà .g ,0] Xaây giôø chuùng ta xaây döïng Ij sau khi ñaõ coù I0, I1,… Ij-1 Vôùi moãi thöïc theå trong Ij-1 coù daïng [Bà a . ab ,i] (vôùi a=aj) cho taäp thöïc theå [Bà a a . b ,i] vaøo trong Ij Thöïc hieän böôùc (5) vaø (6) sau cho ñeán khi khoâng coøn taäp thöïc theå môùi ñöôïc theâm vaøo : Neáu [Aà a . , i] laø moät thöïc theå trong Ij, kieåm tra xem trong taäp Ii caùc thöïc theå coù daïng [Bà a . Ab , k] vôùi moãi taäp thöïc theå tìm ñöôïc nhö vaäy ta cho vaøo Ij [Bà a A . b , k] (6) Neáu [Aà a . Bb, i] laø moät thöïc theå trong Ij, tìm trong P taát caû caùc luaät sinh coù daïng Bà g ta theâm [Bà .g , j] vaøo Ij Keát thuùc giaûi thuaät khi j=n Nhö vaäy : Töø yù töôûng cuûa giaûi thuaät treân ñeå deã nhôù vaø deã trình baøy veà sau ta coù theå ñaët teân cho töøng taùc vuï trong giaûi thuaätï nhö sau : (4) : Scan. (5) : Complete. (6) : Predict. Vaø coù theå moâ taû sô löôït giaûi thuaät nhö sau, sau khi ñaõ taïo ñöôïc taäp I0: Giaûi thuaät Earley chæ döïa vaøo caùc thöïc theå trong taäp traïng thaùi ñeå quyeát ñònh taùc vuï naøo trong ba taùc vuï noùi treân seõ thöïc hieän. Neáu traïng thaùi laø traïng thaùi khoâng keát thuùc vaø kyù hieäu sau daáu chaám laø kyù hieäu khoâng keát thuùc thì ta thöïc hieän taùc vuï predict treân traïng thaùi ñoù baèng caùch : + Tìm treân taäp vaên phaïm P caùc luaät sinh coù kyù hieäu veá traùi truøng vôùi kí hieäu naèm beân phaûi daáu chaám cuûa luaät coù daáu chaám ñang xeùt sau ñoù thöïc hieän : + Theâm vaøo caùc thöïc theå môùi vaøo cuoái traïng thaùi Ii, moãi traïng thaùi môùi goàm coù : - Luaät sinh maø ta môùi tìm ñöôïc vôùi daáu chaám naèm ôû vò trí baét ñaàu beân phaûi cuûa luaät sinh - Con troû (pointer) ñöôïc ñaët haøng i (traïng thaùi môùi naøy seõ khoâng ñöôïc theâm vaøo taäp traïng thaùi neáu noù ñaõ coù trong taäp traïng thaùi) Neáu traïng thaùi laø traïng thaùi khoâng keát thuùc, kyù hieäu naèm sau daáu chaám laø kyù hieäu keát thuùc truøng vôùi kyù hieäu nhaäp ñang xeùt thì ta thöïc hieän taùc vuï Scan; + Scan ñöa vaøo taäp traïng thaùi Ii+1 moät traïng thaùi gioáng vôùi traïng thaùi cuõ nhöng daáu chaám trong luaät töông öùng dòch qua phaûi moät kyù hieäu Neáu traïng thaùi laø traïng thaùi keát thuùc vaø chuoãi kyù hieäu nhìn tröôùc truøng vôùi k kyù hieäu nhaäp baét ñaàu töø vò trí i trong chuoãi nhaäp thì ta thöïc hieän taùc vuï Complete: + Complete laø tìm trong taäp traïng thaùi If (vôùi f laø pointer cuûa thöïc theå ñang xeùt ) caùc thöïc theå coù kyù hieäu naèm beân phaûi cuûa daáu chaám truøng vôùi kyù hieäu veá traùi cuûa thöïc theå coù daáu chaám ñang xeùt, theâm caùc thöïc theå môùi tìm ñöôïc vaøo cuoái traïng thaùi Ii vôùi daáu chaám dòch qua phaûi moät kyù hieäu. Ví duï : Cho moät vaên phaïm G vôùi caùc luaät sinh : Eà T+E Eà T Tà F*T Tà F Fà (E) Fà a Vôùi chuoãi nhaäp : w = (a+a)*a Ñaàu tieân chuùng ta xaây döïng taäp thöïc theå I0 : Cho vaøo I0 caùc thöïc theå [E à .T+E , 0] (01) [Eà .T, 0] (02) - Xeùt (01) aùp duïng luaät (3) cuûa giaûi thuaät ta cho vaøo I0 caùc thöïc theå: [Tà .F*T, 0] (03) [Tà .F , 0 ] (04) - Xeùt (02) aùp duïng luaät (3) cuûa giaûi thuaät ta cuõng coù ñöôïc hai thöïc theå (03) vaø (04) nhöng hai thöïc theå naøy ñaõ toàn taïi trong I0 roài neân ta khoâng theâm vaøo. - Xeùùt (03) aùp duïng luaät (3) cuûa giaûi thuaät ta theâm vaøo I0 caùc thöïc theå : [Fà . (E) , 0] (05) [Fà . a , 0] (06) - Xeùt (04) aùp duïng luaät (3) cuûa giaûi thuaät ta cuõng coù ñöôïc hai thöïc theå (05) vaø (06) nhöng hai thöïc theå naøy ñaõ toàn taïi trong I0 roài neân ta khoâng theâm vaøo. Vaø baây giôø khoâng coù thöïc theå naøo ñöôïc theâm vaøo I0 nöõa. I0 [E à .T+E , 0] (01) [Eà .T, 0] (02) [Tà .F*T, 0] (03) [Tà .F , 0 ] (04) [Fà . (E) , 0] (05) [Fà . a , 0] (06) Xaây döïng I1 töø I0 - Vì a1 = ( neân ta theo luaät (4) ta cho vaøo I1 thöïc theå [F à (. E ) , 0] (11) - Aùp duïng luaät (6) treân luaät (11) ta theâm vaøo I1 caùc thöïc theå sau : [Eà .T, 1] (12) [Tà .F*T, 1] (13) [Tà .F , 1] (14) [Fà . (E) , 1] (15) [Fà . a , 1] (16) - Baây giôø khoâng coøn thöïc theå naøo ñöôïc theâm vaøo nöõa Xaây döïng I2 : - Do a2 = a do ñoù theo luaät (4) ta theo vaøo I2 [F à a . , 1] (21) - Aùp duïng luaät (5) cho taäp thöïc theå (21) ta theâm vaøo taäp I2 caùc thöïc theå : [Tà F . *T , 1] (22) [Tà F . , 1] (23) - Aùp duïng luaät (5) cho taäp thöïc (23) vì trong I1 coù thöïc theå .T do ñoù ta theâm vaøo I2 caùc luaät : [Eà T . +E , 1] (24) [Eà T . , 1] (25) - Töông töï nhö treân ta theâm vaøo I2 luaät sinh [F à (E . ) , 0] (26) Baây giôø khoâng coøn taäp luaät sinh naøo ñöôïc theâm vaøo I2 nöõa. Töông töï ta tính caùc thöïc theå I3, I4, ... I7 ta ñöôïc keát quaû : I0 I1 I2 [F à a ., 1] [Tà F . *T, 1] [Tà F ., 1] [Eà T . + E , 1] [Eà T. , 1] [Fà (E .) , 0] [F à (. E ) , 0] [Eà .T, 1] [Tà .F*T, 1] [Tà .F , 1] [Fà . (E) , 1] [Fà . a , 1] [E à .T+E , 0] [Eà .T, 0] [Tà .F*T, 0] [Tà .F , 0 ] [Fà . (E) , 0] [Fà . a , 0] I3 I4 I5 [Fà ( E ). . 0] [Tà F . *T , 0] [Tà F . , 0] [Eà T. + E, 0] [Eà T. , 0] [Fà a . , 3] [Tà F . *T , 3] [Tà F . , 3] [Eà T. + E, 3] [Eà T. , 3] [Eà T+ E ., 1] Fà ( E . ), 0] [Eà T + .E , 1] [Eà .T+E , 3] [Eà.T , 3] [Tà. F *T , 3] [Tà. F , 3] Fà .( E ), 3] Fà.a ,3] [Fà a . , 6] [Tà F . *T , 6] [Tà F . , 6] [Tà F *T . , 0] [Eà T . + E, 0] [Eà T . , 0] I6 I7 [Tà F * .T, 0] [Tà . F * T , 6] [Tà. F , 6] [Fà . (E) , 6] [Fà . a , 6] 1.4 Xaây Döïng Chuoãi Daãn Xuaát Cho Chuoãi Nhaäp Sau khi xaây döïng ñöôïc caùc taäp thöïc theå I0, I1, ... In vaø coù theå xaùc ñònh chaéc chaén laø chuoãi nhaäp coù thuoäc ngoân ngöõ L(G) hay khoâng. Tuy nhieân, giaûi thuaät treân khoâng ñöa ra ñöôïc chuoãi daãn xuaát cho chuoãi nhaäp. Ñeå ñöa ra ñöôïc chuoãi daãn xuaát cho chuoãi nhaäp ta söû duïng giaûi thuaät sau: Nhaäp : -Moät vaên phaïm phi ngöõ caûnh G=(N,å, P,S) vôùi caùc luaät sinh ñöôïc ñaùnh soá töø 1- p - chuoãi nhaäp w = a1 a2 ... an - Danh saùch caùc taäp thöïc theå I0, I1, ... In cho w Xuaát : - Moät chuoãi daãn xuaát traùi nhaát hoaëc loãi. Giaûi Thuaät : - Neáu khoâng coù thöïc theå [Sà a . , 0] trong taäp I0 thì w khoâng thuoäc L(G) vaø baùo loãi. Nguôïc laïi cho p ={ } vaø thöïc hieän goïi chöông trình con R([Sà a . , 0], n), trong ñoù R([Aà b. , i],j ) ñöôïc ñònh nghóa nhö sau : R([Aà b. , i],j ) (1) Cho h vaøo taäp p (phiaù beân traùi) vôùi h laø soá thöù töï cuûa luaät sinh Aà b (thöôøng khai baùo p laø moät bieán toaøn cuïc). (2) If b = X1, X2,... Xm thì ñaët k=m vaø l=j. (3)(a) If Xk Î å Then k=k-1 vaø l=l-1 (b) If Xk Î N Then tìm moät thöïc theå [Xk ® g . , r] thuoäc Ij maø trong Ir coù thöïc theå [Aà X1X2 ... Xk-1 . Xk ... Xm , i] thì thöïc thi R([Xkà g. , r],l ). sau ñoù k=k-1 vaø ñaët l=r (4) Laäp laïi böôùc (3) cho ñeán khi naøo k=0 thì döøng Ví duï : - Laáy vaên phaïm ôû phaàn 1.3 vaø caùc taäp thöïc theå ôû treân, chuùng ta haõy ñöa ra caây daãn xuaát cho chuoåi nhaäp (a+a)*a söû duïng giaûi thuaät treân. Thöïc thi R([Eà T. , 0],7) => p={2 } (2 chính laø soá thöù töï luaät sinh Eà T) Ñaët k=1 vaø l=7 vaø thöïc hieän böôùc (3b) cuûa giaûi thuaät treân (do TÎ N ) vaø ta tìm ñöôïc [Tà F * T . , 0] treân I7 vaø [Eà . T] treân I0 vaø do ñoù ta thöïc thi R([Tà F *T ., 0], 7) keát quaû laø luaät sinh thöù 3 ñöôïc ñöa vaøo trong p => p={32}, sau khi goïi R treân ta coù k=3 vaø l=7. Vôùi k=3, ta tìm ra ñöôïc [Tà F.] treân I0 vaø [Tà F * .T] treân I6 vaø do ñoù ta goïi R([Tà F . ,6],7] vaø cho 4 vaøo taäp p ={432} vaø ñaët k=2 vaø l=6 Taïi böôùc (3a) ta gaëp * do ñoù giaûn k vaø l ñi 1. k=1 vaø l=5. Tìm thaáy [Fà(E).,0] treân I5 vaø [Tà . F *T, 0] treân I0 do ñoù goïi R([Fà (E) ., 0],5] vaø theâm 6 vaøo p, khi ñoù p ={6432} Tieáp tuïc vieäc phaân tích nhö treân ta tìm ñöôïc p ={64642156432} E a + ( T F a a F T E ) F E * T F T R([Eà T. , 0],7) R([Fà a . , 6],7) R([Fà a . ,1],2) R([Tà F . ,1],2) R([Fà a . ,3],4) R([Tà F . ,3],4) R([Eà T . ,3],4) R([Eà T+E . , 1],4) R([Fà (E) . , 0],5) R([Tà F. , 6],7) R([Tà F*T. , 0],7) - Söï lieân quan giöõa giaûi thuaät Earley vaø Chart Parsing Giaûi thuaät Chart Parsing laø moät daïng toång quaùt cuûa giaûi thuaät Earley, sau ñaây laø moät soá ñaëc ñieåm chæ roõ söï töông quan naøy : Moãi traïng thaùi trong giaûi thuaät Earley töông öùng vôùi moät cung trong Chart Parsing. Traïng thaùi keát thuùc töông öùng vôùi cung cheát vaø traïng thaùi khoâng keát thuùc töông öùng vôùi cung soáng. Moãi taäp traïng thaùi töông öùng vôùi moät nuùt trong Chart Parsing. Taùc vuï predict trong giaûi thuaät Earley töông öùng vôùi qui taéc töø treân xuoáng trong giaûi thuaät Chart Parsing. Taùc vuï Scan trong Earley töông öùng vôùi quaù trình khôõi taïo trong Chart Parsing. Taùc vuï Complete trong Earley töông öùng vôùi caùc qui taéc cô baûn trong Chart Parsing. 1.6 - Ñoä Phöùc Taïp Thôøi Gian Vaø Ñoä Phöùc Taïp Khoâng Gian 1.6.1- Ñoä Phöùc Taïp Thôøi Gian Theo Chieàu Daøi Chuoãi Nhaäp Boä phaân tích coù ñoä phöùc taïp n3 vì caùc lyù do sau : (a) Soá caùc traïng thaùi trong taäp traïng thaùi Ii tæ leä vôùi i (~ i) vì mieàn giaù trò cuûa caùc thaønh phaàn p, j cuûa moät traïng thaùi bò giôùi haïn, chæ coù thaønh phaàn f phuï thuoäc vaøo i maø i laïi phuï thuoäc vaøo n. Moãi taùc vuï Scan vaø Predict thöïc hieän moät soá böôùc höõu haïn treân moät traïng thaùi trong moät taäp traïng thaùi baát kyø. Do vaäy toång soá böôùc xöû lyù caùc traïng thaùi trong taäp traïng thaùi Ii coäng vôùi caùc taùc vuï Scan vaø Predict ~ i (c) Trong tröôøng hôïp xaáu nhaát, taùc vuï complete thöïc thi ~ i böôùc cho moãi traïng thaùi noù xöû lyù bôõi vì noù phaûi theâm ~ f traïng thaùi tôùi If, taäp traïng thaùi ñöôïc troû trôû laïi khi thöïc hieän taùc vuï complete. Do ñoù maát ~ i2 böôùc trong Ii (d) Tính toång I = 0,..., n+1 cuûa i2 ta ñöôïc ~ n3 Vaäy ñoä phöùc taïp cuûa giaûi thuaäy Earley theo chieàu daøi chuoãi nhaäp laø O(n3). Ñoä phöùc taïp naøy khoâng toát hôn giaûi thuaät CYK nhöng Earley vaãn toát hôn vì hai lyù do : + Giaûi thuaät Earley khoâng yeâu caàu nhaäp moät vaên phaïm ñaëc bieät maø laø moät vaên phaïm phi ngöõ caûnh toång quaùt, trong khi giaûi thuaät CYK laïi yeâu caàu giaûi thuaät phaûi ñöa veà daïng chuaån Chomsky. + Giaûi thuaät cuûa Earley thöïc söï chaïy toát hôn O(n3) trong haàu heát caùc lôùp vaên phaïm (giaûi thuaät CYK luoân coù ñoä phöùc taïp O(n3) Hôn nöõa giaûi thuaät CYK coù ñoä phöùc taïp thôøi gian O(n3) treân maùy Turing, vaø noù khoâng theå coù keát quaû toát hôn O(n3) khi chaïy treân maùy RAM (Random Access Machine). 1.6.2 Ñoä Phöùc Taïp Theo Kích Thöôùc Vaên Phaïm Soá kyù hieäu toái ña cuûa veá phaûi cuûa moät luaät sinh baát kyø laø m (coù nghóa laø chieàu daøi veá phaûi laø höõu haïn). Goïi n laø soá luaät sinh cuûa vaên phaïm, giaû söûû chieàu daøi chuoãi nhaäp laø höõu haïn. Nhö vaäy, soá traïng thaùi toái ña trong moät traïng thaùi laø m x n. Do m höõu haïn neân soá traïng thaùi trong moät taäp traïng thaùi phaûi ~ n. Khi thöïc hieän 3 taùc vuï predict, sacn vaø complete treân moät traïng thaùi baát kyø thì : Predict : seõ sinh ra toái ña n traïng thaùi, do ñoù soá traïng thaùi tæ leä vôùi n (~n) Scan : seõ sinh ra moät soá traïng thaùi höõu haïn. Complete : seõ sinh ra toái ña n traïng thaùi (~n). Vôùi moät traïng thaùi baát kyø thì soá traïng thaùi ñöôïc sinh ra khi thöïc hieän moät trong 3 taùc vuï laø ~n. Do ñoù treân moät taäp traïng thaùi thì soá traïng thaùi ñöôïc sinh ra khi thöïc hieän caû 3 taùc vuï laø ~n2. Do chieàu daøi chuoãi nhaäp laø höõu haïn neân khi phaân tích chuoãi nhaäp thì soá traïng sinh ra cuõng ~ n2. Vaäy : Ñoä phöùc taïp cuûa giaûi thuaät Earley theo kích thöôùc vaên phaïm laø O(n2) 1.6.3- Ñoä Phöùc Taïp Theo Khoâng Gian (Theo Chieàu Daøi Chuoãi Nhaäp) Soá taäp traïng thaùi toái ña trong giaûi thuaät Earley laø n, maø moãi taäp traïng thaùi laïi coù soá traïng thaùi tæ leä vôùi n (~n). Do ñoù trong tröôøng hôïp toång quaùt, ñoä phöùc taïp cuûa giaûi thuaät Earley laø O(n2). Giaûi thuaät CKY cuõng coù ñoä phöùc taïp khoâng gian laø O(n2), tuy nhieân öu ñieåm cuûa giaûi thuaät Earley so vôùi giaûi thuaät CYK laø : n2 laø caän treân trong giaûi thuaät Earley trong khi giaûi thuaät CYK laïi luoân luoân coù ñoä phöùc taïp laø O(n2). - Caùc Keát Quaû Thöïc Nghieäm (Theo Jay Earley -University California) Sau ñaây laø caùc ñaùnh giaù cuûa giaûi thuaät Earley vôùi caùc giaûi thuaät phaân tích cuù phaùp töø treân xuoáng (TD) vaø töø döôùi leân (BU) (Ñoái vôùi giaûi thuaät CYK xin xem phaàn 5- So saùnh ñoä phöùc taïp giöõa 2 giaûi thuaät Earley vaø CYK). Caùc so saùnh döôùi ñaây khoâng phaûi laø so saùnh veà thôøi gian chaïy thaät söï maø döôùi daïng caùc taùc vuï cô baûn (primitive operation). Vôùi TD vaø BU thì caùc taùc vuï cô baûn laø moät laàn aùp duïng luaät sinh Vôùi Earley moät taùc vuï cô baûn laø moät haønh ñoäng taïo ra moät traïng thaùi. Caùc taùc vuï cô baûn treân caùc giaûi thuaät naøy ñieàu khoâng phuï thuoäc vaøo kích thöôùc vaên phaïm vaø chieàu daøi chuoåi nhaäp. Caùc vaên phaïm ñeå ñaùnh giaù : G1 G2 G3 G4 SàAb Aà a | Ab Sà aB Bà aB | b Sà ab | aSb Sà AB Aà a | Ab Bà bc | bB | Bd Keát quaû ñaùnh giaù : Grammar Sentence TD STD BU SBU Earley G1 abn (n3+7n+2)/2 (n3+7n+2)/2 9n+5 9n+5 4n+7 G2 anb 3n+2 3n+2 11x2n+7 4n+4 4n+4 G3 anbn 5n-1 5n-1 11x2n-1+7 6n 6n+4 G4 abncd ~3n+1 ~2+1 ~2n+5 (n3+21n2+46n+15)/3 18n+8 Trong ñoù kyù hieäu vieát taéc laø caùc giaûi thuaät : + TD : Top Down + STD : Selective Top Down + BU : Bottom Up + SBU : Selective Bottom Up Nhaän xeùt : Do SBU coù ñoä phöùc taïp thôøi gian toát hôn TD, STD, BU neân ta chæ so saùnh Earley vôùi SBU. Caùc vaên phaïm G1,G2,G3 : caû hai coù ñoä phöùc taïp laø nhö nhau Nhöng ñoái vôùi vaên phaïm khoâng töôøng minh G4, roõ raøng laø SBU coù ñoä phöùc taïp thôøi gian laø O(n3) trong khi ñoä phöùc taïp cuûa giaûi thuaät Ealey laø O(n). Sau ñaây laø 3 vaên phaïm chæ duøng döõ lieäu thoâ (raw data), trong ñoù giaûi thuaät PA laø moät giaûi thuaät phaân tích cuù phaùp töø treân xuoáng ñoaùn nhaän tröôùc coù söõa ñoåi. PROPOSITIONAL CALCULUS GRAMMAR root : Fà C | S | P |U Cà UÉU Uà (F) | ~U | L Là L’ | p | q | r L’à p’ | q’ | r’ Sà U ÚS | UÚ U Pà UÙ S | UÙ U Sentence Length PA SBU Earley P 1 14 18 28 (p Ú q) 5 89 56 68 (p’Ùq) Ú r Ú p Ú q’ 13 232 185 148 pÉ((É~(r’Ú (pÙq))) É(q’Ú r) 26 712 277 277 ~(~p’Ù(pÚr) Ùp’) 17 1955 223 141 (pÙq)Ú(qÙr)Ú(rÙp’)É ((p’Úq’)Ù (r’Úp)) 38 2040 562 399 GRAMMAR GRE root : Xà A |Xb | Ya Xà e | YdY Sentence Length PA SBU Earley ededea 6 35 52 33 ededeab4 10 75 92 45 ededeab10 16 99 152 63 ededeab100 206 859 2052 633 (ed)4eabb 12 617 526 79 (ed)7eabb 18 24352 16336 194 (ed)8eabb 20 86139 54060 251 GRAMMAR NSE root :SàAB Aà a | SC Bà b | DB Cà c Dà d Sentence Length SBU Earley adbcddb 7 43 44 ad3bcdcd3bcd4b 18 111 108 adbcd2bcd5bcd3b 19 117 114 ad18b 20 120 123 a(bc)3d3 (bcd)2 dbcd4b 24 180 141 a(bcd)3 dbcd2b 16 100 95 Treân vaên phaïm GRAMMAR CALCULUS, giaûi thuaät PA coù ñoä phöùc taïp thôøi gian laø O(n2) trong khi SBU vaø Earley coù ñoä phöùc taïp thôøi gian tuyeán tính vaø giaûi thuaät Earley nhanh hôn SBU moät chuùt (do ñoä phöùc taïp thôøi gian cuûa giaûi thuaät SBU coù heä soá lôùn hôn). Vôùi vaên phaïm GRE, ñoä phöùc taïp cuûa caû 3 giaûi thuaät seõ laø O(n) neáu chuoãi nhaäp laø chuoãi caùc kyù hieäu ‘b’. Tuy nhieân, khi chuoãi nhaäp laø moät chuoãi caùc kyù hieäu “ed” thì giaûi thuaät PA vaø SBU seõ coù ñoä phöùc taïp taêng theo qui luaät haøm soá muõ, trong khi giaûi thuaät Earley coù ñoä phöùc taïp laø O(n2). Vôùi vaên phaïm NSE thì caû 3 giaûi thuaät ñeàu cho ñoä phöùc taïp thôøi gian laø O(n) vôùi heä soá nhö nhau. Vaäy : Qua caùc keát quaû thöïc nghieäm treân ta thaáy giaûi thuaät Earley coù ñoä phöùc taïp thôøi gian baèng hoaëc nhoû hôn. 1.8 Keát Luaän Giaûi thuaät Earley laø moät giaûi thuaät phaân tích cuù phaùp töø treân xuoáng cho vaên phaïm phi ngöõ caûnh toång quaùt. Noù khoâng ñoøi hoûi vaên phaïm ñöa ra khoâng caàn ôû daïng chuaån naøo do ñoù khi bieåu dieãn vaên phaïm neân bieåu dieãn noù ôû daïng töï nhieân, deã hieåu nhaát (ñaây laø moät ñieàu raát quang troïng ñeå vieát moät vaên phaïm ñuùng vaø deã kieåm tra). Do caùch bieåu vaên phaïm khaù thoaùng nhö treân neân giaûi thuaät Earley coù theå mang laïi nhöõng keát quaû to lôùn trong caùc öùng duïng cuõng nhö veà lyù thuyeát (ví duï : coù theå öùng duïng Earley trong vieäc nhaän daïng ngoân ngöõ töï nhieân, ...) Ñoä phöùc taïp thôøi gian theo kích thöôùc vaên phaïm cuûa giaûi thuaät laø O(n2), ñoä phöùc taïp thôøi gian theo chieàu daøi caâu nhaäp laø O(n3), trong moät soá lôùp vaên phaïm noù coù ñoä phöùc taïp theo chieàu daøi caâu nhaäp laø O(n2) hoaëc O(n). II- GIAÛI THUAÄT PHAÂN TÍCH CUÙ PHAÙP CYK 2.1- Giôùi Thieäu Ñaây laø moät giaûi thuaät phaân tích cuù phaùp treân vaên phaïm phi ngöõ caûnh toång quaùt. Giaûi thuaät mang teân cuûa 3 ngöôøi tìm ra noù, ñoù laø J. Cocke, D. H Younger vaø T. Kasami (theo Peter Linz 1990). Giaûi thuaät chæ laøm vieäc treân vaên phaïm phi ngöõ caûnh ôû daïng chuaån Chomsky vaø khi thöïc hieän vieäc phaân tích cuù phaùp seõ cho caây daãn xuaát traùi nhaát. YÙ töôûng chính cuûa giaûi thuaät nhö sau : Giaû söû coù moät vaên phaïm phi ngöõ caûnh ôû G=(N,å, P,S) daïng chuaån Chomsky vaø moät chuoãi nhaäp w= a1a2 … an Giaûi thuaät CYK seõ ñi xaây döïng moät baûng phaân tích cuù phaùp T (coù hình moät tam giaùc) , moãi phaàn töû tij 1£ i £ n vaø 1 £ j £ n-i+1 coù caùc giaù trò laø moät taäp con cuûa N. Moät kí hieäu khoâng keát thuùc A Î tij neáu vaø chæ neáu A =*> aiai+1 … ai+j-1. Chuoãi nhaäp w thuoäc ngoân ngöõ L(G) neáu SÎ t1n 2.2- Giaûi Thuaät Phaân Tích Cuù Phaùp CYK Nhaäp : Vaên phaïm phi ngöõ caûnh G=(N,å, P, S) ôû daïng chuaån Chomsky vaø chuoãi nhaäp w= a1a2 … an thuoäc å* Xuaát : Baûng phaân tích cuù phaùp T cho chuoãi w Giaûi thuaät : Tính ti1 = {A | Aà ai laø ôû trong P} Tính tij (phaûi ñaûm baûo laø tij’ phaûi ñöôïc tính tröôùc vôùi "i (1 £ i £ n), vaø "i (1 £ j’ < j). Khi ñoù taäp tij ñöôïc tính nhö sau : 1 £ k < j tij= È { A | Aà BC thuoäc P maø B Î tik vaø C Î ti+k, j-k} (do k vaø j-k ñeàu nhoû hôn j do ñoù tik vaø ti+k, j-k ñaõ ñöôïc tính tröôùc khi tính tij) (3) Laäp laïi böôùc (2) cho ñeán khi tính tij vôùi (1 £ i £ n), vaø (1 £ j £ n- i +1) Ví duï 1: Cho vaên phaïm : Sà AA | AS | b Aà SA | AS | a Chuoãi nhaäp : w = abaab Böôùc 1 : Tính t11 ={A} vì Aà a Î P vaø a1=a Tính t21 ={S} t31 ={A} t41 ={A} t51 ={S} Böôùc 2 : Tính t12 =t11 È t21 = {A,S} Tieáp tuïc tính cho caùc tij khaùc ta coù ñöôïc baûng keát quaû nhö sau : 5 A, S 4 A, S A, S 3 A, S A, S A, S 2 A,S A S A, S j­ 1 A S A A S i ® 1 2 3 4 5 Vì trong taäp T15 coù chöùa kyù hieäu khôõi ñaàu S neân chuoãi nhaäp thoäc vaên phaïm. 2.3- Xaây döïng daãn xuaát ra caâu nhaäp töø baûng T + Nhaäp : - Vaên phaïm ôû daïng chuaån Chomsky G=(N,å, P,S) vaø caùc luaät sinh trong P ñöôïc ñaùnh soá töø 1 -> p - Chuoãi nhaäp w=a1a2...an - Baûng phaân tích T theo giaûi thuaät treân + Xuaát : - Taäp (theo thöù töï) caùc luaät tham gia vaøo daãn xuaát traùi nhaát cho caâu nhaäp (neáu caâu nhaäp thuoäc vaên phaïm G) hoaëc caâu thoâng baùo “chuoãi khoâng thuoäc vaên phaïm”. Giaûi thuaät + Kieãm tra trong taäp T1n coù kyù hieäu khôûi ñaàu hay khoâng, neáu khoâng coù thoâng baùo “chuoãi nhaäp khoâng thuoäc vaên phaïm”, ngöôïc laïi : Chuùng ta thöïc hieän goïi ñeä qui lieân tuïc haøm gen(i,j,A) ñeå taïo ra taäp luaät sinh tham gia vaøo chuoãi daãn xuaát, haøm gen(i,j,A) döôïc ñònh nghóa nhö sau : (1) Neáu j=1 vaø A --> ai laø luaät sinh thöù m trong P thì xuaát ra luaät sinh thöù m. Neáu j>1 vaø k laø moät soá nguyeân trong khoaûng 1£ k BC laø luaät sinh thöù m trong P thì xuaát ra luaät sinh thöù m v2 khi ñoù thöïc thi gen(i,k,B) sau ñoù laø gen(i+k,j-k,C). + Ghi chuù : ÔÛ ñaây coù theå coù nhieàu söï löïa choïn B,C vì 1£ k < j, do ñoù neáu k naøo thoõa (2) thì ta taïo ra löu moät daãn xuaát khaùc cuûa caâu nhaäp. + Keát quaû moät caâu nhaäp coù theå coù moät hoaëc nhieàu daãn xuaát traùi nhaát Ví duï : Laáy vaên phaïm ôû ví duï 1 phaàn 2 vaø baûng phaân tích T nhö treân. w= abaab + Nhaän thaáy SÎ T15, do ñoù w thuoäc L(G) . + Goïi gen(1,5,S) => tìm döôïc A trong T11 vaø A trong T24 vaø luaät sinh S -->AA coù trong taäp luaät sinh P => xuaát ra 1 (1 laø soá thöù töï cuûa luaät sinh S -->AA trong P) vaø khi ñoù goïi gen(1,1,A) vaø gen (2,4,A). + gen(1,1,A) cho luaät sinh thöù 6. + Do SÎ T21 vaø A Î T33, A --> SA laø luaät sinh thöù 4 trong P => gen(2,4,A) xuaát ra luaät sinh thöù 4 vaø thöïc thi gen(2,1,S) vaø gen(3,3,A). + Tieáp tuïc thöïc thi theo giaûi thuaät ôû muïc 3 ta taäp caùc luaät sinh tham gia vaøo quaù trình daãn xuaát laø {1,6,4,3,5,6,2,6,3} Ñoä Phöùc Taïp Thôøi Gian Cuûa Giaûi Thuaät CYK Giaûi thuaät CYK ôû phaàn 2.2 coù ñoä phöùc taïp thôøi gian laø O(n3) khi thöïc hieän vieäc tính toaùn caùc phaàn töû tij cho baûng phaân tích T. Thaät vaäy, ñeå tính toaùn ti1 ta phaûi theâm vaøo taäp ti1 {A | Aà ai laø ôû trong P} quaù trình naøy thöïc hieän cho i=1 cho ñeán i=n cho neân toaøn boä soá böôùc tính toaùn cô baûn trong böôùc naøy ~O(n). -Keá ñeán ta phaûi thöïc hieän caùc böôùc sau ñeå tính tij : Ñaêt j=1. Kieåm tra j=n chöa, neáu chöa taêng j leân 1 vaø thöïc hieän line(j) (xem thuû tuïc ñònh nghóa phía sau). Laëp laïi böôùc (2) cho ñeán khi j=n. Ta nhaän thaáy thuû tuïc line(j) thöïc hieän maát 2n-2 böôùc tính toaùn, do ñoù toång caùc pheùp tính khi thöïc hieän voøng laëp (1) (2) (3) laø : laø O(n2) Vaäy : Toaøn boä soá böôùc tính toaùn cuûa giaûi thuaät CYK laø O(n) +=O(n3). Thuû tuïc line(j) ñöôïc ñònh nghóa nhö sau : Ñaët i=1 vaø j’=n-j+1 Ñaët k=1 Ñaët k’=i+k vaø j”=j-k Khaûo saùt tik vaø tk’j’’. Ñaët vaøo : tij =tij È { A à BC laø ôõ trong P sao cho BÎtik vaø C Î tk’j’’} Taêng k leân 1 Neáu k=j thì thöïc hieän böôùc (7), ngöôïc laïi thì thöïc hieän böôùc (3) Neáu i=j’ thì keát thuùc, ngöôïc laïi thöïc hieän böôùc (8) Taêng I leân 1 vaø thöïc hieän laïi böôùc (2). Vôùi thuû tuïc line(j) treân ta nhaän thaáy : Voøng laëp beân trong (3)-(6) thöïc thi j-1 laàn Voøng laëp beân ngoaøi (2)-(8) thöïc thi n-j+1 laàn Do j£ n neân ñoä phöùc taïp cuûa line(j) = O(n2). Vaäy : Ñoä phöùc taïp cuûa giaûi thuaät CYK laø O(n3) KEÁT LUAÄN Qua tìm hieåu hai giaûi thuaät Earley vaø CYK chuùng ta nhaän thaáy: - Caû hai giaûi thuaät ñieàu coù ñoä phöùc taïp thôøi gian theo chieàu daøi caâu nhaäp laø O(n3).Tuy nhieân, trong moät soá lôùp vaên phaïm Earley coù ñoä phöùc taïp theo chieàu daøi caâu nhaäp laø O(n2) hoaëc O(n). - Taäp vaên phaïm cuûa giaûi thuaät Earley khoâng ñoøi hoûi phaûi ôû moät daïng chuaån naøo, ñaây laø moät lôïi theá cuûa Earley vì haàu nhö moïi vaên phaïm ñònh nghóa trong thöïc theá ñieàu khoâng ôû daïng chuaån. - Trong khi ñoù taäp vaên phaïm cuûa giaûi thuaät CYK phaûi ñöa veà daïng chuaån Chomsky vaø ñoä phöùc taïp cuûa CYK theo chieàu daøi chuoãi nhaäp vôùi moïi taäp vaên phaïm luoân luoân laø O(n3). PHAÀN 3 TÌM HIEÅU VEÀ PHAÀN MEÀM HOÃ TRÔÏ HOÏC TAÄP VAØ GIAÛNG DAÏY 3.1- GIÔÙI THIEÄU Coâng ngheä thoâng tin ngaøy nay ñaõ trôû thaønh moät ngaønh khoa hoïc quan troïng vaø ñöôïc öùng duïng trong moïi lónh vöïc, moïi hoaït ñoäng trong ñôøi soáng xaõ hoäi. Ñeå tieáp caän ñöôïc nhanh choùng vôùi coâng ngheä thoâng tin hay caùc vaán ñeà khaùc nhö Toaùn, Lyù, Sinh vaät ... thì vieäc hoïc hoûi qua caùc phaàn meàn trôï giuùp hoïc taäp laø moät caùch tieáp caän vaán ñeà nhanh nhaát. Muoán thöïc hieän toát moät phaàn meàm hoã trôï vieäc hoïc vaø giaûng daïy, chuùng ta caàn tìm hieåu theâm nhöõng yeâu caàu veà phaàn meàm naøy vaø caùc daïng theå cuûa noù. 3.2- PHAÀN MEÀM GIAÛNG DAÏY (COURSEWARE) a) Phaàn Meàm Daïy Hoïc Phaàn meàn daïy hoïc laø moät moâi tröôøng giuùp ñôõ vieäc daïy vaø hoïc, bao goàm caùc caáu hình giaûng daïy vaø nhöõng heä thoáng quaûn lyù vieäc hoïc, möùc ñoä giaûng daïy ñöôïc xeáp seáp theo thöù töï töø deã ñeán khoù vaø coù theå cho pheùp ngöôøi söû duïng löïa choïn möùc ñoä phöùc taïp ñeå phuø hôïp vôùi trình ñoä ngöôøi hoïc. Ñeå thieát keá toát moät phaàn meàn hoã trôï vieäc giaûng daïy ngöôøi ta thöôøng döïa vaøo lyù thuyeát giaûng daïy. Lyù thuyeát giaûng daïy : nguyeân cöùu 3 vaán ñeà + Ñieàu kieän giaûng daïy : Moâ taû choã laøm vieäc, ñaëc ñieåm ngöôøi hoïc nhö : trình ñoä, nhöõng kieán thöùc caàn phaûi trang bò tröôùc. + Keát quaû giaûng daïy : Keát quaû thu ñöôïc qua quaù trình giaûng daïy ñöa ra möùc ñoä tieáp thu cuûa ngöôøi hoïc + Phöông phaùp giaûng daïy: Laø nhöõng phöông tieän duøng ñeå taùc ñoäng leân ñieàu kieän giaûng daïy ñeå taïo ra keát quaû mong muoán. Döïa vaøo lyù thuyeát giaûng daïy, ngöôøi ta ñöa ra caùc moâ hình giaûng daïy vaø nhöõng phöông phaùp giaûng daïy thích hôïp vôùi ñieàu kieän ñaõ cho nhaèm taïo ra keát quaû giaûng daïy mong muoán. Ñeå coù theå thieát keá vaø phaùt trieån moät phaàn meàm giaûng daïy toát, mang laïi nhöõng keát quaû khaû quan cho ngöôøi hoïc caàn phaûi coù söï tham gia vaø coá vaán cuûa caùc chuyeân gia lieân quan ñeán moân hoïc caàn thieát keá : + Chuyeân gia thieát keá am hieåu veà lónh vöïc phaàn meàm giaûng daïy + Chuyeân gia trong lónh vöïc giaûng daïy + Ñoäi nguõ laäp trình. Muoán thieát keá moät phaàn meàm giaûng daïy caàn phaûi traûi qua 3 böôùc sau: Phaân Tích : + Xaùc ñònh nhöõng ñieàu kieän giaûng daïy + Quyeát ñònh sô boä phöông phaùp giaûng daïy, vieäc ñöa ra moät phöông phaùp giaûng daïy toát phuø hôïp vôùi ñieàu kieän giaûng daïy seõ mang laïi keát quaû raát khaû quang cho ngöôøi hoïc. Phaùt Trieån Vaø Toång Hôïp + Hoaøn taát phöông phaùp giaûng daïy baèng caùch ñöa ra caùc taøi lieäu vaø trình töï giaûng daïy. Trong giai ñoaïn caàn phaûi thöïc hieän toát caùch thöùc trình baøy caùc taøi lieäu vaø thöù töï xeáp seáp caùc baøi giaûng moät caùch hôïp lyù. Ñaùnh Giaù Cuoái Cuøng + Xem xeùt laïi laïi phöông phaùp, ñieàu kieän , keát quaû coù phuø hôïp nhau khoâng vaø söõa ñoåi cho phuø hôïp b) Caùc Phaàn Meàm Giaûng Daïy Hieän Taïi Trôï Lyù Giaûng Daïy (Tutorial) + Noù coù ích lôïi sau khi ngöôøi hoïc ñaõ nghe qua baøi giaûng moät laàn + Thích hôïp vôùi nhöõng ngöôøi thích taäp trung vaøo moät soá phaàn quan troïng trong giaùo trình. + Noù coù theå giuùp cho ngöôøi hoïc coù theå töï hoïc maø khoâng caàn nghe baøi giaûng Thöïc Haønh Vaø Luyeän Taäp (Drill And Pratice Software) + Loaïi naøy ñöôïc duøng ôû nghöõng moân coù khoái löôïng baøi taäp vaø coâng vieäc luyeän taäp treân lôùp khaù nhieàu. + Ñaëc ñieån chính cuûa noù laø coù theå töï cho ñieåm vaø traû lôøi moät soá caâu hoûi cuûa ngöôøi hoïc. Moâ Phoûng (Simulation) + Loaïi naøy thích hôïp ñoái vôùi nhöõng moân doøi hoûi söï thöïc haønh. Vai troø cuûa ñoà hoïa vaø troø chôi ôû ñaây giuùp ích raát nhieàu. Boä ñoà ngheà (Learning Tool) : Ví duï giuùp ngöôøi söû duïng laøm quen vôùi caùc thieát bò cuûa maùy tính. -COMPOMENT DISPLAY THEORY - LYÙ THUYEÁT CUÛA SÖÏ TRÌNH BAØY Khi thieát keá caùc phöông phaùp giaûng daïy cho moät vaán ñeà naøo ñoù ngöôøi ta thöôøng aùp lyù thuyeát Compoment Display Theory(CDT) cho vieäc trình baøy caùc ñoái töôïng giaûng daïy döôùi daïng caùc luaät CDT. CDT giaû thieát raèng taát caû nhöõng daïng trình baøy giaûng daïy bao goàm moät chuoãi nhöõng daïng theå hieän cô baûn. Boán daïng theå hieän cô baûn laø : + Daïng moâ taû toång quaùt + Daïng moâ taû caùc bieät + Daïng kieåm tra toång quaùt + Daïng kieåm tra caù bieät Trong ñoù : Daïng toång quaùt laø : Ñònh nghóa, ñònh lyù, nguyeân lyù, hoaëc caùc böôùc cuûa moät thuû tuïc. Daïng caùc bieät laø söï minh hoïa roõ raøng moät ñoái töôïng, moät kyù hieäu moät söï kieän, moät quaù trình hoaëc moät thuû tuïc. Khi döï ñònh trình baøy moät vaán ñeà naøo ñoù neáu ngöôøi thieát keá trình baøy vaán ñeà döôùi nhöõng daïng theå hieän caàn thieát thì hieäu quaû hoïc taäp seõ ñöôïc naâng leân, ngöôïc laïi veäc trình baøy khoâng thích hôïp laøm cho hieäu quaû hoïc taäp seõ giaûm xuoáng. Ngoaøi nhöõng daïng theå cô baûn coøn coù nhöõng daïng theå hieän phuï. Ñoù laø nhöõng thoâng tin theâm vaøo nhöõng theå hieän chính ñeå taêng chaát löôïng cuûa vieäc hoïc taäp. Moät söï trình baøy daïng caùc vaán ñeà seõ trôû neân chaát löôïng vaø ñaày ñuû hôn neáu theâm vaøo caùc theå hieän phuï thích hôïp. 3.4- GIAÛNG DAÏY QUA MOÂ HÌNH Vieäc thieát keá caùc moâ hình phuïc vuï cho vieäc hoïc taäp thoâng qua maùy tính hieän nay ñöôïc theá giôùi aùp duïng roãng raõi, vôùi caùc öu ñieåm cuûa noù laø ngöôøi hoïc khoâng caàn hoïc qua moâ hình thaät (maéc tieàn vaø nguy hieåm) maø thoâng thoâng qua moâ hình hoùa treân maùy tính. Moät moâ hình giaûng daïy coù theå hieåu nhö laø moät ñôn vò nhoû nhaèm ñaùp öùng caùc yeâu caàu giaûng daïy cuûa moät chöông trình. Moâ hình giaûng daïy laø moät moâ hình ñöôïc xaây döïng nhaèm ñeå minh hoïa hoaëc giaûi thích roõ theâm moät vaán ñeà lyù thuyeát cuûa moân hoïc. Moät moâ hình giaûng daïy caàn coù nhöõng yeâu caàu sau: Döõ lieäu cuûa moâ hình : Ñaây chính laø kieán thöùc cuûa moân hoïc ñöôïc moâ hình hoùa thaønh döõ lieäu cuûa maùy tính. Döõ lieäu cuûa moâ hình coù theå chia thaønh 3 lôùp cô baûn : + Döõ lieäu nhaäp : Döõ lieäu ñaàu vaøo cuûa moâ hình. + Döõ lieäu xuaát : Döõ lieäu xuaát ra cuûa moâ hình. + Döõ lieäu cuïc boä : Döõ lieäu lieäu trung gian, ñaùp öùng caùc nhu caàu hoaït ñoäng, löu tröõ cuûa moâ hình. Ngöôøi söû duïng chæ coù theå giao tieáp vôùi moâ hình thoâng qua döõ lieäu nhaäp vaø döõ lieäu xuaát. Caùc yeâu caàu hoïc taäp cuûa ngöôøi söû duïng ñöôïc chuyeån ñoåi thaønh döõ lieäu nhaäp, qua moät soá böôùc tính toaùn, phaân tích moâ hình seõ ñöa ra caùc döõ lieäu xuaát ñeå giaûi thích hoaëc ñaùp öùng caùc yeâu caàu cuûa ngöôøi söû duïng. Döõ lieäu cuïc boä cuûa moâ hình coù theå ñöôïc trình baøy hoaëc che daáu tuøy muïc ñích cuûa moâ hình. Hoaït ñoäng cuûa moâ hình Caùc hoaït ñoäng cuûa moâ hình coù theå chia laøm hai loaïi chính nhö sau : + Hoaït ñoäng nhaäp xuaát : Ñaây laø caùc hoaït ñoäng theå hieän söï giao tieáp cuûa moâ hình cuûa ngöôøi söû duïng. Caùc phöông thöùc nhaäp/xuaát ñaûm nhaän vieäc nhaän caùc döõ lieäu nhaäp cuûa moâ hình vaø theå hieän caùc döõ lieäu xuaát ra caùc thieát bò ngoaïi vi (maøn hình, maùy in,…) ñeå giaûng daïy cho ngöôøi söû duïng. + Hoaït ñoäng xöû lyù, tính toaùn döõ lieäu : Caùc hoaït ñoäng xöû lyù caùc döõ lieäu cuïc boä cuûa moâ hình phuïc vuï cho yeâu caàu daïy vaø hoïc. Caùc phöông thöùc naøy ñaûm nhaän vieäc chuyeån ñoåi döõ lieäu nhaäp thaønh caùc döõ lieäu cuïc boä cuûa moâ hình. Moâ hình seõ tính toaùn, xöû lyù treân döõ lieäu cuïc boä vaø chuyeån thaønh caùc döõ lieäu xuaát. - VÍ DUÏ VEÀ MOÄT PHAÀN MEÀM TRÔÏ GIUÙP HOÏC TAÄP Ví duï ñöa ra ôû ñaây laø phaàn meàm trôï giuùp hoïc taäp moân Anh Vaên LANGMaster INTERACTIVE ENGLISH. Trong phaàn meàm chöùa ñöïng ñöôïc taát caû caùc ñaëc tính cuûa moät phaàn meàm giaûng daïy hieän ñaïi: - Nhöõng baøi hoïc ñöôïc xeáp töø deã ñeán khoù, tuy nhieân vaãn cho pheùp ngöôøi söû duïng löïa choïn nhöõng phaàn maø mình quan taâm maø khoâng caàn hoïc nhöõng phaàn tröôùc. - Ñöa ra nhöõng hình thöùc thöïc haønh vaø luyeän taäp phong phuù nhö : ñieàn vaøo choã troáng, choïn töø ñuùng, taäp phaùt aâm. - Baùo caùo laïi möùc ñoä tieáp thu cuûa ngöôøi hoïc qua töøng baøi giaûng, ñeå ngöôøi hoïc nhaän bieát ñöôïc trình ñoä töø ñoù cuõng coá kieán thöùc cho nhöõng baøi hoïc tieáp theo. - Ñaëc bieät phaàn meàm LANGMaster INTERACTIVE ENGLISH ñaõ ñöa ra moät phöông phaùp giaûi daïy hieän ñaïi, ñoù laø phöông phaùp hoïc töø vaø thaønh ngöõ RE-WISE: + Phöông phaùp RE_WISE ñöôïc thieát keá vôùi söï tham gia cuûa caùc chuyeân gia veà vieäc hoïc vaø veà moâ hình toaùn hoïc cuûa vieäc hoïc /queân trong nhieàu naêm töø ñoù ñöa ra moät thoáng keâ quaù trình hoïc vaø queân caùc söï kieän ñaõ ñöôïc thu nhaän. Qua ví duï treân cho thaáy ñöôïc caùc tính chaát cuûa moät phaàn meàm giaûng daïy hieän taïi cuõng nhö moät phöông phaùp giaûng daïy toát ñöôïc ñöa ra seõ giuùp ích raát nhieàu trong vieäc hoïc. 3.6- PHAÂN TÍCH ÑIEÀU KIEÄN DAÏY VAØ HOÏC HIEÄN TAÏI vaø LOAÏI PHAÀN MEÀM GIAÛNG DAÏY CAÀN THIEÁT KEÁ Treân cô sôû thieát keá moät phaàn meàn giaûng daïy cho caùc ñoái töôïng laø nhöõng sinh vieân theo hoïc ngaønh Maùy Tính. Chuông trình “Xaây döïng boä coâng cuï thöïc hieän moät soá giaûi thuaät trong Lyù thuyeát Ngoân ngöõ Hình thöùc & Automata”, coá gaéng ñöa nhöõng noäi dung cô baûn cuûa moâ hoïc nhaèm goùp phaàn giuùp cho sinh vieân naém baét ñöôïc caùc cô sôû lyù thuyeát. Hieän nay vôùi ñieàu kieän veà cô sôû vaät chaát cuõng nhö caùc taøi lieäu thoâng tin vaø phöông tieän giaøi daïy coøn chöa ñaày ñuû nhö ôû nöôùc ta toàn taïi caùc hình thöùc daïy vaø hoïc sau: + Hình thöùc hoïc taäp trung (hoïc treân lôùp coù thaày coâ höôùng daãn) + Hình thöùc hoïc haøm thuï töø xa (hoïc theo söï höôùng daãn cuûa ngöôøi chuyeân moân theo giaùo trình hay saùch vôû ñöôïc ñònh höôùng saún). + Hình thöùc töï hoïc (Hoïc theo nhu caàu , do ñieàu kieän khoâng cho pheùp theo hoïc hai hình thöùc treân). Do ñoù vieäc thieát keá ra caùc phaàn meàm trôï giuùp vieäc giaûng daïy raát caàn thieát raát caàn thieát cho nhu caàu giaûng daïy hieän taïi. Döïa vaøo nhöõng phaân tích treân cuøng vôùi caùc moâ tröôøng daïy vaø hoïc vöøa neâu, toâi quyeát ñònh xaây döïng coâng cuï “Xaây döïng boä coâng cuï thöïc hieän moät soá giaûi thuaät trong Lyù thuyeát Ngoân ngöõ Hình thöùc & Automata” theo phía caïnh moâ hình giaûng daïy . PHAÀN 4 PHAÂN TÍCH VAØ THIEÁT KEÁ Sau ñaây chuùng ta baét ñaàu ñi vaøo vieäc phaân tích cuï theå cho boä coâng cuï thöïc hieän moät soá giaûi thuaät trong moân hoïc “ Lyù Thuyeát Ngoân Ngöõ Hình Thöùc & Automata” phaàn ngoân ngöõ phi ngöõ caûnh. I - YEÂU CAÀU ÑAËT RA CHO CHÖÔNG TRÌNH 1.1 Muïc Tieâu Cuûa Chöông Trình Muïc tieâu chính cuûa chöông trình laø : Vôùi boä coâng cuï ñöôïc xaây döïng noù seõ hoå trôï ñaét löïc cho ngöôøi giaûng daïy, giaûm thieåu thôøi gian trong vieäc soaïn giaùo aùn cho caùc baøi taäp aùp duïng moät soá giaûi thuaät maø chuùng toâi theå hieän trong chuông trình, giuùp cho sinh vieân naém baét ñöôïc caùch thöùc thöïc hieän moät baøi taäp theo caùc giaûi thuaät ñaõ neâu ra, giuùp ngöôøi hoïc kieåm tra kieán thöùc cuûa mình, thöïc haønh moät soá baøi taäp töø ñoù naâng kieán thöùc khi hoïc caùc lyù thuyeát lieân quan. 1.2- Caùc Yeâu Caàu Phaûi Vieát Trong Chöông Trình Treân cô sôû thieát keá phaàn meàm daïy vaø hoïc cho nhöõng ñoái töôïng laø nhöõng nhöõng sinh vieân theo hoïc ngaønh khoa hoïc maùy tính. Chuông trình hoã trôï vieäc hoïc moät soá giaûi thuaät cuûa moân hoïc “Ngoân Ngöõ Hình Thöùc & Automat” coá gaéng thöïc hieän ñöôïc caùc vaán ñeà sau: + Ñöa ra nhöõng noäi dung cô baûn lieân quan ñeán moân hoïc nhaèm goùp phaàn giuùp cho sinh vieân hieåu vaø naém baét noäi dung cuûa lyù thuyeát lieân quan, phaàn naøy ñöôïc tích hôïp trong heä thoáng Help cuûa chöông trình. + Thöïc hieän moät boä coâng cuï trôï giuùp cho sinh vieân hoïc moät soá giaûi thuaät trong moân hoïc “Ngoân ngöõ hình thöùc & Automata” nhö : (1) Loaïi boû caùc luaät sinh roãng (2) Loaïi boû caùc luaät sinh ñôn vò (3) Loaïi boû caùc luaät sibnh voâ duïng (4) Chuyeån moät vaên phaïm baát kyø veà daïng chuaån Chomsky Chuyeån moät vaên phaïm baát kyø veà daïng chuaån Greibach Hieän thöïc giaûi thuaät phaân tích cuù phaùp CYK Hieän thöïc giaûi thuaät phaân tích cuù phaùp Earley So saùnh ñoä phöùc taïp cuûa hai giaûi thuaät PTCP treân. AÙp duïng nhaän daïng moät caâu nhaäp thuoäc ngoân ngöõ töï nhieân (Tieáng Anh). + Quaù trình thöïc hieän caùc giaûi thuaät phaûi theå hieän ñöôïc caùc böôùc döõ lieäu trung gian ñeå sinh vieân deã daøng naém baét caùch thöïc hieän giaûi thuaät. II- MOÂI TRÖÔØNG HOAÏT ÑOÄNG vaø CAÙC SÔ ÑOÀ DFD 2.1 Moâi Tröôøng Hoaït Ñoäng & Ngoân Ngöõ Laäp Trình Ñaây laø moät chuông trình mang tính daønh hoïc vieäc hoïc, nghieân cöùu caùch thöïc hieän giaûi thuaät neân chöông trình chæ thieát keá chaïy treân maùy tính caù nhaân, hieän taïi vaán ñeà chaïy treân maïng chöa ñaët ra ôû ñaây. Chuông trình phaùt trieån chaïy treân moâi tröôøng HÑH Microsoft Windows 95, ñaây laø moät HÑH ñöôïc söû duïng roãng raõi nhaát hieän nay treân theá giôùi . Chöông trình seõ keá thöøa nhöõng tieän ích cuûa HÑH naøy neân seõ khoâng theå chaïy treân moâi tröôøng DOS hay Windows 3.11 Ngoân ngöõ Visual C++ 5.0 ñöôïc söû duïng ñeå hieän thöïc heä thoáng, ñaây laø moät ngoân ngöõ laäp trình huôùng ñoái töôïng maïnh vaø hieän nay ñöôïc söû duïng roäng raõi. Ñaëc bieät chöông trình seõ söû duïng caùc class ñöôïc ñònh nghóa trong MFC . 2.2 Sô Ñoà DFD Toång Quaùt a) Tröôøng hôïp bieán ñoåi vaên phaïm Vaên Phaïm phi ngöõ caûnh baát kyø Boä coâng cuï thöïc hieän Thoâng baùo quaù trình thöïc hieän giaûi thuaät vaø keát quaû User User Yeâu caàu : - Boû caùc LS roãng - Boû caùc LS ñôn vò - Boû caùc LS voâ duïng - Daïng chuaån chomsky - Daïng chuaån Greibach b) Tröôøng hôïp phaân tích moät caâu nhaäp Vaên Phaïm phi ngöõ caûnh baát kyø Boä coâng cuï thöïc hieän Thoâng baùo quaù trình thöïc hieän giaûi thuaät & keát quaû Caâu nhaäp User User + Boä coâng cuï bao haøm caùc prosess lôùn sau : Process Loaïi boû caùc luaät sinh roãng (l). Process Loaïi boû caùc luaät sinh ñôn vò. Process Loaïi boû caùc luaät sinh voâ duïng. Process Chuyeån moät vaên phaïm baát kyø veà daïng chuaån Chomsky. Process Chuyeån moät vaên phaïm baát kyø veà daïng chuaån Greibach. Process Phaân tích moät caâu nhaäp theo giaûi thuaät CYK. Process Phaân tích moät caâu nhaäp theo giaûi thuaät Earley. Process So saùnh soá böôùc phaân tích cuûa hai giaûi thuaät CYK vaø Earley.(*) Process Nhaän daïng ngoân ngöõ töï nhieân (**) * : Xin xem chi tieát quaù trình thieát keá ôû phaàn 5 - Trang ** : Xin xem chi tieát quaù trình thieát keá ôû phaàn 6 - Trang c) Moâ hình Data Flow Diagram Chi Tieát + Bieán ñoåi vaên phaïm User Vaên phaïm G Nhaäp VPPNC G Loaïi boû taát caû VP Loaïi boû l VP Loaïi boû ñôn vò VP Loaïi boû voâ duïng Loaïi boû ñôn vò Loaïi boû luaät sinh l Daïng chuaån Greibach User Vaên Phaïm Thoâng baùo Thoâng baùo keát quaû Thoâng baùo keát quaû Thoâng baùo keát quaû Thoâng baùo keát quaû Thoâng baùo keát quaû Loaïi boû luaät sinh voâduïng Loaïi boû luaät sinh ñôn vò Vaên phaïm G Daïng Chuaån Chomsky Vaên phaïm G VP khoâng coù roãng, ñôn vò, voâ duïng VP khoâng coù roãng, ñôn vò, voâ duïng Yeâu caàu DC Chomsky Yeâu caàu DC Greibach + Phaân Tích Caâu Nhaäp User Vaên phaïm G Nhaäp VPPNC G Boä phaân tích cuù phaùp CYK Caâu nhaäp Caâu nhaäp Boä phaân tích cuù phaùp Earley Loaïi boû luaät sinh l User User Vaên Phaïm Thoâng baùo keát quaû Thoâng baùo keát quaû VP daïng chuaån Chomsky Loaïi boû luaät sinh ñôn vò Loaïi boû luaät sinh voâ duïng Vaên phaïm khoâng coù caùc luaät sinh ñôn vò Vaên phaïm khoâng coù caùc luaät sinh voâ duïng Vaên phaïm khoâng coù caùc luaät sinh l Chuyeån veà daïng chuaån Chomsky III- CAÙCH THÖÙC NHAÄP VAØ XUAÁT DÖÕ LIEÄU Nhaäp Lieäu Döõ lieäu ñaàu vaøo laø caâu nhaäp vaø vaên phaïm phi ngöõ caûnh G, döïa vaøo caùc döõ lieäu naøy boä coâng cuï tieán haønh phaân tích theo yeâu caàu. Boä coâng cuï Baøn phím File löu tröõ Löu file Nhaän döõ lieäu töø File 7 + Chöông trình coù hai hình thöùc ñeå ñöa ñöõ lieäu vaøo cho boä coâng cuï : Nhaäp döõ lieäu töø baøn phím Nhaäp töø file löu tröõ treân ñóa töø, file naøy do ngöôøi söû duïng löu laïi khi nhaäp lieäu töø baøn phí hoaëc coù theå soaïn thaûo baèng moät trình soaïn thaûo vaên baûn theo ñuùng format cuûa chöông trình. Xuaát döõ lieäu Döõ lieäu xuaát ôû ñaây chuû yeáu laø caùc doøng vaên baûn keát quaû xuaát ra maøn hình cho ngöôøi söû duïng xem, ñoàng thôøi löu xuoáng file ñeå löu tröõ (döõ lieäu löu laø caùc taäp vaên phaïm keát quaû khi thöïc hieän bieán ñoåi vaên phaïm) Moät soá döõ lieäu trung gian cuõng ñöôïc hieån thò ñeå minh hoïa quaù trình phaân tích, coù theå minh hoïa vieäc trình baøy döõ lieäu xuaát cuûa boä coâng cuï qua so ñoà sau : Boä coâng cuï Löu keát quaû xuoáng file Döõ lieäu keát quaû Döõ lieäu minh hoïa cho giaûi thuaät Hieån thò leân maøn hình Maøn Hình File löu tröõ 3.3 Ñònh Daïng File Döõ Lieäu Döõ lieäu löu tröõ ôû ñaây laø boä vaên phaïm phi ngöõ caûnh G=(V,T,S,P), do ñoù coù theå ñeà nghò moät ñònh daïng nhö sau : //kyù hieäu ñeå nhaän daïng bieán khôõi ñaàu Bieán khôõi ñaàu // kyù hieäu ñeå nhaän daïng döõ lieäu theo sau thuoäc taäp V Danh saùch caùc kyù hieäu khoâng keát thuùc // kyù hieäu ñeå nhaän daïng döõ lieäu theo sau thuoäc taäp T Danh saùch caùc kyù hieäu keát thuùc // kyù hieäu ñeå nhaän daïng döõ lieäu theo sau thuoäc veá traùi cuûa taäp luaät sinh Danh saùch veá traùi (töông öùng thöù töï vôùi veá phaûi) // kyù hieäu ñeå nhaän daïng döõ lieäu theo sau thuoäc veá phaûi cuûa taäp luaät sinh Danh saùch veá phaûi (töông öùng thöù töï vôùi veá traùi) Do ñoù coù theå soaïn thaûo taäp vaên phaïm G baèng moät trình soaïn thaûo vaên baûng baát kyø laø löu ôû daïng .txt, chöông trình cuõng seõ löu taäp vaên phaïm vôùi ñònh daïng treân khi baïn baám nuùt löu. IV - TOÅ CHÖÙC CAÁU TRUÙC DÖÕ LIEÄU 1) Caáu Truùc Döõ Lieäu Cho Vaên Phaïm G=(V,T,S,P) a) Löu taäp V : Laø moät maõng kyù töï laø chöõ in hoa 0 1 2 3 4 5 6 7 8 . . . Löu taäp T : Laø moät maõng kyù töï laø chöõ thöôøng. 0 1 2 3 4 5 6 7 . . . c) Löu bieán khôõi ñaàu S : Söû duïng moät char ñeå löu S d) Löu taäp caùc luaät sinh P : Söû duïng moät maõng chuoãi kyù töï cho veá phaûi vaø moät maõng cho veá traùi Veá Traùi Veá Phaûi 0 0 1 1 2 2 3 3 4 4 . . . . . . 2- Caáu Truùc Döõ Lieäu Cho Giaûi Thuaät CYK a) Sô ñoà caáu truùc döõ lieäu j i 1 2 3 4 ... n 1 string string string string string string string string string 2 ... 3 ... n string b) Hieän Thöïc : Baûng phaân tích cuù phaùp T laø moät maõng hai chieàu, ôû ñaây giôùi haïn chieàu daøi toái ña cuûa chuoãi nhaäp (soá token) laø MAX kyù töï do ñoù, maõng T ñöôïc khai baùo nhö sau trong Visual C++: CString T [MAX][MAX]; Moät soá taùc vuï khi thöïc hieän giaûi thuaät CYK : + Hoäi hai taäp hôïp traû veà taäp hôïp keát quaû CString Hoi(CString B, CString C) { int i; CString Temp; Temp=""; for(i=0;i<B.GetLength();i++) if (Temp.Find(B[i])==-1) Temp=Temp+B[i]; for(i=0;i<C.GetLength();i++) if (Temp.Find(C[i])==-1) Temp=Temp+C[i]; return Temp; } +Tìm kieám caùc luaät sinh coù veá traùi =BC thì traû veà chuoãi chöùa veá traùi cuûa taát caû caùc luaät sinh ñoù ngöôïc laïi traû veà troáng CString TimLuatSinhBC(CString B, CString C) { int soluat; CString temp,st; int i; temp=B+C; soluat=ArrayVeTrai.GetSize(); for(i=0;i<soluat;i++) if (temp==ArrayVePhai[i]) st=st+ArrayVeTrai[i]; if (st.GetLength() !=0) return st; else return ""; } + Neáu coù luaät sinh thì traû veà string chöùa taát caû caùc veá traùi ngöôïc laïi traû veà chuoãi roãng CString TimLuatSinh_a(CString a) { int soluat; CString st; int i; soluat=ArrayVeTrai.GetSize(); for(i=0;i<soluat;i++) if (ArrayVePhai[i]==a) st=st+ArrayVeTrai[i]; if (st.GetLength() !=0) return st; else return ""; } +Neáu chuoãi thuoäc ngoân ngöõ L thì traû veà 1 ngöôïc laïi traû veà 0 int KiemTraChuoiThuocL(CString st) { int i,len; len=st.GetLength(); for(i=0;i<len;i++) if(st[i]==BienKhoiDau) return 1; return 0; } +Traû veà soá thöù töï cuûa luaät sinh P-->ai int Pa(CString A, CString a) { int soluat; int i; soluat=ArrayVeTrai.GetSize(); for(i=0;i<soluat;i++) if ((ArrayVeTrai[i]==A)&&(ArrayVePhai[i]==a)) return i; return -1; Caáu Truùc Döõ Lieäu Cho Giaûi Thuaät Earley Danh Saùch chöùa caùc thöïc theå cuûa I0 . . . . ... I3 I2 I1 I0 Maõng caùc con troû, troû ñeán caùc thöïc theå P ,i ,f P ,i ,f P ,i ,f a) Sô ñoà caáu truùc döõ lieäu b) Hieän Thöïc : - Ñeå theå hieän moät thöïc theå ta söû duïng moät boä 3 bieán nguyeân nhö sau : + p : chæ soá thöù töï cuûa luaät sinh + i : chæ vò trí daáu chaám ( . ) trong taäp thöïc theå + f : chæ vò trí taäp thöïc theå nhö vaäy ñeå xaùc ñònh moät thöïc theå ta chæ caàn xaùc ñònh boä ba (p, i,f) - Taäp thöïc theå caùc I0, I1, ... laø moät maõng caùc con troû vò trí baét ñaàu cuûa taäp thöïc theå - Moãi thöïc theå Ii chöùa con troû troû ñeán ñaàu danh saùch lieân keát chöùa caùc thöïc theå c) Caùch hieän thöïc caáu truùc döõ lieäu treân trong ngoân ngöõ C Ñònh nghóa moät phaàn töû trong danh saùch lieân keát : typedef struct item { int p; int i; int f; struct item *link; } items; trong ñoù : + p : chæ soá thöù töï cuûa luaät sinh + i : chæ vò trí daáu chaám ( . ) trong taäp thöïc theå + f : chæ vò trí taäp thöïc theå + link : laø con troû troû ñeán phaàn töû keát tieáp. Khai baùo moät maõng caùc troû, troû ñeán taäp thöïc theå items items *tapthucthe[MAX]; trong ñoù MAX : soá löôïng taäp thöïc theå lôùn nhaát, soá löôïng naøy seõ baèng vôùi chieàu daøi chuoãi nhaäp d) Moät soá taùc vuï cô baûn khi thöïc hieän giaûi thuaät Earley (söû duïng ngoân ngöõ C) + Khôûi ñoäng moät thöïc theå: items *Init(items *f) { f=NULL; return f; } + Khôûi ñoäng taäp thöïc theå : void Init_thucthe() { int i; for (i=0;i<MAX; i++) tapthucthe[i]=Init(tapthucthe[i]); } + Ñöa döõ lieäu vaøo moät taäp thöïc theå naøo ñoù: items *Insert_data(items *pt, int k,int j ,int f) { items *p,*q,*before; p=new items; (p->p)=k; (p->i)=j; (p->f)=f; q=pt; while(q!=NULL) { before=q; q=q->link; } if(q==pt) pt=p; else before->link=p; p->link=q; return (pt); } +Traû veà kyù töï sau daáu chaám char ChrAfterDot(items *pt) { int sl,ch; CString Vp; sl=(pt->p); ch=(pt->i); Vp=ArrayVePhai[sl]; if (ch<Vp.GetLength()) return (Vp[ch]); else return ""; V - CAÙC LÖU ÑOÀ THUAÄT TOAÙN CHO CAÙC PROCESS START Luaät sinh thöù p coù daïng A --> l p=0 Cho A vaøo trong Vn p > Toång LS Ñ S S p=p+1 Luaät sinh thöù p coù daïng A --> A1A2…An maø A1A2…An Î Vn p=0 Cho A vaøo trong Vn Ñ Ñ S S p=p+1 p > Toång LS Luaät sinh thöù p coù daïng A --> x1x2…xm vôùi m³1vaø xi Î (VÈT) p=0 Cho vaøo P^ caùc toå hôïp coù theå coù baèng caùch thay theá caùc bieán Î Vn baèng l Ñ Ñ S S p=p+1 p > Toång LS END p=0 1- Loaïi Boû Caùc Luaät Sinh l 2- Loaïi Boû Caùc Luaät Sinh Ñôn Vò START Luaät sinh thöù p coù daïng A --> B p=0 Cho luaät sinh thöù p vaøo trong P^ p > Toång LS S Ñ S Ñ p=p+1 Cho luaät sinh thöù p vaøo trong P* Taïo ñoà thò phuï thuoäc cho P* - Aùp duïng vieäc thay theá baèng caùch : laáy veá phaûi cuûa luaät sinh khoâng ñôn vò coù veá traùi laø veá phaûi cuûa luaät sinh ñôn vò thay vaøo veá phaûi cuûa luaät sinh ñôn vò töông öùng - Cho caùc luaät sinh thay theá vaøo P^ END START V1= { } Theâm A vaøo V1 Luaät sinh p coù daïng Aà x1x2… xn vôùi xi Î T* È V1 V1 chöùa A roài Ñ Ñ S Ñ S S p=p+1 p=0 p> Toång LS Cho vaøo trong P1 caùc luaät sinh trong P maø coù VP Î (V1È T*) Loaïi boû caùc luaät sinh voâ duïng loaïi 1 p1> Toång LSP1 If VT=”Bieán khôõi Ñaàu” then For (I=0; I<chieàu daøi VP luaät sinh p1;I++) if VP[I] ÎV1 then B=BÈVP[I] p1=0, B={ } (p1 bieán duyeät caùc luaät sinh trong P1) Ñ S p1=p1+1 A 3- Loaïi Boû Caùc Luaät Sinh Voâ Duïng Döïa vaø taäp B vaø caùc luaät sinh trong P1, taïo ñoà thò phuï thuoäc cho P1 Loaïi boû caùc bieán vaø luaät sinh töông öùng cuûa noù ra khoûi taäp luaät sinh P1 A END Loaïi boû caùc luaät sinh voâ duïng loaïi 2 START Loaïi boû caùc luaät sinh l Loaïi boû caùc luaät sinh ñôn vò Loaïi boû caùc luaät sinh voâ duïng p=0 Luaät sinh thöù p coù chieàu daøi veá phaûi >=2 Cho taát caû caùc luaät sinh coù daïng Aà a vaøo trong P^ Ñ S Thay caùc kyù hieäu keát thuùc (ví duï laø a) ôû veá phaûi baèng veá traùi sinh ra noù (coù trong taäp P^) neáu khoâng coù thì sinh ra kyù töï ñaïi dieän Ba,vaø ñaët Ba àa vaøo trong P^ p=p+1 p=p+1 Sau böôùc treân ta coù ñöôïc luaät sinh : Aà C1C2…Cn, ta tieán haønh chia nhoû luaät sinh naøy thaønh caùc luaät sinh coù chieàu daøi baèng 2 nhö sau : str=VP; n=Len(str) Repeat if (n=2) then cho luaät sinh A vaøo P^ else STP=str[0]+Dk Cho Aà STP vaøo trong P^ str=Right(Len-1); n=n-1; k++; Until (n=2) p> Toång LS END 4- Process Daïng Chuaån Chomsky S Ñ 5- Process Daïng Chuaån Greibach START Loaïi boû caùc luaät sinh l Loaïi boû caùc luaät sinh ñôn vò Loaïi boû caùc luaät sinh voâ duïng G=(V,T,S,P) Ñaùnh soá thöù töï caùc bieán trong V töø 1 ñeán n TEMP=P (taäp luaät sinh) Taát caû caùc luaät sinh trong P coù coù ôû taát caû caùc daïng sau: Ai à Ajxj ,j >I Zi à Ajxj , j£n Ai à axi i < 1 Thöïc hieän loaïi boû ñeä qui traùi vaø thay theá S Ñ S Ñ i=n Thay theá Ai vaøo trong caùc xuaát hieän cuûa noù ôû vò trí ñaàu tieân treân caùc veá phaûi cuûa luaät sinh Ai-1 baèng caùc veá phaûi cuûa noù i=i-1 A START Loaïi boû caùc luaät sinh l Loaïi boû caùc luaät sinh ñôn vò Loaïi boû caùc luaät sinh voâ duïng Cho taát caû caùc luaät sinh coù daïng Aà a vaøo trong P^ START Cho taát caû caùc luaät sinh coù daïng Aà a vaøo trong P^ A p>Toång LS p=0 Luaät sinh thöù p coù veá traùi laø Zi vaø kyù hieäu ñaàu tieân cuûa veá phaûi thuoäc (A1, … An) Thay theá kí hieäu cuûa veá phaûi luaät sinh thöù p baèng veá traùi cuûa kyù hieäu töông öùng Ñ S S Ñ p=p+1 Thay theá caùc kyù hieäu keát thuùc naèm treân veá phaûi cuûa caùc luaät sinh trong P maø khoâng ôû vò trí ñaàu tieân baèng caùc kyù hieäu ñaïi ñieän Bi END 6- Löu Ñoà Giaøi Thuaät Phaân Tích Cuù Phaùp Earley START i=0 i > Toång Luaät Sinh i0=i0+1 i=i+1 Luaät sinh thöù i coù daïng S --> a Cho [S--> .a, 0] vaøo trong I0 Ñ S S S S S Ñ Ñ Ñ Ñ Böôùc 1 Böôùc 2&3 Luaät sinh thöù i0 trong I0 coù daïng [B -->g., 0] i0 =0 Luaät sinh thöù i0 trong I0 coù daïng [A -->a.Bb,0] I0 > ToångLS trong I0 Cho vaøo I0 traïng thaùi [B-->.g,0] cuûa caùc luaät sinh trong P coù daïng B-->g - Tính laïi ToångLS Cho vaøo I0 traïng thaùi [A--> aB.b,0] cuûa caùc traïng thaùi trong I0 coù daïng [A--> aB.b,0] -Tính laïi ToångLS A x=x+1 Ñ S S Ñ Ñ Ñ S S A Luaät sinh thöù x trong Ij-1 coù daïng [B -->a.ab, I] vôùi (a=aj) x=0 j=1 Cho [B -->a.ab, i] vaøo trong Ij x > ToångLS trong Ij-1 y=0 Luaät sinh thöù y trong Ij coù daïng [A -->a. , i] Tìm trong P caùc luaät sinh coù daïng : [B -->g thì cho vaøo Ij taäp : [B --> .g, k