Generator programm leksicheskogo analiza lex Proizvodstvenno-vnedrencheskij kooperativ "I N T E R F E J S" Dialogovaya Edinaya Mobil'naya Operacionnaya Sistema Demos/P 2.1 Generator programm leksicheskogo analiza lex Moskva 1988 Annotaciya V dokumente opisan yazyk programmirovaniya lex, prednaz- nachennyj dlya razrabotki programm leksicheskogo analiza. Pri- vodyatsya pravila raboty s kompilyatorom yazyka lex OS DEMOS. 1. Vvedenie lex - generator programm leksicheskogo analiza. Leksi- cheskij analiz - eto raspoznavanie leksem vo vhodnom potoke simvolov. Predpolozhim, chto zadano nekotoroe konechnoe mno- zhestvo slov (leksem) v nekotorom yazyke i nekotoroe vhodnoe slovo. Neobhodimo ustanovit', kakoj element mnozhestva (esli on sushchestvuet) sovpadaet s dannym vhodnym slovom. Obychno leksicheskij analiz vypolnyaetsya tak nazyvaemym leksicheskim analizatorom. Leksicheskij analizator - eto programma. Leksicheskij analiz primenyaetsya vo mnogih sluchayah, nap- rimer, dlya postroeniya paketnogo redaktora ili v kachestve raspoznavatelya direktiv v dialogovoj programme i t.d. Odnako, naibolee vazhnoe primenenie leksicheskogo analizatora - eto ispol'zovanie ego v kompilyatore. Zdes' leksicheskij analizator vypolnyaet funkciyu programmy vvoda dannyh. Leksicheskij analizator vypolnyaet pervuyu stadiyu kompilya- cii - chitaet stroki kompiliruemoj programmy, vydelyaet lek- semy i peredaet ih na dal'nejshie stadii kompilyacii (gramma- ticheskij razbor, kodogeneraciyu i t.d.). Leksicheskij analizator raspoznaet tip kazhdoj leksemy i sootvetstvuyushchim obrazom pomechaet ee. Naprimer, pri kompilya- cii Si-programmy mogut byt' vydeleny sleduyushchie tipy leksem: chislo, identifikator, operator, ogranichitel' i t.d. Leksicheskij analizator dolzhen ne tol'ko vydelit' lek- semu, no i vypolnit' nekotorye preobrazovaniya. Naprimer, esli leksema - chislo, to ego neobhodimo perevesti vo vnut- rennyuyu (dvoichnuyu) formu zapisi kak chislo s plavayushchej ili fiksirovannoj tochkoj. A esli leksema - identifikator, to ego neobhodimo razmestit' v tablice, chtoby v dal'nejshem obrashchat'sya k nemu ne po imeni, a po adresu v tablice. Hotya leksicheskij analiz po svoej idee prost, tem ne menee eta faza raboty kompilyatora chasto zanimaet bol'she vre- meni, chem lyubaya drugaya. CHastichno eto proishodit iz-za neob- hodimosti prosmatrivat' i analizirovat' ishodnyj tekst sim- vol za simvolom. Inogda dazhe byvaet neobhodimo vernut' pro- chitannyj simvol vo vhodnoj potok s tem, chtoby povtorit' prosmotr i analiz. Proishodit eto potomu, chto chasto byvaet trudno oprede- lit', gde prohodyat granicy leksemy. Dopustim, imeyutsya dve leksemy: make makefile 3 Pust' iz vhodnogo potoka postupaet nabor simvolov: ...makefile... Pri analize vhodnogo potoka simvolov budet vydelena leksema make, hotya pravil'no bylo by vydelit' leksemu makefile. Edinstvennyj sposob preodolet' eto zatrudnenie - pros- motr poluchennoj cepochki simvolov nazad i vpered. V nashem primere pri vydelenii leksemy make my dolzhny prosmotret' sleduyushchij postupayushchij simvol i, esli on budet simvolom "f", to vpolne vozmozhno, chto postupaet leksema makefile. Process prosmotra vhodnogo potoka mozhno rassmatrivat' kak dvizhenie vlevo i vpravo ramki nad cepochkoj simvolov. Pri etom analiziruetsya tol'ko tot simvol, kotoryj ohvachen ram- koj. ... . . source make.f.ile file compiler . . ... <=== ===> Analiz zaklyuchaetsya v opredelenii sootvetstviya rassmatrivae- moj posledovatel'nosti simvolov nekotoromu tak nazyvaemomu regulyarnomu vyrazheniyu. Naprimer, regulyarnoe vyrazhenie (+?[0-9])+|(-?[0-9])+ pozvolyaet vydelit' v cepochke vse leksemy tipa celoe, pered kotorymi libo ukazan znak (+ ili -), libo ne ukazan. Dlya chisel s tochkoj eto vyrazhenie imelo by vid: (+?[0-9.])+|(-?[0-9.])+ V teh sluchayah, kogda vydelenie leksemy zatrudneno libo po prichine togo, chto odno regulyarnoe vyrazhenie ne pozvolyaet ee odnoznachno opredelit', libo iz-za togo, chto leksema yavlyaetsya chast'yu drugoj, prihoditsya pribegat' k kontekstno-zavisimym algoritmam analiza s ispol'zovaniem levogo i pravogo naprav- lenij prosmotra vhodnoj cepochki simvolov. lex chastichno ili polnost'yu avtomatiziruet process napisaniya programmy leksicheskogo analiza. lex - eto program- miruyushchaya programma ili generator programm. lex stroit prog- rammu - leksicheskij analizator na tak nazyvaemom host-yazyke (ili "glavnom" yazyke). |to znachit, chto Lex-programma pishetsya na "yazyke" lex, a Lex-generator, v svoyu ochered', generiruet programmu leksicheskogo analiza na kakom-libo drugom yazyke. 4 Dannaya versiya lex generiruet leksicheskie analizatory na yazy- kah Si i Ratfor (racional'nyj dialekt Fortrana). V kachestve host-yazyka my budem ispol'zovat' yazyk Si. Svedeniya ob ispol'zovanii v kachestve host-yazyka Ratfor vydeleny v otdel'nyj paragraf. V kataloge /usr/lib/lex imeetsya fajl-zagotovka ncform, kotoryj ispol'zuetsya Lex-generatorom dlya postroeniya leksi- cheskogo analizatora. |tot fajl yavlyaetsya uzhe gotovoj prog- rammoj leksicheskogo analiza, no v nem ne opredeleny dejst- viya, kotorye neobhodimo vypolnit' pri raspoznavanii leksemy, otstutstvuyut i sami leksemy, ne sformirovany rabochie massivy i t.d. lex na osnove Lex-programmy dostraivaet fajl ncform. V rezul'tate my poluchaem fajl so standartnym imenem lex.yy.c, kotoryj yavlyaetsya tekstom Si-programmy, osushchestvlyayushchej leksi- cheskij analiz. Lex-programma imeet sleduyushchij format: opredeleniya %% pravila %% podprogrammy, sostavlennye pol'zovatelem Lyuboj iz etih razdelov mozhet byt' pustym. Prostejshaya Lex- programma imeet vid: %% Zdes' net nikakih opredelenij i nikakih pravil. Vse razdely Lex-programmy my podrobno rassmotrim nizhe. Sejchas celesoobrazno rassmotret', chto predstavlyayut soboj pravila. Pravilo sostoit iz dvuh chastej: REGULYARNOE_VYRAZHENIE DEJSTVIE Po regulyarnym vyrazheniyam, soderzhashchimsya v levoj chasti pravil, lex stroit determinirovannyj konechnyj avtomat. |tot avtomat osushchestvlyaet interpretaciyu, a ne kompilyaciyu. Kolichestvo pra- vil i ih slozhnost' ne vliyayut na skorost' leksicheskogo ana- liza, esli tol'ko pravila ne trebuyut slishkom bol'shogo ob®ema povtornyh prosmotrov vhodnoj posledovatel'nosti simvolov. Odnako, s rostom chisla pravil i ih slozhnosti rastet razmer konechnogo avtomata, interpretiruyushchego ih i, sledovatel'no, rastet razmer Si-programmy, realizuyushchej etot konechnyj avto- mat. 5 Rassmotrim v kachestve primera sleduyushchuyu Lex-programmu: %% [jJ][aA][nN][uU][aA][rR][yY] { printf("YAnvar'"); } [fF][eE][bB][rR][uU][aA][rR][yY] { printf("Fevral'"); } [mM][aA][rR][cC][hH] { printf("Mart"); } [aA][pP][rR][iI][lL] { printf("Aprel'"); } [mM][aA][yY] { printf("Maj"); } [jJ][uU][nN][eE] { printf("Iyun'"); } [jJ][uU][lL][yY] { printf("Iyul'"); } [aA][uU][gG][uU][sS][tT] { printf("Avgust"); } [sS][eE][pP][tT][eE][mM][bB][eE][rR] { printf("Sentyabr'"); } [oO][cC][tT][oO][bB][eE][rR] { printf("Oktyabr'"); } [nN][oO][vV][eE][mM][bB][eE][rR] { printf("Noyabr'"); } [dD][eE][cC][eE][mM][bB][eE][rR] { printf("Dekabr'"); } [mM][oO][nN][dD][aA][yY] { printf("Ponedel'nik");} [tT][uU][eE][sS][dD][aA][yY] { printf("Vtornik"); } [wW][eE][dD][nN][eE][sS][dD][aA][yY] { printf("Sreda"); } [tT][hH][uU][rR][sS][dD][aA][yY] { printf("CHetverg"); } [fF][rR][iI][dD][aA][yY] { printf("Pyatnica"); } [sS][aA][tT][uU][rR][dD][aA][yY] { printf("Subbota"); } [sS][uU][nN][dD][aA][yY] { printf("Voskresen'e");} Programma stroit konechnyj avtomat, kotoryj raspoznaet ang- lijskie naimenovaniya mesyacev i dnej nedeli. Kazhdoe pravilo zdes' opredeleyaet dejstvie (kotoroe vzyato v figurnye skobki). Obratite vnimanie na to, chto otkryvayushchaya figurnaya skobka stoit v toj zhe stroke, chto i pravilo - eto trebovanie lex. Dejstvie v kazhdom pravile dannoj Lex-programmy - eto vyvod russkogo znacheniya najdennogo anglijskogo slova. V kachestve operatora, vypolnyayushchego dejstvie, ispol'zuetsya bib- liotechnaya funkciya yazyka Si. 6 Para figurnyh skobok opredelyaet blok (v smysle yazyka Si), kotoryj mozhet soderzhat' lyuboe kolichestvo strok. Esli dejstvie soderzhit vsego odnu stroku Si, to mozhno ee ukazat' bez figurnyh skobok, kak obychno. Edinstvennoe uslovie - ona dolzhna nachinat'sya v toj zhe stroke, gde ukazano regulyarnoe vyrazhenie. V programme soderzhitsya tol'ko razdel pravil, ih vsego 19. Regulyarnoe vyrazhenie kazhdogo pravila opredelyaet anglijs- koe slovo, napisannoe malen'kimi ili bol'shimi latinskimi simvolami. Naprimer "May" (Maj) opredelen kak "[mM][aA][yY]". Po etomu regulyarnomu vyrazheniyu budet vyde- lena vo vhodnom potoke simvolov leksema "May", a po dejstviyu etogo pravila budet vyvedeno "Maj". Nalichie bol'shoj i maloj bukvy v kvadratnyh skobkah obespechivaet raspoznavanie slova "May", napisannogo lyubymi latinskimi simvolami. Takim obrazom, dannaya Lex-programma stroit Si- programmu, kotoraya perevodit na russkij yazyk imena mesyacev i dnej nedeli. Dopustim, Lex-programma razmeshchena v fajle source.l, togda, chtoby poluchit' leksicheskij analizator na Si, neobho- dimo vypolnit' sleduyushchij nabor komand: % lex source.l % cc -O lex.yy.c -ll -o program % lex vsegda, esli ne ukazano drugoe, stroit vyhodnoj fajl s imenem lex.yy.c - Si-programmu - leksicheskij analizator. Vo vtoroj stroke etoj posledovatel'nosti komand zapuskaetsya Si-kompilyator, kotoryj vyvodit rezul'tat v fajl program. Program mozhet rabotat' kak fil'tr v konvejere komand, kak samostoyatel'naya komanda i v interaktivnom rezhime. Napri- mer: % program May Maj MONDAY Ponedel'nik MoNdaY Ponedel'nik CNTRL/C % Flag -ll trebuet podklyucheniya biblioteki /usr/lib/libl.a - biblioteki lex. Esli neobhodimo poluchit' samostoyatel'nuyu programmu, kak v dannom sluchae, podklyuchenie biblioteki 7 obyazatel'no, poskol'ku togda iz nee podklyuchaetsya golovnoj razdel main. V protivnom sluchae, esli imeetsya neobhodimost' vklyuchit' analizator v kachestve funkcii v druguyu programmu (naprimer, v programmu grammaticheskogo razbora), etu biblio- teku neobhodimo vyzvat' uzhe pri sborke i togda, esli main opredelen v vyzyvayushchej leksicheskij analizator programme, redaktor svyazej ne budet podklyuchat' razdel main iz biblio- teki lex. Esli neobhodimo poluchit' fajl s imenem, otlichnym ot lex.yy.c, mozhno vospol'zovat'sya flagom -t : % lex -t source.l >&gt; file Po etomu flagu rezul'tat postupaet v fajl file. 2. Regulyarnye vyrazheniya v Lex-pravilah Regulyarnye vyrazheniya opredelyayut leksemu. Regulyarnoe vyrazhenie mozhet soderzhat' simvoly latinskogo i russkogo alfavitov v verhnem i nizhnem registrah, drugie simvoly (cifry, znaki prepinaniya i t.d.) i simvoly-operatory. Operatory pozvolyayut osushchestvlyat' razlichnye dejstviya nad vydelennoj cepochkoj simvolov. Operatory takzhe oboznachayutsya simvolami. 2.1. Oboznacheniya simvolov v vyrazheniyah V vyrazhenii mozhno ispol'zovat' lyuboj simvol. Simvol mozhno ukazyvat' v dvojnyh kavychkah. V etom sluchae eto vsegda prosto simvol - ego special'noe znachenie otmenyaetsya. Napri- mer: "abc" abc eti posledovatel'nosti simvolov identichny. . tochka oznachaet lyuboj simvol, krome simvola novoj stroki "\n"; \vos'merichnyj_kod_simvola ukazanie simvola ego vos'merichnym kodom (kak v Si); \n simvol novoj stroki; \t simvol tabulyacii; \b vozvrat kursora na odin shag nazad; 8 probel lyuboj simvol probela v vyrazhenii, esli on ne nahoditsya vnutri kvadratnyh skobok, neobhodimo zaklyuchat' v dvoj- nye kavychki. |to neobhodimo, tak kak probel i tabulyaciya ispol'zuyutsya lex v kachestve razdelitelya mezhdu opredele- niem i dejstviem v pravile. 2.2. Operatory regulyarnyh vyrazhenij Operatory oboznachayutsya simvolami-operatorami, k nim otnosyatsya: \ ^ ? * + | $ / % [] {} () <&lt;>&gt; Kazhdyj iz etih simvolov ili par skobok v regulyarnom vyrazhe- nii igraet rol' operatora. Esli neobhodimo otmenit' speci- al'noe znachenie simvola, oboznachayushchego operator, pered nim nuzhno postavit' simvol \ ili ukazat' ego v dvojnyh kavychkah. Naprimer: abc+ - simvol "+" - operator; abc\+ - simvol "+"; abc"+" - simvol "+". 2.3. Operator vydeleniya klassov simvolov Kvadratnye skobki zadayut klassy simvolov, kotorye v nih zaklyucheny. [abc] oznachaet libo simvol "a", libo "b", libo simvol "c"; Znak - ispol'zuetsya dlya ukazaniya lyubogo simvola iz lek- sikograficheski uporyadochennoj posledovatel'nosti: [A-z] oznachaet lyuboj latinskij simvol; [A-YA] lyubaya propisnaya russkaya bukva; [+-0-9] vse cifry i znaki "+" i "-". 2.4. Povtoriteli Kogda neobhodimo ukazat' povtoryaemost' vhozhdeniya sim- vola v regulyarnom vyrazhenii, ispol'zuyut operatory- povtoriteli * i +. 9 Operator * oznachaet lyuboe (v tom chisle i 0) chislo vhozh- denij simvola ili klassa simvolov. Naprimer: x* lyuboe chislo vhozhdenij simvola "x"; abc* lyuboe chislo vhozhdenij cepochki "abc"; [A-z]* lyuboe chislo vhozhdenij lyuboj latinskoj bukvy; [A-ZA-YAa-za-ya_0-9]* lyuboe vhozhdenie russkih i latinskih bukv, znaka podcher- kivaniya i cifr. Operator + oznachaet odno i bolee vhozhdenij. Naprimer: x+ odno ili bolee vhozhdenij "x"; [0-9]+ odno ili bolee vhozhdenij cifr; abc+ odno ili bolee vhozhdenij cepochki abc; [A-z]+ odno ili bolee vhozhdenij lyuboj latinskoj bukvy. 2.5. Operatory vybora Operatory: / | ? $ ^ upravlyayut processom vybora simvolov. Operator /: ab/cd "ab" uchityvaetsya tol'ko togda, kogda za nim sleduet "cd". Operator |: ab|cd ili "ab", ili "cd". Operator ?: x? oznachaet neobyazatel'nyj simvol "x". _?[A-Za-z]* oznachaet, chto pered cepochkoj lyubogo kolichestva latins- kih bukv mozhet byt' neobyazatel'nyj znak podcherkivaniya. 10 -?[0-9]+ vydelit lyuboe celoe chislo s neobyazatel'nym minusom vpe- redi. Operator $: x$ oznachaet vybrat' simvol "x", esli on yavlyaetsya poslednim v stroke. Stoit pered simvolom "\n"! abc$ oznachaet vybrat' cepochku "abc", esli ona zavershaet stroku. Operator ^: ^x oznachaet vybrat' simvol "x", esli on yavlyaetsya pervym simvolom stroki; ^abc oznachaet vybrat' cepochku simvolov "abc", esli ona nachi- naet stroku. [^A-Z]* oznachaet vse simvoly, krome propisnyh latinskih bukv. Kogda simvol ^ stoit pered vyrazheniem ili vnutri [], on vypolnyaet operaciyu dopolnenie. Vnutri kvadratnyh skobok simvol ^ dolzhen obyazatel'no stoyat' pervym u otkryvayushchej skobki! 2.6. Operator {} Operator {} imeet dva razlichnyh primeneniya: x{n,m} zdes' n i m natural'nye, m > n. Oznachaet ot n do m vhozhdenij x, naprimer, x{2,7} - ot 2 do 7 vhozhdenij x. {imya} vmesto {imya} v dannoe mesto vyrazheniya budet podstav- leno opredelenie imeni iz oblasti opredelenij Lex- programmy. Primer: BUKVA [A-ZA-YAa-za-ya_] CIFRA [0-9] IDENTIFIKATOR {BUKVA}({BUKVA}|{CIFRA})* %% {IDENTIFIKATOR} printf("\n%s",yytext); lex postroit leksicheskij analizator, kotoryj budet oprede- lyat' i vyvodit' vse "slova" iz vhodnogo fajla. Pod slovom v dannom sluchae podrazumevaetsya identifikator Si-programmy. V etom primere {IDENTIFIKATOR} budet zamenen na {BUKVA}({BUKVA}|{CIFRA})*, zatem na [A-ZA-YAa-za-ya_]([A-ZA- YAa-za-ya_]|[0-9])*. 11 yytext - eto vneshnij massiv simvolov programmy lex.yy.c, kotoruyu stroit lex. yytext formiruetsya v processe chteniya vhodnogo fajla i soderzhit tekst, dlya kotorogo usta- novleno sootvetstvie kakomu-libo vyrazheniyu. |tot massiv dos- tupen pol'zovatel'skim razdelam Lex-programmy. Operator printf vyvodit kazhdyj identifikator na novoj stroke. Pravilo ".|\n ;" ispol'zuetsya dlya togo, chtoby propustit' (ne vyvodit') vse cepochki simvolov, kotorye ne sootvetstvuyut regulyarnomu vyrazheniyu {IDENTIFIKATOR}. 2.7. Operator <&lt;>&gt;. Sluzhebnye slova START i BEGIN Razdel pravil Lex-programmy mozhet soderzhat' aktivnye i neaktivnye pravila. Aktivnye pravila vypolnyayutsya vsegda. Neaktivnye vypolnyayutsya tol'ko v teh sluchayah, kogda vypolnya- etsya nekotoroe nachal'noe uslovie. Nachal'nye usloviya Lex-programmy pomeshchayutsya v razdel opredelenij, a neaktivnye pravila pomechayutsya sootvetstvuyu- shchimi usloviyami. Operator START pozvolyaet ukazat' spisok nachal'nyh uslovij Lex-programmy, a operator BEGIN pozvolyaet aktivirovat' pravila, pomechennye nachal'nymi usloviyami. Aktivnye pravila imeyut sleduyushchij sintaksis: REGULYARNOE_VYRAZHENIE DEJSTVIE Neaktivnye pravila imeyut sleduyushchij sintaksis: <&lt;METKA_USLOVIYA>&gt;REG_VYRAZHENIE DEJSTVIE VAZHNO: lyuboe pravilo dolzhno nachinat'sya s pervoj pozicii stroki, probely i tabulyacii nedopustimy - oni ispol'zuyutsya kak razdeliteli mezhdu regulyarnym vyrazheniem i dejstviem v pravile! Rassmotrim primer: 12 %START COMMENT KOMM_NACHALO "/*" KOMM_KONEC "*/" %% {KOMM_NACHALO} { ECHO; BEGIN COMMENT;}; [\t\n]* ; <COMMENT>[^*]* ECHO; <COMMENT>[^/] ECHO; <COMMENT>{KOMM_KONEC} { ECHO; printf("0); BEGIN 0;}; lex postroit leksicheskij analizator, kotoryj vydelyaet kom- mentarii v Si-programme i zapisyvaet ih v standartnyj fajl vyvoda. Programma nachinaetsya s klyuchevogo slova START, koto- roe ukazano posle simvola %. Klyuchevoe slovo START mozhno ukazat' i tak: Start, ili S, ili s . Za klyuchevym slovom START ukazana metka nachal'nogo usloviya COMMENT. Operator "<COMMENT>x" oznachaet - x, esli analizator nahoditsya v nachal'nom uslovii COMMENT. Operator "BEGIN COMMENT;" perevodit analizator v nachal'noe uslovie COMMENT (smotrite pervoe pravilo razdela pravil etoj Lex-programmy). Posle etogo analizator uzhe naho- ditsya v novom sostoyanii i teper' razbor vhodnogo potoka sim- volov budet osushchestvlyaetsya i temi pravilami, kotorye nachina- yutsya operatorom "<COMMENT>". Naprimer, pravilo <COMMENT>[^*]* ECHO; vypolnyaetsya tol'ko togda, kogda vo vhodnom potoke simvolov budet obnaruzheno nachalo kommentariev ("/*"). V etom sluchae analizator zapisyvaet v standartnyj fajl vyvoda lyuboe chislo (v tom chisle i nol') simvolov, otlichnyh ot simvola "*". Ope- rator "BEGIN 0;" perevodit analizator v ishodnoe sostoyanie. Lex-programma mozhet soderzhat' neskol'ko pomechennyh nachal'nyh uslovij. Naprimer, esli Lex-programma nachinaetsya strokoj %START AA BB CC DD to eto oznachaet, chto ona upravlyaet chetyr'mya nachal'nymi sos- toyaniyami analizatora. V kazhdoe iz etih nachal'nyh sostoyanij analizator mozhno perevesti, ispol'zuya operator BEGIN. 13 Kazhdoe pravilo, pered kotorym ukazan operator tipa "<&lt;METKA>&gt;", my budem nazyvat' pomechennym pravilom. Metka for- miruetsya tak zhe, kak i metka v Si. Kolichestvo pomechennyh pravil ne ogranichivaetsya. Krome togo, razreshaetsya odno pravilo pomechat' neskol'kimi metkami, naprimer: <&lt;METKA1,METKA2,METKA3>&gt;x DEJSTVIE Zapyataya - obyazatel'nyj razdelitel' spiska metok! Rassmotrim primer s neskol'kimi nachal'nymi usloviyami: %START AA BB CC BUKVA [A-ZA-YAa-za-ya_] CIFRA [0-9] IDENTIFIKATOR {BUKVA}({BUKVA}|{CIFRA})* %% ^# BEGIN AA; ^[ \t]*main BEGIN BB; ^[ \t]*{IDENTIFIKATOR} BEGIN CC; \t ; \n BEGIN 0; <AA>define printf("Opredelenie.\n"); <AA>include printf("Vklyuchenie.\n"); <AA>ifdef { printf("Uslovnaya kompilyaciya.\n"); } <BB>[^\,]*","[^\,]*")" { printf("main s argumentamii.\n"); } <BB>[^\,]*")" { printf("main bez argumentov.\n"); } <CC>":"/[ \t] printf("Metka.\n"); Programma soderzhit aktivnye i neaktivnye pravila. Vse neak- tivnye pravila pomecheny, pered nimi ukazana metka nachal'nogo usloviya. Lex-programma upravlyaet tremya nachal'nymi usloviyami, v sootvetstvii s kotorymi aktiviruyutsya pomechennye pravila. V rezul'tate raboty lex my poluchim leksicheskij analiza- tor, kotoryj budet raspoznavat' v Si-programme stroki prep- rocessora Si-kompilyatora, vydelyat' funkciyu main, raspozna- vaya, s argumentami ona ili bez nih, raspoznavat' metki. Leksicheskij analizator ne vyvodit nichego, krome soobshchenij o vydelennyh leksemah. 14 3. Struktura Lex-programmy Lex-programma vklyuchaet razdely opredelenij, pravil i pol'zovatel'skih programm. Rassmotrim podrobnee sposoby oformleniya etih razdelov. Vse stroki, v kotoryh zanyata pervaya poziciya, otnosyatsya k Lex-programme. Lyubaya stroka, ne yavlyayushchayasya chast'yu pravila ili dejstviya, kotoraya nachinaetsya s probela ili tabulyacii, kopiruetsya v sgenerirovannuyu programmu lex.yy.c - rezul'tat raboty lex. 3.1. Razdel opredelenij Lex-programmy Opredeleniya, prednaznachennye dlya lex, pomeshchayutsya pered pervym %%. Lyubaya stroka etogo razdela, ne soderzhashchayasya mezhdu %{ i %} i nachinayushchayasya v pervoj kolonke, yavlyaetsya opredele- niem stroki podstanovki lex. Razdel opredelenij Lex- programmy mozhet vklyuchat': nachal'nye usloviya, opredeleniya, fragmenty programmy pol'zovatelya, tablicy naborov simvolov, ukazateli host-yazyka, izmeneniya razmerov vnutrennih massivov, kommentarii v formate host-yazyka. NACHALXNYE USLOVIYA zadayutsya v forme: %START imya1 imya2 ... Esli nachal'nye usloviya opredeleny, to eta stroka dolzhna byt' pervoj v Lex-programme. OPREDELENIYA zadayutsya v forme: imya translyaciya V kachestve razdelitelya ispol'zuetsya odin ili bolee probelov ili tabulyacij. Primer: BUKVA [A-ZA-YAa-za-ya_] DIGIT [0-9] IDENTIFIKATOR {BUKVA}({BUKVA}|{DIGIT})* Imya - kak obychno, lyubaya posledovatel'nost' bukv i cifr, nachinayushchayasya s bukvy. Translyaciya - eto regulyarnoe vyrazhenie (ili ego chast'), kotoroe budet podstavleno vsyudu tam, gde ukazano imya (smotrite tret'yu stroku etogo primera). 15 FRAGMENTY PROGRAMMY POLXZOVATELYA ukazyvayutsya dvumya spo- sobami: - v vide "probel fragment"; - v vide: %{ stroki fragmenta programmy pol'zovatelya %} Takaya forma vklyucheniya pol'zovatel'skogo fragmenta neobhodima dlya vvoda, naprimer, makroopredelenij Si, kotorye dolzhny nachinat'sya v pervoj kolonke stroki. Vse stroki fragmenta pol'zovatel'skoj programmy, raz- meshchennye v razdele opredelenij, budut yavlyat'sya vnesh- nimi dlya lyuboj funkcii programmy lex.yy.c TABLICA NABOROV SIMVOLOV zadaetsya v vide: %T celoe_chislo stroka_simvolov ......... celoe_chislo stroka_simvolov %T Sgenerirovannaya programma lex.yy.c osushchestvlyaet vvod-vyvod simvolov posredstvom bibliotechnyh funkcij lex s imenami input, output, unput. Takim obrazom, lex pomeshchaet v yytext simvoly v predstavlenii, ispol'zuemom v etih bibliotechnyh funkciyah. Dlya vnutrennego ispol'zovaniya simvol predstavlya- etsya celym chislom, znachenie kotorogo obrazovano naborom bitov, predstavlyayushchih simvol v konkretnoj |VM. Pol'zovatelyu predostavlyaetsya vozmozhnost' menyat' predstavlenie simvolov (celyh konstant) s pomoshch'yu tablicy naborov simvolov. Esli tablica simvolov prisutstvuet v razdele opredelenij, to lyuboj simvol, poyavlyayushchijsya libo vo vhodnom potoke, libo v pravilah, dolzhen byt' opredelen v tablice simvolov. Simvolam nel'zya naznachat' chislo 0 i chislo, bol'shee chisla, vydelennogo dlya vnutrennego predstavleniya simvolov konkretnoj |VM. Primer: 16 %T 1 Aa 2 Bb 3 Cc . . . 26 Zz 27 28 + 29 - 30 0 31 1 . . . 39 9 %T V etom primere simvoly verhnego i nizhnego registrov perevo- dyatsya v chisla 1-26, simvol novoj stroki v 27, "+" i "-" perevodyatsya v chisla 28 i 29, a cifry - v chisla 30-39. IZMENENIYA RAZMERA VNUTRENNIH MASSIVOV zadayutsya v forme: %x chislo chislo - novyj razmer massiva; x - odna iz bukv: p - pozicii; n - sostoyaniya; e - uzly dereva; a - upakovannye perehody; k - upakovannye klassy simvolov; o - massiv vyhodnyh elementov. lex imeet vnutrennie tablicy, razmery kotoryh ogranicheny. Pri postroenii programmy leksicheskogo analiza mozhet proi- zojti perepolnenie lyuboj iz etih tablic, o chem lex soobshchaet pri postroenii leksicheskogo analizatora. Pol'zovatelyu pre- dostavlyaetsya vozmozhnost' izmenit' razmery tablic (sokrashchaya razmery odnih i uvelichivaya razmery drugih) takim obrazom, chtoby oni ne perepolnyalis'. Estestvenno, eti izmeneniya voz- mozhny lish' v predelah toj pamyati, kotoraya vydelyaetsya pod process. Nizhe perechisleny razmery tablic, kotorye ustanavliva- yutsya po umolchaniyu: 17 p - pozicij 1500 n - sostoyanij 300 e - uzlov 600 a - upakovannyh perehodov 1500 k - upakovannyh klassov simvolov 1000 o - vyhodnyh elementov 1500 Dlya togo chtoby opredelit', kakovy razmery tablic i naskol'ko oni zanyaty, mozhno ispol'zovat' flag -v, naprimer: % lex -v source.l 33/600 uzlov(%e) 97/1500 pozicij(%p) 17/300 sostoyanij(%n) 2551 perehodov 18/1000 upakovannyh klassov simvolov(%k) 41/1500 upakovannyh perehodov(%a) 68/1500 vyhodnyh elementov(%o) % Zdes' pokazano soobshchenie, kotoroe vyvodit lex po flagu -v. CHislo pered simvolom "/" ukazyvaet skol'ko elementov massiva zanyato, a chislo za simvolom "/" ukazyvaet ustanovlennyj raz- mer massiva. KOMMENTARII v razdele opredelenij zadayutsya v forme host-yazyka i dolzhny nachinat'sya ne s pervoj kolonki stroki. 3.2. Razdel pravil Vse, chto ukazano posle pervoj pary %% i do konca Lex- programmy ili do vtoroj pary %%, esli ona ukazana, otnositsya k razdelu pravil. Razdel pravil mozhet soderzhat' pravila i fragmenty programm. Fragmenty programm, soderzhashchiesya v raz- dele pravil, stanovyatsya chast'yu funkcii yylex fajla lex.yy.c, v kotoroj osushchestvlyaetsya vypolnenie dejstvij aktivnyh pra- vil. Fragment programmy ukazyvaetsya sleduyushchim obrazom: %{ stroki fragmenta programmy %} Naprimer: %% %{ #include file.h %} . . . 18 Zdes' stroka "#include file.h" stanet strokoj funkcii yylex(). Razdel pravil mozhet vklyuchat' spisok aktivnyh i neaktiv- nyh (pomechennyh) pravil. Aktivnye i neaktivnye pravila mogut byt' ukazany v lyubom poryadke, v tom chisle byt' "pere- meshannymi" v spiske. Aktivnye pravila vypolnyayutsya vsegda, neaktivnye tol'ko po ssylke na nih operatorom BEGIN. Aktivnoe pravilo imeet vid: VYRAZHENIE DEJSTVIE Neaktivnoe pravilo imeet vid: <METKA>VYRAZHENIE DEJSTVIE ili <SPISOK_METOK>VYRAZHENIE DEJSTVIE gde SPISOK_METOK imeet vid: metka1,metka2,... V kachestve pervogo pravila razdela pravil mozhet byt' pravilo vida: BEGIN METKA; V etom pravile otsutstvuet VYRAZHENIE, i pervym dejstviem v razdele pravil budet aktivizaciya pomechennyh pravil. Dlya vozvrashcheniya avtomata v ishodnoe sostoyanie mozhno ispol'zovat' dejstvie: BEGIN 0; Vazhno otmetit' sleduyushchee. Esli Lex-programma soderzhit aktiv- nye i neaktivnye pravila, to aktivnye pravila rabotayut vsegda. Operator "BEGIN METKA;" prosto rasshiryaet spisok aktivnyh pravil, aktiviruya pomechennye metkoj METKA. A opera- tor "BEGIN 0;" udalyaet iz spiska aktivnyh pravil vse pome- chennye pravila, kotorye do etogo byli aktivirovany. Krome togo, esli iz pomechennogo i aktivnogo v dannyj moment vre- meni pravila osushchestvlyaetsya dejstvie BEGIN METKA, to iz pomechennyh pravil aktivnymi ostanutsya tol'ko te, kotorye pomecheny metkoj METKA. 3.2.1. Dejstviya v pravilah Lex-programmy Dejstvie mozhno predstavlyat' libo kak operator lex, nap- rimer, "BEGIN METKA;", libo kak operator Si. Esli imeetsya neobhodimost' vypolnit' dostatochno bol'shoj nabor preobrazo- vanij, to dejstvie oformlyayut kak blok Si-programmy (on 19 nachinaetsya otkryvayushchej figurnoj skobkoj i zavershaetsya zakry- vayushchej figurnoj skobkoj), soderzhashchij neobhodimye fragmenty. Dejstvie v pravile ukazyvaetsya cherez ne menee, chem odin probel ili tabulyaciyu posle vyrazheniya (obyazatel'no v toj zhe stroke, gde i vyrazhenie), a ego prodolzhenie mozhet byt' uka- zano v sleduyushchih strokah tol'ko v tom sluchae, esli dejstvie oformleno kak blok Si-programmy. Oblast' dejstviya peremennyh, ob®yavlennyh vnutri bloka, rasprostranyaetsya tol'ko na etot blok. Vneshnimi peremennymi dlya vseh dejstvij budut yavlyat'sya tol'ko te peremennye, koto- rye ob®yavleny v razdele opredelenij Lex-programmy. Dejstviya v pravilah Lex-programmy vypolnyayutsya, esli pravilo aktivno, i esli avtomat raspoznaet cepochku simvolov iz vhodnogo potoka kak sootvetstvuyushchuyu regulyarnomu vyrazheniyu dannogo pravila. Odnako, odno dejstvie vypolnyaetsya vsegda - ono zaklyuchaetsya v kopirovanii vhodnogo potoka simvolov v vyhodnoj. |to kopirovanie osushchestvlyaetsya dlya vseh vhodnyh strok, kotorye ne sootvetstvuyut pravilam, preobrazuyushchim eti stroki. Kombinaciya simvolov, ne uchtennaya v pravilah i poya- vivshayasya na vhode, budet napechatana na vyhode. Mozhno ska- zat', chto dejstvie - eto to, chto delaetsya vmesto kopirovaniya vhodnogo potoka simvolov na vyhod. CHasto byvaet neobhodimo ne kopirovat' na vyhod nekotoruyu cepochku simvolov, kotoraya udovletvoryaet nekotoromu regulyarnomu vyrazheniyu. Dlya etoj celi ispol'zuetsya pustoj operator Si, naprimer: [ 0 ; |to pravilo ignoriruet (zapreshchaet) vyvod probelov, tabulyacij i simvola novaya stroka. Zapret vyrazhaetsya v tom, chto na ukazannye simvoly vo vhodnom potoke osushchestvlyaetsya dejstvie ";" - pustoj operator Si, i eti simvoly ne kopiruyutsya v vyvodnoj potok simvolov. Sushchestvuet vozmozhnost' dlya neskol'kih regulyarnyh vyra- zhenij ukazyvat' odno dejstvie. Dlya etogo ispol'zuetsya simvol "|", kotoryj ukazyvaet, chto dejstvie dannogo pravila sovpa- daet s dejstviem dlya sleduyushchego, naprimer: " " | | ; Rezul'tat budet tot zhe, chto i v primere, ukazannom vyshe. Kogda neobhodimo vyvesti ili preobrazovat' tekst, soot- vetstvuyushchij nekotoromu regulyarnomu vyrazheniyu, ispol'zuetsya vneshnij massiv simvolov, kotoryj formiruet lex. Nazyvaetsya on yytext i dostupen v dejstviyah pravil. Naprimer: 20 [A-Z]+ printf("%s",yytext); Po etomu pravilu raspoznaetsya slovo, soderzhashchee propisnye latinskie bukvy i vyvoditsya s pomoshch'yu printf, esli ono vyde- leno. Operaciya vyvoda raspoznannogo vyrazheniya ispol'zuetsya ochen' chasto, poetomu imeetsya sokrashchennaya forma zapisi etogo dejstviya: [A-Z]+ ECHO; Rezul'tat dejstviya etogo pravila budet analogichen rezul'tatu predydushchego primera. V vyhodnom fajle lex.yy.c ECHO oprede- leno kak makropodstanovka: #define ECHO fprintf(yyout, "%s",yytext); Kogda neobhodimo znat' dlinu obnaruzhennoj posledovatel'nosti simvolov, ispol'zuetsya schetchik najdennyh simvolov yyleng, kotoryj takzhe dostupen v dejstviyah. Naprimer: [A-Z]+ printf("%c",yytext[yyleng-1]); V etom primere budet vyvoditsya poslednij simvol slova, soot- vetstvuyushchego regulyarnomu vyrazheniyu [A-Z]+. Rassmotrim eshche odin primer: [A-Z]+ {chislo_slov++;chislo_bukv += yyleng;} Zdes' vedetsya podschet chisla raspoznannyh slov i kolichestva simvolov vo vseh slovah. 3.2.2. Poryadok dejstviya aktivnyh pravil Spisok pravil Lex-programmy mozhet soderzhat' aktivnye i neaktivnye pravila, razmeshchennye v lyubom poryadke v razdele pravil. V processe raboty leksicheskogo analizatora spisok aktivnyh pravil mozhet vidoizmenyat'sya za schet dejstvij opera- tora BEGIN. V processe raspoznavaniya simvolov vhodnogo potoka mozhet okazat'sya tak, chto odna cepochka simvolov budet udovletvoryat' neskol'kim pravilam i, sledovatel'no, vozni- kaet problema: dejstvie kakogo pravila dolzhno vypolnyat'sya? Dlya razresheniya etogo protivorechiya mozhno ispol'zovat' kvantovanie (razbienie) regulyarnyh vyrazhenij etih pravil Lex-programmy na takie novye regulyarnye vyrazheniya, kotorye dadut, po vozmozhnosti, odnoznachnoe raspoznavanie leksemy. Odnako, kogda eto ne sdelano, lex ispol'zuet opredelennyj determinirovannyj mehanizm razresheniya takogo protivorechiya: - vybiraetsya dejstvie togo pravila, kotoroe raspoznaet naibolee dlinnuyu posledovatel'nost' simvolov iz vhod- nogo potoka; 21 - esli neskol'ko pravil raspoznayut posledovatel'nosti simvolov odnoj dliny, to vypolnyaetsya dejstvie togo pravila, kotoroe zapisano pervym v spiske razdela pravil Lex-programmy. Rassmotrim primer: . . . [Mm][Aa][Jj] ECHO; [A-YAa-ya]+ ECHO; . . . Slovo "Maj" raspoznayut oba pravila, odnako, vypolnitsya per- voe iz nih, tak kak i pervoe, i vtoroe pravilo raspoznali leksemu odinakovogo razmera (3 simvola). Esli vo vhodnom potoke budet, dopustim, slovo "majskij", to pervye 3 simvola udovletvoryayut pervomu pravilu, a vse 7 simvolov udovletvo- ryayut vtoromu pravilu, sledovatel'no, vypolnitsya vtoroe pra- vilo, tak kak emu udovletvoryaet bolee dlinnaya posledovatel'- nost' simvolov. 3.3. Razdel programm pol'zovatelya Vse, chto razmeshcheno za vtorym naborom %%, otnositsya k razdelu programm pol'zovatelya. Soderzhimoe etogo razdela kopiruetsya v vyhodnoj fajl lex.yy.c bez kakih-libo izmene- nij. V fajle lex.yy.c stroki etogo razdela rassmatrivayutsya kak funkcii v smysle Si. |ti funkcii mogut vyzyvat'sya v dejstviyah pravil i, kak obychno, peredavat' i vozvrashchat' zna- cheniya argumentov. 3.4. Kommentarii Lex-programmy Kommentarii mozhno ukazyvat' vo vseh razdelah Lex- programmy. Format kommentariev dolzhen sootvetstvovat' for- matu kommentariev host-yazyka. Odnako, v kazhdom razdele Lex- programmy kommentarii ukazyvayutsya po raznomu. V razdele opredelenij kommentarii dolzhny nachinat'sya ne s pervoj pozi- cii stroki. V razdele pravil kommentarii mozhno ukazyvat' tol'ko vnutri blokov, prinadlezhashchih dejstviyam. V razdele programm pol'zovatelya kommentarii ukazyvayutsya kak i v host- yazyke. 3.5. Primery Lex-programm Primer1. 22 %Start KOMMENT /* * Programma zapisyvaet v * standartnyj fajl vyvoda * kommentarii Si-programmy. * Obratite vnimanie na to, chto * zdes' stroki kommentariev ukazany * ne s pervoj pozicii stroki! */ KOMM_NACHALO "/*" KOMM_KONEC "*/" %% {KOMM_NACHALO} { ECHO; BEGIN KOMMENT;} [0* ; <KOMMENT>[^*]* ECHO; <KOMMENT>[^/] ECHO; <KOMMENT>{KOMM_KONEC} { ECHO; printf("0); /* * Zdes' priveden primer * ispol'zovaniya kommentariev v * razdele pravil Lex-programmy. * Obratite vnimanie na to, chto * kommentrij ukazan vnutri bloka, * opredelyayushchego dejstvie pravila. */ BEGIN 0;} %% /* * Zdes' priveden primer kommentariev * v razdele programm pol'zovatelya. */ Primer 2. 23 %Start IC1 IC2 Normal /* * Otladochnyj fragment * Lex-programmy, kotoraya stroit * leksicheskij analizator dlya * kompilyatora yazyka Paskal'. * Dejstvie return(...) * vozvrashchaet tip leksemy v * v vyzyvayushchuyu analizator