Ngôn ngữ lập trình đơn giản: thiết kế và cài đặt

ra maìn hçnh, in xong khäng xuäúng doìng. Daûng (2): In caïc chuäùi vaì giaï trë cuía caïc biãøu thæïc ra maìn hçnh, in xong xuäúng doìng. Daûng (3): Khäng in gç caí vaì xuäúng doìng. Vê duû: viãút(‘a=’, a,’b=’,b); viãút_xd(); hay viãút_xd(‘a+b=’,c); b. Lãûnh nháûp dæî liãûu tæì baìn phêm (1) âoüc(biãún) (2) âoüc_xd(biãún1, biãún2, ..., biãúnN); (3) âoüc_xd(); Daûng (1): Maïy seî nháûn ngay kyï tæû nháûp vaìo vaì gaïn cho biãún maì khäng chåì nháún ENTER. Daûng (2): Maïy chåì ngæåìi duìng nháûp dæî liãûu tæì baìn phêm, caïc dæî liãûu naìy ngàn caïch nhau êt nháút mäüt kyï tæû träúng nãúu trong lãûnh coï nhiãöu biãún, räöi nháún ENTER âãø kãút thuïc viãûc nháûp. Sau âoï maïy seî láön læåüc láúy giaï trë nháûp vaìo âãø gaïn cho caïc biãún tæång æïng. Biãún nháûn giaï trë thuäüc kiãøu thæûc. Daûng (3): Chåì ngæåìi duìng nháún phêm ENTER âãø tiãúp tuûc thæûc hiãûn chæång trçnh. 2.4.3 Caïc lãûnh âiãöu khiãøn a. Xoïa maìn hçnh xoïa_mh(); Xoïa saûch maìn hçnh træåïc khi in ra kãút quaí. b.Taûo cæía säø cæía_säø(x1, y1, x2, y2); Taûo cæía säø coï toüa âäü goïc trãn bãn traïi x1, y1 vaì toüa âäü goïc dæåïi bãn phaíi x2, y2. c. Âàût maìu chæî, maìu nãön maìu_chæî(color); maìu_nãön(color); Trong hai træåìng håüp trãn color laì mäüt biãún nguyãn chæïa maî cuía maìu (xem baíng2.1) Vê duû: maìu_chæî(4) chæî in ra seî laì maìu âoí maìu_nãön(1) maìu cuía nãön seî laì maìu xanh da tråìi d. Di chuyãøn con troí âãún(x, y) Di chuyãøn con troí âãún taûo âäü x, y cuía maìn hçnh tæång æïng våïi cæía säø hiãûn taûi. e. Caïc lãûnh vãö ám thanh ám_thanh(f); Taûo tên hiãûu ám thanh våïi táön säú f. tàõt(); Tàõt tên hiãûu ám thanh. f. Lãûnh trãù chæång trçnh chåì(ms); Laìm trãù chæång trçnh mäüt khoaíng thåìi gian miligiáy 2.4.4 Caïc haìm toaïn hoüc a. Tênh càn báûc hai cuía x càn_bh(x); Haìm naìy tênh càn báûc hai cuía biãún säú x, våïi x laì mäüt säú báút kç låïn hån 0 b. Haìm tênh giaï trë tuyãût âäúi cuía x trë_td(x); Haìm naìy tênh trë tuyãût âäúi cuía biãún säú x c. Caïc haìm tênh sin(x), cos(x), tg(x) sin(x); cos(x); tg(x); 2.4.5 Caïc haìm veî âäö hoüa Caïc haìm veî âäö hoüa âån giaín coï maìu neït veî âæåüc xaïc âënh båíi haìm maìu_veî(tãn maìu), våïi tãn maìu laì caïc säú trong baíng maìu 2.1. a. Haìm veî âæåìng thàóng â_thàóng(x1, y1, x2, y2); Veî mäüt âæåìng thàóng xaïc âënh våïi toüa âäü âiãøm âáöu laì (x1,y1) toüa âäü âiãøm cuäúi laì (x2,y2). b. Haìm veî hçnh chæî nháût hçnh_cn(x1, y1, x2, y2); Toüa âäü âènh trãn bãn traïi (x1,y1), toüa âäü âènh dæåïi bãn phaíi (x2,y2). c. Haìm veî âæåìng troìn â_troìn(x, y, r); Toüa âäü tám cuía âæåìng troìn (x,y), baïn kiïnh âæåìng troìn r d. Haìm veî elip elip(x, y, gd, gc, xr, yr); (x,y) laì toüa âäü cuía tám elip gd laì goïc âáöu gd laì goïc cuäúi xr laì baïn truûc ngang, yr laì baïn truûc âæïng. Tãn maìu Giaï trë säú (maî maìu) Maìu chæî hay maìu nãön Âen 0 Caí hai Xanh da tråìi 1 Caí hai Xanh laï cáy 2 Caí hai Xanh lå 3 Caí hai Âoí 4 Caí hai Têm 5 Caí hai Náu 6 Caí hai Xaïm nhaût 7 Caí hai Xaïm sáùm 8 Maìu chæî Xanh nhaût 9 Maìu chæî Xanh nhaût 10 Maìu chæî Xanh nhaût 11 Maìu chæî Âoí nhaût 12 Maìu chæî Têm nhaût 13 Maìu chæî Vaìng 14 Maìu chæî Tràõng 15 Maìu chæî Baíng 2.1 Baíng maìu CHÆÅNG 3 AÏP DUÛNG MÄÜT SÄÚ KYÎ THUÁÛT BIÃN DËCH CÅ BAÍN Chæång naìy seî trçnh baìy caïc bæåïc cå baín âãø xáy dæûng mäüt chæång trçnh dëch nhàòm laìm cå såí lyï thiãút âãø xáy dæûng chæång trçnh trong chæång tiãúp theo. 3.1 PHÁN TÊCH TÆÌ VÆÛNG Phán têch tæì væûng laì giai âoaûn âáöu cuía quaï trçnh biãn dëch. Nhiãûm vuû chuí yãúu cuía noï laì âoüc caïc kyï tæû nháûp räöi taûo ra mäüt chuäùi theí tæì cho bäü phán têch cuï phaïp sæí duûng trong giai âoaûn phán têch cuï phaïp. Tæång taïc giæîa bäü phán têch tæì væûng vaì bäü phán têch cuï phaïp minh hoüa (hçnh 3.1), âæåüc caìi âàût bàòng caïch cho bäü phán têch tæì væûng laìm mäüt thuí tuûc con hoàûc mäüt âäöng thuí tuûc våïi bäü phán têch cuï phaïp. chæång trçnh nguäön bäü phán têch tæì væûng baíng kyï hiãûu theí tæì láúy theí tæì kãú tiãúp Hçnh 3.1 Tæång taïc cuía bäü phán têch tæì væûng vaì bäü phán têch cuï phaïp bäü phán têch cuï phaïp Khi nháûn âæåüc yãu cáöu láúy theí tæì tiãúp theo tæì bäü phán têch cuï phaïp, bäü phán têch tæì væûng seî âoüc caïc kyï tæû cho âãún khi noï nháûn diãûn ra âæåüc mäüt theí tæì. Bäü phán têch tæì væûng laì thaình pháön âoüc chæång trçnh nguäön cuía trçnh biãn dëch, noï thæåìng thæûc hiãûn thãm mäüt säú taïc vuû khaïc åí mæïc giao diãûn ngæåìi sæí duûng nhæ sau: 3.1.1 Loaûi boí khoaíng tràõng vaì caïc doìng chuï thêch Chæång trçnh dëch seî xeït caïc kyï tæû trong nguyãn liãûu, vç thãú caïc kyï tæû ngoaìi dæû kiãún nhæ caïc kyï tæû träúng seî khiãún noï tháút baûi. Ngän ngæî láûp trçnh thæåìng cho pheïp caïc khoaíng tràõng (kyï tæû träúng, kyï tæû tab, kyï tæû xuäúng doìng) xuáút hiãûn giæîa caïc theí tæì. Bäü phán têch tæì væûng coï nhiãûm vuû loaûi boí caïc khoaíng tràõng naìy træåïc khi âæa qua bäü phán têch cuï phaïp. Caïc doìng chuï thêch cuîng âæåüc bäü phán têch cuï phaïp vaì chæång trçnh dëch boí qua, vç thãú chuïng cuîng âæåüc xæí lyï nhæ khoaíng tràõng. 3.1.2 Caïc hàòng Mäùi khi coï mäüt kyï säú xuáút hiãûn trong mäüt biãøu thæïc, coï leî seî håüp lyï hån khi cho pheïp âàût mäüt hàòng säú naìo âoï åí vë trê cuía noï. Båíi vç mäüt hàòng säú laì mäüt daîy caïc kyï säú, noï coï thãø duìng âæåüc bàòng caïch thãm caïc luáût sinh vaìo vàn phaûm cho caïc biãøu thæïc hoàûc bàòng caïch taûo ra mäüt theí tæì cho caïc hàòng nhæ thãú. Cäng viãûc gom caïc kyï säú thaình säú, âæåüc thæûc hiãûn båíi bäü phán têch tæì væûng båíi vç caïc säú coï thãø âæåüc xæí lyï nhæ nhæîng âån vë riãng biãût trong quaï trçnh dëch. Chàóng haûn num laì theí tæì biãøu thë mäüt säú thç bäü phán têch tæì væûng seî chuyãøn num cho bäü phán têch cuï phaïp. Giaï trë cuía säú seî âæåüc chuyãøn theo dæåïi daûng mäüt thuäüc tênh cuía theí tæì num, bäü phán têch tæì væûng seî chuyãøn caí theí tæì vaì thuäüc tênh cuía noï cho bäü phán têch cuï phaïp. Nãúu ta viãút mäüt theí tæì vaì thuäüc tênh cuía noï nhæ mäüt bäü dæî liãûu âæåüc bao giæîa hai dáúu thç nguyãn liãûu 25.5 + 90 - 20 âæåüc biãún âäøi thaình mäüt daîy caïc bäü Theí tæì +,- khäng coï thuäüc tênh. Thaình pháön thæï hai cuía caïc bäü khäng coï vai troì gç trong khi phán têch cuï phaïp nhæng seî cáön duìng âãún khi dëch. 3.1.3 Nháûn diãûn âënh danh vaì tæì daình riãng Ngän ngæî sæí duûng âënh danh laìm tãn cho caïc biãún. Mäüt vàn phaûm cho mäüt ngän thæåìng xæí lyï âënh danh nhæ mäüt theí tæì. Bäü phán têch cuï phaïp dæûa trãn mäüt vàn phaûm, nhæ thãú muäún nháûn âæåüc cuìng mäüt theí tæì chàóng haûn laì id, mäùi khi coï mäüt âënh danh xuáút hiãûn trong nguyãn liãûu. Vê duû: a:= a+ b; seî âæåüc bäü phán têch tæì væûng biãún âäøi thaình doìng theí tæì id = id + id Khi gàûp mäüt tæì täú taûo ra mäüt âënh danh trong nguyãn liãûu, thç ta cáön coï mäüt cå chãú xem tæì täú naìy âaî gàûp træåïc âoï hay chæa. Ta seî duìng mäüt baíng kyï hiãûu cho cäng viãûc naìy. Tæì täú læu trong baíng kyï hiãûu vaì mäüt con troí chè âãún muûc ghi trãn baíng tråí thaình mäüt thuäüc tênh cuía theí tæì id. Ngoaìi âënh danh coìn coï caïc tæì khoïa, caïc tãn haìm laì caïc tæì daình riãng, caïc âënh danh khäng âæåüc truìng tãn våïi caïc tæì naìy. Bäü phán têch tæì væûng xaïc âënh âënh danh hay tæì daình riãng bàòng caïch sau khi gom thaình theí tæì räöi so saïnh våïi caïc tæì daình riãng trong baíng kyï hiãûu nãúu khäng truìng thç theí tæì âoï laì id, ngæåüc laûi laì tæì daình riãng. 3.1.4 Giao diãûn cho bäü phán têch tæì væûng Khi mäüt bäü phán têch tæì væûng âæåüc âàût giæîa bäü phán têch cuï phaïp vaì doìng nguyãn liãûu, noï tæång taïc våïi caí hai pháön naìy nhæ (hçnh 3.2). Noï âoüc caïc kyï tæû tæì nguyãn liãûu, nhoïm chuïng laûi thaình caïc tæì täú räöi gæíi caïc theí tæì âæåüc taûo båíi caïc tæì täú cuìng våïi giaï trë thuäüc tênh cuía chuïng âãún giai âoaûn sau cuía trçnh biãn dëch. Trong mäüt säú tçnh huäúng, bäü phán têch tæì væûng phaíi âoüc træåïc mäüt kyï tæû træåïc khi coï thãø quyãút âënh seî traí vãö theí tæì naìo cho bäü phán têch cuï phaïp. Vê duû: Khi gàûp kyï tæû > thç bäü phán têch tæì væûng seî âoüc tiãúp. Nãúu kyï tæû kãú tiãúp laì = thç chuäùi kyï tæû >= laì tæì täú taûo ra theí tæì cho toaïn tæí “låïn hån hoàûc bàòng”. Ngæåüc laûi thç > laì tæì täú taûo ra theí tæì cho toaïn tæí “låïn hån”, vaì bäü phán têch tæì væûng âaî âoüc mäüt kyï tæû nhiãöu láön. Kyï tæû “dæ” ra naìy phaíi âæåüc âæa tråí laûi nguyãn liãûu, båíi vç noï coï thãø laì kyï tæì âáöu tiãn cuía tæì täú kãú tiãúp trong nguyãn liãûu. nguyãn liãûu truyãön theí tæì vaì thuäüc tênh âoüc kê tæû âáøy kê tæû tråí vãö bäü phán têch tæì væûng Hçnh 3.2 Âàût bäü phán têch tæì væûng vaìo giæîa nguyãn liãûu vaì bäü phán têch cuï phaïp bäü phán têch cuï phaïp Bäü phán têch tæì væûng taûo ra caïc theí tæì vaì bäü phán têch cuï phaïp seî sæí duûng noï. Caïc theí tæì sinh ra âæåüc giæî trong vuìng âãûm cho âãún khi chuïng âæåüc sæí duûng. Tæång taïc giæîa hai bäü phán têch naìy chè bë raìng buäüc båíi kiïch thæåïc vuìng âãûm båíi vç bäü phán têch tæì væûng seî khäng thãø tiãún haình khi vuìng âãûm âáöy coìn bäü phán têch cuï phaïp seî khäng thãø tiãún haình khi vuìng âãûm räùng. Vç vuìng âãûm chè giæî mäüt theí tæì nãn tæång taïc âæåüc caìi âàût âån giaín bàòng caïch âæa bäü phán têch tæì væûng thaình mäüt haìm âæåüc bäü phán têch cuï phaïp goüi, traí vãö caïc theí tæì theo nhæ yãu cáöu. 3.2 ÂËNH NGHÉA CUÏ PHAÏP Trong pháön naìy seî giåïi thiãûu mäüt hãû kyï phaïp coï tãn goüi laì vàn phaûm phi ngæî caính âæåüc duìng âãø xaïc âënh cuï phaïp cuía mäüt ngän ngæî. Mäüt vàn phaûm thæåìng mä taí cáúu truïc phán cáúp cuía nhiãöu kãút cáúu cuía caïc ngän ngæî láûp trçnh. Vê duû: Mäüt cáu lãûnh trong C coï daûng: if (biãøu_thæïc) lãûnh else lãûnh Coï nghéa laì mäüt pheïp näúi cuía tæì khoïa if, mäüt dáúu ngoàûc måí, mäüt biãøu thæïc, mäüt dáúu ngoàûc âoïng, cáu lãûnh, tæì khoïa else vaì cáu lãûnh khaïc. Cáu lãûnh coï thãø biãøu diãùn theo quy tàõc sau: lãûnh ® if (biãøu_thæïc) lãûnh else lãûnh Mäüt qui tàõc nhæ trãn âæåüc goüi laì luáût sinh. Trong luáût sinh, mäüt thaình pháön tæì væûng nhæ tæì khoïa vaì caïc dáúu ngoàûc âæåüc goüi laì caïc theí tæì (token). Caïc biãún nhæ biãøu_thæïc vaì lãûnh biãøu thë chuäùi caïc theí tæì vaì âæåüc goüi laì kyï hiãûu chæa kãút thuïc. Mäüt vàn phaûm phi ngæî caính coï bäún thaình pháön : 1. Mäüt táûp caïc theí tæì, goüi laì caïc kyï hiãûu kãút thuïc. 2. Mäüt táûp caïc kyï hiãûu chæa kãút thuïc. 4. Mäüt kyï hiãûu khåíi âáöu, âoï laì mäüt kyï hiãûu chæa kãút thuïc. 3. Mäüt táûp luáût sinh, trong âoï mäùi luáût sinh gäöm mäüt kyï hiãûu chæa kãút thuïc goüi laì vãú traïi cuía luáût sinh, mäüt muîi tãn, vaì mäüt chuäùi caïc theí tæì vaì/hoàûc caïc kyï hiãûu chæa kãút thuïc laì vãú phaíi cuía luáût sinh. Vê duû: A® a1ôa2ô. . .ôan, våïi a1, a2 ... laì caïc kyï hiãûu kãút thuïc hoàûc chæa kãút thuïc. Vê duû: Cho vàn phaûm G sinh ra caïc biãøu thæïc gäöm caïc säú, ngàn giæîa caïc säú laì dáúu + hoàûc - list ® list + digit | list - digit (3.1) | digit digit ® 0|1|2| ... |9 3.2.1 Cáy phán têch cuï phaïp Cáy phán têch cuï phaïp cho tháúy bàòng hçnh aính xem laìm nhæ thãú naìo dáùn xuáút ra mäüt chuäùi cuía ngän ngæî tæì kyï hiãûu khåíi âáöu cuía mäüt vàn phaûm. Vãö hçnh thæïc cho træåïc mäüt vàn phaûm phi ngæî caính, mäüt cáy phán têch cuï phaïp laì mäüt cáy coï âàûc tênh sau: - Gäúc coï nhaîn laì kyï hiãûu khåíi âáöu - Mäùi nuït laì coï nhaîn laì mäüt theí tæì hoàûc e - Mäùi nuït khäng phaíi laì nuït cuäúi cuía cáy thç âoï laì kyï hiãûu chæa kãút thuïc. - Nãúu A mäüt kyï hiãûu chæa kãút thuïc, laì nhaîn cuía nuït khäng phaíi laì nuït cuäúi, X1, X2,...Xn laì nhaîn caïc con cuía nuït coï nhaîn A tæì traïi sang phaíi thç A ® X1, X2,...Xn laì mäüt luáût sinh. X1, X2,...Xn laì caïc kyï hiãûu kãút thuïc hoàûc chæa kãút thuïc. Nãúu A® e thç mäüt nuït âæåüc gaïn nhaîn A coï thãø coï mäüt con duy nháút coï nhaîn e. 3.2.2 Tênh âa nghéa Mäùi cáy phán têch cuï phaïp âãöu dáùn xuáút chênh xaïc chuäùi âæåüc âoüc tæì caïc nuït laï nhæng mäüt vàn phaûm coï thãø coï nhiãöu cáy phán têch cuï phaïp sinh ra chuäùi theí tæì âaî cho. Mäüt vàn phaûm nhæ thãú goüi laì âa nghéa. Mäüt chuäùi våïi nhiãöu cáy phán têch cuï phaïp thæåìng coï nhiãöu nghéa. Âãø biãn dëch caïc chæång trçnh æïng duûng, chuïng ta cáön thiãút kãú caïc vàn phaûm âån nghéa, hoàûc sæí duûng caïc vàn phaûm âa nghéa våïi caïc qui tàõc bäø sung nhàòm giaíi quyãút tênh âa nghéa. 3.2.3 Tênh kãút håüp cuía toaïn tæí Trong pháön låïn caïc ngän ngæî láûp trçnh bäún toaïn tæí säú hoüc cäüng(+), træì(-), nhán(*) chia(/) âãöu coï tênh kãút håüp traïi, toaïn tæí láúy luîy thæìa, toaïn tæí gaïn coï tênh kãút håüp phaíi. 3.2.4 Tênh thæï báûc cuía toaïn tæí Chuïng ta noïi ràòng toaïn tæí nhán coï thæï báûc cao hån toaïn tæí cäüng nãúu * láúy caïc toaïn haûng cuía noï træåïc toaïn tæí +. Trong säú hoûc pheïp nhán vaì pheïp chia coï thæï báûc cao hån pheïp cäüng vaì pheïp træì. a. Cuï phaïp cho biãøu thæïc Vàn phaûm cho caïc biãøu thæïc säú hoüc coï thãø âæåüc xáy dæûng tæì mäüt baíng trçnh baìy tênh kãút håüp vaì thæï báûc cuía toaïn tæí. Chuïng ta bàõt âáöu våïi bäún toaïn tæí säú hoüc thäng thæåìng vaì mäüt baíng thæï báûc, trçnh baìy caïc toaïn tæí theo thæï báûc ngaìy caìng cao, caïc toaïn tæí coï cuìng thæï báûc åí trãn mäüt haìng. kãút håüp traïi: + - kãút håüp traïi: * / Chuïng ta taûo ra hai chæa táûn expr vaì term cho hai mæïc thæï báûc vaì mäüt chæa táûn factor næîa âãø taûo ra nhæîng âån vë cå baín cho biãøu thæïc. Caïc âån vë cå baín hiãûn coï trong biãøu thæïc laì caïc kyï säú(digit) vaì caïc biãøu thæïc coï âoïng måí ngoàûc âån. factor ® digit| (expr) Báy giåì ta xeït âãún toaïn tæí hai ngäi * vaì / våïi thæï báûc cao nháút. Båíi vç nhæîng toaïn tæí naìy coï tênh kãút håüp traïi, luáût sinh cuía chuïng tæång tæû nhæ luáût sinh cho caïc list(3.1) våïi tênh kãút håüp traïi. term ® term * factor |term / factor |factor Tæång tæû, expr sinh ra danh saïch(list) caïc term âæåüc phán caïch båíi toaïn tæí cäüng vaì træì expr ® expr + term |expr - term |term Do váûy chuïng ta thu âæåüc vàn phaûm sau expr ® expr + term | expr - term | term term ® term * factor | term / factor | factor factor ® digit | (expr) Vàn phaûm naìy xæí lyï biãøu thæïc nhæ mäüt danh saïch caïc term âæåüc phán caïch båíi dáúu * hoàûc /. Báút kyì mäüt biãøu thæïc naìo coï âoïng måí ngoàûc âãöu laì factor, vç thãú våïi caïc dáúu ngoàûc chuïng ta coï thãø xáy dæûng caïc biãøu thæïc tuìy nghi nhiãöu cáúp läöng vaìo nhau. b. Cuï phaïp caïc cáu lãûnh Tæì khoïa cho pheïp chuïng ta nháûn ra caïc cáu lãûnh trong pháön låïn caïc ngän ngæîî láûp trçnh. Táút caí moüi cáu lãûnh âæåüc xáy dæûng cho ngän ngæî Âån Giaín âãöu bàõt âáöu bàòng mäüt tæì khoïa ngoaûi træì lãûnh gaïn vaì låìi goüi haìm. Vê duû: Mäüt âoaûn vàn phaûm âæåüc xáy dæûng cho cuï phaïp cáu lãûnh Âån Giaín nhæ sau: lãûnh ® id:=biãøu_thæïc | nãúu bt_logic thç lãûnh | nãúu bt_logic thç lãûnh nãúu_khäng lãûnh | trong_khi bt_logic làûp lãûnh Dæûa vaìo nguyãn tàõc naìy chuïng ta coï thãø xáy dæûng cuï phaïp cho biãøu thæïc säú hoüc, duìng hai kyï hiãûu chæa kãút thuïc expr vaì term cho hai mæïc æu tiãn, term cho * vaì /, expr cho + vaì -. Kyï hiãûu chæa kãút thuïc factor sinh ra cho caïc biãøu thæïc cå baín. expr ® expr + term ï expr - term ï term term ® term * factor ï term / factor ï factor factor ® digit ï (expr) 3.3 PHÁN TÊCH CUÏ PHAÏP Quaï tçnh taûo ra dáùn xuáút hoàûc cáy dáùn xuáút cáu cuía ngän ngæî cho træåïc âæåüc goüi laì sæû phán têch hay laì phán têch cuï phaïp cuía cáu. Muûc âêch cuía quaï trçnh naìy khäng chè khàóng âënh laì liãûu mäüt xáu trãn baíng chæî cuía ngän ngæî coï phaíi laì cáu cuía ngän ngæî âoï khäng, nghéa laì khäng chæïa caïc läùi cuï phaïp, maì coìn khäng keïm pháön quan troüng laì tçm cáúu truïc cuï phaïp cuía cáu, âãø sau âoï coï thãø taûo ra baín dëch sang ngän ngæî khaïc. Bäü phán têch cuï phaïp phán têch chuäùi caïc theí tæì do bäü phán têch tæì væûng cung cáúp, âãø coï âæåüc cáúu truïc phæïc taûp hån cuía chæång trçnh nguäön nhæ biãøu thæïc, phaït biãøu, chæång trçnh con. Caïc cáúu truïc naìy âæåüc thãø hiãûn dæåïi daûng cáy cuï phaïp hay cáy dáùn xuáút dæûa trãn âënh nghéa cuía ngän ngæî nguäön. Caïc nuït laï cuía cáy cuï phaïp laì caïc theí tæì. Háöu hãút caïc phæång phaïp phán têch âãöu nàòm trong caïc låïp: Phán têch tæì trãn xuäúng (top-down) vaì phán têch cuï phaïp tæì dæåïi lãn (bottom-down). 3.3.1 Vai troì cuía bäü phán têch cuï phaïp Bäü phán têch cuï phaïp nháûn caïc chuäùi theí tæì tæì bäü phán têch tæì væûng (hçnh 3.3) âãø taûo ra cáúu truïc cuï phaïp cuía chæång trçnh nguäön. Âoï cuîng laì quaï trçnh xáy dæûng cáy phán têch cuï phaïp cho chuäùi theí tæì. Phæång phaïp thäng duûng âãø xáy dæûng bäü phán têch cuï phaïp laì phán têch cuï phaïp tæì trãn xuäúng hoàûc tæì dæåïi lãn. Bäü phán têch cuï phaïp tæì trãn xuäúng seî taûo cáy phán têch bàõt âáöu tæì gäúc tiãún haình âãún caïc nuït laï. Ngæåüc laûi bäü phán têch cuï phaïp tæì dæåïi lãn seî bàõt âáöu tæì caïc nuït laï âi âãún âènh cuía cáy phán têch cuía mäüt cáu cho træåïc. Kyï hiãûu nháûp cuía caí hai bäü phán têch cuï phaïp trãn âãöu âæåüc âoüc tæì traïi sang phaíi vaì âoüc tæìng kyï hiãûu mäüt. Tuy nhiãn hai phæång phaïp trãn chè laìm viãûc trãn táûp con cuía vàn phaûm phi ngæî caính maì thäi. Màûc duì laì caïc táûp con cuía vàn phaûm phi ngæî caính nhæng chuïng cuîng âuí miãu taí cuï phaïp cuía háöu hãút ngän ngæî láûp trçnh. Tênh thäng duûng cuía bäü phán têch cuï phaïp tæì trãn xuäúng laì do coï thãø xáy dæûng âæåüc chuïng mäüt caïch hiãûu quaí theo läúi thuí cäng. Bäü phán têch cuï phaïp tæì dæåïi lãn thæåìng âæåüc taûo tæì caïc cäng cuû tæû âäüng. cáy phán têch cuï phaïp caïc pháön khaïc cuía TBD chæång trçnh nguäön bäü phán têch tæì væûng baíng kyï hiãûu theí tæì láúy theí tæì kãú tiãúp Hçnh 3.3 Tæång taïc cuía bäü phán têch tæì væûng vaì bäü phán têch cuï phaïp bäü phán têch cuï phaïp (a) type type array [ simple ] of type type (c) array [ simple ] of type num dotdot num type (d) array [ simple ] of type num dotdot num simple integer type (e) array [ simple ] of type num dotdot num simple Hçnh 2.4 Caïc bæåïc xáy dæûng cáy phán têch cuï phaïp tæì trãn xuäúng 3.3.2 Phán têch cuï phaïp tæì trãn xuäúng Khi phán têch cuï phaïp tæì trãn xuäúng ta bàõt âáöu taûo ra cáy dáùn xuáút tæì gäúc laì kyï hiãûu âáöu cuía vàn phaûm vaì láön læåüc aïp duûng caïc qui tàõc cho kyï hiãûu chæa kãút thuïc traïi nháút trong caïc cáu thu âæåüc cho âãún âènh cuäúi cuía cáy dáùn xuáút laì kyï hiãûu nháút trong caïc cáu thu âæåüc cho âãún âènh cuäúi cuía cáy dáùn xuáút laì kyï hiãûu cuía cáu âæåüc phán têch. Giåïi thiãûu kyî thuáût phán têch cuï phaïp qua xem xeït mäüt vàn phaûm sau: type ® simple |­ id | array[simple] of type (3.2) simple ® integer | char | num dotdot num Sæí duûng theí tæì dotdot thay cho “..” âãø nháún maûnh ràòng chuäùi kyï tæû naìy âæåüc xæí lyï nhæ mäüt âån vë. Xáy dæûng cáy phán têch cuï phaïp theo läúi tæì trãn xuäúng (hçnh 3.4) âæåüc thæûc hiãûn tæì gäúc, våïi nhaîn laì chæa táûn khåíi âáöu räöi thæûc hiãûn hai bæåïc sau làûp âi làûp laûi: -Taûi nuït n coï nhaîn laì chæa táûn A, choün mäüt trong nhæîng luáût sinh cho A vaì cho caïc kyï hiãûu åí vãú phaíi cuía luáût sinh naìy laìm con cuía n. -Tçm nuït kãú tiãúp âãø xáy dæûng mäüt cáy con taûi âoï. Âäúi våïi mäüt säú vàn phaûm caïc bæåïc trãn coï thãø caìi âàût trong khi queït chuäùi nguyãn liãûu tæì traïi sang phaíi. Theí tæì âang âæåüc queït trong nguyãn liãûu thæåìng âæåüc goüi laì kyï hiãûu nhçn træåïc (lookahead symbol). Luïc ban âáöu kyï hiãûu nhçn træåïc laì theí tæì âáöu tiãn, nghéa laì theí tæì táûn traïi cuía chuäùi nguyãn liãûu. Hçnh 3.5 minh hoüa viãûc phán têch chuäùi. array [num dotdot num ] of integer Ban âáöu theí tæì array laì kyï hiãûu nhçn træåïc vaì pháön âaî biãút cuía cáy phán têch cuï phaïp bao gäöm gäúc coï nhaîn laì chæa táûn khåíi âáöu type trong (hçnh 3.4a). Muûc âêch laì xáy dæûng pháön coìn laûi cuía cáy sao cho chuäùi âæåüc sinh ra båíi cáy seî so khåïp âæåüc våïi chuäùi nguyãn liãûu. Âãø coï âæåüc mäüt âäúi saïnh cho chæa táûn type phaíi dáùn xuáút ra mäüt chuäùi bàõt âáöu bàòng kyï hiãûu nhçn træåïc array. Trong vàn phaûm (3.2) chè coï mäüt luáût sinh cho type coï thãø dáùn xuáút mäüt chuäùi nhæ thãú nãn ta seî choün luáût sinh âoï vaì xáy dæûng caïc con cho gäúc coï nhaîn laì nhæîng kyï hiãûu åí vãú phaíi cuía luáût sinh. Mäùi trong ba hçnh 3.4 coï caïc muîi tãn chè ra kyï hiãûu nhçn træåïc trong nguyãn liãûu vaì nuït âang âæåüc xeït trong cáy phán têch cuï phaïp. Khi xáy dæûng caïc con cuía mäüt nuït thç bæåïc kãú tiãúp ta xeït caïc con táûn traïi. Trong hçnh 3.4b, caïc con væìa âæåüc xáy dæûng taûi gäúc vaì con táûn traïi våïi nhaîn array seî âæåüc xeït. Trong cáy phán têch cuï phaïp, khi mäüt táûn vaì mäüt nuït cho táûn âoï âäúi saïnh âæåüc våïi kyï hiãûu nhçn træåïc thç ta dëch tåïi træåïc mäüt bæåïc, caí åí cáy phán têch cuï phaïp vaì åí nguyãn liãûu. Theí tæì kãú tiãúp trong nguyãûn liãûu tråí thaình lookahead(nhçn træåïc) måïi vaì con kãú tiãúp trong cáy seî âæåüc xeït. Trong hçnh 3.4c muîi tãn trong cáy âaî âæåüc dëch tåïi con kãú tiãúp cuía gäúc vaì muîi tãn trong nguyãn liãûu seî âæåüc dëch chuyãøn tåïi theí tæì tiãúp theo laì [. Sau khi dëch tåïi træåïc, muîi tãn trong cáy seî chè tåïi con coï nhaîn laì chæa táûn simple. Khi mäüt nuït coï nhaîn laì chæa táûn âæåüc xeït âãún, ta seî làûp laûi quaï trçnh choün mäüt luáût sinh cho chæa táûn âoï. Noïi chung, viãûc choün mäüt luáût sinh cho mäüt kyï hiãûu chæa táûn coï thãø âæåüc thæûc hiãûn theo kiãøu thæí vaì sai; nghéa laì ta coï thãø phaíi thæí mäüt luáût sinh räöi phaíi quay laûi âãø thæí mäüt luáût sinh khaïc nãúu luáût sinh thæï nháút khäng phuì håüp. Mäüt luáût sinh seî khäng phuì håüp nãúu sau khi duìng noï, ta khäng thãø taûo ra mäüt cáy khåïp âæåüc våïi chuäùi nguyãûn liãûu. Tuy nhiãn coï mäüt træåìng håüp âàûc biãût coï tãn laì phán têch cuï phaïp dæû âoaïn(predictive parsing) khäng coï tçnh traûng phaíi thæí laûi. (a) type Hçnh 3.5 Phán têch cuï phaïp tæì trãn xuäúng trong khi âoüc nguyãn liãûu tæì traïi sang phaíi array of integer [ num dotdot num ] type (b) array [ simple ] of type cáy PTCP nguyãn liãûu array of integer [ num dotdot num ] type (c) array [ simple ] of type cáy PTCP nguyãn liãûu array of integer [ num dotdot num ] cáy PTCP nguyãn liãûu 3.3.4 Phán têch cuï phaïp dæû âoaïn Phán têch cuï phaïp âãû qui xuäúng(recursive desent parsing) laì phæång phaïp phán têch tæì trãn xuäúng, trong âoï chuïng ta thæûc thi mäüt táûp thuí tuûc âãû qui âãø xæí lyï chuäùi nguyãn liãûu. Mäùi chæa táûn cuía vàn phaûm âæåüc keìm våïi mäüt thuí tuûc. ÅÍ âáy ta xeït mäüt hçnh thaïi âàûc biãût cuía phán têch cuï phaïp âãû qui xuäúng, âoï laì phán têch cuï phaïp dæû âoaïn, trong âoï lookahead giuïp xaïc âënh âuïng thuí tuûc cáön choün cho mäùi chæa táûn. Loaût thuí tuûc âæåüc goüi trong khi xæí lyï chuäùi nguyãn liãûu ngáöm âënh nghéa mäüt cáy phán têch cuï phaïp cho nguyãn liãûu. Bäü phán têch cuï phaïp dæû âoaïn (hçnh 3.5) gäöm caïc thuí tuûc cho chæa táûn type vaì simple cuía vàn phaûm (3.2) vaì mäüt thuí tuûc bäø sung match. Ta duìng match nhàòm âån giaín hoïa âoaûn maî cho type vaì simple; noï dëch tåïi theí tæì tiãúp theo nãúu âäúi t cuía noï so khåïp âæåüc våïi lookahead. Vç thãú match laìm thay âäøi biãún lookahead, âoï laì theí tæì hiãûn âang âæåüc queït trong nguyãn liãûu. procedure match(t:token); begin if lookahead=t then lookahead:= nexttolen else error end; procedure type; begin if lookahead thuäüc{integer, char,num} then simple else if lookahead = ‘­’ then begin match(‘­‘); match(id) end else if looahead = array then begin match(array);match(‘[‘); simple; match(‘]’) match(of); type end else error end; procedure simple; begin if lookahead = integer then match(integer) else if lookahead=char then match(char) else if lookahead = num then begin match(num); match(dotdot); match(num) end else error end; Hçnh 3.6 Âoaûn maî giaí cho bäü phán têch cuï phaïp dæû âoaïn Phán têch cuï phaïp bàõt âáöu bàòng mäüt låìi goüi âãún thuí tuûc cho chæa táûn khåíi âáöu type. Cuìng våïi nguyãn liãûu (hçnh 3.5), ban âáöu lookahead laì theí tæì thæï nháút array. Thuí tuûc type thæûc thi âoaûn maî. match(array); match(‘[‘); simple; match(‘]’) match(of); type tæång æïng våïi vãú phaíi cuía luáût sinh type ® array [simple] of type Mäùi táûn åí vãú phaíi âæåüc âäúi saïnh våïi kyï hiãûu nhçn træåïc vaì mäùi chæa táûn åí vãú phaíi dáùn âãún mäüt låìi goüi thuí tuûc cuía noï. Våïi nguyãn liãûu (hçnh 3.4), sau khi caïc theí tæì array vaì [ âaî âäúi saïnh, kyï hiãûu nhçn træåïc seî laì num. Luïc naìy thuí tuûc simple âæåüc goüi laì âoaûn maî match(num); match(dotdot); match(num) trong pháön thán cuía noï âæåüc thæûc thi. Kyï hiãûu nhçn træåïc hæåïng dáùn viãûc choün læûa luáût sinh. Nãúu vãú phaíi cuía mäüt luáût sinh bàõt âáöu bàòng mäüt theí tæì thç luáût sinh coï thãø âæåüc duìng khi kyï hiãûu nhçn træåïc âäúi saïnh âæåüc våïi theí tæì. Báy giåì ta xeït vãú phaíi bàõt âáöu bàòng mäüt chæa táûn nhæ: type ® simple Luáût sinh naìy âæåüc duìng nãúu kyï hiãûu nhçn træåïc coï thãø âæåüc sinh ra tæì simple. Vê duû trong khi thæûc hiãûn âoaûn maî: match(array); match(‘[‘); simple; match(‘]’) match(of); type giaí sæí kyï hiãûu nhçn træåïc integer khi quyãön âiãöu khiãøn âæåüc trao cho låìi goüi thuí tuûc type. Khäng coï luáût sinh naìo cho type bàõt âáöu bàòng theí tæì integer. Tuy nhiãn mäüt luáût sinh simple laûi coï vç thãú luáût sinh type ®simple âæåüc duìng bàòng caïch yãu cáöu type goüi thuí tuûc simple trãn nhçn træåïc integer. Phán têch cuï phaïp dæû âoaïn dæûa vaìo thäng tin vãö nhæîng kyï hiãûu âáöu tiãn âæåüc sinh ra båíi vãú phaíi cuía luáût sinh. Noïi chênh xaïc hån, goüi a laì vãú phaíi cuía mäüt luáût sinh cho båíi chæa táûn A. Ta âënh nghéa FIRST(a) laì táûp theí tæì xuáút hiãûn nhæ nhæîng kyï hiãûu âáöu tiãn cuía mäüt hoàûc nhiãöu chuäùi âæåüc sinh ra tæì a. Nãúu a laì e hoàûc coï thãø sinh ra e thç e cuîng thuäüc FIRST(a). Caïc táûp FIRST phaíi âæåüc xeït âãún nãúu coï hai luáût sinh A ® a vaì B ®b. Phán têch âãû qui xuäúng khäng tråí lui âoìi hoíi ràòng FIRST(a) vaì FIRST(b) phaíi råìi nhau. Vç thãú kyï hiãûu nhçn træåïc coï thãø âæåüc duìng âãø quyãút âënh xem phaíi sæí duûng luáût sinh naìo; nãúu kyï hiãûu saíi våïi thuäüc FIRST(a) thç a âæåüc duìng. Ngæåüc laûi nãúu kyï hiãûu saíi våïi thuäüc FIRST(b) thç b âæåüc duìng. 3.3.5 Thiãút kãú bäü phán têch cuï phaïp dæû âoaïn Bäü phán têch cuï phaïp dæû âoaïn laì mäüt chæång trçnh gäöm coï mäüt thuí tuûc cho mäùi kyï hiãûu chæa táûn. Mäùi thuí tuûc seî âæåüc thæûc hiãûn hai viãûc: 1. Noï quyãút âënh xem luáût sinh naìo nhåì vaìo kyï hiãûu saíi våïi. Luáût sinh coï vãú phaíi a seî âæåüc duìng nãúu kyï hiãûu saíi våïi thuäüc FIRST(a). Nãúu coï xung âäüt giæîa hai vãú trãn mäüt kyï hiãûu saíi våïi naìo âoï thç chuïng ta khäng thãø duìng phæång phaïp phán têch cuï phaïp naìy trãn vàn phaûm âang coï. Mäüt luáût sinh coï e åí vãú phaíi âæåüc duìng nãúu nhçn træåïc(lookahead) khäng thuäüc táûp FIRST cuía mäüt vãú phaíi khaïc. 2. Thuí tuûc seî âæåüc sæí duûng mäüt luáût sinh bàòng caïch mä phoíng vãú phaíi. Mäüt chæa táûn gáy ra mäüt låìi goüi âãún thuí tuûc cho kyï hiãûu âoï vaì mäüt theí tæì âäúi saïnh âæåüc våïi kyï hiãûu nhçn træåïc gáy ra haình âäüng âoüc theí tæì kãú tiãúp. Nãúu taûi mäüt thåìi âiãøm naìo âoï, theí tæì trong luáût sinh khäng âäúi saïnh âæåüc våïi kyï hiãûu nhçn træåïc thç seî phaíi khai baïo mäüt läùi. 3.3.6 Âãû qui traïi Mäüt vàn phaûm laì âãû qui traïi nãúu noï coï mäüt chæa táûn A sao cho coï mäüt dáùn xuáút A ® aA våïi a laì mäüt chuäùi naìo âoï. Caïc phæång phaïp phán têch cuï phaïp tæì trãn xuäúng khäng xæí lyï caïc vàn phaûm âãû qui traïi, vç thãú cáön phaíi coï mäüt pheïp biãún âäøi loaûi boí âãû qui traïi. ÅÍ âáy chè nãu ra caïch âån giaín laì thay thãú càûp luáût sinh âãû qui traïi A ® aA|b bàòng caïc luáût sinh khäng âãû qui traïi A ® bA’ A’ ® aA’ | e maì khäng laìm thay âäøi táûp chuäùi khaí suy tæì A. 3.4 BAÍNG KYÏ HIÃÛU Mäüt cáúu truïc dæî liãûu âæåüc goüi laì baíng kyï hiãûu(symbol table) âæåüc duìng âãø læu træî thäng tin vãö nhiãöu kãút cáúu cuía ngän ngæî nguäön. Caïc thäng tin naìy âæåüc thu tháûp trong giai âoaûn phán têch cuï phaïp, seî cáön thiãút cho giai âoaûn phán têch ngæî nghéa vaì sinh maî âäúi tæåüng.Vê duû trong quaï trçnh phán têch tæì væûng, caïc tæì täú taûo ra mäüt âënh danh seî âæåüc læu vaìo muûc ghi trong baíng kyï hiãûu. Caïc giai âoaûn sau coï thãø bäø sung thãm caïc thäng tin vãö kiãøu cuía âënh danh vaì vë trê âæåüc læu trong baíng. 3.4.1 Giao diãûn cuía baíng kyï hiãûu Caïc thuí tuûc cuía baíng kyï hiãûu chuí yãúu liãn quan âãún viãûc læu vaì truy xuáút caïc tæì täú. Khi mäüt tæì täú âæåüc læu chuïng ta cuîng læu theí tæì âi keìm våïi tæì täú âoï. Caïc thao taïc âæåüc thæûc hiãûn trãn baíng kyï hiãûu: insert(s,t): traí vãö chè muûc cuía muûc ghi måïi cho chuäùi s, theí tæì t lookup(s): traí vãö chè muûc cuía muûc ghi daình cho chuäùi s, hoàûc laì 0 nãúu khäng tçm tháúy s. Bäü phán têch tæì væûng duìng thao taïc lookup âãø xaïc âënh xem âaî coï mäüt muûc ghi daình cho mäüt tæì täú trong baíng kyï hiãûu hay chæa. Nãúu muûc ghi âoï chæa coï thç noï duìng thao taïc insert âãø taûo ra. Mäüt caìi âàût trong âoï caí bäü phán têch tæì væûng vaì bäü phán têch cuï phaïp âãöu biãút vãö daûng thæïc cuía caïc muûc ghi trong baíng kyï hiãûu seî âæåüc thaío luáûn pháön sau. 3.4.2 Xæí lyï caïc daình riãng Coï thãø sæí duûng caïc thuí tuûc trãn âãø xæí lyï caïc tæì daình riãng. Vê duû xeït caïc theí tæì (laì tæì khoïa) if vaì then våïi caïc tæì täú if vaì then: insert (“if”, if); insert(“then”,then). Moüi låìi goüi cuía haìm lookup(if), lookup(then) sau âoï seî traí vãö theí tæì if, then vç thãú if, then khäng thãø laìm duìng âënh danh âæåüc. Mäüt táûp caïc tæì daình riãng coï thãø âæåüc xæí lyï theo läúi naìy qua viãûc khåíi gaïn baíng kyï hiãûu cho phuì håüp. 3.4.3 Mäüt caìi dàût cho baíng kyï hiãûu Cáúu truïc dæî liãûu caìi âàût cho baíng kyï hiãûu âæåüc phaït thaío trong (hçnh 3.7). lexptr token value 1 5 9 15 div mod id id 1 2 3 4 0 symtable EOS n EOS EOS d i v m o d c o u t i EOS lexems Hçnh 3.7 Baíng kyï hiãûu Ta khäng muäún daình ra mäüt læåüng khäng gian nháút âënh âãø læu caïc tæì täú taûo ra âënh danh; mäüt læåüng khäng gian cäú âënh coï thãø khäng âuí låïn âãø læu caïc âënh danh ráút daìi vaì coï thãø laìm laîng phê nhiãöu khi gàûp mäüt âënh danh ngàõn. Baíng symtale laì mäüt daîy. Mäùi pháön tæí cuía daîy laì máøu tin læu giæîa hai vuìng. Vuìng con troí lexptr chè âãún kyï tæû bàõt âáöu cuía mäùi trë tæì væûng trong daîy lexemes. Vuìng token læu giæî loaûi token. Coìn caïc trë thuäüc tênh khaïc seî khäng noïi åí âáy. Vë trê thæï 0 cuía symtale âãø träúng vç khi lookup khäng tçm tháúy token cáön tçm, noï seî traí vãö 0 laì vë trê cuía symtable. Vë trê 1, 2 chæïa caïc tæì khoïa div, mod. Vë trê 3, 4 chæïa danh biãøu coï trë tæì væûng laì count vaì i, ngàn caïch giæîa caïc trë tæì væûng kyï hiãûu EOS, khäng thuäüc trong danh biãøu. Giaíi thuáût nháûn daûng token cuía bäü phán têch tæì væûng (hçnh 3.8). Nãúu kyï tæû laì dáúu träúng, kyï tæû tab, dáúu xuäúng doìng âæåüc bäü phán têch tæì væûng raì âãún chuïng seî boí qua maì khäng cáút vaìo baíng danh kyï hiãûu vaì khäng sinh ra token. Biãún toaìn cuûc lineno seî tàng lãn mäüt khi dáúu xuäúng doìng âæåüc raì âãún. Bäü phán têch tæì væûng seî âoüc kyï tæû tiãúp theo. Nãúu gàûp kyï tæû âáöu tiãn cuía trë tæì væûng måïi laì säú, bäü phán têch tæì væûng seî âoüc tiãúp caïc kyï tæû kãú tiãúp. Nãúu laûi laì säú, bäü phán têch tæì væûng gheïp caïc säú thaình mäüt con säú chæïa vaìo biãún tokenval, cho loaûi token laì num. Nãúu kyï tæû âáöu tiãn cuía token tiãúp theo laì chæî, bäü phán têch tæì væûng seî cáút chæî säú vaìo bäü âãûm lexbuf. Sau âoï lookup seî duìng lexbuf tçm kiãúm trong baíng kyï hiãûu, nãúu näüi dung cuía lexbuf laì div hoàûc mod thç khäng coï haình vi cáút vaìo baíng danh biãøu, maì traí sang bäü phán têch cuï phaïp hoàûc . Nãúu lookup tçm tháúy näüi dung trong lexbuf âaî coï trong baíng kyï hiãûu maì khäng phaíi laì tæì daình riãng thç bäü phán têch tæì væûng seî gåíi sang bäü phán têch cuï phaïp . Trong træåìng håüp naìy trë thuäüc tênh laì vë trê cuía danh biãøu trong baíng symtable. Nãúu khäng tçm tháúy lookup seî traí vãö trë 0, luïc âoï insert thæûc hiãûn haình vi thãm näüi dung cuía lexbuf vaì loaûi token vaìo baíng kyï hiãûu, trë p âæåüc tokenval læu chæïa vaì loaûi token âæåüc giæî trong biãún typetoken. function lexan:integer; var lexbuf: array[0..100]of char; c: char; begin loop begin âoüc mäüt kyï tæû vaìo c; if c laì mäüt kyï tæû träúng then khäng thæûc hiãûn gç caí else if c laì mäüt kyï tæû newline then lineno:=lineno+1 else if c laì mäüt kyï säú then begin âàût tokenval laì giaï trë cuía kyï säú naìy vaì caïc kyï säú theo sau; return num end else if c laì mäüt chæî caïi then begin âàût c vaì caïc kyï tæû, kyï säú theo sau vaìo lexbuf; p:=lookup(lexbuf ); if p=0 then p:=insert(lexbuf,id); tokenval:=p; return træåìng token cuía muûc ghi p end else begin /* theí tæì laì mäüt kyï tæû*/ âàût tokenval laì none ; /*khäng coï thuäüc tênh*/ return säú nguyãn maî hoïa kyï tæû c end end end Hçnh 3.8 Âoaûn maî giaí cho bäü phán têch tæì væûng CHÆÅNG 4 THIÃÚT KÃÚ CHÆÅNG TRÇNH DËCH CHO NGÄN NGÆÎ ÂÅN GIAÍN Chæång naìy seî nãu lãn caïch thiãút kãú chæång trçnh dëch dæûa trãn cå såí lyï thuyãút âaî nãu åí chæång 3. Ngän ngæî âæåüc caìi âàût âãø thiãút kãú laì ngän ngæî C. Âáöu vaìo laì mäüt file chæång trçnh nguäön viãút bàòng ngän ngæî Âån Giaín, âáöu ra laì kãút quaí cuía chæång trçnh naìy. 4.1 MÄ TAÍ CHÆÅNG TRÇNH DËCH Chæång trçnh dëch âæåüc thiãút kãú bàòng caïch duìng læåüc âäö dëch cuï phaïp (hçnh4.1a,b,c). Læåüc âäö naìy âæåüc xáy dæûng dæûa trãn cuï phaïp cuía ngän ngæî Âån Giaín chæång_trçnh ® daîy_lãûnh daîy_lãûnh ® lãûnh;daîy_lãûnh|lãûnh; lãûnh ® {daîy_lãûnh} |nãúu btqh thç lãûnh opt_else_clause |cho id:=bt tåïi bt lãûnh |cho id:=bt xuäúng bt lãûnh |trong_khi btqh làûp lãûnh |làûp_laûi lãûnh âãún_khi btqh |id:=bt |lãûnh_khaïc opt_else_lause ®nãúu_khäng lãûnh|e Hçnh 4.1a Læåüc âäö dëch cuï phaïp cho caïc cáu lãûnh lãûnh_khaïc laì caïc lãûnh goüi haìm, mäùi haìm coï mäüt chæïc nàng riãng vaì tãn goüi cuía mäùi haìm khaïc nhau. Táûp caïc kyï hiãûu chæa kãút thuïc: Vn = {chæång_trçnh, daîy_lãûnh, lãûnh, btqh, biãøu_thæïc, lãûnh_khaïc} Táûp caïc kyï hiãûu kãút thuïc: Vt={; {, }, nãúu, thç, nãúu_khäng, cho, tåïi, xuäúng, trong_khi, làûp, làûp_laûi, âãún_khi, id, :=, =} Kyï hiãûu muûc tiãu: chæång_trçnh Trong âoï: btqh: (biãøu thæïc quan hãû): gäöm caïc pheïp toaïn quan hãû giæîa biãøu thæïc våïi biãøu thæïc (, >=, =, ), caïc pheïp toaïn logic (phuí_âënh,vaì,hoàûc) coï theí läöng nhau. Noï âæåüc âënh nghéa: btqh ® qh term1 term1 ® bt_logic qh term1 |e bt_logic ® vaì | hoàûc qh ® ( btqh ) | phuí_âënh qh | bt pt_qh bt pt_qh ® | >= | = | Hçnh 4.1b Læåüc âäö dëch cuï phaïp cho biãøu thæïc quan hãû bt(biãøu thæïc säú hoüc): caïc säú, âënh danh vaì caïc pheïp toaïn säú hoüc coï thãø läöng nhau thäng qua caïc dáúu ngoàûc âån “(“, ”)”. bt ® term rest1 | -bt rest1 ®+term rest1 |-term rest1 |e term ® factor rest2 rest2 ® *factor rest2 |/factor rest2 |div factor rest2 |mod factor rest2 |e factor ® (bt) |id |num Hçnh 4.1c Læåüc âäö dëch cho caïc biãøu thæïc säú hoüc Theí tæì id(âënh danh) biãøu diãùn mäüt daîy khäng räùng gäöm caïc chæî caïi vaì kyï säú bàõt âáöu bàòng chæî caïi, num laì mäüt daîy kyï säú, eof laì kyï tæû cuäúi táûp tin. Caïc theí tæì âæåüc phán caïch båíi caïc khoaíng tràõng. Âoaûn maî chæång trçnh âæåüc viãút trong nhiãöu mä âun, mäùi mä âun laì mäüt haìm, thæûc hiãûn tæìng chæïc nàng riãng trong quaï trçnh phán têch vaì diãùn dëch. Mä âun chênh âãø dëch chæång trçnh laì haìm compile(), caìi âàût nhæ sau: int compile() { init(); nextsym(); lookahead=typetoken; order(1); if (err) return 0; else return 1; } Haìm init() âæåüc goüi âáöu tiãn âãø khåíi gaïn caïc tæì daình riãng vaìo baíng kyï hiãûu. Luïc âáöu loaûi token vaì trë tæì væûng cuía caïc tæì daình riãng âæåüc cáút trong daîy keyword, init seî duìng haìm insert âãø cáút caïc tæì khoïa vaìo baíng kyï hiãûu træåïc khi trçnh biãn dëch bàõt âáöu laìm viãûc.Tiãúp theo haìm nextsym() âæåüc goüi, haìm naìy thæûc hiãûn chæïc nàng phán têch tæì væûng. Biãún lookahead âæåüc gaïn cho loaûi tæì täú typetoken træåïc khi goüi haìm order(1) âãø thæûc hiãûn caïc lãûnh trong chæång trçnh. 4.2 MÄ ÂUN PHÁN TÊCH TÆÌ VÆÛNG Bäü phán têch tæì væûng laì mäüt haìm coï tãn laì nextsym() âæåüc goüi båíi bäü phán têch cuï phaïp. Haìm naìy âoüc nguyãn liãûu, mäùi láön mäüt kyï tæû räöi âæa vaìo maíng lexbuf, tçm ra theí tæì vaì traí vãö theí tæì væìa tçm âæåüc cho bäü phán têch cuï phaïp. Giaï trë thuäüc tênh âi keìm âæåüc gaïn cho biãún toaìn cuûc tokenval, nãúu laì säú thç tokenval nháûn giaï trë cuía säú âoï, ngæåüc laûi tokenval seî læu vë trê cuía theí tæì âoï trong baíng kyï hiãûu. Caïc hàòng nguyãn id biãøu diãùn cho mäüt âënh danh, num laì mäüt säú, done laì kyï hiãûu cuäúi táûp tin, none laì mäüt kyï tæû báút kyì. Biãún typetoken læu giæî loaûi theí tæì. Baíng 3.1 trçnh baìy theí tæì vaì giaï trë sinh ra båíi bäü phán têch tæì væûng cho mäùi tæì täú cuía chæång trçnh nguäön. Tæì täú Theí tæì Giaï trë thuäüc tênh khoaíng tràõng...... daîy säú................ tæì daình riãng...... âënh danh........... kyï tæû cuäúi táûp tin kyï tæû báút kyì........ num chênh tæì âoï id done kyï tæû âoï giaï trë säú cuía daîy chè muûc vaìo baíng symtable none Baíng 3.1 Mä taí caïc theí tæì Haìm input() loaûi boí caïc khoaíng tràõng, caïc doìng chuï thêch vaì tàng biãún toaìn cuûc lineno lãn mäùi khi gàûp kyï tæû newline. Bäü phán têch tæì væûng sæí duûng haìm lookup(str s) trãn baíng kyï hiãûu âãø xaïc âënh xem mäüt tæì täú cho âënh danh âaî tæìng gàûp træåïc âoï hay chæa vaì haìm insert(str s, int typetoken, float val) seî læu mäüt tæì täú måïi vaìo trong baíng kyï hiãûu. 4.3 MÄ ÂUN PHÁN TÊCH CUÏ PHAÏP Bäü phán têch cuï phaïp gäöm táûp håüp caïc haìm, mäùi haìm coï nhiãûm vuû suy dáùn mäüt kyï hiãûu khäng kãút thuïc cuía vàn phaûm thaình mäüt âoaûn cuía vàn baín nguäön. Ta goüi cäng viãûc cuía haìm laì triãøn khai mäüt âêch. Coï bao nhiãu kyï hiãûu khäng kãút thuïc tæïc laì coï báúy nhiãu haìm. Khi triãøn khai mäüt âêch(dæûa vaìo læåüc âäö dëch cuï phaïp) laûi coï thãø gàûp mäüt kyï hiãûu khäng kãút thuïc, âoìi hoíi phaíi triãøn khai mäüt âêch måïi(âêch con) trong khi âêch cuî chæa triãøn khai xong. Båíi váûy, caïc haìm phán têch cuï phaïp seî goüi láùn nhau. Xem biãøu âäö cuï phaïp hçnh 4.2. Bäü phán têch cuï phaïp åí âáy âæåüc xáy dæûng theo phæång phaïp âãû quy xuäúng dæûa trãn læåüc âäö dëch dæûa cuï phaïp (hçnh 4.1). Trong âoï ta xáy dæûng caïc haìm cho caïc chæa táûn factor(haûng thæïc), term(säú haûng), bt(biãøu thæïc), qh(quan hãû), btqh(biãøu thæïc quan hãû), order(lãûnh), other_order (lãûnh_khaïc). Caïc haìm naìy seî luän goüi haìm match() âãø kiãøm tra ra caïc theí tæì, âoüc theí tæì kãú tiãúp nãúu kyï hiãûu nhçn træåïc våïi(lookahead) âäúi saïnh âæåüc vaì thäng baïo läùi trong træåìng håüp ngæåüc laûi. 4.3.1 Xáy dæûng biãøu âäö cuï phaïp Mäùi ä chæî nháût tæång æïng våïi mäüt haìm vaì caïc haìm seî goüi láùn nhau nhæ trong biãøu âäö sau: chæång trçnh factor term bt qh btqh other_order order Hçnh 4.2 Biãøu âäö cuï phaïp 4.3.2 Phán têch cuï phaïp âãû qui xuäúng Âãø váûn duûng phæång phaïp phán têch cuï phaïp âãû qui xuäúng vàn phaûm cuía ngän ngæî phaíi laì mäüt vàn phaûm LL(1). Muäún thãú phaíi thoîa maîn hai âiãöu kiãûn Âiãöu kiãûn 1: Våïi moüi saín xuáút coï daûng A® a1| a2| a3...| an thç phaíi coï: FIRST(ai) Ç FIRST(aj) = f våïi moüi i#j Âiãöu kiãûn 2: Våïi moüi kyï hiãûu khäng kãút thuïc A maì A Þ *e thç phaíi coï: FIRST(A) Ç FOLLOW(A) = f Våïi FIRST(a) laì táûp caïc kyï hiãûu kãút thuïc âæïng âáöu mäüt xáu naìo âoï suy dáùn tæì a, coìn FOLLOW(A) laì táûp caïc kyï hiãûu kãút thuïc âæïng liãön sau A trong mäüt daûng cáu naìo âoï suy dáùn tæì kyï hiãûu âáöu S. Våïi vàn phaûm cuía ngän ngæî Âån Giaín, ta coï baíng4.2 tênh FIRST, FOLLOW thoía maîn hai âiãöu kiãûn trãn nhæ sau: A FIRST(A) FOLOW(A) daîy_lãûnh { nãúu cho trong_khi làûp_laûi id } ; nãúu_khäng âãún_khi lãûnh { nãúu cho trong_khi làûp_laûi id } ; nãúu_khäng âãún_khi btqh ( phuí_âënh id num } ; ) thç làûp nãúu_khäng âãún_khi qh ( phuí_âënh id num } ; vaì hoàûc thç làûp ) nãúu_khäng âãún_khi bt - ( id num } ; ) >= = xuäúng tåïi thç làûp ; } vaì hoàûc nãu_khäng âãn_khi term ( id num } ; + - >= = ) xuäúng tåïi thç làûp nãu_khäng âãún_khi factor id num ( } ; * / div mod + - >= = xuäúng tåïi thç làûp ) nãúu_khäng âãún_khi Baíng 4.2 Baíng tênh FIRST, FOLLOW cho caïc kyï hiãûu chæa kãút thuïc Phán têch theo läúi âãû quy xuäúng: ÅÍ mäùi thåìi âiãøm luän coï mäüt âêch âang âæåüc triãøn khai (tæïc laì thuí tuûc tæång æïng våïi âêch âoï) âang âæåüc thæûc hiãûn vaì viãûc kiãøm tra cuï phaïp âaî tiãún haình âãún mäüt âiãøm naìo âoï trãn vàn baín nguäön. Bãn traïi cuía âiãøm âoï laì pháön vàn baín nguäön âaî triãøn khai cuï phaïp, coìn bãn phaíi laì pháön chæa kiãøm tra. Cäng viãûc cuía mäüt thuí tuûc triãøn khai mäüt âêch laì tiãún haình kiãøm tra cuï phaïp cuía âoaûn vàn baín nguäön âæåüc âoüc vaìo, räöi noï âem âäúi chiãúu våïi mäüt âæåìng trãn så âäö cuï phaïp cuía ngän ngæî nguäön, xem âoaûn vàn baín âoï coï thãø hiãûn âuïng cuï phaïp diãùn taí båíi cuï phaïp trãn âæåìng âoï khäng. ÅÍ mäùi bæåïc cuía quaï trçnh âoï, thç træåïc hãút tæì täú trong vàn baín nguäön âæåüc âoüc vaìo, räöi noï âem âäúi chiãúu våïi nuït tiãúp âãún trãn så âäö cuï phaïp. Nãúu nuït âoï khäng phaíi laì nuït chæî nháût thç nuït âoï phaíi chæïa âuïng tæì täú væìa âoüc. Coìn nãúu nuït âoï laì nuït chæî nháût coï chæïa mäüt kyï hiãûu khäng kãút thuïc A thç tæì täú væìa âoüc phaíi thuäüc FIRST(A) vaì báúy giåì phaíi triãøn khai âêch con A. Nãúu khäng khåïp nhæ váûy thç vàn baín nguäön coï läùi cuï phaïp taûi tæì täú âang xeït. Trong quaï trçnh phán têch cuï phaïp, tæì täú tiãúp âãún luän âæåüc âoüc træåïc räöi måïi âäúi chiãúu våïi cuï phaïp sau. Chênh viãûc âoüc træåïc naìy cho pheïp choün âuïng âæåìng âi trãn så âäö cuï phaïp (pháön 2.2). Khi ra khoíi mäüt thuí tuûc phán têch cuï phaïp thç mäüt tæì täú âaî âæåüc âoüc dæ ra. Tæì täú naìy khäng thuäüc cáúu truïc A væìa triãøn khai xong, maì thuäüc FOLLOW(A) vaì seî laì tæì täú âæïng âáöu cuía cáúu truïc tiãúp sau A. 4.4 XÆÍ LYÏ NGÆÎ NGHÉA Giai âoaûn phán têch ngæî nghéa âæåüc läöng vaìo trong giai âoaûn phán têch cuï phaïp nhàòm xaïc âënh toaïn tæí vaì toaïn haûng cuía caïc biãøu thæïc vaì cáu lãûnh. ÅÍ âáy, chæång trçnh dëch seî kiãøm tra kiãøu dæûa theo âàûc taí cuía ngän ngæî nguäön, xem caïc toaïn haûng cuía mäüt toaïn tæí coï håüp lãû khäng. CHÆÅNG 5 THÆÍ NGHIÃÛM CHÆÅNG TRÇNH 5.1 CAÏCH SÆÍ DUÛNG Âãø thæûc hiãûn chæång trçnh trãn ngän ngæî láûp trçnh Âån Giaín ta láön læåüc theo caïc bæåïc sau: - Chaûy chæång trçnh CT.BAT seî suáút hiãûn mäüt maìn hçnh soaûn thaío. Doìng Cäüt Thoaït Tãn ct Cheìn Læu Måí Måïií Âoïng In Læu laûi - Soaûn thaío chæång trçnh. Nãúu chæång trçnh âaî coï sàôn trãn âéa thç báúm F3 sau âoï nháûp tãn âæåìng dáùn, tãn file cáön måí. - Chaûy chæång trçnh bàòng caïch báúm Crtl+F9 âãø biãn dëch vaì sæía läùi. Coï thãø Báúm Alt+F5 âãø xem maìn hçnh kãút quaí. - Báúm F2 âãø læu laûi nãúu cáön thiãút. - Thoaït chæång trçnh bàòng caïch báúm Alt+X. 5.2 BAÌI TOAÏN VÊ DUÛ Vê duû 1: “Viãút chæång trçnh tênh tiãön âiãûn “Tiãön thuã bao âiãûn kãú laì 1000 âäöng/thaïng “TIãön âënh mæïc sæí duûng mäùi häü laì 50 kW “Pháön âënh mæïc tênh giaï 250 âäöng/Kwh “Nãúu pháön væåüt quaï âënh mæïc thç tiãön phaût cho pháön naìy laì 500 “âäöng/Kwh xoïa_mh(); maìu_chæî(4); viãút_xd('Chæång trçnh tênh tiãön âiãûn’); giaï_âm:=250; thuã_bao:=1000; âënh_mæïc:=50; maìu_chæî(15); viãút(‘Chè säú cuî:’); âoüc_xd(chè_sc); viãút(‘Chè säú måïi:’); âoüc_xd(chè_sm); nãúu((chè_sm-chè_sc)<=âënh_mæïc)thç{ traí_âm:=(chè_sm-chè_sc)*200; traí_phaût:=0; täøng:=traí_âm+thuã_bao; } nãúu((chè_sm-chè_sc)>âënh_mæïc)thç{ traí_âm:=50*200; traí_phaût:=(chè_sm-chè_sc)*500; täøng:=thuã_bao+traí_âm+traí_phaût; } viãút_xd(‘Pháön traí âënh mæïc:’,traí_âm); viãút_xd(‘Pháön taí phaût laì:’,traí_phaût); viãút_xd(‘Tiãön traí täøng cäüng laì:’täøng); âoüc_xd(); Kãút quaí: Chæång trçnh tênh tiãön âiãûn Chè säú cuî:50 Chè säú måïi: 150 Pháön traí âënh mæïc: 10000 Pháön traí phaût: 25000 Täøng tiãön traí: 36000 Vê duû 2: "Vãút chæång trçnh nháûp vaìo hai säú giáy khaïc nhau âäøi "giáyra giåì phuït giáy “ Cäüng hai säú giáy laûi âäøi ra giåì phuït giáy xoïa_mh(); viãút(‘Nháûp säú giáy thæï nháút:’); âoüc_xd(säú1); viãút(‘Nháûp säú giáy thæï hai:’); âoüc_xd(säú2); “Biãún âäøi säú1 ra giåì phuït giáy giåì1:=säú1 div 3600; säú_dæ:=säú1 mod 3600; phuït1:=säú_dæ div 60; giáy1:=säú_ dæ mod 60; viãút_xd(säú1,’giáybàòng:’,giåì1,’giåì’ ,phuït1,’phuït’,giáy1,’giáy’); “biãún âäøi säú2 tæì giáy ra giåì phuït giáy giåì2:=säú2 div 3600; säú_dæ:=säú2 mod 3600; phuït2:=säú_dæ div 60; giáy2:=säú_ dæ mod 60; viãút_xd(säú2,’giáybàòng:’,giåì2,’giåì’ ,phuït2,’phuït’,giáy2,’giáy’); “Biãún âäøi täøng ra giåì phuït giáy “Caïch tênh thæï nháút giåì_täøng:=säú_täøng div 3600; säú_dæ:= säú_täøng mod 3600; phuït_täøng:=säú_dæ div 60; giáy_täøng:=säú_dæ mod 60; viãút_xd(‘Täøng hai säú bàòng:’,giåì_täøng,’giåì, phuït_täøng,’phuït’,giáy_täøng,’giáy’); “Kiãøm tra baìng pheïp tênh thæï hai nhæ sau: giåì:=giåì1+giåì2; phuït:=phuït1+phuït2; giáy:=giáy1+giáy2; nãúu(giáy>=60)thç{ giáy:=giáy-60; phuït:=phuït+1; } nãúu(phuït>=60)thç{ phuït:=phuït-60; giåì_:=giåì+1; } viãút_xd(‘Täøng hai säú laì:’,giåì,’giåì’,phuït,’phuït’,giáy,’giáy’); “So saïnh hai kãút quaí cuía pheïp tênh nãúu((giåì_täøng=giåì) vaì(phuït_täøng=phuït) vaì(giáy_täøng=giáy)) thç viãút_xd(‘Pheïp biãún âäøi chênh xaïc’); nãúu_khäng viãút_xd(‘Pheïp biãún âäøi sai,xem laûi’); âoüc_xd(); Kãút quaí: Nháûp säú giáy thæï nháút: 4000 Nháûp säú giáy thæï hai: 5000 4000 giáy bàòng: 1giåì 6phuït 40giáy 5000 giáy bàòng: 1giåì 23phuït 20giáy Täøng cuía hai säú bàòng:2giåì 30phuït 0giáy Täøng cuía hai säú bàòng:2giåì 30phuït 0giáy Pheïp biãún âäøi chênh xaïc Vê duû 3: ” Veî hçnh chæî nháût, veî âæåìng thàóng våïi toüa âäü xaïc âënh xoïa_mh(); âäö_hoüa(); maìu_veî(3); â_thàóng(100,100,200,100); hçnh_cn(100,100,300,200); âoïng_dh(); Kãút quaí: CHÆÅNG 6 KÃÚT LUÁÛN 6.1 KÃÚT QUAÍ ÂAÛT ÂÆÅÜC Âaî hoaìn thaình viãûc thiãút kãú mäüt ngän ngæî láûp trçnh Âån Giaín vaì xáy dæûng chæång trçnh dëch cho ngän ngæî naìy. Âáöu vaìo laì mäüt chæång trçnh Âån Giaín, âáöu ra laì kãút quaí dëch âæåüc cuía chæång trçnh naìy. chæång trçnh nguäön phán têch tæì væûng phán têch cuï phaïp & xæí lyï lãûnh kãút quaí chæång trçnh Hçnh 6.1 Caïc giai âoaûn diãùn dëch 6.2 TÊNH KHAÍ THI Hãû thäúng dãù daìng sæí duûng cho nhæîng ai måïi bàõt âáöu hoüc láûp trçnh, æïng duûng âãø giaíi quyãút caïc baìi toaïn, laìm quen våïi caïch láûp trçnh trãn maïy tênh. Chæång trçnh dëch âæåüc xáy dæûng theo phæång phaïp diãùn dëch nãn coï låiü thãú vãö màût khäng gian hån so våïi phæång phaïp biãn dëch 6.3 HAÛN CHÃÚ Chæång trçnh âæåüc xáy dæûng âãø giaíi quyãút caïc baìi toaïn nhoí, khäng phæïc taûp, våïi cáúu truïc lãûnh âån giaín. Chæa xáy dæûng âæåüc hãû thäúng chæång trçnh giaíi quyãút kiãøu maíng, kiãøu cáúu truïc... Thåìi gian dëch cháûm, so våïi trçnh biãn dëch thç âáy laì nhæåüc âiãøm. Nãúu chæång trçnh màõc nhiãöu läùi thç seî phaíi dëch nhiãöu láön, mäùi láön dëch chè biãút âæåüc mäüt läùi trong chæång trçnh. 6.4 HÆÅÏNG PHAÏT TRIÃØN Coï thãø phaït triãøn chæång trçnh bàòng caïch âæa thãm mäüt säú kiãøu dæî liãûu måïi nhæ: kiãøu kyï tæû, kiãøu maíng, kiãøu cáúu truïc,...vaì nhiãöu cäng cuû âäö hoüa hån âãø hoüc sinh phäø thäng, cuîng nhæ nhæîng ngæåìi muäún láûp trçnh giaíi quyãút caïc baìi toaïn phæïc taûp hån coï thãø æïng duûng âæåüc. PHUÛ LUÛC chuï thêch táûp caïc kyï hiãûu trong ngän ngæî âån giaín Loaûi tæì täú TT Caïc kyï hiãûu YÏ nghéa Pheïp toaïn säú hoüc 1 2 3 4 5 6 + - * / div mod cäüng træì nhán chia chia láúy nguyãn chia láúy dæ Pheïp toaïn quan hãû 7 8 9 10 11 12 < <= > >= = nhoí hån nhoí hån hoàûc bàòng låïn hån låïn hån hoàûc bàòng bàòng khaïc Pheïp toaïn logic 13 14 15 vaì hoàûc phuí_âënh vaì hoàûc phuí âënh Caïc lãûnh 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 := viãút viãút_xd âoüc âoüc_xd càn_bh trë_tâ â_thàóng â_troìn elip hçnh_cn xoïa_mh cæía_säø maìu_chæî maìu_nãön âãún ám_thanh tàõt chåì Lãûnh gaïn Lãûnh hiãøn thë ra maìn hçnh Viãút xong xuäúng doìng Âoüc vaìo mäüt giaï trë Âoüc xong xuäúng doìng Tênh càn báûc hai Tênh trë tuyãût âäúi Veî âæåìng thàóng Veî âæåìng troìn Veî elip Veî hçnh chæî nháût Xoïa maìn hçnh Taûo mäüt cæía säø trãn maìn hçnh Âàût maìu chæî Âàût maìu nãön Di chuyãøn con troí Taûo tên hiãûu ám thanh Tàõt tên hiãûu ám thanh Ngæng chæång trçnh mäüt khoaíng thåìi gian TAÌI LIÃÛU THAM KHAÍO [1] Compiler design in C Alfred.Aho, Ravi Sethi vaì Jeffrey Ullman [2] PASCAL An Introduction To The Art Walter J. Savitch and Sience of Programming [3] Trçnh Biãn Dëch Phan Thë Tæåi [4] Kyî Thuáût Láûp Trçnh C GS. Phaûm Vàn ÁÚt [5] Âäö aïn män hoüc Trçnh Biãn Dëch Nguyãùn Minh Nháût