Generator programm sintaksicheskogo analiza yacc Proizvodstvenno-vnedrencheskij kooperativ "I N T E R F E J S" Dialogovaya Edinaya Mobil'naya Operacionnaya Sistema Demos/P 2.1 Generator programm sintaksicheskogo analiza yacc Moskva 1988 Annotaciya Znachitel'naya chast' sozdavaemyh programm, rasschitannyh na opredelennuyu strukturu vhodnoj informacii, yavno ili neyavno vklyuchaet v sebya nekotoruyu proceduru sintaksicheskogo analiza. V zadachah, gde pol'zovatelyu pri zadanii vhodnoj informacii predostavlyaetsya otnositel'naya svoboda (v otnoshe- nii sochetaniya i posledovatel'nosti strukturnyh elementov), sintaksicheskij analiz dostatochno slozhen. Pri reshenii podob- nyh zadach sushchestvennuyu podderzhku mogut okazat' servisnye programmy, osushchestvlyayushchie postroenie sintaksicheskih (gramma- ticheskih) analizatorov na osnove zadannyh svedenij o sintak- sicheskoj strukture vhodnoj informacii. yacc otnositsya k chislu etih servisnyh programm - generatorov sintaksicheskih analizatorov. Poskol'ku obshirnoj oblast'yu, gde naibolee yavno vidna neobhodimost' (netrivial'nogo) grammaticheskogo analiza, a sledovatel'no i ego avtomatizacii, yavlyaetsya oblast' sozdaniya translyatorov (v chastnosti, kompilyatorov), programmy, podob- nye yacc, poluchili eshche nazvanie kompilyatorov (ili generato- rov) kompilyatorov. Zametim, chto ponyatie translyatora mozhet otnosit'sya ne tol'ko k yazykam programmirovaniya, no i k komandnym yazykam, vhodnym yazykam lyubyh dialogovyh sistem, yazykam upravleniya tehnologicheskimi processami i t.p. Pol'zovatel' yacc dolzhen opisat' strukturu svoej vhod- noj informacii (grammatiku) kak nabor pravil v vide, blizkom k Bekusovo-Naurovskoj forme (BNF). Kazhdoe pravilo opisyvaet grammaticheskuyu konstrukciyu, nazyvaemuyu neterminal'nym simvo- lom, i sopostavlyaet ej imya. S tochki zreniya grammaticheskogo razbora pravila rassmatrivayutsya kak pravila vyvoda (podsta- novki). Grammaticheskie pravila opisyvayutsya v terminah neko- toryh ishodnyh konstrukcij, kotorye nazyvayutsya leksicheskimi edinicami, ili leksemami. Imeetsya vozmozhnost' zadavat' lek- semy neposredstvenno (literal'no) ili upotreblyat' v gramma- ticheskih pravilah imya leksemy. Kak pravilo, imena sopostav- lyayutsya leksemam, sootvetstvuyushchim klassam ob容ktov, konkret- noe znachenie kotoryh ne sushchestvenno dlya celej grammatiches- kogo analiza. (Inogda v literature s ponyatiem leksemy sovpa- daet ponyatie terminal'nogo simvola; odnako, ryad avtorov nazyvaet terminal'nymi simvolami otdel'nye simvoly standart- nogo nabora). Primerami imen leksem mogut sluzhit' identifi- kator i chislo, a vvedenie takih lBeksem pozvolyaet obobshchit' konkretnye sposoby zapisi identifikatorov i chisel. V nekoto- ryh sluchayah imena leksem sluzhat dlya pridaniya pravilam bol'- shej vyrazitel'nosti. Leksemy dolzhny raspoznavat'sya programmoj leksicheskogo analiza, opredelyaemoj pol'zovatelem. Pol'zovatel' zhe predva- ritel'no vybiraet konstrukcii,kotorye bolee udobno i effektivno raspoznavat' neposredstvenno, i v sootvetstvii s etim ob座avlyaet imena leksem. Pol'zovatel'skaya programma lek- sicheskogo analiza - leksicheskij analizator - osushchestvlyaet chtenie real'noj vhodnoj informacii i peredaet sintaksiches- komu analizatoru raspoznannye leksemy. Kak uzhe otmechalos', yacc obespechivaet avtomaticheskoe postroenie lish' procedury grammaticheskogo analiza. Odnako, dejstviya po obrabotke vhodnoj informacii obychno dolzhny vypolnyat'sya po mere raspoznavaniya na vhode teh ili inyh dopustimyh grammaticheskih konstrukcij. Poetomu naryadu s zadaniem grammatiki vhodnyh tekstov yacc predusmatrivaet vomozhnost' opisaniya dlya otdel'nyh konstrukcij semanticheskih procedur (dejstvij) s tem, chtoby oni byli vklyucheny v prog- rammu grammaticheskogo razbora. V zavisimosti ot haraktera pol'zovatel'skih semanticheskih procedur (interpretaciya ras- poznannogo fragmenta vhodnogo teksta, generaciya fragmenta ob容ktnogo koda, otmetka v spravochnoj tablice ili formatiro- vanie vershiny v dereve razbora) generiruemaya s pomoshch'yu yacc programma budet obespechivat' krome analiza tot ili inoj vid obrabotki vhodnogo teksta, v chastnosti, ego kompilyaciyu ili interpretaciyu. Itak, pol'zovatel' yacc podgotavlivaet obshchee opisanie (specifikacii) obrabotki vhodnogo potoka, vklyuchayushchee pra- vila, opisyvayushchie vhodnye konstrukcii, kodovuyu chast', k kotoroj dolzhno byt' organizovano obrashchenie pri obnaruzhenii etih konstrukcij, i programmu vvoda bazovyh elementov potoka (leksicheskij analizator). Kompilyator kompilyatorov obespechi- vaet sozdanie podprogrammy (sintaksicheskogo analizatora), realizuyushchej proceduru obrabotki vhodnogo potoka v sootvetst- vii s zadannymi specifikaciyami. yacc napisan na yazyke Si i rabotaet pod upravleniem sistemy DEMOS. K komponentam kompilyatora kompilyatorov otnosyatsya vypol- nyaemyj fajl yacc, biblioteka standartnyh programm /lib/liby.a, Fajl /usr/lib/yaccpar. Zaklyuchitel'naya faza postroeniya kompilyatora trebuet primeneniya kompilyatora yazyka Si. 1. Principy raboty yacc Grammaticheskie analizatory, sozdavaemye s pomoshch'yu yacc, realizuyut tak nazyvaemyj LALR(1)-razbor, yavlyayushchijsya modifi- kaciej odnogo iz osnovnyh metodov razbora "snizu vverh" - LR(k)-razbora (bukvy L(eft) i R(ight) v oboih sokrashcheniyah oznachayut sootvetstvenno chtenie vhodnyh simvolov sleva nap- ravo i ispol'zovanie pravostoronnego vyvoda. Indeks v skob- kah pokazyvaet chislo predvaritel'no prosmatrivaemyh leksi- cheskih edinic). - 3 - Lyuboj razbor po principu "snizu vverh" (ili voshodyashchij razbor) sostoit v popytke privedeniya vsej sovokupnosti vhod- nyh dannyh (vhodnoj cepochki) k tak nazyvaemomu "nachal'nomu simvolu grammatiki" (eto ponyatie budet ob座asneno v razdele 4.1) putem posledovatel'nogo primeneniya pravil vyvoda. V kazhdyj moment grammaticheskogo razbora analizator nahoditsya v nekotorom sostoyanii, opredelyaemom predystoriej razbora, i v zavisimosti ot ocherednoj leksemy predprinimaet to ili inoe dejstvie dlya perehoda k novomu sostoyaniyu. Razli- chayut dva tipa dejstvij: sdvig, t.e. chtenie sleduyushchej vhodnoj leksemy, i svertku, t.e. primenenie odnogo iz pravil pods- tanovki dlya zameshcheniya neterminalom posledovatel'nosti simvo- lov, sootvetstvuyushchej pravoj chasti pravila. Rabota yacc po generacii procedury grammaticheskogo analiza zaklyuchaetsya v postroenii tablic, kotorye dlya kazhdogo iz sostoyanij oprede- lyayut tip dejstvij analizatora i nomer sleduyushchego sostoyaniya v sootvetstvii s kazhdoj iz vhodnyh leksem. Lyuboj metod razbora trebuet grammatik s opredelennymi svojstvami. V etom smysle yacc predpolagaet kontekstno- svobodnye grammatiki so svojstvami LALR(1). LALR(1)- grammatiki, yavlyayas' podmnozhestvom LR(1)-grammatik, dopuskayut pri postroenii tablic razbora sokrashchenie obshchego chisla sosto- yanij za schet ob容dineniya identichnyh sostoyanij, razlichayushchihsya tol'ko naborom simvolov-sledovatelej (simvolov, kotorye mogut sledovat' posle primeneniya odnogo iz pravil vyvoda, esli razbor po etomu pravilu prohodil cherez dannoe sostoya- nie). Drugie grammatiki yavlyayutsya neodnoznachnymi dlya prinya- togo v yacc metoda razbora i vyzovut konflikty (razdel 5). Odnako, esli yazyk, opisyvaemyj dannoj grammatikoj, v prin- cipe dopuskaet zadanie grammatiki, odnoznachnoj dlya dannogo metoda razbora, to yacc pozvolyaet bez perestrojki grammatiki postroit' grammaticheskij analizator, razreshayushchij konflikty na osnove mehanizma prioritetov (razdel 5). 2. Vhodnye i vyhodnye fajly, struktura grammaticheskogo ana- lizatora Vhodnaya informaciya dlya yacc zadaetsya v specifikacionnom fajle, struktura kotorogo rassmatrivaetsya v razdele 4. Na vyhode kompilyatora kompilyatorov v rezul'tate obra- botki specifikacij sozdaetsya fajl y.tab.c s ishodnym tekstom Si-procedur, sostavlyayushchih grammaticheskij analizator. Osnov- noj v fajle y.tab.c yavlyaetsya procedura yyparse, realizuyushchaya algoritm grammaticheskogo razbora. Pri formirovanii ee yacc ispol'zuet fajl /usr/lib/yaccpar, soderzhashchij neizmenyaemuyu chast' analizatora. Krome yyparse, v fajl y.tab.c yacc vklyu- chaet postroennye im tablicy razbora, opisaniya i programmnye fragmenty pol'zovatel'skih specifikacij. - 4 - Procedura yyparse predstavlyaet soboj celochislennuyu funkciyu, vozvrashchayushchuyu znachenie 0 ili 1. Znachenie 0 vozvrashcha- etsya v sluchae uspeshnogo razbora po dostizhenii priznaka konca fajla, znachenie 1- v sluchae nesootvetstviya vhodnogo teksta zadannym specifikaciyam. Procedura yyparse soderzhit mnogok- ratnoe obrashchenie k procedure leksicheskogo analiza yylex, tekst kotoroj libo perenositsya v fajl y.tab.c iz specifika- cionnogo fajla, libo prikomponovyvaetsya vposledstvii. Dlya organizacii obrashcheniya k procedure yyparse v biblio- teke yacc sushchestvuet standartnaya procedura main, ne soderzha- shchaya pomimo obrashcheniya k yyparse nikakih dejstvij. Pol'zova- tel' mozhet napisat' sobstvennuyu proceduru main, vklyuchiv v nee kak nachal'nye dejstviya, predvaryayushchie vyzov yyparse (ustanovka nuzhnyh rezhimov, otkrytie fajlov, chastichnoe zapol- nenie tablic), tak i dejstviya po zavershenii razbora, kotorym dolzhen predshestvovat' analiz vozvrashchaemogo yyparse znacheniya; dejstviyami v sluchae uspeshnogo razbora mogut byt' zakrytie fajlov, vyvod rezul'tatov, vyzov sleduyushchej fazy translyatora, v chastnosti, povtornyj vyzov yyparse. Dlya zameny standartnoj procedury pol'zovatel'skoj programmoj main ona dolzhna byt' opisana v specifikacionnom fajle ili prisoedinena na etape vyzova Si- kompilyatora dlya podgotovki ispolnyaemoj programmy. Krome vyhodnogo fajla y.tab.c, yacc mozhet dopolnitel'no generirovat' sleduyushchie vyhodnye fajly: y.output soderzhashchij opisanie sostoyanij analizatora i soobshcheniya o konfliktah (razdel 6) y.tab.h soderzhashchij opisanie leksem (razdel 4.3). Dlya generacii etih fajlov trebuetsya zadanie sootvetst- vuyushchih flagov pri vyzove yacc. 3. Procedura postroeniya grammaticheskogo analizatora Postroenie grammaticheskogo analizatora osushchestvlyaetsya v dva etapa. Na pervom etape fajl specifikacij vhodnogo yazyka obrabatyvaetsya kompilyatorom kompilyatorov yacc, dlya chego zadaetsya komandnaya stroka yacc [-vd] yfile Zdes' yfile - imya fajla specifikacij, a flagi imeyut sleduyu- shchij smysl: v - sformirovat' v fajle y.output podrobnoe opisanie gram- maticheskogo analizatora; - 5 - d - sformirovat' v fajle y.tab.h opisanie leksem. Teksto- vye fajly y.output i y.tab.h soderzhat spravochnuyu infor- maciyu dlya pol'zovatelya i nikak ne ispol'zuyutsya na vto- rom etape postroeniya grammaticheskogo analizatora. Osnovnoj rezul'tat raboty yacc - procedura yyparse i grammaticheskie tablicy - pomeshchaetsya v fajl y.tab.c. Na vto- rom etape postroeniya grammaticheskogo analizatora dlya poluche- niya v fajle a.out ispolnyaemoj programmy kompiliruetsya fajl y.tab.c i prisoedinyayutsya drugie programmnye komponenty: cc y.tab.c [cfile...ofile...lfile...] -ly cfile, ofile, lfile - imena ishodnyh, ob容ktnyh i bibliotech- nyh fajlov, soderzhashchih prisoedinyaemye procedury. V etot spi- sok ne vklyuchaetsya imya standartnoj biblioteki yacc /lib/liby.a, ee podklyuchenie obespechivaetsya zadaniem flaga ly. |tot flag polezno schitat' obyazatel'nym. 4. Zadanie vhodnoj informacii yacc 4.1. Struktura specifikacionnogo fajla Pol'zovatel'skie specifikacii, zadayushchie pravila organi- zacii vhodnoj informacii i algoritm ee obrabotki, ob容dinya- yutsya v specifikacionnyj fajl sleduyushchej struktury: deklaracii %% pravila %% programmy YAdrom specifikacionnogo fajla i edinstvennoj ego obyaza- tel'noj chast'yu yavlyaetsya sekciya pravil. Pri otsutsivii sekcii programm mozhet byt' opushchena vtoraya gruppa "%%"; sledova- tel'no, minimal'naya dopustimaya konfiguraciya vhodnogo fajla imeet vid: %% pravila Probely, znaki tabulyacii i perevoda stroki ignoriru- yutsya, nedopustimo lish' poyavlenie ih v imenah. Kommentarij, ogranichennyj simvolami "/*" v nachale i "*/" v konce, mozhet nahodit'sya mezhdu lyubymi dvumya razdelitelyami v lyuboj sekcii vhodnogo fajla. - 6 - Sekciya pravil sostoit iz odnogo ili neskol'kih gramma- ticheskih pravil. |ti pravila dolzhny opredelyat' vse dopusti- mye vhodnye konstrukcii i svyazannye s opredelennymi konst- rukciyami dejstviya po obrabotke vhodnogo potoka. Naznachenie sekcii deklaracij sostoit v osnovnom v zada- nii informacii o leksemah. Sekciya programm predstavlyaet soboj nekotoryj nabor pro- cedur na yazyke Si, kotorye dolzhny vklyuchat'sya v tekst prog- rammy grammaticheskogo razbora. Naprimer, eto mogut byt' procedura leksicheskogo analiza yylex i pol'zovatel'skie pro- cedury, vyzyvaemye v dejstviyah. 4.2. Sekciya pravil V dannoj sekcii s pomoshch'yu nabora grammaticheskih pravil dolzhny byt' opredeleny vse konstrukcii, iz kotoryh vpos- ledstvii budut stroit'sya vhodnye teksty. Ne podlezhat oprede- leniyu v sekcii pravil lish' konstrukCii, vybrannye pol'zova- telem v kachestve leksem, schitayushchiesya dlya grammaticheskogo analiza ishodnymi edinicami. Pravila zadayutsya v forme, bliz- koj BNF. Pravilo, opredelyayushchee sintaksicheskij vid konstrukcii, zadaetsya takim obrazom: <imya_neterminal'nogo_simvola>: opredelenie; Zdes' ":" i ";" - special'nye simvoly yacc. Pravaya chast' pravila - opredelenie - predstavlyaet soboj uporyadochennuyu posledovatel'nost' elementov (neterminal'nyh simvolov i lek- sem), sostavlyayushchih opisyvaemuyu konstrukciyu. Pri grammatiches- kom razbore takaya posledovatel'nost' v rezul'tate primeneniya pravila zamenyaetsya neterminal'nym simvolom, imya kotorogo ukazano v levoj chasti. neterminal'nye simvoly v opredelenii zadayutsya imenami, a leksemy - imenami ili literalami. Zapis' imen i literalov sovpadaet s zapis'yu identifikatorov i sim- vol'nyh konstant, prinyatoj v Si. Pravilo: P_Head: P_name '(' P_list ')'; opredelyaet neterminal P_Head kak posledovatel'nost' 4-h ele- mentov: dva elementa zadany literal'no, dva drugih - ime- nami. Po vidu pravila nel'zya zaklyuchit', otnosyatsya eti imena k leksemam ili neterminal'nym simvolam. yacc schitaet imenami neterminalov vse imena, ne ob座avlennye v sekcii deklaracij imenami leksem (razd.4.3). Vse neterminaly dolzhny byt' - 7 - opredeleny, t.e. imya kazhdogo iz nih dolzhno poyavit'sya v levoj chasti hotya by odnogo pravila. Dopustimo zadanie neskol'kih pravil, opredelyayushchih odin neterminal'nyj simvol, t.e. pravil s odinakovoj levoj chast'yu. Takie pravila opredelyayut konst- rukcii, identichnye na nekotorom urovne. Nizhe privodyatsya tri pravila, opredelyayushchie vidy operatorov v nekotorom yazyke: statement : assign_stat ; statement : if_then_stat; statement : goto_stat; Pravila s obshchej levoj chast'yu mozhno zadavat' v sokrashchen- noj zapisi, bez povtoreniya levoj chasti, ispol'zuya dlya razde- leniya al'ternativnyh opredelenij simvol "|". Predydushchie pra- vila mozhno perepisat' v vide: statement : assign_stat | if_then_stat | goto_stat; Pri neobhodimosti s lyubym pravilom mozhno svyazat' dejst- vie - nabor operatorov yazyka Si, kotorye budut vypolnyat'sya pri kazhdom raspoznavanii konstrukcii vo vhodnom tekste. Dejstvie ne yavlyaetsya obyazatel'nym elementom pravil. Dejstvie zaklyuchaetsya v figurnye skobki i pomeshchaetsya vsled za pravoj chast'yu pravila, t.e. pravilo s dejstviem imeet vid: <imya_neterminal'nogo_simvola>: opredelenie {dejstvie}; Tochka s zapyatoj posle pravila s dejstviem mozhet opuskat'sya. Pri ispol'zovanii sokrashchennoj zapisi pravil s obshchej levoj chast'yu sleduet imet' v vidu, chto dejstvie mozhet otno- sit'sya tol'ko k otdel'nomu pravilu, a ne k ih sovokupnosti. Sleduyushchij primer illyustriruet zadanie dejstvij v sluchae pra- vil s obshchej levoj chast'yu. statement: assign_stat | if_then_stat {printf("if_operator\n");} | goto_stat {kgoto++; printf("goto_operator\n");} - 8 - Na operatory, vhodyashchie v dejstviya, ne nakladyvaetsya nikakih ogranichenij. V chastnosti, v dejstviyah mogut soder- zhat'sya vyzovy lyubyh funkcij. Otdel'nye operatory mogut byt' pomecheny, k nim vozmozhen perehod iz drugih dejstvij. Sushchestvuet vozmozhnost' zadaniya dejstvij, kotorye budut vypolnyat'sya po mere raspoznavaniya otdel'nyh fragmentov pra- vila. Dejstvie v etom sluchae pomeshchaetsya posle odnogo iz ele- mentov pravoj chasti tak, chtoby polozhenie dejstviya sootvest- vovalo momentu razbora, v kotoryj dannomu dejstviyu budet peredano upravlenie. Naprimer, v pravile if_then_stat: if'(' expression ')' {dejstvie1} then statement ';' {dejstvie 2} dejstviya zadany s takim raschetom, chtoby pri razbore stroki vida if (a>b) then x=a; dejstvie 1 vypolnyalos' pri nahozhdenii pravoj krugloj skobki, a dejstvie 2 - po okonchanii razbora. Dlya togo, chtoby dejstviya imeli real'nyj smysl, oni, kak pravilo, dolzhny ispol'zovat' nekotorye obshchie peremennye, t.e. peremennye, dostupnye vo vseh dejstviyah i sohranyayushchie svoi znacheniya po okonchanii ocherednogo dejstviya. Takie pere- mennye opisyvayutsya v nachale sekcii pravil, vse opisanie ogranichivaetsya s dvuh storon strokami %{ i %} Zdes' zhe mogut nahodit'sya proizvol'nye operatory Si, rass- matrivaemye kak obshchie dejstviya dlya vseh pravil. Dopolnim privedennyj vyshe fragment specifikacij dlya statement s tem, chtoby osushchestvlyalsya podschet i vyvod na pechat' operatorov goto - 9 - %{ int kgoto; %} prog: DECLS {kgoto=0;} stats {printf("%d\n",kgoto);} stats: statement | stats statement; statement:assign_stat ... | if_then_stat ... | goto_stat {kgoto++; ... } Ukazhem eshche na dva vida ob容ktov, ispol'zuyushchihsya v dejstviyah. |to, vo-pervyh, global'nye peremennye, kotorye opisyvayutsya v sekcii deklaracij (razd.4.3), i, vo-vtoryh, special'nye peremennye (psevdoperemennye),oblegchayushchie vzai- mosvyaz' mezhdu dejstviyami i svyaz' ih s leksicheskim analizato- rom. Rabote s psevdoperemennymi posvyashchen razdel 4.5. Struk- tura vhodnoj informacii opisyvaetsya v nabore pravil ierarhi- cheski, t.e. kazhdoe pravilo sootvetstvuet opredelennomu urovnyu strukturnogo razbieniya. Odnako, posledovatel'nost' zadaniya pravil mozhet ne otrazhat' etoj ierarhii i byt' vpolne proizvol'noj. Edinstvenno neobhodimoj dlya yacc yavlyaetsya informaciya o tom, kakoj iz neterminalov zadaet vershinu ierarhii, t.e. sootvestvuet konstrukciyam, opredelyayushchim vhod- noj tekst v celom. |tot neterminal prinyato nazyvat' nachal'- nym simvolom. Privedenie vhodnogo teksta k nachal'nomu sim- volu yavlyaetsya cel'yu grammaticheskogo analizatora. Po umolcha- niyu yacc schitaet nachal'nym simvolom tot neterminal, imya kotorogo stoit v levoj chasti pervogo iz pravil. Odnako, esli opredelyat' nachal'nyj simvol v pervom pravile pol'zovatelyu neudobno, on mozhet yavno zadat' imya nachal'nogo simvola v sek- cii deklaracij. Sushchestvuet dva specificheskih vida pravil, na kotorye polezno obratit' vnimanie. Vo-pervyh, eto pustoe pravilo vida <imya_neterminal'nogo_simvola>: ; opredelyayushchee pustuyu posledovatel'nost' simvolov. Sochetanie pustogo pravila s drugimi pravilami, opredelyayushchimi tot zhe neterminal'nyj simvol, yavlyaetsya odnim iz sposobov ukazat' na neobyazatel'nost' vhozhdeniya sootvetstvuyushchej konstrukcii. Naprimer, sovokupnost' pravil - 10 - celoe_chislo:znak celoe_bez_znaka; znak: | '+'|'-'; opredelyaet vozmozhnost' zadaniya celyh chisel so znakom i bez nego. Drugoj sposob opisat' etu vozmozhnost' sostoit v zada- nii sleduyushchej gruppy pravil: celoe_chislo:znak celoe_bez_znaka | celoe_bez_znaka ; znak: '+'|'-'; S pustym pravilom mozhet byt' obychnym obrazom svyazano dejstvie: IMYA: {telo_dejstviya} ; Vo-vtoryh, pravila chasto opisyvayut nekotoruyu konstrukciyu rekursivno, t.e. pravaya chast' mozhet rekursivno vklyuchat' opredelyaemyj neterminal'nyj simvol. Razlichayut levorekursiv- nye pravila vida: <imya_neterminala>:<imya_neterminala> <mnogokratno_povtoryaemyj_fragment>; i pravorekursivnye vida <imya_neterminala>: <mnogokratno_povtoryaemyj_fragment> <imya_neterminala>; yacc dopuskaet oba vida rekursivnyh pravil, odnako pri ispol'zovanii pravil s pravoj rekursiej ob容m analizatora uvelichivaetsya, a vo vremya razbora vozmozhno perepolnenie vnutrennego steka analizatora. Rekursivnye pravila neobhodimy pri zadanii posledova- tel'nostej i spiskov. Sleduyushchie primery illyustriruyut uni- versal'nyj sposob opisaniya etih konstrukcij: posledovatel'nost': element | posledovatel'nost' element; spisok: element|spisok ',' element; - 11 - Zametim, chto v kazhdom iz etih sluchaev pervoe pravilo (ne soderzhashchee rekursii) budet primeneno tol'ko dlya pervogo ele- menta, a vtoroe (rekursivnoe) - dlya vseh posleduyushchih. Neter- minal'nye simvoly, svyazannye s posledovatel'nostyami ili spiskami raznorodnyh elementov, mogut opisyvat'sya proizvol'- nym chislom rekursivnyh i nerekursivnyh pravil. Naprimer, gruppa pravil identifikator: bukva | '$' | identifikator bukva| identifikator cifra| identifikator '_' ; opisyvaet identifikator kak posledovatel'nost' bukv, cifr i simvolov "_", nachinayushchuyusya s bukvy ili simvola "$". Sleduet obratit' vnimanie na to, chto rekursivnye pravila ne imeyut smysla, esli dlya opredelyaemogo imi neterminala ne zadano ni odnogo pravila bez rekursii. Dlya obespecheniya vozmozhnosti zadaniya pustyh spiskov ili posledovatel'nostej v kachestve nerekursivnogo pravila ispol'zuetsya pustoe: posledovatel'nost' : | posledovatel'nost' element ; Sochetanie pustyh i rekursivnyh pravil yavlyaetsya udobnym sposobom predstavleniya grammatik i vedet k bol'shej ih obshch- nosti, odnako,nekorrektnoe ispol'zovanie pustyh pravil mozhet vyzyvat' konfliktnye situacii (razdel 5) iz-za neodnoznach- nosti vybora neterminala, sootvetstvuyushchego pustoj posledova- tel'nosti. 4.3. Sekciya deklaracij Sekciya deklaracij sostoit iz posledovatel'nosti strok dvuh vidov: strok-direktiv i strok ishodnogo teksta. Stroki ishodnogo teksta bez izmenenij kopiruyutsya v vyhodnoj fajl y.tab.c i mogut soderzhat' operatory preproces- sora i opisanie vneshnih ob容ktov. Oblast' dejstviya peremen- nyh, opisannyh v sekcii deklaracij, rasprostranyaetsya na ves' specifikacionnyj fajl, t.e. oni dostupny kak v operatorah dejstvij, tak i v procedurah, nahodyashchihsya v sekcii programm. Stroki-direktivy nachinayutsya simvolom "%" (etot simvol v yacc igraet rol' svoego roda esc-simvola). Dve special'nye direktivy - 12 - %{ i %} ogranichivayut s dvuh storon gruppy strok ishodnogo teksta. Ostal'nye direktivy sluzhat dlya zadaniya dopolnitel'noj infor- macii o grammatike. 5. Deklaraciya imen leksem %token <spisok_imen_leksem> Pol'zovatel' pri opisanii grammatiki reshaet, kakie konstrukcii celesoobraznee neposredstvenno vydelyat' iz vhod- nogo teksta na etape leksicheskogo analiza, i na urovne etih konstrukcij (leksem) zadaet grammaticheskie pravila. Vse vidy leksem, krome literalov, oboznachayutsya nekotorymi imenami i pod etimi imenami figuriruyut v sekcii pravil. Blagodarya dek- laracii imen leksem v direktive %token yacc otlichaet imena leksem ot imen neterminal'nyh simvolov. Odnako, deklaraciya ni v koej mere ne obespechivaet raspoznavaniya leksem, i pol'- zovatelyu rekomenduetsya schitat' dlya sebya direktivu %token napominaniem o neobhodimosti postroeniya leksicheskogo anali- zatora (razd.4.4) i rukovodstvovat'sya etoj direktivoj pri ego napisanii. Primer deklaracii imen leksem: %token IDENT CONST ZNAK IF THEN GOTO Zametim, chto klyuchevye slova opisyvaemogo vhodnogo yazyka chasto byvaet udobno schitat' leksemami. Imena leksem mogut sovpadat' s etimi klyuchevymi slovami, nedopustimym yavlyaetsya lish' sovpadenie imen leksem s zarezervirovannymi slovami yazyka Si. V primere vo izbezhanie nedorazumenij dlya imen lek- sem ispol'zovany propisnye bukvy. 6. Deklaraciya prioritetov i associativnosti leksem %left <spisok_leksem> %right <spisok_leksem> %nonassoc <spisok_leksem> Leksemy v dannyh direktivah zadayutsya literalami ili imenami. V poslednem sluchae deklaraciya prioriteta zamenyaet takzhe deklaraciyu imeni leksemy, hotya v celyah obespecheniya naglyadnosti opisaniya yavlyaetsya zhelatel'nym prisutstvie v - 13 - spiske direktivy %token vsego nabora imen leksem. Soderzhatel'nyj smysl deklaracii prioritetov i associa- tivnosti vyyasnyaetsya v razdele 5 v svyazi s voprosom o razre- shenii konfliktov grammaticheskogo razbora. Ispol'zovanie leksemy samo po sebe ne trebuet zadaniya ee prioriteta ili associativnosti. Pri pervom poyavlenii leksemy ili literala v sekcii dek- laracij za kazhdym iz nih mozhet sledovat' neotricatel'noe celoe chislo, rassmatrivaemoe kak nomer tipa leksemy. Po umolchaniyu nomera tipov vseh lekseM opredelyayutsya yacc sleduyu- shchim obrazom: - dlya literala nomerom tipa leksemy schitaetsya chislovoe znachenie dannogo literal'nogo simvola, rassmatrivaemogo kak odnobajtovoe celoe chislo; - leksemy,oboznachennye imenami, v sootvetstvii s ochered- nost'yu ih ob座avleniya poluchayut posledovatel'nye nomera, nachinaya s 257; - special'naya leksema error, zarezervirovannaya dlya obra- botki oshibok (razdel 7), poluchaet nomer tipa 256. Dlya kazhdogo imeni leksemy nezavisimo ot togo, pereopre- delen li ee nomer pol'zovatelem, yacc generiruet v vyhodnom fajle y.tab.c operator makropreprocessora #define <imya_leksemy> <nomer_tipa> V sluchae pereopredeleniya nomera tipa literal'noj lek- semy takzhe formiruetsya operator #define, naprimer, direktiva %left 'z' 258 porodit operator #define z 258 Zametim, chto vozmozhno pereopredelenie nomerov lish' dlya bukvennyh literalov. Pri vyzove yacc s flagom -d posledovatel'nost' operato- rov #define pomeshchaetsya takzhe v informacionnyj fajl y.tab.h. Pereopredeliv pri neobhodimosti ryad nomerov tipov leksem,pol'zovatel' dolzhen proverit' unikal'nost' nomerov u vseh ispol'zuemyh leksem. - 14 - 7. Deklaraciya imeni nachal'nogo simvola %start <imya_nachal'nogo_simvola> Direktiva otmenyaet dejstvuyushchij po umolchaniyu vybor v kachestve nachal'nogo simvola neteriminala, opredelyaemogo per- vym grammaticheskim pravilom. 7.1. Sekciya programm V sekciyu programm pomeshchaetsya opisanie pol'zovatel'skih procedur, kotorye dolzhny byt' vklyucheny v generiruemuyu prog- rammu grammaticheskogo analiza. Lyubaya iz opredelyaemyh pol'zo- vatelem programmnyh komponent mozhet nahodit'sya v sekcii programm specifikacionnogo fajla, libo prisoedinyat'sya na etape vyzova Si-kompilyatora dlya translyacii fajla y.tab.c i komponovki vyhodnoj programmy. Perechislim procedury, kotorye odnim iz etih sposobov dolzhny byt' zadany: - leksicheskij analizator - funkciya s imenem yylex(); - vse procedury, vyzovy kotoryh soderzhatsya v dejstviyah, svyazannyh s grammaticheskimi pravilami; - glavnaya procedura main() pri neobhodimosti zamenit' ee standartnyj bibliotechnyj variant, kotoryj imeet vid main() {return (yyparse();} - procedura obrabotki oshibok yyerror() - takzhe dlya zameny bibliotechnogo varianta (ego tekst privoditsya nizhe). #include <stdio.h> yyerror(s) char *s; { fprintf(stderr, "%s\n", s);} Dlya obespecheniya korrektnoj raboty grammaticheskogo ana- lizatora funkciya leksicheskogo analiza yylex dolzhna byt' sog- lasovana s konkretnoj specifikaciej grammatiki i udovletvo- ryat' opredelennym trebovaniyam. Osnovnaya zadacha funkcii yylex sostoit vo vvode iz vhodnogo potoka ryada ocherednyh simvolov do vyyavleniya konstrukcii, sootvetstvuyushchej odnoj iz leksem, i vozvrashchenii nomera tipa etoj leksemy. Dlya neliteral'nyh lek- sem nomerom tipa mozhet sluzhit' ob座avlennoe v sekcii deklara- cij imya leksemy (s pomoshch'yu mehanizma #define yacc obespechi- vaet zamenu ego nuzhnym nomerom), v sluchae literalov nomerom tipa yavlyaetsya chislovoe znachenie simvola (esli ono ne bylo - 15 - pereopredeleno). Algoritm poiska dolzhen zaklyuchat'sya v popytke nahozhdeniya snachala bolee slozhnyh (neliteral'nyh) leksem i lish' pri nesovpadenii ni s odnoj iz nih tekushchih elementov vvoda vozvrashchat' nomer tipa literal'noj leksemy (lyuboj odnoznachnyj simvol, ne nachinayushchij ni odnu iz vozmozh- nyh leksem, sam obrazuet leksemu). Privedem tekst procedury leksicheskogo analiza, raspoz- nayushchej identifikatory i celye chisla: #include <stdio.h> yylex() {char c; while ((c=getc(stdin))==' '||c=='\n'); if(c>='0'&&c<='9'){ while((c=getc(stdin))>='0'&&c<='9'); ungetc(c,stdin)); return (CONST);} if (c>='a'&&c<='z'){ while ((c=getc(stdin))>'a'&&c<='z' ||c>='0'&&c<='9'); ungetc(c,stdin); return (NAME);} return (c); } Slozhnost' leksicheskogo analizatora zavisit ot togo, kakie strukturnye edinicy vzyaty za osnovu pri opisanii gram- maticheskih pravil. Detalizovav grammatiku do otdel'nyh sim- volov, mozhno obojtis' prostejshim leksicheskim analizatorom, osushchestvlyayushchim tol'ko ih vvod: yylex() {return (getchar());} Odnako, v etom sluchae chislo pravil rastet, a grammati- cheskij razbor okazyvaetsya menee effektivnym. Poetomu pol'zo- vatel' obychno dolzhen najti nekotoryj kompromiss pri vybore nabora leksem. V procedure leksicheskogo analiza krome vydeleniya leksem mozhno predusmotret' nekotoruyu obrabotku leksem opredelennyh tipov, v chastnosti, zapominanie konkretnyh znachenij leksem. Krome togo, eti znacheniya obychno trebuetsya peredat' grammati- cheskomu analizatoru. S etoj cel'yu nuzhnoe znachenie dolzhno byt' prisvoeno vneshnej peremennoj celogo tipa s imenem yyl- val. Esli funkciya yylex nahoditsya v otdel'nom fajle, to eta peremennaya dolzhna byt' ob座avlena: extern int yylval; - 16 - Utochnim, chto v dal'nejshem znacheniem leksemy my budem nazyvat' znachenie, prisvoennoe pri ee raspoznavanii peremen- noj yylval; znachenie, vozvrashchaemoe funkciej yylex, yavlyaetsya nomerom tipa leksemy. Primerom znacheniya leksemy mogut sluit' chislovoe znachenie cifry, vychislennoe znachenie konstanty, adres identifikatora v tablice imen (postroenie tablicy imen udobno osushchestvlyat' leksicheskim analizatorom). Zametim, chto, hotya znachenie yylval ustanavlivaetsya s cel'yu ispol'zo- vaniya ego v dejstviyah, neposredstvennoe obrashchenie k pereMen- noj yylval v dejstvii ne imeet smysla (poskol'ku v yylval vsegda nahoditsya znachenie poslednej vydelennoj leksemy). Dostup v dejstviyah k znacheniyam leksem osushchestvlyaetsya s pomoshch'yu special'nogo mehanizma, opisannogo v razdele 4.5. 7.2. Dejstviya s ispol'zovaniem psevdoperemennyh Dlya obespecheniya svyazi mezhdu dejstviyami, a takzhe mezhdu dejstviyami i leksicheskim analizatorom sozdavaemye yacc gram- maticheskie analizatory podderzhivayut special'nyj stek, v kotorom sohranyayutsya znacheniya leksem i neterminal'nyh simvo- lov. Znachenie leksemy avtomaticheski popadaet v stek posle ee raspoznavaniya leksicheskim analizatorom (napomnim, chto im schitaetsya tekushchee znachenie peremennoj yylval). Posle kazhdoj svertki vychislyaetsya znachenie neterminala, zamestivshego sver- nutuyu stroku, i pomeshchaetsya v vershinu steka; znacheniya elemen- tov pravoj chasti primenennogo pravila pered etim vytalkiva- yutsya iz steka. Zametim, chto takim obrazom k momentu svertki lyubogo pravila vse znacheniya neterminalov v pravoj chasti oka- zyvayutsya vychislennymi v rezul'tate svertok. Sposob vychisle- niya znacheniya neterminala budet rassmotren nizhe. Opisannyj mehanizm ne trebuet vmeshatel'stva pol'zova- telya i predostavlyaet emu sleduyushchie vozmozhnosti: - Ispol'zovat' v dejstviyah, osushchestvlyaemyh posle svertki po pravilu, znachenie lyubogo elementa ego pravoj chasti. Dostup k etim znacheniyam obespechivaetsya naborom tak nazyvaemyh psevdoperemennyh s imenami $1,$2,..., gde $i sootvetstvuet znacheniyu i-go elementa; elementy pravoj chasti pravila numeruyutsya sleva napravo bez razlichiya leksem i neterminal'nyh simvolov, naprimer, v pravile P_Head: P_name '(' P_list ')'; psevdoperemennye $1,$2,$3,$4 otnosilis' by sootvetst- venno k P_name, '(', P_list, ')'. - Formirovat' v dejstviyah znachenie, obrazovannogo v rezul'tate svertki neterminala putem prisvoeniya etogo znacheniya psevdoperemennoj s imenem $$. Tak, v pravile - 17 - expr: expr '+' expr { $$=$1+$3; } znacheniem novogo neterminala expr stanet summa ranee vychislennyh znachenij dvuh drugih neterminalov expr. Esli v dejstvii ne opredelyaetsya znachenie peremennoj $$ (a takzhe esli dejstvie otsutstvuet), znacheniem netermi- nala posle svertki po umolchaniyu stanovitsya znachenie pervogo elementa pravoj chasti, t.e. neyavno vypolnyaetsya prisvaivanie $$=$1; Primer (vychislenie znacheniya celogo chisla) %token DIGIT %% ... CONST: DIGIT | CONST DIGIT {$$=$1*10+$2;} ... %% yylex() { char c; if((c=getchar())>='0'&& c<='9') { yylval = c-'0'; return (DIGIT); } ... } Zdes' pri svertke po pervomu pravilu neterminal CONST poluchaet znachenie pervoj cifry, prisvoennoe v funkcii yylex peremennoj yylval; pri kazhdoj svertke po vtoromu pravilu yavno vychislyaetsya znachenie novogo neterminala CONST. Neskol'ko inaya situaciya v otnoshenii ispol'zovaniya psev- doperemennyh imeet mesto dlya pravil, soderzhashchih dejstviya vnutri pravoj chasti. Na samom dele yacc interpretiruet pra- vilo vida A: B C {dejstvie 1} D {dejstvie 2} K {dejstvie 3} kak A: B C EMPTY1 D EMPTY2 K; EMPTY1: {dejstvie 1} EMPTY2: {dejstvie 2} i v meste, gde vstavleno dejstvie, pri razbore - 18 - osushchestvlyaetsya svertka po pustomu pravilu, soprovozhdayushchayasya vypolneniem ukazannogo dejstviya. Pri etom nezavisimo ot haraktera dejstviya ocherednoj element v steke znachenij otvo- ditsya dlya hraneniya znacheniya neyavno prisutstvuyushchego "pustogo" neterminala. V dejstvii, nahodyashchemsya v konce pravila, sogla- shenie o znacheniyah psevdoperemennyh ostaetsya prezhnim, esli imet' v vidu nalichie dopolnitel'nyh simvolov. V privedennom vyshe pravile v dejstvii 3 dlya dostupa k znacheniyam elementov B, C, D, K sledovalo by ispol'zovat' sootvetstvenno psevdo- peremennye $1, $2, $4, $6; psevdoperemnnye $3, $5 hranyat rezul'taty dejstvij 1 i 2. V dejstviyah, nahodyashchihsya vnutri pravila, s pomoshch'yu psevdoperemnnyh $i dostupny znacheniya ras- polozhennyh levee elementov, a takzhe rezul'taty predshestvuyu- shchih vstavlennyh v telo dejstvij. Rezul'tatom vnutrennego dejstviya (t.e. znacheniem neyavnogo neterminala) yavlyaetsya zna- chenie, prisvoennoe v etom dejstvii psevdoperemennoj $$, pri otsutstvii takogo prisvaivaniya rezul'tat dejstviya ne oprede- len. Zametim, chto prisvaivanie znacheniya psevdoperemennoj $$ vo vnutrennih dejstviyah ne vyzyvaet predvaritel'noj usta- novki znacheniya neterminala, stoyashchego v levoj chasti pravila: eto znachenie v lyubom sluchae ustanavlivetsya tol'ko dejstviem v konce pravila ili schitaetsya ravnym znacheniyu $1. V nashem primere v dejstvii 1 dostupnymi yavlyayutsya tol'ko znacheniya elementov B i C (im sootvetstvuyut psevdoperemennye $1 i $2), a v dejstvii 2 - znacheniya elementov B, C, D i rezul'tat dejstviya 1 s pomoshch'yu psevdoperemennyh $1, $2, $4, $3. Sleduyushchij primer illyustriruet varianty ispol'zovaniya psevdoperemennyh: %token IMYA KLYUCH1 KLYUCH2 KONEC . . . %% vhodnoj_potok: dannye KONEC {printf("Dannye zaneseny v fajl %s\n",$1);}; dannye: IMYA {abc = creat($1,0666);} KLYUCH1 KLYUCH2 {option($3,$4);} upr_stroka '\n' {converse(0,$5,$6); write($1,$6,80);} tekst {converse(1,$5,$8); write($1,$6,$8); close($1);}; upr_stroka: ... tekst : ... . . . - 19 - Upravlyayushchaya stroka i tekst preobrazuyutsya v sootvetstvii s zadannymi klyuchami i zapisyvayutsya v fajl s ukazannym imenem. Znacheniem neterminala dannye v rezul'tate neyavnogo dejstviya stanovitsya znachenie leksemy IMYA (adres stroki s imenem fajla prisvaivaetsya v leksicheskom analizatore peremennoj yylval). 8. Konflikty grammaticheskogo razbora Zadannaya grammatika yavlyaetsya neodnoznachnoj, esli sushchestvuet vhodnaya stroka, kotoraya v sootvetstvii s etoj grammatikoj mozhet byt' razobrana dvumya ili bolee razlichnymi sposobami. Rassmotrim, naprimer, nabor pravil, opisyvayushchih konstantnoe arifmeticheskoe vyrazhenie: expr: CONST /*1*/ | expr '+'expr /*2*/ | expr '-'expr /*3*/ | expr '*'expr /*4*/ | expr '/'expr; /*5*/ Opisyvaya vozmozhnost' postroeniya vyrazheniya iz dvuh vyra- zhenij, soedinennyh znakom arifmeticheskoj operacii, pravila neodnoznachno opredelyayut put' razbora nekotoryh vhodnyh strok. Tak, stroka vida: expr*expr-expr dopuskaet dva puti razbora, privodyashchih k razlichnym gruppi- rovkam ee elementov: expr*(expr-expr) i (expr*expr) - expr S tochki zreniya raboty grammaticheskogo analizatora dan- naya situaciya proyavlyaetsya v neodnoznachnosti vybora dejstviya pri vvode leks