Toan Roi Rac

Luaän Toát Nghieäp KS2-K7

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 Trang

1

Luaän Toát Nghieäp KS2-K7

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 Trang

2

Luaän Toát Nghieäp KS2-K7 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 daïy toát.

thöùc ñeå thieát keá vaø löïa choïn moâ hình giaûng

♦ 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 Trang

3

Luaän Toát Nghieäp KS2-K7 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öø http://www.devgr.com)

♦ 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 Σ ♦ 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 Σ laø baûng chöõ caùi (alphabet), moät töø w treân Σ 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 Σ={a,b} ♦ Chuoãi roãng cuõng laø moät töø treân baûng chöõ caùi Σ kyù hieäu laø λ

♦ Keát noái chuoãi (concatenation) : Cho hai chuoãi u,v treân baûng chöõ caùi Σ, 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 Σ bao goàm caùc kyù hieäu thuoäc u theo sau laø caùc kyù hieäu thuoäc v. Trang

4

Luaän Toát Nghieäp KS2-K7 Ví duï: Σ ={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 Σ 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ì w n 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=λ ♦ Σ* : Neáu Σ laø moät baûng chöõ caùi thì taäp taát caû caùc chuoãi treân Σ keå caû chuôûi troáng ñöôïc goïi laø Σ* ♦ Σ+: Neáu Σ laø moät baûng chöõ caùi thì taäp taát caû caùc chuoãi treân Σ khoâng keå chuôûi troáng ñöôïc goïi laø Σ+ 3. NGOÂN NGÖÕ

♦ Baát kyø moät taäp L naøo treân baûng chöõ caùi Σ, hay taäp con L cuûa Σ* ñöôïc goïi laø moät ngoân ngöõ. Ví duï : Cho Σ={a,b} thì Σ*={λ,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 ∑: Trang

5

Luaän Toát Nghieäp KS2-K7 + 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={λ} 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, Trang

6

Luaän Toát Nghieäp KS2-K7 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ì: + ∅,λ 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. Trang

7

Luaän Toát Nghieäp KS2-K7 + λ laø moät bieåu thöùc chính qui bieåu thò taäp {λ} + Ñ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. Trang

8

Luaän Toát Nghieäp KS2-K7 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

Ñònh Nghóa

a

A phi ngöõ B caûnh. c Moät caây coù thöù töï Cho G=(V,T,S,P) laø moätb vaên phaïm 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∪{λ}) + 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 λ khoâng coù anh chò e, töùc laø moät noát vôùi moät con ñöôïc gaùn nhaõn λ 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ö : Trang

9

Luaän Toát Nghieäp KS2-K7 + + + + +

Loaïi boû caùc Loaïi boû caùc Loaïi boû caùc Chuyeån vaên Chuyeån vaên

luaät sinh roãng luaät sinh voâ duïng luaät sinh ñôn vò phaïm baát kyø veà daïng chuaån Chomsky 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 (λ) Baát kyø luaät sinh naøo cuûa vaên phaïm phi ngöõ caûnh coù daïng A --> λ ñöôïc goïi laø luaät sinh λ, vaø baát kyø bieán A naøo maø ñoái vôùi noù daãn xuaát A--*> λ 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->λ 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 λ 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->λ vaøo trong P^ Ví duï: Cho vaên phaïm G =({S,A,B,C,D},{a, b,d,λ},{S},P) vaø caùc luaät sinh trong P nhö sau : S ---> ABaC Trang 10

Luaän Toát Nghieäp KS2-K7 A ---> BC B ---> b | λ C ---> D | λ 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--->λ, C--->λ 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á λ 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ù : Trang 11

Luaän Toát Nghieäp KS2-K7 Neáu muoán trong P^ khoâng chöùa luaät sinh roãng λ thì tröôùc tieân ta phaûi loaïi boû luaät sinh λ 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:

S

A

B

- 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 | λ | 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 Trang 12

Luaän Toát Nghieäp KS2-K7 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(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 Trang 13

Luaän Toát Nghieäp KS2-K7 • 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: Trang 14

Luaän Toát Nghieäp KS2-K7 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(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. Trang 15

Luaän Toát Nghieäp KS2-K7 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) Trang 16

Luaän Toát Nghieäp KS2-K7 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 B 2 ñ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 Trang 17

Luaän Toát Nghieäp KS2-K7 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

Trang 18

Luaän Toát Nghieäp KS2-K7 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

Chuoãi nhaäp

Stack

Parser

Xuaát keát quaû

Baûng phaân tích LL

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. Trang 19

Luaän Toát Nghieäp KS2-K7 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-->α thì giaûi thuaät seõ ñaåy X ra khoûi stack vaø theâm α vaøo stack sao cho kyù hieäu ñaàu tieân cuûa α naèm treân ñænh stack. Luaät sinh X --> α ñöôï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 :

Chuoãi nhaäp

Stack

Parser

Xuaát keát quaû

Baûng Action - Goto Trang 20

Luaän Toát Nghieäp KS2-K7 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 α, vôùi α laø veá phaûi cuûa luaät sinh 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ët | α | laø chieàu daøi cuûa α, ñaåy 2*|α | 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  α ñöôï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

Trang 21

Luaän Toát Nghieäp KS2-K7 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ä : (<start-vertex>, <end-vertex>, <edge-lable>) trong ñoù : + <start-vertex> : Moät soá töï nhieân chæ ra ñænh baét ñaàu cuûa cung. + <end-vertex> : Moät soá töï nhieân chæ ra ñænh keát thuùc cuûa cung. + <edge-vertex> : Ñ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)

Trang 22

Luaän Toát Nghieäp KS2-K7 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ù <start-vertex> =i-1, <end-vertex>=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 --> α theâm cung (0,0,S-->.α) 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 Trang 23

Luaän Toát Nghieäp KS2-K7 the her her they on see report report nurses nurses

Det Det NP NP P TV N IV NP 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 report. NP  they.

Det  her. TV  see.

N nurses.

P  on. Det 

IV  report.

the. III- COÂNG CUÏ PHAÂN TÍCH CUÙ PHAÙP YACC

1- Toång Quan

N nurses.

N  her.

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 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 ñaëc taû Yacc.translate.y Yacc Compiler

y.tab.c

Chuoãi Token

C Compiler

a.out

y.tab.c

a.out

Daãn xuaát

Trang 24

Luaän Toát Nghieäp KS2-K7 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ù Trang 25

Luaän Toát Nghieäp KS2-K7 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.

4- 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 α 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ø α 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.

Trang 26

Luaän Toát Nghieäp KS2-K7

CHÖÔNG 4 GIAÛI THUAÄT PHAÂN TÍCH CUÙ PHAÙP EARLEY VAØ CYK I- 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] Trang 27

Luaän Toát Nghieäp KS2-K7 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 α . β , i] laø ôû trong Ij (0 ≤ i ≤ j) neáu vaø chæ neáu toàn taïi γ vaø δ sao cho chuùng ta coù S =*> γAδ vaø γ =*> a1…ai vaø α =*> 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öø α ñeán vò trí j vaø ñang chôø chuoåi tieáp theo ñöôïc daãn xuaát töø β. • 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 α . ,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 : (1) Neáu S α laø moät luaät sinh trong P thì ta cho [S.α , 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.

(2) Neáu [B γ . , 0] thuoäc I0 (chuù yù : γ coù theå laø ∈) thì cho vaøo I0 [A αB . β , 0] cho taát caû caùc thöïc theå coù daïng [A α . Bβ , 0] coù trong I0

(3) Neáu [A α . Bβ ,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 γ caùc thöïc theå [B .γ ,0]

•

Xaây giôø chuùng ta xaây döïng Ij sau khi ñaõ coù I0, I1,… Ij-1

(4) Vôùi moãi thöïc theå trong Ij-1 coù daïng [B α . aβ ,i] (vôùi a=aj) cho taäp thöïc theå [B α a . β ,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 :

(5) Neáu [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β , k] vôùi moãi taäp thöïc theå tìm ñöôïc nhö vaäy ta cho vaøo Ij [B α A . β , k] (6) Neáu [A α . Bβ, 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 γ ta theâm [B .γ , j] vaøo Ij Trang 28

Luaän Toát Nghieäp KS2-K7 •

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 : (1) E T+E Trang 29

Luaän Toát Nghieäp KS2-K7

(2) (3) (4) (5) (6)

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 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 I 0 caù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 theå (03) vaø (04) nhöng hai thöïc theå naøy ñaõ toàn taïi trong I0 roài 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 I 0 caùc theå : [F . (E) , 0] (05) [F . a , 0] (06)

caùc

thöïc

thöïc neân thöïc

- 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] [E .T, 0] [T .F*T, 0] [T .F , 0 ] [F . (E) , 0] [F . a , 0]

(01) (02) (03) (04) (05) (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) Trang 30

Luaän Toát Nghieäp KS2-K7 - 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 I 2 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

[E  .T+E , 0] [E .T, 0] [T .F*T, 0] [T .F , 0 ] [F . (E) , 0] [F . aI3, 0]

I1

[F  (. E ) , 0] [E .T, 1] [T .F*T, 1] [T .F , 1] [F . (E) , 1] [F . aI4, 1]

I2

[F  a ., 1] [T F . *T, 1] [T F ., 1] [E T . + E , 1] [E T. , 1] [F (E .) I5 , 0]

[E T + .E , 1] [F a . , 3] [F ( E ). . 0] [E .T+E , 3] [T F . *T , 3] [T F . *T , 0] [E.T , 3] [T F . , 3] [T F . , 0] [T. F *T , 3] [E T. + E, 3] [E T. + E, 0] [T. F , 3] [E T. , 3] [E T. , 0] F .( E ), 3] [E T+ E ., 1] I6 I7 F.a ,3] F ( E . ), 0] [F a . , 6] [T F * .T, 0] [T F . *T , 6] [T . F * T , 6] [T F . , 6] [T. F , 6] [T F *T . , 0] [F . (E) , 6] [E T . + E, 0] [FXaây . a , Döïng 6] 1.4 Chuoãi Daãn Xuaát Cho Chuoãi [E Nhaäp  T . , 0]

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. Trang 31

Luaän Toát Nghieäp KS2-K7 Ñ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 α . , 0] trong taäp I0 thì w khoâng thuoäc L(G) vaø baùo loãi. Nguôïc laïi cho π ={ } vaø thöïc hieän goïi chöông trình con R([S α . , 0], n), trong ñoù R([A β. , i],j ) ñöôïc ñònh nghóa nhö sau : R([A β. , i],j ) (1) Cho h vaøo taäp π (phiaù beân traùi) vôùi h laø soá thöù töï cuûa luaät sinh A β (thöôøng khai baùo π laø moät bieán toaøn cuïc). (2) If β = 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 → γ . , r] thuoäc Ij maø trong Ir coù thöïc theå [A X1X2 ... Xk-1 . Xk ... Xm , i] thì thöïc thi R([Xk γ. , 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) => π={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 π => π={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 π ={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 π, khi ñoù π ={6432}

• Tieáp tuïc vieäc phaân tích nhö treân ta tìm ñöôïc π ={64642156432} Trang 32

Luaän Toát Nghieäp KS2-K7

R([F (E) . ,

E

R([E T. , 0],7)

T

R([T F*T. ,

F *

( R([T F .

E

T

T

R([T F. , 6],7)

) R([E T+E . , 1],4) E R([E T .

F

R([F a . ,

+ R([F a .

F

T R([T F .

a

F

a

R([F a .

1.5 - Söï lieân quan giöõa giaûi thuaät Earley vaø Chart Parsing Giaûi thuaät Chart Parsing laø moät a 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.

Trang 33

Luaän Toát Nghieäp KS2-K7

(b) 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. Trang 34

Luaän Toát Nghieäp KS2-K7 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ø : n 2 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).

1.7 - 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

SAb

S aB

A a | Ab

B aB | b

G3

G4

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

11x2n1 +7

6n

6n+4

Trang 35

Luaän Toát Nghieäp KS2-K7 G4

abncd

~3n+1

~2+1

~2n+5

(n3+21n2 +46n+1 5)/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

Trang 36

Luaän Toát Nghieäp KS2-K7

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 Trang 37

Luaän Toát Nghieäp KS2-K7 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 Trang 38

Luaän Toát Nghieäp KS2-K7 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 : (1) Tính ti1 = {A | A ai laø ôû trong P} (2) 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 : tij= ∪ { A | A BC thuoäc P maø B ∈ tik vaø C ∈ ti+k, j-k} 1≤k<j

(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 4 3 2 j↑ i →

A, S A, S A, S A,S 1 A 1

A, S A, S A S 2

A, S S A 3

A, S A 4

S 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 : Trang 39

Luaän Toát Nghieäp KS2-K7 - 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.

(2) Neáu j>1 vaø k laø moät soá nguyeân trong khoaûng 1≤ k < j vaø tìm ñöôïc B trong Tik vaø C trong Ti+k, j-k, vaø A --> 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}

2.4- Ñ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 :

(1) Ñaêt j=1. (2) 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). Trang 40

Luaän Toát Nghieäp KS2-K7

(3) 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ø :

∑

n j=2

line( j ) 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) +

∑

n j=2

line( j ) =O(n3).

Thuû tuïc line(j) ñöôïc ñònh nghóa nhö sau :

(1) Ñaët i=1 vaø j’=n-j+1 (2) Ñaët k=1 (3) Ñaët k’=i+k vaø j”=j-k (4) 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’’}

(5) Taêng k leân 1 (6) Neáu k=j thì thöïc hieän böôùc (7), ngöôïc laïi thì thöïc hieän böôùc (3) (7) Neáu i=j’ thì keát thuùc, ngöôïc laïi thöïc hieän böôùc (8) (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)

III- 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).

Trang 41

Luaän Toát Nghieäp KS2-K7

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. Trang 42

Luaän Toát Nghieäp KS2-K7 Ñ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. Trang 43

Luaän Toát Nghieäp KS2-K7

• 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.

3.3 -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 : Trang 44

Luaän Toát Nghieäp KS2-K7 Ñ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. 3.5 - 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. Trang 45

Luaän Toát Nghieäp KS2-K7 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 .

Trang 46

Luaän Toát Nghieäp KS2-K7

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 Trang 47

Luaän Toát Nghieäp KS2-K7 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) (2) (3) (4)

Loaïi boû caùc luaät sinh roãng Loaïi boû caùc luaät sinh ñôn vò Loaïi boû caùc luaät sibnh voâ duïng Chuyeån moät vaên phaïm baát kyø veà daïng chuaån Chomsky (5) Chuyeån moät vaên phaïm baát kyø veà daïng chuaån Greibach (6) Hieän thöïc giaûi thuaät phaân tích cuù phaùp CYK (7) Hieän thöïc giaûi thuaät phaân tích cuù phaùp Earley (8) So saùnh ñoä phöùc taïp cuûa hai giaûi thuaät PTCP treân. (9) 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 Vaên ñoåi Phaïm phi phaïm a) Tröôøng hôïp bieán vaên ngöõ caûnh baát kyø

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

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

User Trang 48

Luaän Toát Nghieäp KS2-K7

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

User

Thoâng baùo quaù trình thöïc hieän giaûi thuaät & keát

User

Caâu nhaäp

+ Boä coâng cuï bao haøm caùc prosess lôùn sau :

• Process

Loaïi boû caùc luaät sinh roãng (λ).

•

Process

Loaïi boû caùc luaät sinh ñôn vò.

•

Process

Loaïi boû caùc luaät sinh voâ duïng.

•

Process Chomsky.

Chuyeån moät vaên phaïm baát kyø veà daïng chuaån

•

Process Greibach.

Chuyeån moät vaên phaïm baát kyø veà daïng chuaån

•

Process

Phaân tích moät caâu nhaäp theo giaûi thuaät CYK. Trang 49

Luaän Toát Nghieäp KS2-K7 •

Process

•

Process So saùnh soá böôùc phaân tích cuûa hai giaûi thuaät CYK vaø Earley.(*)

•

Process

Phaân tích moät caâu nhaäp theo giaûi thuaät Earley.

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

Trang 50

Vaên Phaïm

Nhaäp VPPNC G

Luaän Toát Nghieäp KS2-K7 Vaên phaïm G

Loaïi boû luaät sinh λ

User

VP Loaïi boû λ

Thoâng baùo keát quaû Vaên phaïm G

+ Phaân Tích Caâu Nhaäp Caâu Loaïi boûnhaäp ñôn vòLoaïi boû Thoâng Caâu nhaäp luaät sinh baùo Vaên ñôn vò Phaïm VP Loaïi boû ñôn Vaên vò phaïmBoä G phaân tích cuù Boä phaân Nhaäp phaùpbaùo keát Thoâng Loaïi boû tích cuù VPPNC G Earley quaû luaät sinh phaùp CYK voâduïng VP daïng VP Loaïi boû voâ chuaån Thoâng User User Chomsky duïng baùo Thoâng baùo keát keát quaû Loaïi boû quaû taát caû Thoâng Chuyeån veà VP khoâng coù roãng, baùo Yeâu daïng chuaån ñôn vò, keát quaû User Chomskycaàu voâ duïng Vaên phaïm Thoâng baùo keát Daïng G Vaên phaïm quaû DC Chuaån khoâng coù User Chomsky Chomsky VP khoâng coù roãng, caùc luaät sinh ñôn vò, voâ duïng Yeâu voâ duïng Loaïi caàu boû Loaïi boû baùo keát luaät sinh Daïng Thoâng luaät sinh λ voâ duïng chuaån quaû DC Greibach Greibach

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 Loaïi boû luaät sinh ñôn vò Trang 51

Luaän Toát Nghieäp KS2-K7 III- CAÙCH THÖÙC NHAÄP VAØ XUAÁT DÖÕ LIEÄU

3.1 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.

File löu tröõ

Löu file

Nhaän döõ lieäu töø File

Baøn phím Boä coâng cuï

+ 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.

3.2 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 File löu tröõ 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 : Maøn Hình Löu keát quaû xuoáng file

Döõ lieäu keát quaû Boä Hieån thò leân coâng cuï maøn hình

Trang 52 Döõ lieäu minh hoïa cho giaûi thuaät

Luaän Toát Nghieäp KS2-K7

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 : <S> //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 Trang 53

Luaän Toát Nghieäp KS2-K7 6 7 8 . . .

b) 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 0 1 2 3 4 . . .

Veá Phaûi 0 1 2 3 4 . . .

Trang 54

Luaän Toát Nghieäp KS2-K7 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 1 2 3 ...

i 1 string ...

n

string

2 string

3 string

4 string

... string

string

string

n string 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];

c) 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
Luaän Toát Nghieäp KS2-K7 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;iai 0 int Pa(CString A, CString a) I1 { int soluat; I2 int i; soluat=ArrayVeTrai.GetSize();

P ,i ,f

Danh Saùch chöùa caùc thöïc theå cuûa

I3

for(i=0;i<soluat;i++) P ,i ,f ... if ((ArrayVeTrai[i]==A)&&(ArrayVePhai[i]==a)) return i; return -1; 3- Caáu Truùc Döõ Lieäu Cho Giaûi Thuaät Earley

. . . .

a) Sô ñoà caáu truùc döõ lieäu P ,i ,f

Maõng caùc con troû, troû ñeán caùc thöïc theå

Trang 56

Luaän Toát Nghieäp KS2-K7

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ù : Trang 57

Luaän Toát Nghieäp KS2-K7

•

+ 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) Trang 58

Luaän Toát Nghieäp KS2-K7 { int sl,ch; CString Vp; START sl=(pt->p); ch=(pt->i); Vp=ArrayVePhai[sl]; if (ch
Luaät sinh thöù p coù daïng A --> λ S p=p+1

Cho A vaøo trong Vn

Ñ

p > Toång LS S p=0

Luaät sinh thöù p coù daïng A --> A1A2…An maø

p=0 Ñ

A1A2…An ∈ Vn S p=p+1

S

Cho A vaøo trong Vn

p > Toång LS Ñ

V - CAÙC LÖU ÑOÀ THUAÄT TOAÙN CHO CAÙC PROCESS p=0 1- Loaïi Boû Caùc Luaät Sinh λ

Luaät sinh thöù p coù daïng A --> x1x2…xm vôùi m≥ S

Cho vaøo P^ caùc Ñ toå hôïp coù theå coù baèng caùch thay Trang 59

p=p+1

S

p > Toång LS

Ñ

END

Luaän Toát Nghieäp KS2-K7

START p=0

Luaät sinh thöù p S coù daïng A --> B Ñ

Cho luaät sinh thöù p vaøo trong P^

Cho luaät sinh thöù p vaøo trong P*

p=p+1

S

2- Loaïi Boû Caùc Luaät Sinh Ñôn VòLS p > Toång

Ñ 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 Trang 60

END

Luaän Toát Nghieäp KS2-K7

START V1= { } p=0

Luaät sinh p coù daïng A x1x2… xn vôùi

S

xi ∈ T* ∪ V1 Ñ

S

V1 chöùa A roài

Theâm A vaøo V1

3- Loaïi Boû Caùc Luaät Sinh Voâ Duïng

Ñ p=p+1

S

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=0, B={ } (p1 bieán duyeät caùc luaät sinh trong If VT=”Bieán khôõi Ñaàu” then For (I=0; I
S

p1> Toång LSP1

Ñ

Trang 61

A

Luaän Toát Nghieäp KS2-K7

A 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

Loaïi boû caùc luaät sinh voâ duïng loaïi 2

END

Trang 62

Luaän Toát Nghieäp KS2-K7

START Loaïi boû caùc luaät sinh λ Loaïi boû caùc luaät sinh ñôn vò

4- Process Daïng Chuaån Chomsky

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 p=0

S

p=p+1

Luaät sinh thöù p coù chieàu daøi Ñ

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

p=p+1 S

p> Toång LS Ñ END

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 Trang 63 STP=str[0]+Dk Cho A STP vaøo trong P^ str=Right(Len-1); n=n-1; k++;

Loaïi caùc luaät Cho boû taát caû caùc START luaätsinh sinhλ coù Luaän Toát Nghieäp KS2-K7 daïng A a vaøo Loaïi boû caùc luaät sinh ñôn vò Loaïi boû caùc luaät sinh voâ duïng START 5- Process Daïng Chuaån Greibach

Loaïi boû caùc luaät sinh λ 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

S

Thöïc hieän loaïi boû ñeä qui traùi vaø thay theá

Zi  Ajxj , j≤n Ñ i=n i=i-1 i<1 Ñ A

S

Thay theá Ai vaøo trong caùc xuaát hieän cuûa noù ôû vò trí Trang 64 ñaàu tieân treân caùc veá phaûi

Luaän Toát Nghieäp KS2-K7

A

p=0 START i=0 Luaät sinh thöù p coù veá traùi laø Zi vaø kyù sinh thöù Ñ Luaät i i=i+1 Ñ coùtieân daïng hieäu ñaàu cuûa veá phaûi S --> α S thuoäc (A1, … An) Böôù c1

S p =p+

S

Thay theá kí Cho [S--> hieäu cuûa . α, phaûi 0] vaøo veá trong luaät sinhI0thöù p baèng veá

i > Toång Luaät Sinh Ñ

S

p>Toång i0 =0 LS Ñ

Thay theá caùc kyù thöù i0 hieäu keát Luaät thuùcsinh naèm trongcuûa I0 coù treân veá phaûi caùc luaät sinh P 0] daïngtrong [B -->γ., maø khoâng ôû vò Strí Cho vaøo ñaàu I0 tieân baèng caùc traïng thaùi Luaät sinh thöù i0 [B-->.γ,0] cuûa END trong I0 coù caùc luaät sinh Ñ trong P coù daïngS[A -->α.Bβ,

Cho vaøo I0 traïng thaùi Ñ [A--> αB.β,0] cuûa caùc traïng thaùi

6- Löu Ñoà Giaøi Thuaät Phaân Tích Cuù Phaùp Earley

Böôùc 2&3

i0=i0+1

S

I0 > ToångLS trong I0 Ñ A

Trang 65

Luaän Toát Nghieäp KS2-K7

A j=1 x=0

Luaät sinh thöù x trong Ij-1 coù

Cho [B --> Ñ α.aβ, i] vaøo trong

daïng [B -->α.aβ, I] vôùi (a=aj) S x=x+1

x > ToångLS trong Ij-1 Ñ

S

Böôùc 4

y=0

Luaät sinh thöù y trong Ij coù daïng [A -->α. , i] S

Tìm trong P caùc luaät sinh coù daïng : Ñ [B -->γ thì cho vaøo Ij taäp : y =y+1

Tìm trong taäp Ii caùc thöïc theå coù daïng : Ñ [B -->α.Aβ, k] thì cho vaøo Ij taäp : [B -->αA .β, k]

Luaät sinh thöù y trong Ij coù daïng [A -->α.Bβ , i] S S

y>LSJ

Böôùc 5&6

Ñ j=j+1

S

j>n (n chieàu daøi chuoãi

Trang 66

Ñ

END

Luaän Toát Nghieäp KS2-K7

START i=1,p=0

luaät sinh thöù p coù daïng A--> ai S p=p+1

i=i+1,p =0

S

p> soá luaät sinh Ñ

S

i>= chieàu daøi chuoãi Ñ

Cho A vaøo trong ti1

Ñ

Böôùc 1

i=1, j=2,p=0 k=1

B

7- Löu ñoà Giaûi thuaät phaân tích cuù phaùp CYK

luaät sinh thöù p coù daïng A--> BC maø B∈ tik

Böôùc 2 Ñ

tij= tij ∪

S S

k=k+ 1

p=p+ 1

k>=j Ñ

S

p> soá luaät sinh Ñ A

Trang 67

Luaän Toát Nghieäp KS2-K7

A

i=i+1

B

(1 ≤ i ≤ n ) AND (1≤ j ≤ n-

Ñ

S i=1 j=j+1

S

j> n (chieàu daøi chuoãi) Ñ END Trang 68

Luaän Toát Nghieäp KS2-K7

VI - THIEÁT KEÁ MOÄT SOÁ FROM NHAÄP - XUAÁT QUANG TROÏNG Döïa vaøo caùc form ñöôïc thieát keá ôû phaàn naøy, laäp trình vieân thieát keá caùc phaàn giao dieän cho boä coâng cuï. a ) Form Nhaäp VP PNC Taäp Kh Khoâng Keát Thuùc

Bieán Khôûi Ñaàu: Baêng nhaäp

Theâm

----Nhaäp Luaät Taäp luaät sinh

Xoùa

Xoùa Luaät

Taäp Kh Keát Thuùc

Theâm Xoùa

Löu File

Ñoàng YÙ

Môû File Trang 69 Boû Qua

Luaän Toát Nghieäp KS2-K7 Form naøy ñöôïc thieát keá ñeå taïo giao dieän khi nhaäp vaên phaïm phi ngöõ caûnh, trong Form cho pheùp, nhaäp, löu hay môû vaên töø file, coù theå boû qua hay chaáp nhaän vaên phaïm vöøa nhaäp.

b) Form Loaïi Boû Caùc Luaät Sinh Roãng, Ñôn Vò, Voâ Duïng Taäp luaät sinh ban ñaàu

Loaïi boû luaät sinh roãng

Taäp luaät sinh keát quaû

Loaïi boû luaät sinh ñv Loaïi boû luaät sinh Vd Loaïi boû heát caùc luaät Ñoùng

Minh hoïa giaû thuaät

Söû duïng form naøy khi thöïc hieän vieát caùc giaûi thuaät loaïi boû caùc luaät sinh roãng, ñôn vò, voâ duïng. Khi baám moät nuùt thì giaûi thuaät töông öùng seõ thöïc hieän.

Trang 70

Luaän Toát Nghieäp KS2-K7

c) Form Chuyeån Vaên Phaïm Veà Daïng Chuaån Chomsky Taäp luaät sinh ban ñaàu

Chomsky >>>

Taäp luaät sinh daïng chuaån Chomsky

Xem VP

Chomsky Xem VP Ñaàu Giuùp Ñôõ Ñoùng Minh hoïa giaû thuaät

Form naøy daønh cho thöïc hieän giaûi thuaät Chomsky, Form thöïc hieän giaûi thuaät Greibach töông töï .

Trang 71

Luaän Toát Nghieäp KS2-K7

d) Form Duøng Ñeå Hieån Thò Vaên Phaïm Goác

Bieán Khôûi Ñaàu

Taäp bieán

G=(V,T,{S },P) Taäp kyù hieäu keát thuùc

Ñoùng

Taäp Luaät Sinh

Form naøy duøng ñeå hieån thò vaên phaïm goác khi ngöôøi söû duïng coù yeâu caàu xem, vaên phaïm goác hieån thò ñaày ñuû :  Bieán khôõi ñaàu :S  Taäp caùc kyù hieäu keát thuùc :T  Taäp caùc kyù hieäu khoâng keát thuùc :V  Taäp caùc luaät sinh :P

Trang 72

Caâu Nhaäp : e) Form Thöïc Hieän Giaûi Thuaät CYK

Luaän Toát Nghieäp KS2-K7

Hieån Thò Baûng phaân Tích T

Phaân tích caâu nhaäp Vaên Phaïm daïng Chomsky

Xem vaên phaïm goác

Giuùp ñôõ

Chuoãi Daãn Xuaát

Caâu Nhaäp :

Taäp luaät sinh P

Caùc traïng thaùi Si

Phaân tích caâu nhaäp Döõ lieäu minh hoïa cho giaûi thuaät bao goàm :  Baûng phaân tích T Xem vaên phaïm  Chuoãi daãn xuaát ra caâu nhaäpgoác  Taäp vaên phaïm ôû daïng chuaån Chomsky Khi nhaäp lieäu xong, ngöôøi söû duïng baám nuùt “Phaân Tích Caâu Nhaäp” Giuùp ñôõ thì giaûi thuaät CYK seõ hieän thöïc.

Chuoãi Daãn f) Form Thöïc Hieän Giaûi Thuaät Earley Xuaát

Trang 73

Luaän Toát Nghieäp KS2-K7

Döõ lieäu minh hoïa cho giaûi thuaät bao goàm :  Caùc traïng thaùi Si  Chuoãi daãn xuaát ra caâu nhaäp  Taäp vaên phaïm P (toång quaùt) Khi nhaäp lieäu xong, ngöôøi söû duïng baám nuùt “Phaân Tích Caâu Nhaäp” thì giaûi thuaät Earley seõ hieän thöïc

Giuùp ÑôõThoâng Tin Nhaän Daïng …Bieân Veà Chöông Trình Soaïn Vaên Phaïm.. VI - môùi THIEÁT KEÁ HEÄ THOÁNG MENU Taïo vaên Bieân Soaïn Töø Ñieån… phaïmÑoùng Heä thoáng vaên Menu cuûa chöông trình ñöôïc thieát keá theo daïng pushdown phaïm (trình hieän ñôn ñaåy xuoáng). haønhMôû vaên 1) Caáu truùc cuûa heä thoáng Menu : phaïmThoaùt Baét Coâng Cuï Ngoân Ñaàu Nhieân Loaït boû caùc luaät sinh … Alt+BCaùc Daïng Chuaån … Alt+DCaùc Giaûi Thuaät Phaân Tích Cuù Phaùp

Ngöõ

Töï Giuùp Ñôõ

Daïng Chuaån ChomskyDaïng Chuaån Greibach

Giaûi Thuaät CYK … Trang 74 Alt+KGiaûi Thuaät Earley… Alt+ESo Saùnh Ñoä Phöùc Taïp

Luaän Toát Nghieäp KS2-K7

2) Hoaït ñoäng cuûa töøng Menu Item ⇒ Baét Ñaàu : • Baét Ñaàu | Taïo Môùi Vaên Phaïm : Khích hoaït process “Nhaäp Vaên Phaïm” cho pheùp ngöôøi söû duïng ñònh nghóa taäp vaên phaïm maø mình seõ laøm vieäc treân noù. • Baét Ñaàu | Ñoùng vaên phaïm hieän haønh : Taäp vaên phaïm hieän haønh ñang laøm vieäc seõ xoùa khoûi vuøng nhôù caáp phaùt cho noù, khi muoán laøm vieäc laïi phaûi thöïc hieän Taïo Môùi Vaên Phaïm • Baét Ñaàu | Môû Vaên Phaïm : Môû vaên phaïm laøm vieäc ñöôïc löu töø file. ⇒ Coâng Cuï : • Coâng Cuï | Loaïi Boû Caùc Luaät Sinh : Kích hoaït Dialog “Loaïi Boû Luaät Sinh” trong Dialog naøy thöïc hieän caùc process sau : + Loaïi boû caùc luaät sinh λ + Loaïi boû caùc luaät sinh ñôn vò + Loaïi boû caùc luaät sinh voâ duïng • Coâng Cuï | Caùc Daïng Chuaån | Daïng Chuaån Chomsky : Kích hoaït process “Daïng Chuaån Chomsky” • Coâng Cuï | Caùc Daïng Chuaån | Daïng Chuaån Greibach : Kích hoaït process “Daïng Chuaån Greibach” • Coâng Cuï | Caùc Giaûi Thuaät Phaân Tích Cuù Phaùp | Giaûi Thuaät CYK : Kích hoaït process “Giaûi thuaät CYK” • Coâng Cuï | Caùc Giaûi Thuaät Phaân Tích Cuù Phaùp | Giaûi Thuaät Earley : Kích hoaït process “Giaûi thuaät Earley” • Coâng Cuï | Caùc Giaûi Thuaät Phaân Tích Cuù Phaùp | So Saùnh Ñoä Phöùc Taïp : Thöïc hieän so saùnh ñoä phöùc taïp cuûa hai giaûi thuaät : “Giaûi thuaät Earley” & “Giaûi thuaät CYK”. ⇒ Ngoân Ngöõ Töï Nhieân • Ngoân Ngöõ Töï Nhieân | Nhaän Daïng : Phaàn aùp duïng giaûi thuaät Earley ñeå nhaän daïng moät caâu nhaäp thuoäc ngoân ngöõ töï nhieân (Tieáng Anh). Trang 75

Luaän Toát Nghieäp KS2-K7

• Ngoân Ngöõ Töï Nhieân | Bieân Soaïn Vaên Phaïm : Coâng cuï duøng ñeå

bieân soaïn taäp vaên phaïm cuûa ngoân ngöõ töï nhieän (laø moät coâng cuï cuûa boä nhaän daïng) • Ngoân Ngöõ Töï Nhieân | Nhaän Daïng : Coâng cuï duøng ñeå bieân soaïn boâ töø ñieån token cuûa caùc töø trong Tieáng Anh. (laø moät coâng cuï cuûa boä nhaän daïng) ⇒ Giuùp Ñôõ • Giuùp Ñôõ | Giuùp Ñôõ : Hích hoaït heä thoáng Help Contents

• Giuùp Ñôõ | Thoâng Tin Veà Chöông Trình : Kích hoaït maøn hình giôùi thieäu thoâng tin veà chöông trình

VII - THIEÁT KEÁ HEÄ THOÁNG TOOLBAR

Pch Pgre   Nhaäp vaên phaïm Xoùa vaên Phaïm Loaïi boû caùc luaät sinh

AX. Big E O CYK

Gram ABC . AX

?

Giaûi Thuaät CYK

Bieân Soaïn Töø Ñieån Bieân Soaïn Vaên Giaûi Thuaät Phaïm Earley Nhaän daïng So Saùnh Ñoä Phöùc Giuùp taïp Ñôõ

Daïng Chuaån Chomsky Daïng Chuaån Greibach Taát caû caùc chöùc naêng hoaït ñoäng cuûa thanh toolbar töông töï nhö hoaït ñoäng cuûa caùc Menu Items töông öùng nhö moâ taû ôû phaàn VI

PHAÀN 5 SO SAÙNH ÑOÄ PHÖÙC TAÏP CUÛA HAI GIAÛI THUAÄT CYK VAØ EARLEY I- GIÔÙI THIEÄU Qua phaàn phaân tích vaø thieát keá, ñeå vieäc thieát keá caùc process phuø hôïp vôùi caùc giaûi thuaät ñaõ trình baøy trong phaàn lyù thuyeát neân Trang 76

Luaän Toát Nghieäp KS2-K7 vieäc tính toaùn ñoä phöùc taïp cuûa CYK vaø Earley khoâng ñöôïc loàng vaøo trong caùc process naøy. Do ñoù trong phaàn naøy chæ daønh rieâng cho vieäc trình baøy caùch hieän thöïc ñeå tính toaùn ñoä phöùc taïp cuûa hai giaûi thuaät treân. Trong phaàn naøy giuùp cho sinh vieân thaáy ñöôïc moät caùch tröïc quan (baèng hình aûnh) ñoä phöùc taïp cuûa hai giaûi thuaät treân caùc loaïi vaên phaïm khaùc nhau cuõng nhö caùch thöùc hieän thöïc tính toaùn ñoä phöùc taïp töø ñoù töï ruùt ra keát luaän cho hai giaûi thuaät naøy.

II- HIEÄN THÖÏC TÍNH ÑOÄ PHÖÙC TAÏP Ñeå hieän thöïc tính ñoä phöùc taïp cuûa hai giaûi thuaät chuùng ta chaáp nhaän caùc giaû thieát sau :  Moãi moät laàn tham khaûo moät luaät sinh laø moät böôùc tính toaùn  Taát caû caùc pheùp toaùn khaùc nhö +,-.*,/ gaùn … ñöôïc boû qua  Khoâng tính ñeán quaù trình chuyeån vaên phaïm sang daïng chuaån Chomsky cho giaûi thuaät CYK.  Do ñoù ñoä phöùc taïp cuûa hai giaûi thuaät CYK vaø Earley chæ phuï thuoäc vaøo soá laàn tham khaûo caùc luaät sinh. YÙ töôûng ñeå tính toaùn ñoä phöùc taïp ta söû duïng moät bieán toaøn cuïc DPT ñeå ñeám soá laàn tham khaûo ñeán caùc luaät sinh hay töøng phaàn töû trong taäp traïng thaùi (ñoái vôùi Earley) hay baûng T(ñoái vôùi CYK). ⇒ Trong code chöông trình choã naøo tham khaûo ñeán nhöõng phaàn töû treân ñeàu taêng bieán DPT leân 1. III- SO SAÙNH THÖÏC NGHIEÄM Sau ñaây laø moät chöông trình trong boä coâng cuï ñöôïc vieát ñeå so saùnh ñoä phöùc taïp cuûa hai giaûi thuaät CYK vaø Earley treân caùc loaïi vaên phaïm khaùc nhau :

Trang 77

Luaän Toát Nghieäp KS2-K7

 Chöông trình cho pheùp ngöôøi söû duïng so saùnh ñoä phöùc taïp cuûa hai giaûi thuaät CYK vaø Earley sau khi ñaõ nhaäp taäp vaên phaïm cho boä coâng cuï.

 Chuoãi caàn so saùnh ñöôïc ñaùnh vaøo oâ “Caâu Nhaäp”. SAU ÑAÂY LAØ CAÙC KEÁT QUAÛ VAØ ÑOÀ THÒ MINH HOÏA :

Trang 78

Luaän Toát Nghieäp KS2-K7 VAÊN PHAÏM G1 (Vaên phaïm bieåu thöùc soá hoc) E T+E E T T F*T T F F (E) F a Caâu nhaäp Length CYK Earley a+a

3

174

115

a+a+a+a

7

1014

237

a+a+a+a+a+a

11

2766

391

a+a+a+a+a+a+a+a

15

5734

577

a+a+a+a+a+a+a+a+a+a

19

10222

795

a+a+a+a+a+a+a+a+a+a+ 23 a+a a+a+a+a+a+a+a+a+a+a+ 27 a+a+a+a

16534

1045

24974

1327

25000

Big O

20000 15000

CY K Earley

10000 5000 0 3

7

11

15

19

23

27

Length

Hình 1: Ñöôøng cong ñoä phöùc taïp theo vaên phaïm G1

Trang 79

Luaän Toát Nghieäp KS2-K7 VAÊN PHAÏM G2 (Coù luaät sinh ñôn vò vaø voâ duïng) S aS | A | C A a B aa C aCb Caâu Nhaäp Length CYK Earley aa 2 14 95 (aa)2 4 79 208 (aa)3 6 216 377 (aa)4 8 449 610 5 (aa) 10 802 915 6 (aa) 12 1299 1300 (aa)7 14 1964 1773 8 (aa) 16 2821 2342 9 (aa) 18 3894 3015

4000 3500

Big O

3000 2500 CY K

2000

Earley

1500 1000 500 0 2

4

6

8

10

12

14

16

18

Length

Hình 2: Ñöôøng cong ñoä phöùc taïp theo vaên phaïm G2

VAÊN PHAÏM G3 (Vaên Phaïm GRE cuûa Jay Earley) X a | Xb | Ya Y e | YdY Trang 80

Luaän Toát Nghieäp KS2-K7 Caâu Nhaäp ededea ededeab4 ededeab10 (ed)4eabb (ed)7eabb (ed)8eabb

Length 6 10 16 12 18 20

CYK 222 658 1312 1074 2880 3782

Earley 97 125 167 200 426 530

4000 3500

Big O

3000 2500

CY K

2000

Earley

1500 1000 500 0 6

10

12

16

18

20

Length

Hình 3: Ñöôøng cong ñoä phöùc taïp

IV- KEÁT LUAÄN theo vaên phaïm G3 Qua chöông trình töï vieát cho boä coâng cuï baèng caùc giaûi thuaät ñaõ trình baøy trong phaàn lyù thuyeát vaø caùc giaû thieát ñeå tính toaùn ñoä phöùc taïp nhö ñaõ neâu ôû phaàn II (vôùi caùch ñaët giaû thieát khaùc nhau thì ñoä phöùc taïp cuûa giaûi thuaät tính ra seõ khaùc nhau) cuøng vôùi caùc döõ lieäu thöïc teá nhaäp vaøo cho töøng loaïi vaên phaïm, toâi coù moät vaøi nhaäp xeùt sau :

 Vôùi vaên phaïm G1 vaø G2 giaûi thuaät Earley luoân luoân coù ñoä phöùc taïp lôùn hôn

 Vôùi taäp vaên phaïm G2 laø loaïi vaên phaïm vöøa coù luaät sinh ñôn vò vaø luaät sinh voâ duïng, do ñoù khi loaïi boû 2 loaïi luaät sinh treân thì taäp vaên phaïm thöïc teá maø CYK thao taùc chæ coøn laø {S DS,Da, Sa} trong khi ñoù Earley phaûi thao taùc treân vaên phaïm goác ban ñaàu. Cho neân khi chieàu daøi chuoãi nhaäp nhoû thì CYK coù ñoä phöùc taïp lôùn hôn, tuy nhieân khi chieàu daøi chuoãi nhaäp taêng leân thì Earley laïi coù ñoä phöùc

Trang 81

Luaän Toát Nghieäp KS2-K7 taïp nhoû hôn raát nhieàu do luùc naøy soá löông phaàn töû trong baûng T sinh ra raát lôùn.

 Veà maët lyù thuyeát giaûi thuaät CYK vaø Earley coù ñoä phöùc taïp thôøi gian laø O(n3), tuy nhieân vôùi Earley thì O(n3) chæ laø caän treân trong khi CYK luoân luoân laø O(n3).

PHAÀN 6 NHAÄN DAÏNG NGOÂN NGÖÕ TÖÏ NHIEÂN I- GIÔÙI THIEÄU Trang 82

Luaän Toát Nghieäp KS2-K7 Ñaây laø phaàn aùp duïng caùc giaûi thuaät phaân tích cuù phaùp ñeå nhaän daïng moät caâu nhaäp thuoäc ngoân ngöõ töï nhieân (Tieáng Anh). Qua phaàn nhaän xeùt vaø ñaùnh giaù hai giaûi thuaät phaân tích cuù phaùp Earley vaø CYK, chuùng ta nhaän thaáy giaûi thuaät CYK khoâng thích hôïp cho vieäc nhaän daïng ngoân ngöõ töï nhieân vôùi caùc lyù do sau : + Phaûi chuyeån vaên phaïm NNTN veà daïng chuaån Chomsky + Soá böôùc thöïc hieän cuûa gt CYK lôùn hôn raát nhieàu so vôùi giaûi thuaät Earley (xem phaàn hieän thöïc so saùnh ñoäphöùc taïp cuûa hai giaûi thuaät naøy ñeå thaáy roõ hôn). Do ñoù trong phaàn aùp duïng nhaän daïng ngoân ngöõ töï nhieân seõ söû duïng giaûi thuaät Earley ñeå thöïc hieän. Trong phaàn naøy thöïc hieän nhieäm vuï : Phaân tích caâu nhaäp vaø in ra chuoãi daãn xuaát neáu caâu nhaäp thuoäc ngoân ngöõ ñaõ cho. Sô ñoà DFD khi nhaän daïng caâu nhaäp : Vaên phaïm

Chuoãi daãn xuaát

User

Caâu nhaäp tieáng Anh

Nhaäp VP NNTN

Nhaän daïngNNTN

Vaên phaïm NNTN

Töø Ñieån Token Chuoãi token cuûa caâu nhaäp

Phaân tích token

Taïo töø ñieån

Töø Quaù trình nhaän daïng moät caâu nhaäp coù theå moâ taû nhö sau : • Chuoãi nhaäp laø moät caâu tieáng Anh seõ ñöôïc ñöa qua boä “phaân tích token”, ñaâu ra seõ laø moät chuoãi caùc token cuûa caâu nhaäp. • Chuoãi token naøy seõ ñöôïc boä “nhaän daïng NNTN” phaân tích theo giaûi thuaät Earley döïa vaøo taäp vaên phaïm NNTN ñònh nghóa tröôùc. • Boä “nhaän daïng NNTN” seõ in ra quaù trình daãn xuaát ra caâu nhaäp neáu noù thuoäc vaên phaïm ñaõ cho. • Boä nhaän daïng chæ nhaän daïng ñöôïc nhöõng töø coù trong töø ñieån, neáu khoâng coù seõ baùo loãi. Neáu chuùng ta taïo ra ñöôïc boä töø ñieån caøng nhieàu töø thì boä nhaän daïng seõ nhaän daïng ñöôïc nhieàu caâu nhaäp hôn. Ví duï :

Trang 83

Luaän Toát Nghieäp KS2-K7

Phaân Tích Token

i see a book on the table.

Caùc token

Nhaän daïng NNTN

Caây daãn xuaâ`t

II- XAÂY DÖÏNG TÖØ ÑIEÅN CAÙC TOKEN Ñeå phuïc vuï cho vieäc nhaän daïng caâu nhaäp, ta caàn phaûi xaây döïng moät boä töø ñieån cho ngoân ngöõ ñoù. Ñeå taïo ra ñöôïc boä töø ñieån naøy caàn coù moät söï goùp yù vaø trôï giuùp raát nhieàu cuûa caùc chuyeân gia veà ngoân ngöõ hoïc, bieân soaïn töø ñieån. Thöïc chaát cuûa boä töø ñieån token laø phaân caùc töø ra thaønh nhieàu nhoùm, seõ nhoùm ñöôïc ñaïi dieän baèng moät token. Trong luaän vaên naøy, toâi xin trình baøy moät caùch bieân soaïn boä töø ñieån token nhö sau : Boä töø ñieån ñöôïc chia laøm 4 tröôøng Token

lexme

Loaïi töø

Nghóa Tieáng Vieät

Chöùa Chöùa lemex Chöùa giaù trò Caùc töø trong tieáng Anh chia ra thaønh caùc nhoùm nhö sau : cuûa loaïi töø laø token token Token Loaïi töø n p v t s o d a j b ví duï : Token n n p p v v t t

Noun Prepositional Intransitive verb Transitive verb Pronoun_subject Pronoun_Object Determiners Article Adj. Tobe Lexme

book pen to with go run like see

Loaïi töø Noun Noun Prepositional Prepositional Intransitive verb Intransitive verb Transitive verb Transitive verb

Nghóa Vieät quyeån saùch tôø baùo tôùi vôùi ñi chaïy thích thaáy Trang 84

Luaän Toát Nghieäp KS2-K7 s I Pronoun_S toâi s he Pronoun_S anh ta o me Pronoun_O toâi o her Pronoun_O coâ aáy a an Article moät a a Article moät a the Article d that Determiners kia d this Determiners naøy j beautiful Adj ñeïp … … … … Xin xem theâm phaàn keát quaû hieän thöïc boä töø ñieån ôû phaàn 8. III- VAÊN PHAÏN NGOÂN NGÖÕ TÖÏ NHIEÂN Sau ñaây laø vaên phaïm coù theå xöû lyù ngoân ngöõ töï nhieân. Khi thöïc hieän giaûi thuaät Earley cho vaên phaïm naøy thì caâu nhaäp laø caâu tieáng Anh. (0) (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) (14) (15) (16) (17) (18) (19) (20) (21) (22) (23) (24) (25)

<Sentence> <Sentence> <Sentence>

                         

<Sentence> s b n j d a r p Trang 85

Luaän Toát Nghieäp KS2-K7 (26) (27) (28) (29) (30) (31) (32)



      

o t v

Ví duï :

Trang 86

Luaän Toát Nghieäp KS2-K7

Ñeå thaáy roõ hôn caùc keát quaû töø vieäc bieân soaïn töø ñieån token ñeán nhaän daïng xin xem phaàn 7 “Minh hoïa keát quaû” phaàn “Nhaän daïng ngoân ngöõ töï nhieân”.

PHAÀN 7

Trang 87

Luaän Toát Nghieäp KS2-K7

TÌM HIEÅU WINDOWS HELP VAØ PHAÀN MEÀM XAÂY DÖÏNG HEÄ THOÁNG HELP WINDOWS HELP DESIGNER PRO I- GIÔÙI THIEÄU Moät tieâu chuaån chaát löôïng cuûa moät chöông trình chuyeân nghieäp laø phaïm vi vaø möùc ñoä hoaøn chænh cuûa heä thoáng Help cuûa noù. Trong chöông naøy, chuùng ta tìm hieåu caùc vaán ñeà sau :  Caùc khaùi nieäm lieân quan ñeán vieäc xaây döïng heä thoáng Help  Caùc böôùc caàn thieát ñeå xaây döïng heä thoáng Help chuyeân nghieäp  Coâng cuï Windows Help Desginer Pro ñeå xaây döïng heä thoàng Help II- TÌM HIEÅU WINDOWS HELP 1- Caùc Khaùi Nieäm  Topic : Ñôn vò thoâng tin cuûa heä thoáng Help, ñöôïc vieát cho moät chuû ñeà. Chuû ñeà bao goàm chuoãi vaên baûn xuaát hieän trong heä thoáng Help, Chuû ñeà ñöôïc lieân keát vôùi pop_up (hoäp baät leân), hot spots (vuøng taùc ñoäng) vaø caùc leänh nhaûy theo chuoãi ngöõ caûnh keát hôïp vôùi chuû ñeà.  Pop_up : Vaên baûn cuûa chuû ñeà tham chieáu ñöôïc xuaát hieän ñuùng luùc trong heä thoáng Help vaø coù hình chöõ nhaät bao quanh. Pop_up seõ maát ñi khi ngöôøi söû duïng baám chuoät ra phía ngoaøi khung.  Context String : (chuoãi ngöõ caûnh). Chuoãi tham chieáu ñeán chuû ñeà vaø ñöôïc duøng gioáng nhö teân bieán töôïng tröng trong heä thoáng Help. Moïi tham chieáu ñeán chuû ñeà ñöôïc hình thaønh thoâng qua chuoãi ngöõ caûnh.  Hot spot : Vuøng aûnh höôûng cuûa chuoät trong vaên baûn hay aûnh coù lieân keát vôùi chuoãi ngöõ caûnh hay söï thöïc hieän cuûa marco. Vieäc nhaáp chuoät vaøo hot spot seõ laøm nhaûy ñeán chuû ñeà coù chuoãi ngöõ caûnh tham chieáu ñeán, ngöôøi söû duïng nhaän bieát ñöôïc hot spot khi thaáy con chuoät ñoåi töø hình muõi teân sang daïng baøn tay.  Marco : Laø khaû naêng saün coù cuûa Windows Help nhaèm thöïc hieän moät soá taùc vuï trôï giuùp. Caùc marco coù theå ñöôïc goïi vaøo luùc môû taäp tin help, naûy ñeán moät chuû ñeà, hay choïn hot spot, nuùt trôï giuùp help, menu. Heä thoáng Help coù saün 52 marco chuaån.  Jump : Laø chuyeån ñeán moät chuû ñeà khaùc theo yù muoán cuûa ngöôøi duøng

Trang 88

Luaän Toát Nghieäp KS2-K7  Taäp tin RTF : Ñaây laø caùc taäp tin Rich Text Format coù theå ñöôïc soaïn thaûo nhôø chöông trình soaïn vaên baûn coù hoã trôï file RTF. Microsoft Word for Windows coù theå taïo ra file RTF. Taäp tin RTF chöùa vaên baûn nguoàn ñeå taïo ra heä thoáng Help, thoâng qua trình bieân dòch ñeå chuyeån thaønh taäp tin .HLP  Taäp Tin HPJ : (Help Project) - Ñaây laø taäp tin chuû ñeà chöùa caùc leänh lieân quan ñeán taäp tin .RTF nhaèm chuyeån ñeán trình bieân dòch Help caùc quan heä cuûa chuoãi ngöõ caûnh, aûnh bipmap, caùc tuøy choïn caáu hình nhaèm ñieàu khieån Help Compiler. Taäp tin .HPJ daïng maõ ASCII thoâng thöôøng.  Help ContextID : Soá nguyeân keát hôïp vôùi chuoãi ngöõ caûnh ñöôïc lieät keâ trong phaàn [MAP] cuûa taäp tin .HPJ. Caùc soá nguyeân naøy seõ ñöôïc duøng nhö giaù trò cuûa thuoäc tính Help ContextID cuûa control hay bieåu maãu.

Help File HELPFILE.HLP (File thöïc thi) Help Project File HELPFILE.HPJ

Help Compiler HCRTF.EXE

Bitmap File(s) *.BMP Graphics

SHED Topics File(s) File(s) *.SHG *.RTF Graphics vaø Save döôùi Hot spot daïng file Rich Text Format Hình 1 : Caùc thaønh phaàn cuûa heä thoáng help 2- Caùc Thaønh Phaàn Trong File Help Project Phaàn [OPTION] [FILES] [BUILDTAGS]

Muïc ñích vaø moâ taû Xaùc ñònh caùc tuøy choïn ñeå ñieàu khieån quaù trình bieân dòch Lieät keâ taát caû caùc file tieâu ñeà vaên baûn RTF chöùa trong chöông trình ñaõ ñöôïc dòch, phaàn naøy laø baét buoäc. Xaùc ñònh caùc build ñeå söû duïng trong chöông trình dòch. Phaàn naøy laø tuøy choïn Trang 89

Luaän Toát Nghieäp KS2-K7 [CONFIG] [BITMAP]

[MAP] [ALIAS] [WINDOWS]

Taïo ra caùc menu cuûa taùc giaû vaø caùc nuùt baám trong file help Chæ ñònh caùc file bitmap chöùa trong chöông trình ñöôïc dòch. Phaàn naøy khoâng baét buoäc phaûi coù neáu file help project ñaõ lieät keâ danh saùch caùc ñöôøng daãn cho caùc file bitmap trong phaàn [OPTION] baèng caùch söû duïng tuøy choïn BMROOT. Phaàn naøy toå chöùc caùc chuoãi noäi dung vôùi caùc soá ngueân HelpContextID. Phaàn naøy laø tuøy choïn Gaùn moät hay nhieàu chuoãi noäi dung ñeán tieâu ñeà Help maãu, phaàn naøy laø tuøy choïn. Ñònh nghóa caùc tính chaát cuûa cöûa soå Help cuøng vôùi kieåu vaø caùc tính chaát cuûa moïi cöûa soå thöù hai coù theå ñöôïc söû duïng trong heä thoáng Help. Phaàn naøy laø baét buoäc neáu baïn coù söû duïng cöûa soå thöù 2

Caùc thaønh phaàn cuûa tham soá Option trong file .HPJ : + BMRoot : Chæ thö muïc chöùa caùc file hình aûnh ñöôïc söû duïng trong file .rtf + CharSet : Chæ ñònh taäp hôïp caùc kyù töï default + Compress : Chæ ñònh caùch thöùc neùn cuûa file help. + Content : Chæ ñònh Topic ID + CNT : Chæ ñònh file content cuûa file help. + Copyright : Duøng ñeå theâm thoâng tin veà version vaø taùc giaû cuûa file help. + BDCS : Duøng chæ ñònh Topic ID söû duïng maõ 1 byte hay 2 byte. + HLP : Chæ ñònh teân cuûa file help 3- Caùc Böôùc Caàn Thieát Ñeå Xaây Döïng Heä Thoáng Help  Xaùc ñònh roõ ñoái töôïng söû duïng Help, chæ roõ trình ñoä, kyõ naêng vaø ñònh höôùng taùc vuï cuûa ngöôøi duøng Help. Neáu caàn phaûi thaønh laäp nhieàu heä thoáng help ñeå aùp duïng cho caùc loaïi ngöôøi söû duïng khaùc nhau.  Thieát keá kieán truùc cuûa chuû ñeà theå hieän caùc quan heä giöõa caùc chuû ñeà maø baïn seõ ñöa vaøo heä thoáng Help. Baét ñaàu baèng phaàn toång quaùt nhaát cuûa kieán truùc roài theâm caùc taàng keá tieáp ôû möùc thaáp hôn.  Thieát keá kòch baûn minh hoïa caùc neùt chính cho moãi chuû ñeà help, caùc töø khoùa cho moãi chuû ñeà hay caùc töø ñöôïc tham chieáu ñeán caùc chuû ñeà.  Neáu moãi kòch baûn coù nhieàu neùt chính (3 hay 4) thì neân chuù yù caån thaän vieäc taùch moät chuû ñeà lôùn thaønh caùc chuû ñeà nhoû hôn.  Muïc tieâu thoáng nhaát laø coá gaéng laøm cho moãi chuû ñeà naèm goïn trong moät trang Help (Toaøn maøn hình khoâng caàn coù thanh cuoán). Trang 90

Luaän Toát Nghieäp KS2-K7

III - COÂNG CUÏ WINDOWS HELP DESGINER PRO 1- Giôùi thieäu boä coâng cuï Coâng cuï naøy ñöôïc laáy töø Internet ôû ñòa chæ :http//www.devgr.com, ñòa chæ Email lieân laïc : [email protected] Vì laø coâng cuï chöa coù baûn quyeàn neân ôû cuoái moãi Topic seõ coù doøng vaên baûn caûnh baùo cuûa nhaø saûn xuaát. Neáu ñaêng kyù (traû tieàn) thì doøng chuù thích naøy seõ maát. Qua phaàn trình baøy ôû treân ta nhaän thaáy ñeå thieát keá moät heä thoáng help ngöôøi laäp trình caàn phaûi nhôù raát nhieàu maõ ñeå cheøn vaøo file .RTF . Nick Ameladiotis ñaõ ñöa ra boä coâng cuï WINDOWS HELP DESGINER PRO nhaèm giuùp cho nhaø laäp trình thieát keá moät heä thoáng help hoaøn chænh maø khoâng caàn nhôù ñeán caùc maõ ñieàu khieån. Boä coâng cuï gioáng nhö moät trình soaïn thaûo vaên baûn, khi soaïn thaûo moät Topic naøo thì click vaøo muïc Topic, ñaët teân vaø baét ñaàu soaïn thaûo, boä soaïn cho pheùp cheøn vaøo caùc hình aûnh, file AVI, caùc kyù hieäu symbol. Ñaàu ra cuûa boä coâng cuï laø caùc file : HELPFILE.CNT HELPFILE.HPJ HELPFILE.RTF Caùc file naøy seõ qua Compliler Help ñeå dòch qua file thöïc thi .HLP Ñeå bieát ñöôïc chi tieát hôn veà boä coâng cuï naøy xin vieáng thaên trang WEB : http//www.devgr.com Chuông trình vieát trong luaän vaên toát nghieäp söû duïng boä coâng cuï naøy ñeå taïo ra file help thöïc thi.

2- File Hep Project cuûa chöông trình ; This file is maintained by WHD. Do not modify this file directly. ; ; This help project was created with Windows Help Designer V 2.1.5.3 ; *** UNREGISTERED *** ; Windows Help Designer is copyright (C) 1996, 1997, by Nick Ameladiotis ; Visit http://www.devgr.com for more informations ; [OPTIONS] REPORT=Yes ERRORLOG=H:\KS2_K7\LVTN_KS2\WHELP\Automat.LOG [WINDOWS] main="", , 0,(255,255,225),(192,192,192),0 ; Trang 91

Luaän Toát Nghieäp KS2-K7 [FILES] Automat.RTF [MAP] Topic1=0x1 Topic2=0x2 Topic3=0x3 Topic4=0x4 Topic5=0x5 Topic6=0x6 Topic7=0x7 Topic8=0x8 Topic9=0x9 Topic10=0xA Topic11=0xB V=0xC S=0xD T=0xE Topic15=0xF Topic16=0x10 Topic17=0x11 Topic18=0x12 Topic19=0x13 Topic20=0x14

Trang 92

Luaän Toát Nghieäp KS2-K7

PHAÀN 8 GIÔÙI THIEÄU KEÁT QUAÛ CHÖÔNG TRÌNH Maøn Hình Giôùi Thieäu :

I-

GIÔÙI THIEÄU HEÄ THOÁNG HELP Trang 93

Luaän Toát Nghieäp KS2-K7 1- Maøn Hình Help Contents

2-

Ví duï moät noäi dung Help

Trang 94

Luaän Toát Nghieäp KS2-K7

II- BIEÁN ÑOÅI VAÊN PHAÏM

1- Nhaäp Vaên Phaïm Laøm Vieäc

Trang 95

Luaän Toát Nghieäp KS2-K7

Taäp vaên phaïm maø caùc giaûi thuaät seõ laøm vieäc coù theå ñöôïc nhaäp tröïc tieáp vaø löu vaøo file, coù theå laáy taäp vaên phaïm ñaõ löu xuoáng file ñeå söû duïng baèng caùch söû duïng nuùt “Môû Vaên Phaïm”. Neáu coù luaät sinh roãng thì ñöôïc nhaäp laø #.(ví duï A #)

2- Loaïi Boû Caùc Luaät Sinh Roãng

Trang 96

Luaän Toát Nghieäp KS2-K7

Ghi chuù : Vaên phaïm nhaäp cho vieäc loaïi boû caùc luaät sinh roãng nhö sau : S ADaC A BC B b B # C D C # D d Neáu coù luaät sinh roãng thì ñöôïc nhaäp laø #.(ví duï A #)

2- Loaïi Boû Caùc Luaät Sinh Ñôn Vò Trang 97

Luaän Toát Nghieäp KS2-K7

Ghi Chuù : Vaên phaïm söû duïng cho vieäc loaïi boû luaät sinh ñôn vò nhö sau SAa SB BA Bbb Aa Abc AB Neáu coù luaät sinh roãng thì ñöôïc nhaäp laø #.(ví duï A #)

3- Loaïi Boû Caùc Luaät Sinh Voâ Duïng

Trang 98

Luaän Toát Nghieäp KS2-K7

Ghi Chuù : Vaên phaïm söû duïng cho caùc luaät sinh voâ duïng nhö sau: S aS S A S C A a B aa CaCb Neáu coù luaät sinh roãng thì ñöôïc nhaäp laø #.(ví duï A #)

III- CAÙC DAÏNG CHUAÅN 1-Daïng Chuaån Chomsky Trang 99

Luaän Toát Nghieäp KS2-K7

Ghi chuù : Vaên phaïm nhaäp cho daïng chuaån Chomsky coù daïng S Aba AaaB BAc Neáu coù luaät sinh roãng thì nhaäp laø # (ví duï : A #)

2-Daïng Chuaån Greibach

Trang100

Luaän Toát Nghieäp KS2-K7

Ghi chuù : Vaên phaïm nhaäp cho daïng chuaån Greibach coù daïng SAB SBBB A BAA A aa BDD DAA Neáu coù luaät sinh roãng thì nhaäp laø # (ví duï : A #)

IV- GIAÛI THUAÄT PHAÂN TÍCH CUÙ PHAÙP 1- Giaûi Thuaät Earley Trang101

Luaän Toát Nghieäp KS2-K7

Ghi chuù : Vaên phaïm nhaäp cho daïng chuaån Chomsky coù daïng E T+E E T TF*T TF F(E) F a Neáu coù luaät sinh roãng thì nhaäp laø # (ví duï : A #)

2- Giaûi Thuaät CYK

Trang102

Luaän Toát Nghieäp KS2-K7

Ghi chuù : Vaên phaïm nhaäp cho daïng chuaån Chomsky coù daïng E T+E E T TF*T TF F(E) F a Neáu coù luaät sinh roãng thì nhaäp laø # (ví duï : A #)

V- SO SAÙNH ÑOÄ PHÖÙC TAÏP CUÛA HAI GIAÛI THUAÄT EARLEY VAØ CYK

Trang103

Luaän Toát Nghieäp KS2-K7

Ghi Chuù : Vaên phaïm duøng ñeå so saùnh : E T+E E T TF*T TF F(E) F a Neáu coù luaät sinh roãng thì nhaäp laø # (Ví duï A #)

VI- NHAÄN DAÏNG NGOÂN NGÖÕ TÖÏ NHIEÂN

1- Bieân Soaïn Töø Ñieån Trang104

Luaän Toát Nghieäp KS2-K7

Ñaây laø coâng cuï duøng ñeå bieân soaïn boä töø ñieå token duøng ñeå söû duïng cho vieäc nhaän daïng ngoân ngöõ töï nhieân Ñeå boä nhaän daïng nhaän bieát ñöôïc caøng nhieàu caâu nhaäp thì boä töø ñieån phaûi ñöôïc ñònh nghóa caøng lôùn.

2- Bieân Soaïn Vaên Phaïm

Trang105

Luaän Toát Nghieäp KS2-K7

Coâng cuï naøy cho pheùp ngöôøi söû duïng bieân soaïn laïi taäp vaên phaïm ñöôïc löu töø file (hay bieân soaïn laïi môùi vaø löu xuoáng file) Xin xem theâm phaàn 6 ñeå bieát chi tieát ñònh nghóa taäp vaên phaïm ngoân ngöõ töï nhieân.

3- Nhaän Daïng Ngoân Ngöõ Töï Nhieân

Trang106

Luaän Toát Nghieäp KS2-K7

Neáu caâu nhaäp thuoäc ngoân ngöõ töï nhieân thì boä coâng cuï seõ in chuoãi daãn xuaát cho noù, ngöôïc laïi baùo loãi laø “caâu nhaäp khoâng thuoäc vaên phaïm” Ñeå boä nhaän daïng nhaän bieát ñöôïc caøng nhieàu caâu nhaäp thì boä töø ñieån phaûi ñöôïc ñònh nghóa caøng lôùn.

PHAÀN 9 PHUÏ LUÏC - MAÕ CHÖÔNG TRÌNH Trang107

Luaän Toát Nghieäp KS2-K7 GIAÛI THUAÄT EARLEY // gtEARLEY.cpp : implementation file #include "stdafx.h" #include "Automat.h" #include "gtEARLEY.h" #ifdef _DEBUG #define new DEBUG_NEW #undef THIS_FILE static char THIS_FILE[] = __FILE__; #endif ///////////////////////////////////////////////////////////////////////////// // gtEARLEY dialog //====================================== gtEARLEY::gtEARLEY(CWnd* pParent /*=NULL*/) : CDialog(gtEARLEY::IDD, pParent) { //{{AFX_DATA_INIT(gtEARLEY) //}}AFX_DATA_INIT } void gtEARLEY::DoDataExchange(CDataExchange* pDX) { CDialog::DoDataExchange(pDX); //{{AFX_DATA_MAP(gtEARLEY) DDX_Control(pDX, IDC_EDIT_STR, m_chuoi_nhap); DDX_Control(pDX, IDC_LIST_I, m_list_thuc_the); DDX_Control(pDX, IDC_LIST_P, m_list_p); DDX_Control(pDX, IDC_LIST_DAN_XUAT, m_list_dan_xuat); //}}AFX_DATA_MAP } BEGIN_MESSAGE_MAP(gtEARLEY, CDialog) //{{AFX_MSG_MAP(gtEARLEY) ON_BN_CLICKED(IDC_BUTTON_EARLEY, OnButtonEarley) ON_BN_CLICKED(IDC_BUTTON_VPDAU, OnButtonVP_Goc) ON_BN_CLICKED(IDC_BUTTON_HELP, OnButtonHelp) ON_EN_CHANGE(IDC_EDIT_STR, OnChangeChuoi_Nhap) //}}AFX_MSG_MAP END_MESSAGE_MAP() ///////////////////////////////////////////////////////////////////////////// // gtEARLEY message handlers BOOL gtEARLEY:: OnInitDialog() { int soluat;//So luat sinh da luu int i; CString luatsinh; CDialog::OnInitDialog(); soluat=ArrayVePhai.GetSize(); char st[250]; char str[250]; Trang108

Luaän Toát Nghieäp KS2-K7 //Cho hien lai tap luat sinh for(i=0;i<soluat;i++) { luatsinh=ArrayVeTrai[i]+"---->"+ArrayVePhai[i]; strcpy(str,LPCTSTR(luatsinh)); sprintf(st,"(%d) %s",i,str); m_list_p.AddString(st); } //Copy cac bien toan cuc cho Dialog VPBanDau BanDau.ArrayKkt.Copy(ArrayKkt); BanDau.ArrayKt.Copy(ArrayKt); BanDau.ArrayVePhai.Copy(ArrayVePhai); BanDau.ArrayVeTrai.Copy(ArrayVeTrai); BanDau.ArrayLuatSinh.Copy(ArrayLuatSinh); BanDau.BienKhoiDau=BienKhoiDau; return TRUE; } //==================================== //Khoi dong mot con tro items *gtEARLEY::Init(items *f) { f=NULL; return f; } //==================================== //Khoi dong tap thuc the void gtEARLEY::Init_thucthe() { int i; for (i=0;i<MAX; i++) tapthucthe[i]=Init(tapthucthe[i]); } //Dua du lieu vao tap thuc the //====================================== items *gtEARLEY::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; Trang109

Luaän Toát Nghieäp KS2-K7 } if(q==pt) pt=p; else before->link=p; p->link=q; return (pt); } //============================================= = //Hien thi cac trang thai trong tap thuc the void gtEARLEY::Display_Items(items *f, int th) { items *q; char st[20]; char ft[10]; CString trangthai; CString str_t,str_s; int ls,ch,s;//luat sinh, dau cham , trang thai q=f; sprintf(st,"TrÁng ThÀi : S[%d]",th); m_list_thuc_the.AddString(st); while(q!=NULL) { ls=q->p;//lay so thu tu luat sinh ch=q->i;//Lay vi tri dau cham s=q->f;//lay vi tri con tro str_t=StrBeforeDot(ls,ch); str_s=StrAfterDot(ls,ch); sprintf(ft,"%d ]",s); trangthai="[ " + ArrayVeTrai[ls]+"---->"+str_t+ " . "+str_s+" , "+ft; m_list_thuc_the.AddString(trangthai); q=q->link; } } //============================================= = void gtEARLEY::OnButtonEarley() { // TODO: Add your control notification handler code here CString str; CString stdx; int chieudaichuoi; int i,ls,soluatdanxuat; char st[50]; m_chuoi_nhap.GetWindowText(str); chieudaichuoi=str.GetLength(); m_list_thuc_the.ResetContent(); m_list_dan_xuat.ResetContent(); DanXuat_So.RemoveAll(); Trang110

Luaän Toát Nghieäp KS2-K7 DanXuat_Chuoi.RemoveAll(); Init_thucthe(); luat123(); luat456(); if (chieudaichuoi==0) Display_Items(tapthucthe[0],0); else { for (i=0;i<=chieudaichuoi; i++) if(tapthucthe[i]!=NULL) Display_Items(tapthucthe[i],i); else { sprintf(st,"Læi TÁi Kü Tø NhËp Th÷ %d",i); m_list_thuc_the.AddString(st); m_list_thuc_the.AddString("CÀc TËp TrÁng ThÀi Trê VÒ Sau Lª Ræng"); i=chieudaichuoi+1; } } ls=KiemTraThuocLG(chieudaichuoi); if(ls==-1) m_list_dan_xuat.AddString("Chuæi NhËp Kh¤ng Thuèc VŸn PhÁm !"); else {//In ra ccay dan xuat m_list_dan_xuat.AddString("+ Chuæi NhËp Thuèc VŸn PhÁm !"); XayDungTapT_N(); ChuoiDanXuat(ls,ArrayVePhai[ls].GetLength(),0,chieudaichuoi); soluatdanxuat=DanXuat_So.GetSize(); for(i=0;i<soluatdanxuat;i++) stdx=stdx+DanXuat_So[i]+" "; m_list_dan_xuat.AddString("+ Th÷ Tø CÀc LuËt Sinh Tham Gia Vªo QuÀ TrØnh D…n XuÊt :"); InDanXuat(stdx,114); m_list_dan_xuat.AddString("+ Chuæi D…n XuÊt Ra Chuæi NhËp :"); DanXuatRaChuoiNhap(); stdx=""; soluatdanxuat=DanXuat_Chuoi.GetSize(); for(i=0;i<soluatdanxuat;i++) stdx=stdx+DanXuat_Chuoi[i]; /*int lendx; int j; CString temp; soluatdanxuat=DanXuat_Chuoi.GetSize(); for(i=0;i<soluatdanxuat;i++) { temp=DanXuat_Chuoi[i]; lendx=temp.GetLength(); for(j=0;j
Luaän Toát Nghieäp KS2-K7 stdx=stdx.Left(stdx.GetLength()-2); InDanXuat(stdx,72); } } //============================================= = //TÛnh tËp trÁng thÀi S0 void gtEARLEY::luat123() { int i; int kq23; int soluatsinh; soluatsinh=ArrayVeTrai.GetSize(); //luat 1 for(i=0;i<soluatsinh;i++) { if (ArrayVeTrai[i]==BienKhoiDau) if (ArrayVePhai[i]=="#") tapthucthe[0]=Insert_data(tapthucthe[0],i,1,0); else tapthucthe[0]=Insert_data(tapthucthe[0],i,0,0); }//het luat 1 do { kq23=luat23(); } while (kq23==1); } //Thuc hien luat thu 3 int gtEARLEY::luat23() { items *q; items *pt; int soluat; int i,flay; q=tapthucthe[0]; flay=0; soluat=ArrayVeTrai.GetSize(); while(q!=NULL) { if (ChrAfterDot(q)=="")//neu dau cham o sau cung {//luat 2 pt=tapthucthe[0];//quay lai tap thuc the i=q->f while(pt!=NULL) { if(ChrAfterDot(pt)==ArrayVeTrai[q->p]) if(KiemTraTrangThai(0,pt->p,(pt->i)+1,0)==0) {tapthucthe[0]=Insert_data(tapthucthe[0],pt->p,(pt>i)+1,0); flay=1;} Trang112

Luaän Toát Nghieäp KS2-K7 pt=pt->link; } } else //luat 3 { for (i=0;i<soluat;i++) if (ArrayVeTrai[i]==ChrAfterDot(q)) { if (ArrayVePhai[i]=="#") { if(KiemTraTrangThai(0,i,1,0)==0) tapthucthe[0]=Insert_data(tapthucthe[0],i,1,0); } else if(KiemTraTrangThai(0,i,0,0)==0) tapthucthe[0]=Insert_data(tapthucthe[0],i,0,0); } } q=q->link; } if (flay==1) return 1; else return 0; } //Thuc hien luat so 4 void gtEARLEY::luat456() { CString str; int j,chieudaichuoi; items *q; CString a; m_chuoi_nhap.GetWindowText(str); chieudaichuoi=str.GetLength(); for (j=0;jp),(q->i)+1,(q->f))==0) tapthucthe[j+1]=Insert_data(tapthucthe[j+1],(q->p),(q>i)+1,(q->f)); q=q->link; } //het luat 4 luat56(j+1);//ap dung lien tiep luat 5 va 6 cho den khi khong them va duoc nua } } Trang113

Luaän Toát Nghieäp KS2-K7 //========================================== //Thuc hien luat so 5 va so 6 void gtEARLEY::luat56(int th) { items *q;// con tro cua tap j=th items *pt;//con tro cua tap i int i; int soluat; q=tapthucthe[th]; soluat=ArrayVeTrai.GetSize(); while(q!=NULL) { if (ChrAfterDot(q)=="")//neu dau cham o sau cung {//luat 5 pt=tapthucthe[q->f];//quay lai tap thuc the i=q->f while(pt!=NULL) { if(ChrAfterDot(pt)==ArrayVeTrai[q->p]) if(KiemTraTrangThai(th,pt->p,(pt->i)+1,pt->f)==0) tapthucthe[th]=Insert_data(tapthucthe[th],pt->p,(pt>i)+1,pt->f); pt=pt->link; } } else {//luat 6 for (i=0;i<soluat;i++) if (ArrayVeTrai[i]==ChrAfterDot(q)) { if (ArrayVePhai[i]=="#") { if(KiemTraTrangThai(th,i,1,th)==0) tapthucthe[th]=Insert_data(tapthucthe[th],i,1,th); } else if(KiemTraTrangThai(th,i,0,th)==0) tapthucthe[th]=Insert_data(tapthucthe[th],i,0,th); } } q=q->link; } }//ket thuc luat56 //============================================= === //Tra ve chuoi ky tu truoc dau cham CString gtEARLEY::StrBeforeDot(int ls, int ch) { int i; Trang114

Luaän Toát Nghieäp KS2-K7 CString Temp,Vp; Vp=ArrayVePhai[ls]; Temp=""; for(i=0; ip); ch=(pt->i); Vp=ArrayVePhai[sl]; if (chp==p) && (q->i==i) && (q->f==ft)) return 1; else q=q->link; } return 0; } Trang115

Luaän Toát Nghieäp KS2-K7 void gtEARLEY::OnButtonVP_Goc() { // TODO: Add your control notification handler code here BanDau.DoModal(); } int gtEARLEY::KiemTraThuocLG(int th) { int i,len; int soluat; if (tapthucthe[th]==NULL) return -1;//chuoi khong thuoc van pham else { soluat=ArrayVeTrai.GetSize(); for (i=0; i<soluat;i++) { len=ArrayVePhai[i].GetLength(); if (ArrayVeTrai[i]==BienKhoiDau) if(KiemTraTrangThai(th,i,len,0)==1) return i; } } return -1; } //============================================= ====== void gtEARLEY::ChuoiDanXuat(int ls,int ch, int i, int j) { char stt[10]; int k,l,m,r; items *q; items *pt; CString Vp; sprintf(stt,"%d",ls); DanXuat_So.Add(stt); Vp=ArrayVePhai[ls]; m=Vp.GetLength(); k=m-1; l=j; while(k!=-1) { if (FindChar(Vp[k],TapT)==1) { k=k-1; l=l-1; } else Trang116

Luaän Toát Nghieäp KS2-K7 { q=tapthucthe[l]; while(q!=NULL) { if(ArrayVeTrai[q->p]==Vp[k] && ChrAfterDot(q)=="") { r=q->f; pt=tapthucthe[r];//tim trong tap thuc the r=q->j; while(pt!=NULL) { if((ChrAfterDot(pt)==Vp[k])&&(k==pt->i) && ((pt>f)==i) && (ArrayVePhai[pt->p]==ArrayVePhai[ls])&&//(ArrayVePhai[pt>p].GetLength()==m) && (ArrayVeTrai[pt->p]==ArrayVeTrai[ls])) { ChuoiDanXuat(q->p,q->i,r,l);//ArrayVePhai[q>p].GetLength(),r,l); k=k-1; l=r; pt=NULL; q=NULL; } else { pt=pt->link; if (pt==NULL) q=q->link; } }//end while pt }//end if else q=q->link; }//end while q }//end else }//end while k }//end function //============================================= = //tra ve 1 neu co tra ve 0 neu khong co int gtEARLEY::FindChar(CString string, CString V) { if (V.Find(string)!=-1) return 1; else return 0; } //============================================= void gtEARLEY::XayDungTapT_N() { Trang117

Luaän Toát Nghieäp KS2-K7 int sokytu; int i; //Xay dung tap T sokytu=ArrayKt.GetSize(); for(i=0;i<sokytu;i++) TapT=TapT+ArrayKt[i]; //Xay dung tap N sokytu=ArrayKkt.GetSize(); for(i=0;i<sokytu;i++) TapN=TapN+ArrayKkt[i]; } //============================================= == void gtEARLEY::InDanXuat(CString stdx,int so) { CString s1; CString s2; while (stdx.GetLength()>so) { s1=stdx.Left(so); m_list_dan_xuat.AddString(s1); s2=stdx.Mid(so,stdx.GetLength()); stdx=s2; } m_list_dan_xuat.AddString(stdx); } //======================================= void gtEARLEY::DanXuatRaChuoiNhap() { int i,n,l,k,j; int len_so,len_chuoi; CString st,str,str1; len_so=DanXuat_So.GetSize(); i=atoi(DanXuat_So[0]); DanXuat_Chuoi.Add(ArrayVeTrai[i]); DanXuat_Chuoi.Add("=>"); DanXuat_Chuoi.Add(ArrayVePhai[i]); DanXuat_Chuoi.Add("=>"); len_chuoi=DanXuat_Chuoi.GetSize(); n=len_chuoi-2; for(j=1;j=0) { Trang118

Luaän Toát Nghieäp KS2-K7 if (st[k]==ArrayVeTrai[i]) { str=st.Left(k); str=str+ArrayVePhai[i]; str1=st.Mid(k+1,st.GetLength()); str=str+str1; DanXuat_Chuoi.Add(str); DanXuat_Chuoi.Add("=>"); len_chuoi=DanXuat_Chuoi.GetSize(); n=len_chuoi-2; k=-1; } else k=k-1; }//while }//for } void gtEARLEY::OnButtonHelp() { // TODO: Add your control notification handler code here WinHelp(8,HELP_CONTEXT);//(0,HELP_CONTENTS); } void gtEARLEY::OnChangeChuoi_Nhap() { // TODO: If this is a RICHEDIT control, the control will not // send this notification unless you override the CDialog::OnInitDialog() // function to send the EM_SETEVENTMASK message to the control // with the ENM_CHANGE flag ORed into the lParam mask. // TODO: Add your control notification handler code here m_list_dan_xuat.ResetContent(); m_list_thuc_the.ResetContent(); }

Trang119

Luaän Toát Nghieäp KS2-K7

GIAÛI THUAÄT CYK // gtCKY.cpp : implementation file #include "stdafx.h" #include "Automat.h" #include "gtCKY.h" #ifdef _DEBUG #define new DEBUG_NEW #undef THIS_FILE static char THIS_FILE[] = __FILE__; #endif ///////////////////////////////////////////////////////////////////////////// // gtCKY dialog gtCKY::gtCKY(CWnd* pParent /*=NULL*/) : CDialog(gtCKY::IDD, pParent) { //{{AFX_DATA_INIT(gtCKY) Trang120

Luaän Toát Nghieäp KS2-K7 //}}AFX_DATA_INIT } void gtCKY::DoDataExchange(CDataExchange* pDX) { CDialog::DoDataExchange(pDX); //{{AFX_DATA_MAP(gtCKY) DDX_Control(pDX, IDC_EDIT_STR, m_chuoi_nhap); DDX_Control(pDX, IDC_LIST_TABLE_T, m_list_t); DDX_Control(pDX, IDC_LIST_P, m_list_p); DDX_Control(pDX, IDC_LIST_DAN_XUAT, m_list_dan_xuat); //}}AFX_DATA_MAP } BEGIN_MESSAGE_MAP(gtCKY, CDialog) //{{AFX_MSG_MAP(gtCKY) ON_BN_CLICKED(IDC_BUTTON_CYK, OnButtonCYK) ON_BN_CLICKED(IDC_BUTTON_VP_DAU, OnButtonVP_Goc) ON_EN_CHANGE(IDC_EDIT_STR, OnChangeChuoiNhap) //}}AFX_MSG_MAP END_MESSAGE_MAP() ///////////////////////////////////////////////////////////////////////////// // gtCKY message handlers BOOL gtCKY:: OnInitDialog() { int soluat;//So luat sinh da luu int i; char st[250]; CString luatsinh; CDialog::OnInitDialog(); Chomsky(); soluat=ChomskyVeTrai.GetSize(); //Cho hien lai tap luat sinh for(i=0;i<soluat;i++) { sprintf(st,"(%d) ",i); luatsinh=st+ChomskyVeTrai[i]+"---->"+ChomskyVePhai[i]; m_list_p.AddString(luatsinh); } m_list_t.SetHorizontalExtent(3000); m_list_dan_xuat.SetHorizontalExtent(700); m_list_p.SetHorizontalExtent(200); //Copy cac bien toan cuc cho Dialog VPBanDau Trang121

Luaän Toát Nghieäp KS2-K7 Goc_Chomsky.ArrayKkt.Copy(ArrayKkt); Goc_Chomsky.ArrayKt.Copy(ArrayKt); Goc_Chomsky.ArrayVePhai.Copy(ArrayVePhai); Goc_Chomsky.ArrayVeTrai.Copy(ArrayVeTrai); Goc_Chomsky.ArrayLuatSinh.Copy(ArrayLuatSinh); Goc_Chomsky.BienKhoiDau=BienKhoiDau; Goc_Chomsky.ChomskyKkt.Copy(ChomskyKkt); Goc_Chomsky.ChomskyKt.Copy(ChomskyKt); Goc_Chomsky.ChomskyVePhai.Copy(ChomskyVePhai); Goc_Chomsky.ChomskyVeTrai.Copy(ChomskyVeTrai); Goc_Chomsky.ChomskyBanDau=ChomskyBanDau; Goc_Chomsky.VeTrai_TG.Copy(VeTraiVoDung); Goc_Chomsky.VePhai_TG.Copy(VePhaiVoDung); return TRUE; } //Thuc hien giai thuat CYK void gtCKY::OnButtonCYK() { // TODO: Add your control notification handler code here int i,j,chieudaichuoi; int soluatdanxuat; CString str,stdx; m_chuoi_nhap.GetWindowText(str); Goc_Chomsky.str=str; m_list_t.ResetContent(); m_list_dan_xuat.ResetContent(); DanXuat_So.RemoveAll(); DanXuat_Chuoi.RemoveAll(); chieudaichuoi=str.GetLength(); for (i=0;i<250;i++) for (j=0;j<250;j++) T[i][j]=""; XayDungBangT(str); //Kiem tra chuoi nhap co thuoc van pham hay khong if (KiemTraChuoiThuocL(T[1][chieudaichuoi])==0) m_list_dan_xuat.AddString("Chuæi NhËp Kh¤ng Thuèc Ng¤n Ngö L(G)"); else { m_list_dan_xuat.AddString("+ Chuæi NhËp Thuèc Ng¤n Ngö L(G)"); //tao chuoi dan xuat gen(1,chieudaichuoi,BienKhoiDau,str); //In ra chuoi dan xuat so Trang122

Luaän Toát Nghieäp KS2-K7 m_list_dan_xuat.AddString("+ Th÷ Tø Àp Dóng CÀc LuËt Sinh TrÀi NhÊt :"); InDanXuat_Chuoi(InDanXuat_So(),70); DanXuatRaChuoiNhap(); stdx=""; soluatdanxuat=DanXuat_Chuoi.GetSize(); for(i=0;i<soluatdanxuat;i++) stdx=stdx+DanXuat_Chuoi[i]; m_list_dan_xuat.AddString("+ Chuæi D…n XuÊt TrÀi NhÊt Ra CÁu NhËp :"); stdx=stdx.Left(stdx.GetLength()-2); InDanXuat_Chuoi(stdx,50); } //Copy cac bien cho class VPgoc_ch Goc_Chomsky.DanXuat_So.Copy(DanXuat_So); Goc_Chomsky.DanXuat_Chuoi.Copy(DanXuat_Chuoi); } /////////////////////////////////////////// //Xay dung bang phan tich T void gtCKY::XayDungBangT(CString str) { int i,j; int chieudaichuoi; CString st; chieudaichuoi=str.GetLength(); if (chieudaichuoi==0) MessageBox("BÁn Ch§a ThËt Sø NhËp Vªo Chuæi CÇn PhÁn TÛch", "Th¤ng BÀo",MB_ICONSTOP); else { //buoc 1 for(i=0;i
Luaän Toát Nghieäp KS2-K7 int l; CString s; char s1[250]; s=T[i][j]; sprintf(s1,"T%d,%d=",i,j); l=s.GetLength(); while(l<5) {s=s+" "; l=s.GetLength();} st=st+s1+"{"+s+"}"+" "; } m_list_t.AddString(st); } } /////////////////////////////////////////// void gtCKY::line(int j, int n) { int i,j1,j11,k,k1,x,y; CString Tik,Tk1_j11,B,C; //(1) i=1;j1=n-j+1; while(i<=j1) { k=1; //(2) while (k<=j) { k1=i+k;j11=j-k; //(3) //Khao sat Tik va Tk1j11 (4) Tik=T[i][k]; Tk1_j11=T[k1][j11]; for (x=0;x<Tik.GetLength();x++) for (y=0;y
Luaän Toát Nghieäp KS2-K7 int soluat; CString temp,st; int i; temp=B+C; soluat=ChomskyVeTrai.GetSize(); for(i=0;i<soluat;i++) if (temp==ChomskyVePhai[i]) st=st+ChomskyVeTrai[i]; if (st.GetLength() !=0) return st; else return ""; } //neu co luat sinh thi tra ve string chua tat ca ve trai //nguoc lai tra ve chuoi rong CString gtCKY::TimLuatSinh_a(CString a) { int soluat; CString st; int i; soluat=ChomskyVeTrai.GetSize(); for(i=0;i<soluat;i++) if (ChomskyVePhai[i]==a) st=st+ChomskyVeTrai[i]; if (st.GetLength() !=0) return st; else return ""; } ///////////////////////////////////////////// //Tra ve hoi cua nhai CString CString gtCKY::Hoi(CString B, CString C) { int i; CString Temp; Temp=""; for(i=0;i
Luaän Toát Nghieäp KS2-K7 return 0; } //tao ra chuoi dan xuat void gtCKY::gen(int i, int j, CString A, CString Str) { int k,len1,len2,x,y; int h; char st[250]; CString B,C,BC; CString Tik,Tik_jk; if (j==1) { sprintf(st,"%d",Pa(A,Str[i-1])); DanXuat_So.Add(st); } else if (j>1) { k=1; while(k<j) { Tik=T[i][k]; Tik_jk=T[i+k][j-k]; len1=Tik.GetLength(); len2=Tik_jk.GetLength(); for (x=0;xai Trang126

Luaän Toát Nghieäp KS2-K7 int gtCKY::Pa(CString A, CString a) { int soluat; int i; soluat=ChomskyVeTrai.GetSize(); for(i=0;i<soluat;i++) if ((ChomskyVeTrai[i]==A)&&(ChomskyVePhai[i]==a)) return i; return -1; } ////////////////////////////////////////// //In ra chuoi dan xuat so CString gtCKY::InDanXuat_So() { int len,i; CString dxs; len=DanXuat_So.GetSize(); for(i=0;iabgd void gtCKY::DanXuatRaChuoiNhap() { int i,n,l,k,j; int len_so,len_chuoi; CString st,str,str1; len_so=DanXuat_So.GetSize(); i=atoi(DanXuat_So[0]); DanXuat_Chuoi.Add(ChomskyVeTrai[i]); DanXuat_Chuoi.Add("=>"); DanXuat_Chuoi.Add(ChomskyVePhai[i]); DanXuat_Chuoi.Add("=>"); len_chuoi=DanXuat_Chuoi.GetSize(); n=len_chuoi-2; for(j=1;j
Luaän Toát Nghieäp KS2-K7 { str=st.Left(k); str=str+ChomskyVePhai[i]; str1=st.Mid(k+1,st.GetLength()); str=str+str1; DanXuat_Chuoi.Add(str); DanXuat_Chuoi.Add("=>"); len_chuoi=DanXuat_Chuoi.GetSize(); n=len_chuoi-2; k=l; } else k=k+1; }//while }//for } //============================================= == void gtCKY::InDanXuat_Chuoi(CString stdx,int so) { CString s1; CString s2; while (stdx.GetLength()>so) { s1=stdx.Left(so); m_list_dan_xuat.AddString(s1); s2=stdx.Mid(so,stdx.GetLength()); stdx=s2; } m_list_dan_xuat.AddString(stdx); } //////////////////////////////////////////// //Hien Thi van pham goc void gtCKY::OnButtonVP_Goc() { // TODO: Add your control notification handler code here Goc_Chomsky.DoModal(); } /////////////////////////////////////////// //Phan chuyen van pham bat ky ve gtCKY void gtCKY::LoaiBoTatCa() { //Loai Bo Rong { CStringArray Vn;//Mang chua cac ve trai co kha ngag sinh ra rong; CString V; CString string; CString stringp; Trang128

Luaän Toát Nghieäp KS2-K7 CString Vtemp; CString stringkt; CString stringkkt_kt; int i;//bien de duyet int soluat; int soluattrong; int sokt; //Xoa het cac gia tri trong VePhaiRong & VeTraiRong VePhaiRong.RemoveAll(); VeTraiRong.RemoveAll(); {//Tim cac ky hieu khong ket thuc dan xuat ra rong sokt=ArrayKt.GetSize(); for(i=0;i<sokt;i++) if(ArrayKt[i]!="#") stringkt=stringkt+ ArrayKt[i]; soluat=ArrayVeTrai.GetSize(); for(i=0;i<soluat;i++) { string=ArrayVePhai[i]; if(FindStr(string,stringkt)!=0) stringkkt_kt=stringkkt_kt+ArrayVeTrai[i]; }//end for stringkkt_kt=stringkkt_kt+stringkt; //Tim tap cac bien dan xuat ra cac ky tu ket thuc for(i=0;i<soluat;i++) { string=ArrayVePhai[i]; if((FindStr(string,stringkkt_kt)!=0) &&(FindStr(ArrayVeTrai[i],stringkkt_kt)==0)) { stringkkt_kt=stringkkt_kt+ArrayVeTrai[i]; i=-1; } } }//het tim cac ky hieu khong ket thuc dan xuat ra rong soluat=ArrayVeTrai.GetSize(); V=""; //Duyet qua cac luat sinh rong; for(i=0;i<soluat;i++) { string=ArrayVePhai[i]; if(string=="#") Vn.Add(ArrayVeTrai[i]); Trang129

Luaän Toát Nghieäp KS2-K7 } soluattrong=Vn.GetSize(); //In ra cua so minh hoa tap Vn for(i=0;i<soluattrong;i++) V=V+Vn[i]; //Duyet qua cac luat sinh ma ve phai tat ca cac ki tu van pham man trong tap Vn int j; int chieudaivephai; i=0; while (i<soluat) { string=ArrayVePhai[i]; chieudaivephai=string.GetLength(); j=0; while(j
Luaän Toát Nghieäp KS2-K7 soluat=ArrayVeTrai.GetSize(); for(i=0;i<soluat;i++) { if(ArrayVePhai[i] !="#") { VeTraiTemp.Add(ArrayVeTrai[i]); VePhaiTemp.Add(ArrayVePhai[i]); cd=VeTraiTemp.GetSize(); for(j=0;j
Luaän Toát Nghieäp KS2-K7 VeTraiTemp.Add(ArrayVeTrai[i]); cd=VePhaiTemp.GetSize(); } strtemp.RemoveAll(); str1=""; }//end if(V.Find... }//end for(k=0;... }//end for(j=0;... cd=VePhaiTemp.GetSize(); for (n=0;n
Luaän Toát Nghieäp KS2-K7 CStringArray CStringArray CStringArray CStringArray CStringArray CStringArray CStringArray CStringArray

DonViTrai; DonViPhai; KhongDonViTrai; KhongDonViPhai; TempT; TempP; DVT; DVP;

int tm; int n,j,k; int soluatkdv; int daitemp; VeTraiDonVi.RemoveAll(); VePhaiDonVi.RemoveAll(); strkkt=""; sokkt=ArrayKkt.GetSize(); //Tim chuoi cac ki tu khong ketthuc for(i=0;i<sokkt;i++) { strkkt=strkkt+ArrayKkt[i]; } soluatsinh=VeTraiRong.GetSize(); //Tim nhung luat sinh la don vi for(i=0;i<soluatsinh;i++) { str=VePhaiRong[i]; if((strkkt.Find(str)!=-1) && (str.GetLength()==1)) { DonViTrai.Add(VeTraiRong[i]); DonViPhai.Add(str); }//end for(i=0;i<soluatsinh;i++) else { KhongDonViTrai.Add(VeTraiRong[i]); KhongDonViPhai.Add(str); } } //Tim cac cay dan xuat cua cac luat sinh don vi soluat=DonViTrai.GetSize(); for(i=0;i<soluat;i++) { Trang133

Luaän Toát Nghieäp KS2-K7 TempT.Add(DonViTrai[i]); TempP.Add(DonViPhai[i]); daitemp=TempT.GetSize(); for (j=0;j
Luaän Toát Nghieäp KS2-K7 if(DVT.GetSize() ==0) {DVT.Add(TempT[n]); DVP.Add(TempP[n]);} else { CString string1; CString string2; int b;//Bien dung de duyet qua int soluatsinh; soluatsinh=DVT.GetSize(); for(b=0;b<soluatsinh;b++) { string1=DVT[b]; string2=DVP[b]; if(string1.Compare(TempT[n])==0 && string2.Compare(TempP[n])==0) { flag=0; b=soluatsinh+1; } else flag=1; } if((flag==1) || (soluatsinh==0)) flag= 1;else flag= 0; if (flag !=0) { DVT.Add(TempT[n]); DVP.Add(TempP[n]); } }//end khoi } //end for (n... TempT.RemoveAll(); TempP.RemoveAll(); }//end for i soluatkdv=KhongDonViTrai.GetSize(); for(i=0;i<soluatkdv;i++) { VeTraiDonVi.Add(KhongDonViTrai[i]); VePhaiDonVi.Add(KhongDonViPhai[i]); } int soluatDVT; soluatDVT=DVT.GetSize(); for(i=0;i<soluatDVT;i++) { for(j=0;j<soluatkdv;j++) { if(DVP[i].Compare(KhongDonViTrai[j])==0) Trang135

Luaän Toát Nghieäp KS2-K7 { { CString string1; CString string2; int c;//Bien dung de duyet qua int soluatsinh; soluatsinh=VeTraiDonVi.GetSize(); for(c=0;c<soluatsinh;c++) { string1=VeTraiDonVi[c]; string2=VePhaiDonVi[c]; if(string1.Compare(DVT[i])==0 && string2.Compare(KhongDonViPhai[j])==0) { flag=0; c=soluatsinh+1; } else flag=1; } if((flag==1) || (soluatsinh==0)) flag=1;else flag=0; }//end khoi if (flag!=0) { VeTraiDonVi.Add(DVT[i]); VePhaiDonVi.Add(KhongDonViPhai[j]); } } } } }//end procedure loai bo don vi // Loai Bo luat sing vo dung { // TODO: Add your control notification handler code here int soluat; int i; int sokt; CString stringkt; CString string; CString strdx; CString strkt; CString strkt_dx; CString stringkkt_kt; CString B_thuoc_S; Trang136

Luaän Toát Nghieäp KS2-K7 stringkt =""; stringkkt_kt="";//BienKhoiDau; B_thuoc_S=BienKhoiDau; CStringArray TempTrai; CStringArray TempPhai; CStringArray VeTraiVDLoai1; CStringArray VePhaiVDLoai1; CStringArray VeTraiVDLoai2; CStringArray VePhaiVDLoai2; TempTrai.Copy(VeTraiDonVi); TempPhai.Copy(VePhaiDonVi); VeTraiVoDung.RemoveAll(); VePhaiVoDung.RemoveAll(); sokt=ArrayKt.GetSize(); for(i=0;i<sokt;i++) stringkt=stringkt+ ArrayKt[i]; soluat=TempTrai.GetSize(); for(i=0;i<soluat;i++) { string=TempPhai[i]; if((FindStr(string,stringkt)!=0) && (FindStr(TempTrai[i],stringkkt_kt)==0)) stringkkt_kt=stringkkt_kt+TempTrai[i]; }//end for strkt=stringkkt_kt; stringkkt_kt=stringkkt_kt+stringkt; //Tim tap cac bien dan xuat ra cac ky tu ket thuc for(i=0;i<soluat;i++) { string=TempPhai[i]; if((FindStr(string,stringkkt_kt)!=0) &&(FindStr(TempTrai[i],stringkkt_kt)==0)) { strdx=strdx+TempTrai[i]; stringkkt_kt=stringkkt_kt+TempTrai[i]; i=-1; } } //het viec tim cac bien dan xuat strkt_dx=strkt+strdx; Trang137

Luaän Toát Nghieäp KS2-K7 //Cho nhung luat sinh dan xuat ra rong //ma co trong chuoi dan xuat tu S for(i=0;i<soluat;i++) { string=TempPhai[i]; if((TempTrai[i]==BienKhoiDau) && (FindStr(string,stringkkt_kt)!=0)) if(FindStr(string,B_thuoc_S)==0) B_thuoc_S=B_thuoc_S+string; } for (i=0;i<soluat;i++) { string=TempPhai[i]; if((TempTrai[i]!=BienKhoiDau) && (FindStr(string,stringkkt_kt)!=0)) if((FindStr(TempTrai[i],B_thuoc_S)!=0)&&(FindStr(string,B_thuoc_S)==0)) {B_thuoc_S=B_thuoc_S+string; i=-1;} } for(i=0;i<soluat;i++) { string=TempPhai[i]; if(FindStr(string,stringkkt_kt)!=0) if(FindStr(TempTrai[i],B_thuoc_S)!=0) { VeTraiVoDung.Add(TempTrai[i]); VePhaiVoDung.Add(TempPhai[i]); } else { VeTraiVDLoai2.Add(TempTrai[i]); VePhaiVDLoai2.Add(TempPhai[i]); } else { VeTraiVDLoai1.Add(TempTrai[i]); VePhaiVDLoai1.Add(TempPhai[i]); } }//end for }//end khoi } ////////////////////////////////////////////////////////////// int gtCKY::KiemTraChuoiPhai(CString chuoivephai,CString chuoivetrai) { CString string1; Trang138

Luaän Toát Nghieäp KS2-K7 CString string2; int i;//Bien dung de duyet qua int soluatsinh; int flag; soluatsinh=VePhaiRong.GetSize(); for(i=0;i<soluatsinh;i++) { string1=VePhaiRong[i]; string2=VeTraiRong[i]; if(string1.Compare(chuoivephai)==0 && string2.Compare(chuoivetrai)==0) { flag=0; i=soluatsinh+1; } else flag=1; } if((flag==1) || (soluatsinh==0)) return 1;else return 0; } //-------------------------------------int gtCKY::KiemTraChuoiPhaiRong(CString chuoiphai, CString V) { int chieudaichuoi; int i; //bien duyet int flag; chieudaichuoi=chuoiphai.GetLength(); for (i=0;i
Luaän Toát Nghieäp KS2-K7 if (V.Find(string[i])==-1) { flag=0; i=chieudai+1; } else flag=1; } if (flag==1) return 1; else return 0; } //===================================== int gtCKY::FindChar(CString string, CString V) { int chieudai; int i; int flag; chieudai=string.GetLength(); for(i=0;i
Luaän Toát Nghieäp KS2-K7 CString string; CString stringphai; CString stringT; CString Strp,St,Stp,Str1; char Str[20]; CString T;//Tap Cac ky hieu ket thuc CString V;//Tap cac ky hieu khonng ket thuc //Loai bo tat cac cac luat sinh rong, don vi, vo dung ChomskyVePhai.RemoveAll(); ChomskyVeTrai.RemoveAll(); ChomskyKt.RemoveAll(); ChomskyKkt.RemoveAll(); PhaiX.RemoveAll(); TraiX.RemoveAll(); LoaiBoTatCa(); k=65; //Xay dung tap T soluat=ArrayKt.GetSize(); for(i=0;i<soluat;i++) { if(ArrayKt[i]!="#") ChomskyKt.Add(ArrayKt[i]); T=T+ArrayKt[i]; } //Xay dung tap V soluat=ArrayKkt.GetSize(); for(i=0;i<soluat;i++) V=V+ArrayKkt[i]; //Copy tap luat sinh sau khi loai bo vo dung VePhai.Copy(VePhaiVoDung); VeTrai.Copy(VeTraiVoDung); //============================================ soluat=VeTrai.GetSize(); for(i=0;i<soluat;i++) { stringphai=VePhai[i]; len=stringphai.GetLength(); if(len==1) { ChomskyVeTrai.Add(VeTrai[i]); ChomskyVePhai.Add(VePhai[i]); } else if((len==2) && (FindStr(VePhai[i],V) !=0)) { Trang141

Luaän Toát Nghieäp KS2-K7 //Cho vao Chomsy nhung luat sinh ve phai toan la nhung ky hieu //khong ket thuc ma co chieu dai la 2 ChomskyVeTrai.Add(VeTrai[i]); ChomskyVePhai.Add(VePhai[i]); Len2T.Add(VeTrai[i]); Len2P.Add(VePhai[i]); } else { stringT=VeTrai[i]; for(j=0;j
Luaän Toát Nghieäp KS2-K7 haiso=sokytu; b=0; while(sokytu >=2) {//begin while if(sokytu==2) { Str1=PhaiTemp[haiso-2]+PhaiTemp[haiso-1]; ChomskyVeTrai.Add(stringT); ChomskyVePhai.Add(Str1); } else { St=PhaiTemp[b]; //sprintf(Str,"(X%d)",k); sprintf(Str,"%c",k); while(FindStr(Str,V)==1) {k++;sprintf(Str,"%c",k);} Stp=St+Str; ChomskyVeTrai.Add(stringT); ChomskyVePhai.Add(Stp); stringT=Str; k++; } sokytu=sokytu-1; b=b+1; }//end while PhaiTemp.RemoveAll(); }//end else }//end for ChomskyVeTrai.Append(TraiX); ChomskyVePhai.Append(PhaiX); //Copy Cac bien cho van pham Dialog Chdlog; {//bat dau CStringArray Temp; CString Vv; soluat=ChomskyVeTrai.GetSize(); for (i=0;i<soluat;i++) { if(Vv.Find(ChomskyVeTrai[i]) ==-1) { Temp.Add(ChomskyVeTrai[i]); Vv=Vv+ChomskyVeTrai[i]; } } ChomskyKkt.Copy(Temp); ChomskyBanDau=BienKhoiDau; }//ket thuc viec copy Trang143

Luaän Toát Nghieäp KS2-K7 }//Ket thuc ham ///////////////////////////////////////////// //tra ve 0 neu khong co, tra ve vi tri neu co int gtCKY::KiemTraSinhKetThuc(CString luatsinh) { CString string; int i;//Bien dung de duyet qua int j; int soluatsinh; int flag; soluatsinh=PhaiX.GetSize(); for(i=0;i<soluatsinh;i++) { string=PhaiX[i]; if(string.Compare(luatsinh)==0) { j=i; flag=0; i=soluatsinh+1; } else flag=1; } if((flag==1) || (soluatsinh==0)) return -1;else return j; } //============================================= = void gtCKY::OnChangeChuoiNhap() { // TODO: If this is a RICHEDIT control, the control will not // send this notification unless you override the CDialog::OnInitDialog() // function to send the EM_SETEVENTMASK message to the control // with the ENM_CHANGE flag ORed into the lParam mask. // TODO: Add your control notification handler code here m_list_dan_xuat.ResetContent(); m_list_t.ResetContent(); }

Trang144

Luaän Toát Nghieäp KS2-K7

NHAÄN DAÏNG NGOÂN NGÖÕ TÖÏ NHIEÂN // ndnntn.cpp : implementation file #include "stdafx.h" #include "Automat.h" #include "ndnntn.h" #include "fstream.h" #ifdef _DEBUG #define new DEBUG_NEW #undef THIS_FILE static char THIS_FILE[] = __FILE__; #endif ///////////////////////////////////////////////////////////////////////////// // ndnntn dialog ndnntn::ndnntn(CWnd* pParent /*=NULL*/) : CDialog(ndnntn::IDD, pParent) { //{{AFX_DATA_INIT(ndnntn) // NOTE: the ClassWizard will add member initialization here //}}AFX_DATA_INIT } void ndnntn::DoDataExchange(CDataExchange* pDX) { CDialog::DoDataExchange(pDX); //{{AFX_DATA_MAP(ndnntn) DDX_Control(pDX, IDC_EDIT_TIENG_VIET, m_nghia_viet); DDX_Control(pDX, IDC_EDIT_Cau_Nhap, m_chuoi_nhap); DDX_Control(pDX, IDC_LIST_TOKEN, m_list_token); DDX_Control(pDX, IDC_LIST_THUC_THE, m_list_thuc_the); DDX_Control(pDX, IDC_LIST_DAN_XUAT, m_list_dan_xuat); //}}AFX_DATA_MAP } BEGIN_MESSAGE_MAP(ndnntn, CDialog) //{{AFX_MSG_MAP(ndnntn) ON_BN_CLICKED(IDC_BUTTON_PT, OnButtonPhanTich) ON_BN_CLICKED(IDC_BUTTON_XEM_VP, OnButtonXemVPTN) ON_EN_CHANGE(IDC_EDIT_Cau_Nhap, OnChangeChuoiNhap) //}}AFX_MSG_MAP END_MESSAGE_MAP() Trang145

Luaän Toát Nghieäp KS2-K7 ///////////////////////////////////////////////////////////////////////////// // ndnntn message handlers BOOL ndnntn::OnInitDialog() { CString st; CDialog::OnInitDialog(); VP_TN.ArrayKkt2.Copy(ArrayKkt2); VP_TN.ArrayKt1.Copy(ArrayKt1); VP_TN.ArrayKt2.Copy(ArrayKt2); VP_TN.ArrayVePhai2.Copy(ArrayVePhai2); VP_TN.ArrayVeTrai2.Copy(ArrayVeTrai2); VP_TN.BienKhoiDau2=BienKhoiDau2; st="Token\tLexme\tLoÁi Tô"; m_list_token.AddString(st); return TRUE; } ///////////////////////////////////////////////// //Khoi dong mot con tro its *ndnntn::Init(its *f) { f=NULL; return f; } //==================================== //Khoi dong tap thuc the void ndnntn::Init_thucthe() { int i; for (i=0;i<MAX; i++) tapthucthe[i]=Init(tapthucthe[i]); } //Dua du lieu vao tap thuc the //====================================== its *ndnntn::Insert_data(its *pt, int k,int j ,int f) { its *p,*q,*before; p=new its; (p->p)=k; (p->i)=j; (p->f)=f; q=pt; while(q!=NULL) { before=q; Trang146

Luaän Toát Nghieäp KS2-K7 q=q->link; } if(q==pt) pt=p; else before->link=p; p->link=q; return (pt); } //============================================= = //Hien thi cac trang thai trong tap thuc the void ndnntn::Display_its(its *f, int th) { its *q; char st[20]; char ft[10]; CString trangthai; CString str_t,str_s; int ls,ch,s;//luat sinh, dau cham , trang thai q=f; sprintf(st,"TrÁng ThÀi : S[%d]",th); m_list_thuc_the.AddString(st); while(q!=NULL) { ls=q->p;//lay so thu tu luat sinh ch=q->i;//Lay vi tri dau cham s=q->f;//lay vi tri con tro str_t=StrBeforeDot(ls,ch); str_s=StrAfterDot(ls,ch); str_t=DoiToSt2(str_t); str_s=DoiToSt2(str_s); sprintf(ft,"%d ]",s); //trangthai="[ " + ArrayVeTrai1[ls]+"---->"+str_t+ " . "+str_s+" , "+ft; trangthai="[ " + ArrayVeTrai2[ls]+"---->"+str_t+ " . "+str_s+" , "+ft; m_list_thuc_the.AddString(trangthai); q=q->link; } m_list_thuc_the.AddString(" "); } //============================================= = //TÛnh tËp trÁng thÀi S0 void ndnntn::luat123() { int i; int kq23; int soluatsinh; soluatsinh=ArrayVeTrai1.GetSize(); //luat 1 Trang147

Luaän Toát Nghieäp KS2-K7 for(i=0;i<soluatsinh;i++) { if (ArrayVeTrai1[i]==BienKhoiDau1) if (ArrayVePhai1[i]=="#") tapthucthe[0]=Insert_data(tapthucthe[0],i,1,0); else tapthucthe[0]=Insert_data(tapthucthe[0],i,0,0); }//het luat 1 do { kq23=luat23(); } while (kq23==1); } //Thuc hien luat thu 3 int ndnntn::luat23() { its *q; its *pt; int soluat; int i,flay; q=tapthucthe[0]; flay=0; soluat=ArrayVeTrai1.GetSize(); while(q!=NULL) { if (ChrAfterDot(q)=="")//neu dau cham o sau cung {//luat 2 pt=tapthucthe[0];//quay lai tap thuc the i=q->f while(pt!=NULL) { if(ChrAfterDot(pt)==ArrayVeTrai1[q->p]) if(KiemTraTrangThai(0,pt->p,(pt->i)+1,0)==0) {tapthucthe[0]=Insert_data(tapthucthe[0],pt->p,(pt>i)+1,0); flay=1;} pt=pt->link; } } else //luat 3 { for (i=0;i<soluat;i++) if (ArrayVeTrai1[i]==ChrAfterDot(q)) { if (ArrayVePhai1[i]=="#") { if(KiemTraTrangThai(0,i,1,0)==0) tapthucthe[0]=Insert_data(tapthucthe[0],i,1,0); } else if(KiemTraTrangThai(0,i,0,0)==0) tapthucthe[0]=Insert_data(tapthucthe[0],i,0,0); Trang148

Luaän Toát Nghieäp KS2-K7 } } q=q->link; } if (flay==1) return 1; else return 0; } //Thuc hien luat so 4 void ndnntn::luat456() { CString str; int j,chieudaichuoi; its *q; CString a; str=token; //m_chuoi_nhap.GetWindowText(str); chieudaichuoi=str.GetLength(); for (j=0;jp),(q->i)+1,(q->f))==0) tapthucthe[j+1]=Insert_data(tapthucthe[j+1],(q->p),(q>i)+1,(q->f)); q=q->link; } //het luat 4 luat56(j+1);//ap dung lien tiep luat 5 va 6 cho den khi khong them va duoc nua } } //========================================== //Thuc hien luat so 5 va so 6 void ndnntn::luat56(int th) { its *q;// con tro cua tap j=th its *pt;//con tro cua tap i int i; int soluat; q=tapthucthe[th]; soluat=ArrayVeTrai1.GetSize(); while(q!=NULL) { if (ChrAfterDot(q)=="")//neu dau cham o sau cung Trang149

Luaän Toát Nghieäp KS2-K7 {//luat 5 pt=tapthucthe[q->f];//quay lai tap thuc the i=q->f while(pt!=NULL) { if(ChrAfterDot(pt)==ArrayVeTrai1[q->p]) if(KiemTraTrangThai(th,pt->p,(pt->i)+1,pt->f)==0) tapthucthe[th]=Insert_data(tapthucthe[th],pt->p,(pt>i)+1,pt->f); pt=pt->link; } } else {//luat 6 for (i=0;i<soluat;i++) if (ArrayVeTrai1[i]==ChrAfterDot(q)) { if (ArrayVePhai1[i]=="#") { if(KiemTraTrangThai(th,i,1,th)==0) tapthucthe[th]=Insert_data(tapthucthe[th],i,1,th); } else if(KiemTraTrangThai(th,i,0,th)==0) tapthucthe[th]=Insert_data(tapthucthe[th],i,0,th); } } q=q->link; } }//ket thuc luat56 //============================================= === //Tra ve chuoi ky tu truoc dau cham CString ndnntn::StrBeforeDot(int ls, int ch) { int i; CString Temp,Vp; Vp=ArrayVePhai1[ls]; Temp=""; for(i=0; i
Luaän Toát Nghieäp KS2-K7 CString Temp,Vp; Vp=ArrayVePhai1[ls]; lenvephai=Vp.GetLength(); Temp=""; for (i=ch; ip); ch=(pt->i); Vp=ArrayVePhai1[sl]; if (chp==p) && (q->i==i) && (q->f==ft)) return 1; else q=q->link; } return 0; } /////////////////////////////////////////////////// int ndnntn::KiemTraThuocLG(int th) { int i,len; int soluat; if (tapthucthe[th]==NULL) return -1;//chuoi khong thuoc van pham else { soluat=ArrayVeTrai1.GetSize(); for (i=0; i<soluat;i++) { len=ArrayVePhai1[i].GetLength(); if (ArrayVeTrai1[i]==BienKhoiDau1) Trang151

Luaän Toát Nghieäp KS2-K7 if(KiemTraTrangThai(th,i,len,0)==1) return i; } } return -1; } //============================================= ====== void ndnntn::ChuoiDanXuat(int ls,int ch, int i, int j) { char stt[10]; int k,l,m,r; its *q; its *pt; CString Vp; sprintf(stt,"%d",ls); DanXuat_So.Add(stt); Vp=ArrayVePhai1[ls]; m=Vp.GetLength(); k=m-1; l=j; while(k!=-1) { if (FindChar(Vp[k],TapT)==1) { k=k-1; l=l-1; } else { q=tapthucthe[l]; while(q!=NULL) { if(ArrayVeTrai1[q->p]==Vp[k] && ChrAfterDot(q)=="") { r=q->f; pt=tapthucthe[r];//tim trong tap thuc the r=q->j; while(pt!=NULL) { if((ChrAfterDot(pt)==Vp[k])&&(k==pt->i) && ((pt>f)==i) && (ArrayVePhai1[pt->p]==ArrayVePhai1[ls])&&//(ArrayVePhai1[pt>p].GetLength()==m) && (ArrayVeTrai1[pt->p]==ArrayVeTrai1[ls])) { ChuoiDanXuat(q->p,q->i,r,l);//ArrayVePhai1[q>p].GetLength(),r,l); k=k-1; Trang152

Luaän Toát Nghieäp KS2-K7 l=r; pt=NULL; q=NULL; } else { pt=pt->link; if (pt==NULL) q=q->link; } }//end while pt }//end if else q=q->link; }//end while q }//end else }//end while k }//end function //============================================= = //tra ve 1 neu co tra ve 0 neu khong co int ndnntn::FindChar(CString string, CString V) { if (V.Find(string)!=-1) return 1; else return 0; } //============================================= void ndnntn::XayDungTapT_N() { int sokytu; int i; //Xay dung tap T sokytu=ArrayKt1.GetSize(); for(i=0;i<sokytu;i++) TapT=TapT+ArrayKt1[i]; //Xay dung tap N sokytu=ArrayKkt1.GetSize(); for(i=0;i<sokytu;i++) TapN=TapN+ArrayKkt1[i]; } //============================================= == void ndnntn::InDanXuat(CString stdx,int so) { CString s1; CString s2; while (stdx.GetLength()>so) { Trang153

Luaän Toát Nghieäp KS2-K7 s1=stdx.Left(so); m_list_dan_xuat.AddString(s1); s2=stdx.Mid(so,stdx.GetLength()); stdx=s2; } m_list_dan_xuat.AddString(stdx); } //======================================= void ndnntn::DanXuatRaChuoiNhap() { int i,n,l,k,j; int len_so,len_chuoi; CString st,str,str1; len_so=DanXuat_So.GetSize(); i=atoi(DanXuat_So[0]); DanXuat_Chuoi.Add(ArrayVeTrai1[i]); DanXuat_Chuoi.Add("=>"); DanXuat_Chuoi.Add(ArrayVePhai1[i]); DanXuat_Chuoi.Add("=>"); len_chuoi=DanXuat_Chuoi.GetSize(); n=len_chuoi-2; for(j=1;j=0) { if (st[k]==ArrayVeTrai1[i]) { str=st.Left(k); str=str+ArrayVePhai1[i]; str1=st.Mid(k+1,st.GetLength()); str=str+str1; DanXuat_Chuoi.Add(str); DanXuat_Chuoi.Add("=>"); len_chuoi=DanXuat_Chuoi.GetSize(); n=len_chuoi-2; k=-1; } else k=k-1; }//while }//for } void ndnntn::OnButtonPhanTich() Trang154

Luaän Toát Nghieäp KS2-K7 { // TODO: Add your control notification handler code here CString str; CString stdx,temp; int chieudaichuoi; int i,ls,soluatdanxuat; char st[50]; m_list_thuc_the.ResetContent(); m_list_dan_xuat.ResetContent(); m_list_token.ResetContent(); m_list_token.AddString("Token\tLexme\tLoÁi Tô"); DanXuat_So.RemoveAll(); DanXuat_Chuoi.RemoveAll(); token=nexttoken(); str=token; //m_chuoi_nhap.GetWindowText(str); chieudaichuoi=str.GetLength(); Init_thucthe(); luat123(); luat456(); if (chieudaichuoi==0) Display_its(tapthucthe[0],0); else { for (i=0;i<=chieudaichuoi; i++) if(tapthucthe[i]!=NULL) Display_its(tapthucthe[i],i); else { sprintf(st,"Læi TÁi Tô NhËp Th÷ %d",i); m_list_thuc_the.AddString(st); m_list_thuc_the.AddString("CÀc TËp TrÁng ThÀi Trê VÒ Sau Lª Ræng"); i=chieudaichuoi+1; } } ls=KiemTraThuocLG(chieudaichuoi); if(ls==-1) m_list_dan_xuat.AddString("Chuæi NhËp Kh¤ng Thuèc Ng¤n Ngö L(G) ! "); else {//In ra ccay dan xuat m_list_dan_xuat.AddString("+ Chuæi NhËp Thuèc Ng¤n Ngö L(G) !"); XayDungTapT_N(); ChuoiDanXuat(ls,ArrayVePhai1[ls].GetLength(),0,chieudaichuoi); soluatdanxuat=DanXuat_So.GetSize(); for(i=0;i<soluatdanxuat;i++) stdx=stdx+DanXuat_So[i]+" "; Trang155

Luaän Toát Nghieäp KS2-K7 m_list_dan_xuat.AddString("+ Th÷ Tø CÀc LuËt Sinh Tham Gia Vªo QuÀ TrØnh D…n XuÊt :"); InDanXuat(stdx,114); m_list_dan_xuat.AddString("+ Chuæi D…n XuÊt Ra Chuæi NhËp :"); DanXuatRaChuoiNhap(); stdx=""; soluatdanxuat=DanXuat_Chuoi.GetSize(); for(i=0;i<soluatdanxuat;i++) stdx=stdx+DanXuat_Chuoi[i]; stdx=stdx.Left(stdx.GetLength()-2); stdx=DoiToSt2(stdx); m_chuoi_nhap.GetWindowText(temp); stdx=stdx+"=>"+temp; stdx=stdx.Left(stdx.GetLength()-1); InDanXuat(stdx,85); m_nghia_viet.SetWindowText(nghia_viet); } } /////////////////////////////////////////////////////////// void ndnntn::OnButtonXemVPTN() { // TODO: Add your control notification handler code here VP_TN.DoModal(); } /////////////////////////////////////////////////// //Tra ve so thu tu cua ky hieu khong ket thuc int ndnntn::SoThuTu(CString st) { int i,stt; stt=ArrayKkt1.GetSize(); for(i=0;i<stt;i++) if (ArrayKkt1[i]==st) return i; return -1; } ///////////////////////////////////////// //Doi mot chuoi tu st1 sang st2 CString ndnntn::DoiToSt2(CString st) { int i,len,stt; CString st_temp; len=st.GetLength(); for (i=0;i
Luaän Toát Nghieäp KS2-K7 if(stt!=-1) st_temp=st_temp+ArrayKkt2[stt]; else st_temp=st_temp+st[i]; } return st_temp; } //Tra ve mot token khi doc het mot chu CString ndnntn::nexttoken() { int i,len,stt; int beginning,forward; CString str,token,c,st; m_chuoi_nhap.GetWindowText(str); len=str.GetLength(); beginning=0; forward=0; if (len==0) MessageBox("BÁn Ch§a NhËp Vªo CÁu CÇn PhÁn TÛch","Th¤ng BÀo"); else if (str[len-1]!='.') MessageBox("Læi NhËp CÁu, Cuçi CÁu Ph¶i Câ DÊu ChÊm (.)","Th¤ng BÀo"); else { while(forward
Luaän Toát Nghieäp KS2-K7 m_list_token.AddString(st); } c=""; } else forward++; } } return token; } //////////////////////////////////////////////// int ndnntn::Find_TD(CString st) { int i,stt; stt=lexme_td.GetSize(); for(i=0;i<stt;i++) if (lexme_td[i]==st) return i; return -1; } void ndnntn::OnChangeChuoiNhap() { // TODO: If this is a RICHEDIT control, the control will not // send this notification unless you override the CDialog::OnInitDialog() // function to send the EM_SETEVENTMASK message to the control // with the ENM_CHANGE flag ORed into the lParam mask. // TODO: Add your control notification handler code here m_list_thuc_the.ResetContent(); m_list_dan_xuat.ResetContent(); m_list_token.ResetContent(); nghia_viet=""; }

PHAÀN 10 TAØI LIEÄU THAM KHAÛO Trang158

Luaän Toát Nghieäp KS2-K7

1. A Introduction To Formal Languages And Automata Peter Linz University of California at Davis 372 Trang 1. Compilers - Principle, Techniques, and Tool Alfred V. Aho Ravi Sethi Jeffrey D. Ulman 796 Trang 1. The Theory Of Parsing, Translation, and Compiling - Volume 1 : Parsing Alfred V. Aho Feffrey D. Ullman 541 Trang 1. Trình Bieân Dòch Phan Thò Töôi 458 Trang - Nhaø xuaát baûn giaùo duïc

1. An Efficient Context-Free Parsing Algorithm - Jay Earley University of California 1. Natural Language Processing In LISP Gazdar Gerald Chris Mellish 524 Trang 7- Website : http://www.devgr.com

Trang159