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:
%%
%%
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:
%%
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;
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;
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 leksemy "-" v moment, kogda razobrannaya chast'
stroki privedena k vidu expr*expr. Dva vozmozhnyh dejstviya
analizatora sostoyat v sleduyushchem:
Mozhno vvesti sleduyushchij simvol i bez primeneniya pravila
podstanovki perejti v novoe sostoyanie. V razdele 1 my
nazvali takoe dejstvie sdvigom. Vybor sdviga privedet k
tomu, chto v odnom iz sleduyushchih sostoyanij ko vtoroj
chasti konstrukcii dlya privedeniya ee k expr budet prime-
neno pravilo (3), a zatem vsya poluchennaya konstrukciya
svedetsya k expr primeneniem pravila (4).
- 20 -
Mozhno srazu primenit' k konstrukcii expr*expr pravilo
(4), tem samym privedya ee k expr, i bez vvoda novogo
simvola perejti v ocherednoe sostoyanie. Takoe dejstvie v
razdele 1 bylo nazvano svertkoj. Ispol'zovanie svertki
v dannom sostoyanii privedet k primeneniyu v dal'nejshem
pravila (3) dlya svertyvaniya ostavshejsya chasti konstruk-
cii v expr.
Neodnoznachnost' takogo roda budem nazyvat' konfliktom
"sdvig/svertka". (Vyshe etot konflikt byl umyshlenno pokazan
na primere vyrazheniya, poryadok razbora kotorogo sushchestven v
svyazi s razlichiem prioritetov operacij. Na samom dele konf-
likt sdvig/svertka voznikaet i pri razbore takoj stroki, kak
expr-expr-expr. V etom sluchae raznica v razbore vedet lish'
k traktovke operacii "-" kak levo- ili pravoassociativnoj.
Odnako, kak izvestno, associativnost' inogda igraet vazhnuyu
rol', naprimer, dlya operacij prisvaivaniya, vozvedeniya v ste-
pen'. Vozmozhen drugoj vid konflikta, sostoyashchij v vybore
mezhdu dvumya vozmozhnymi svertkami; budem nazyvat' ego konf-
liktom "svertka/svertka". Dlya primera podobnogo konflikta
privedem grammatiku, zadayushchuyu desyatichnuyu i shestnadcaterichnuyu
formu zapisi konstanty:
const: const_10 /*1*/
| const_16 ; /*2*/
const_10: dec_sequence; /*3*/
const_16: hex_sequence 'x'; /*4*/
dec_sequence:digit /*5*/
| dec_sequence digit; /*6*/
hex_sequence:digit /*7*/
| ABCDEF /*8*/
|hex_sequence digit /*9*/
|hex_sequence ABCDEF; /*10*/
ABCDEF : 'A'|'B'|'C'|'D'|'E'|'F';
digit:'0'|'1'|'2'|'3'|'4'|'5'|'6'
|'7'|'8'|'9';
Pri poyavlenii na vhode pervoj zhe desyatichnoj cifry (esli
s nee nachinaetsya posledovatel'nost') posle ee zameny neter-
minalom digit voznikaet konflikt mezhdu dvumya vozmozhnymi
svertkami: k neterminalu dec_sequence v rezul'tate primene-
niya pravila (5) i k neterminalu hex_sequence s pomoshch'yu pra-
vila (7). Zametim, chto eta grammatika, v otlichie ot gramma-
tiki v predydushchem primere, ne pozvolyaet korrektno razobrat'
kakuyu-libo stroku dvumya sposobami i v principe neterminal
const opredelen odnoznachno. Odnako, algoritm razbora s
prosmotrom vpered na 1 simvol ne v sostoyanii pravil'no osu-
shchestvit' vybor nuzhnogo pravila. Sledovatel'no, v etom sluchae
rech' idet o neodnoznachnosti grammatiki po otnosheniyu k prinya-
tomu v yacc metodu razbora. Poskol'ku vopros o principial'-
noj neodnoznachnosti grammatiki formal'no nerazreshim, budem v
dal'nejshem ponimat' pod neodnoznachnost'yu nevozmozhnost' dlya
- 21 -
analizatora v nekotorye momenty razbora vybrat' ocherednoe
dejstvie. Kazhdaya situaciya (t.e. poyavlenie v nekotorom sosto-
yanii nekotoroj vhodnoj leksemy), kotoraya pri razbore spo-
sobna vyzvat' konflikt "sdvig/svertka" ili "svertka/
svertka", vyyavlyaetsya yacc uzhe na etape postroeniya grammati-
cheskogo analizatora. Pri etom yacc vydaet soobshchenie o chisle
vyyavlennyh konfliktnyh situacij oboih vidov, a v vyhodnoj
fajl y.output (esli on formiruetsya) pomeshchaetsya podrobnoe
opisanie vseh konfliktov. Odnako, yacc ne schitaet nalichie
konfliktov fatal'noj oshibkoj grammatiki i stroit grammati-
cheskij analizator, zaranee razreshaya vse vozmozhnye konflikty
putem vybora v kazhdoj situacii edinstvennogo dejstviya.
Pri rabote yacc ispol'zuyutsya dva sposoba razresheniya
konfliktov. Pervyj sposob dejstvuet po umolchaniyu (t.e. pri
otsutstvii special'noj pol'zovatel'skoj informacii) i zaklyu-
chaetsya v primenenii sleduyushchih dvuh pravil dlya vybora dejst-
viya v konfliktnyh situaciyah:
V sluchae konflikta sdvig/svertka po umolchaniyu delaetsya
sdvig.
V sluchae konflikta svertka/svertka po umolchaniyu dela-
etsya svertka po tomu iz konkuriruyushchih pravil, kotoroe
zadano pervym v specifikacionnom fajle.
Grammaticheskij analizator, postroennyj s ispol'zovaniem
etih pravil, mozhet ne obespechivat' "pravil'nogo" s tochki
zreniya pol'zovatel'skoj grammatiki razbora. V chastnosti,
dlya pervogo iz privedennyh vyshe primerov razbor zaklyuchalsya
by v svorachivanii arifmeticheskih vyrazhenij sprava nalevo bez
ucheta prioritetov operacij. Vo vtorom primere v rezul'tate
zameny pervoj konstrukcii digit neterminalom dec_sequence
vse chisla, nachinayushchiesya s cifry, razbiralis' by kak desyatich-
nye, a poyavlenie odnoj iz bukv ot A do F ili simvola "x" v
konce chisla neverno traktovalos' kak oshibka vo vhodnom
tekste.
Odnako, v ryade situacij opisannyj sposob razresheniya
konfliktov privodit k nuzhnomu rezul'tatu. Naprimer, rassmot-
rim fragment grammatiki yazyka programmirovaniya, opisyvayushchij
uslovnyj operator:
operator: if '(' uslovie ')' operator /*1*/
|
if '(' uslovie ')' operator else
operator; /*2*/
Vhodnaya stroka vida:
if(C1) if(C2) S1 else S2
vyzvala by pri razbore konflikt sdvig/svertka v moment
- 22 -
prosmotra simvola else. Vvedennaya chast' stroki k etomu vre-
meni imeet vid:
if (uslovie) if (uslovie) operator
Esli vypolnit' svertku vtoroj chasti konstrukcii po pravilu
(1), to stroka svedetsya k:
if (uslovie) operator
(Zametim, chto primenit' eshche raz pravilo(1) meshaet prosmot-
rennyj zaranee simvol else). Posle vvoda konstrukcii S2 i
zameny ee neterminalom operator k stroke:
if (uslovie) operator else operator
budet primeneno pravilo (2). Poluchennyj razbor sootvetstvuet
sleduyushchej interpretacii vhodnoj stroki:
if (C1) {if(C2) S1} else S2
Pri al'ternativnom podhode v sluchae primeneniya sdviga v
moment poyavleniya else vhodnaya stroka byla by vvedena pol-
nost'yu:
if (uslovie) if (uslovie) operator
else operator
Ko vtoroj chasti stroki mozhno primenit' pravilo (2), a zatem
svernut' poluchennuyu konstrukciyu:
if (uslovie) operator
po pravilu (1). Takoj razbor sootvetstvuet vtoroj vozmozhnoj
interpretacii vhodnoj stroki:
if (C1) {if(C2) S1 else S2}
Kak izvestno, v bol'shinstve yazykov programmirovaniya prinyata
imenno eta interpretaciya (kazhdyj else otnositsya k blizhajshemu
predshestvuyushchemu if). Znachit, vybor sdviga, osushchestvlyaemyj po
umolchaniyu, dlya dannoj grammatiki veren.
V kachestve rekomendacii otmetim,chto primenenie principa
umolchaniya dlya konfliktov sdvig/svertka privodit k polozhi-
tel'nomu rezul'tatu, esli v grammatike prinyata pravoassocia-
tivnaya interpretaciya sootvetstvuyushchih konstrukcij i dlya nih
otsutstvuet ponyatie prioriteta. CHto kasaetsya konfliktov
svertka/svertka, to standartnyj sposob ih razresheniya okazy-
vaetsya poleznym tol'ko togda, kogda pri lyubyh konfliktah
mezhdu dannymi dvumya pravilami spravedliv vybor odnogo i togo
zhe pravila.
- 23 -
V lyubom sluchae, esli yacc soobshchil o nalichii konfliktnyh
situacij, pol'zovatel' dolzhen tshchatel'no proanalizirovat'
soderzhatel'nyj smysl kazhdogo konflikta i pravil'nost' vyb-
rannogo yacc dejstviya. Vsya neobhodimaya dlya etogo informaciya
soderzhitsya v fajle y.output, struktura kotorogo budet rass-
motrena nizhe. Esli okazalos', chto konflikty razresheny neu-
dovletvoritel'no, to grammatika dolzhna byt' perestroena ili
utochnena pol'zovatelem. V sluchae konfliktov svertka/svertka
vsegda trebuetsya izmenenie samih grammaticheskih pravil; dlya
konfliktov sdvig/svertka est' vozmozhnost' bez perestrojki
pravil utochnit' grammatiku putem zadaniya informacii o prio-
ritetah i associativnosti leksem i pravil.
V kachestve primerov ustraneniya konfliktov putem izmene-
niya pravil privedem perestroennye varianty rassmatrivavshihsya
vyshe grammatik. Poskol'ku ishodnye konfliktnye grammatiki
polnost'yu udovletvoryayut trebovaniyam generiruemyh imi yazykov,
no soderzhat nedostatochno informacii dlya odnoznachnogo raz-
bora, perestrojka pravil nosit utochnyayushchij harakter.
Perestroennaya grammatika konstantnogo arifmeticheskogo
vyrazheniya:
expr: expr1
|
expr '+' expr1
|
expr '-' expr1;
expr1: CONST
|
expr1 '*' CONST
|
expr1 '/' CONST;
Nizhe budet priveden takzhe variant grammatiki, poluchennoj iz
ishodnoj vvedeniem prioritetov (bez perestrojki pravil).
Perestroennaya grammatika dlya zadaniya konstanty:
const: const_10
| const_16;
const_10: dec_sequence ;
const_16: hex_sequence 'x'
| dec_sequence 'x';
dec_sequence: digit
| dec_sequence digit;
hex_sequence: ABCDEF
| dec_sequence ABCDEF
| hex_sequence ABCDEF
|hex_sequence dec_sequence;
ABCDEF:...
digit:...
- 24 -
Rassmotrim teper' vtoroj iz ispol'zuemyh yacc sposobov raz-
resheniya konfliktov, baziruyushchijsya na zadanii pol'zovatelem
informacii o prioritetah i associativnosti. Otmetim predva-
ritel'no dve osnovnye prichiny konfliktnosti grammatik:
principial'naya nevozmozhnost' zadat' generiruemyj yazyk
beskonfliktnoj grammatikoj;
nedostatochnost' informacii dlya postroeniya odnoznachnogo
grammaticheskogo razbora.
Grammatiki, konfliktnye po vtoroj prichine, vsegda
dopuskayut preobrazovanie pravil do polnogo ustraneniya konf-
liktov; v sluchae konfliktov sdvig/svertka yacc vsegda mozhet
postroit' dlya etih grammatik korrektnyj razbor putem razre-
sheniya konfliktov. Dlya grammatik, konfliktnyh po prichine 1,
popytki razresheniya konfliktov ne privedut k nuzhnomu rezul'-
tatu. Odnako, nado ubedit'sya v tom, chto konfliktnaya gramma-
tika dejstvitel'no otrazhaet vhodnoj yazyk: vozmozhno, konf-
likty ne imeyut otnosheniya k etomu yazyku, a vyzvany neodnoz-
nachnost'yu drugogo, real'no opisannogo yazyka. Voobshche, konf-
likty stoit rassmatrivat' kak povod proverit' grammatiku na
sootvetstvie yazyku (hotya poslednee ne garantiruetsya i
otsutstviem konfliktov). Zadanie prioritetov dlya nevernoj
grammatiki ne privedet k generacii nuzhnogo yazyka, no mozhet
zamaskirovat' oshibki, snyav vopros o konfliktah.
Prioritetnoe razreshenie konfliktov sdvig/svertka sos-
toit v tom, chto s oboimi dejstviyami yacc associiruet priori-
tety (so sdvigom - prioritet leksemy, chtenie kotoroj vyzy-
vaet dannyj konflikt, so svertkoj - prioritet konkuriruyushchego
pravila) i vybiraet bolee prioritetnoe dejstvie. V sluchae
ravenstva prioritetov yacc rukovodstvuetsya pri vybore
svojstvom associativnosti. Prioritety i associativnost'
otdel'nyh leksem (yavno) i pravil (yavno i neyavno) zadayutsya
pol'zovatelem, vse ostal'nye prioritety schitayutsya neizvest-
nymi. yacc ispol'zuet dlya razresheniya konflikta dannyj spo-
sob, esli izvestny prioritety oboih konkuriruyushchih dejstvij.
Poetomu dlya razresheniya ryada konfliktov na prioritetnoj
osnove neobhodimo ustanovit' prioritety uchastvuyushchih v nih
leksem i pravil.
Sleduet ponimat',chto zadanie prioritetov ne vedet k
ustraneniyu konfliktov i ne delaet grammatiku odnoznachnoj. No
v otlichie ot konfliktov, razreshaemyh yacc po principu umol-
chaniya, pol'zovatel' poluchaet zdes' vozmozhnost' upravlyat'
razresheniem konfliktov. yacc, soobshchaya obshchee chislo konflik-
tov, ne uchityvaet v nem konfliktov, razreshennyh v sootvetst-
vii s informaciej o prioritetah i ne vklyuchaet v vyhodnoj
fajl y.output opisaniya etih konfliktov.
Prioritety i associativnost' leksem zadayutsya v sekcii
deklaracij s pomoshch'yu direktiv treh vidov:
- 25 -
%left <spisok_leksem>
%right <spisok_leksem>
%nonassoc <spisok_leksem>
Kazhdaya direktiva pripisyvaet vsem perechislennym v spiske
leksemam odinakovyj prioritet. Direktivy %left i %right
odnovremenno zadayut sootvetstvenno levuyu ili pravuyu associa-
tivnost' leksem. Direktiva %nonassoc govorit ob otsutstvii
u perechislennyh leksem svojstva associativnosti. Ustanavli-
vaemyj direktivami prioritet ne imeet chislennogo vyrazheniya,
a ego otnositel'noe znachenie vozrastaet sverhu vniz.
Primer zadaniya prioritetov leksem:
%token OR NOR XOR AND NAND
%right '='
%left OR NOR XOR
%left AND NAND
%left '+' '-'
%left '*' '/'
/* samyj nizkij prioritet imeet leksema "=",
samyj vysokij - leksemy "*" i "/"
*/
Prioritet pravila avtomaticheski opredelyaetsya priorite-
tom poslednej leksemy v tele pravila. Esli v sekcii deklara-
cij dlya etoj leksemy ne zadan prioritet ili esli pravaya
chast' pravila voobshche ne soderzhit leksem, to prioritet pra-
vila ne opredelen. |tot princip mozhno otmenit' yavnym zada-
niem prioriteta pravila ravnym prioritetu lyuboj (imeyushchej
prioritet) leksemy s pomoshch'yu direktivy:
%prec <leksema>
pomeshchennoj vsled za pravoj chast'yu pravila (pered tochkoj s
zapyatoj ili dejstviem). Naprimer, pravilu:
expr: '-' expr %prec '*';
direktiva %prec pridaet prioritet leksemy "*" (leksema "-"
pri zadanii grammatiki vyrazhenij chasto ispol'zuetsya dlya
oboznacheniya unarnoj i binarnoj operacij, imeyushchih raznyj pri-
oritet; s pomoshch'yu direktivY %prec unarnoj operacii mozhno
pripisat' bolee vysokij prioritet. Inogda, chtoby svyazat' s
pravilom prioritet, ne sovpadayushchij s prioritetom ni odnoj
leksemy, vvodyat psevdoleksemu, zadav ej v sekcii deklaracij
unikal'nyj prioritet, i pripisyvayut prioritet psevdoleksemy
pravilu. V primere grammatiki nastol'nogo kal'kulyatora, pri-
vodimom v prilozhenii, s operaciej "unarnyj minus" svyazan
prioritet psevdoleksemy UMINUS).
- 26 -
Sformuliruem teper' polnost'yu ispol'zuemye yacc pravila
razresheniya konfliktov sdvig/svertka na osnove informacii o
prioritetah i associativnosti (napomnim, chto konflikty
svertka/svertka razreshayutsya tol'ko po principu umolchaniya):
Esli dlya vhodnoj leksemy i pravila zadany prioritety i
eti prioritety razlichny, to vybiraetsya dejstvie s bol'-
shim prioritetom. Bol'shij prioritet pravila vyzyvaet
svertku po nemu, bol'shij prioritet leksemy vyzyvaet
sdvig.
Esli prioritety zadany i sovpadayut, to prinimaetsya vo
vnimanie zadannaya odnovremenno s prioritetom associa-
tivnost': v sluchae levoj associativnosti ispol'zuetsya
svertka, v sluchae pravoj - sdvig. Otsutstvie svojstva
associativnosti (direktiva %nonassoc) v dannom sluchae
ukazyvaet na oshibku vo vhodnom tekste i analizator
vosprimet vyzvavshuyu dannyj konflikt leksemu kak oshiboch-
nuyu.
Esli ne zadan prioritet vhodnoj leksemy i/ili prioritet
pravila, to dejstvuet princip razresheniya konfliktov po
umolchaniyu, v rezul'tate chego vybiraetsya sdvig.
Primer grammatiki konstantnogo vyrazheniya, utochnennoj zada-
niem prioritetov:
%left '+' '-'
%left '*' '/'
%%
expr: CONST
| expr '+' expr
| expr '-' expr
| expr '*' expr
| expr '/' expr;
9. Struktura informacionnogo vhodnogo fajla y.output
Osnovnuyu chast' dannogo fajla sostavlyaet opisanie sosto-
yanij postroennogo grammaticheskogo analizatora. Informaciya o
kazhdom sostoyanii privoditsya v sleduyushchem poryadke:
- Perechen' sootvetstvuyushchih dannomu sostoyaniyu konfiguracij
grammatiki (konfiguraciya harakterizuetsya opredelennym
grammaticheskim pravilom i poziciej v ego pravoj chasti,
dostignutoj k dannomu momentu razbora). Kazhdaya konfigu-
raciya predstavlyaetsya pravilom s otmechennoj s pomoshch'yu
simvola podcherkivaniya "_" raspoznannoj chast'yu (poziciej
konfiguracii). Naprimer, konfiguraciya:
expr: expr +_expr
- 27 -
sootvetstvuet raspoznannoj pri razbore stroki po uka-
zannomu pravilu posledovatel'nosti simvolov expr+.
- Dejstviya analizatora pri vvode v kachestve ocherednogo
prosmatrivaemogo simvola kazhdoj iz leksem. Razlichnye
vidy dejstvij ukazyvayutsya sleduyushchim obrazom:
<leksema> sdvig <nomer_sostoyaniya> -
sdvig pri vvode dannoj leksemy v sostoyanie s ukazannym
nomerom;
<leksema> svertka <nomer_pravila> -
svertka pri vvode leksemy po pravilu s ukazannym nome-
rom;
<leksema> error -
vydacha soobshcheniya ob oshibke vo vhodnyh dannyh ("sintak-
sicheskaya oshibka") i vozvrat iz procedury grammatiches-
kogo analiza s kodom 1 (dal'nejshij razbor nevozmozhen);
<leksema> accept -
vozvrat iz procedury grammaticheskogo analiza s kodom 0
(uspeshnoe zavershenie razbora). Poslednyaya iz strok,
opisyvayushchih dejstviya analizatora, soderzhit vmesto uka-
zaniya leksemy simvol "." i soobshchaet dejstvie, vypolnyae-
moe analizatorom dlya vseh leksem, ne perechislennyh v
dannom sostoyanii. CHasto eta stroka imeet vid:
. error
i ukazyvaet, chto vse perechislennye leksemy v dannom
sostoyanii yavlyayutsya nedopustimymi.
- Perechen' perehodov dlya dannogo sostoyaniya. Kazhdyj pere-
hod zadaetsya strokoj
<imya_terminala> perehod <nomer_sostoyaniya>
soobshchayushchej, v kakoe sostoyanie perejdet analizator posle
svertki ukazannogo neterminala, esli ego raspoznavanie
bylo nachato iz dannogo sostoyaniya.
Krome togo, opisaniyu sostoyaniya mozhet predshestvovat'
informaciya o konfliktah obnaruzhennyh yacc dlya etogo sostoya-
niya i razreshennyh po principu umolchaniya. Informaciya o konf-
likte soderzhit tip konflikta (sv/sv ili sdv/sv), konkuriruyu-
shchie dejstviya analizatora (pri etom dlya sdviga ukazyvaetsya
nomer sostoyaniya, dlya svertki - nomer pravila) i leksemu, pri
poyavlenii kotoroj voznikaet dannyj konflikt. Uznat', kakoe
- 28 -
iz vozmozhnyh dejstvij budet vypolneno analizatorom, mozhno iz
opisaniya samogo sostoyaniya.
Primer opisaniya sostoyaniya:
8:Konflikt sdv/sv (sdvig 5,svertka 2) pri +
Sostoyanie 8
a:a_+a
a:a+a_ (2)
+ sdvig 5
. svertka 2
Sostoyaniyu 8 zdes' sootvetstvuyut dve razlichnye pozicii, dos-
tignutye pri razbore po pravilu
a: a '+' a
Konflikt mezhdu svertkoj po etomu pravilu i sdvigom v sostoya-
nie 5 pri vvode leksemy "+" razreshen v pol'zu sdviga. Vvod
ostal'nyh leksem vyzyvaet svertku.
Posle opisaniya sostoyaniya vozmozhen ryad soobshchenij o nes-
vernutyh pravilah (s ukazaniem etih pravil), t.e. o pravi-
lah, svertka po kotorym ne budet proizvedena ni v odnom iz
sostoyanij. Nalichie takih pravil s bol'shoj veroyatnost'yu svi-
detel'stvuet o nekorrektnosti grammatiki.
V konce fajla privoditsya informaciya statisticheskogo
haraktera o real'nom i predel'nom kolichestve terminal'nyh i
neterminal'nyh simvolov, grammaticheskih pravil i sostoyanij.
Fiksiruetsya chislo konfliktov kazhdogo tipa, chislo razlichnyh
dejstvij grammaticheskogo analizatora, zanimaemyj im ob容m
pamyati, privodyatsya dannye ob ispol'zovanii vnutrennih struk-
tur dannyh (mnozhestv).
10. Obrabotka oshibok pri grammaticheskom razbore
Esli vhodnoj potok ne udovletvoryaet zadannoj gramma-
tike, to grammaticheskij analizator v moment vvoda leksemy,
delayushchej nevozmozhnym prodolzhenie razbora, fiksiruet oshibku.
|tu leksemu my v dal'shejshem budem nazyvat' oshibochnoj lekse-
moj. Real'no oshibka mozhet byt' vyzvana ne tol'ko nevernymi
vhodnymi dannymi, no i nekorrektnost'yu samogo grammatiches-
kogo analizatora, yavlyayushchejsya sledstviem nekorrektnoj gramma-
tiki.
Standartnoj reakciej grammaticheskogo analizatora na
oshibku yavlyaetsya vydacha soobshcheniya ("sintaksicheskaya oshibka") i
prekrashchenie razbora. |tu reakciyu mozhno neskol'ko izmenit',
naprimer, sdelat' soobshchenie ob oshibke neskol'ko bolee infor-
mativnym, zadav sobstvennuyu proceduru yyerror. Odnako, nai-
bolee vazhnaya zadacha sostoit v tom, chtoby zastavit' analiza-
tor v etom sluchae prodolzhat' prosmotr vhodnogo potoka, v
- 29 -
chastnosti, dlya vyyavleniya ostal'nyh oshibok. Primenyaemyj yacc
mehanizm vosstanovleniya osnovan na chtenii i otbrasyvanii
nekotorogo chisla vhodnyh leksem; ot pol'zovatelya trebuetsya
vvedenie dopolnitel'nyh grammatichsekih pravil, ukazyvayushchih,
v kakih konstrukciyah sintaksicheskie oshibki yavlyayutsya dopusti-
mymi (v otnoshenii vozmozhnosti vosstanovleniya). Odnovremenno
eti pravila opredelyayut put' dal'nejshego razbora dlya oshiboch-
nyh situacij. Dlya ukazaniya tochek dopustimyh oshibok ispol'-
zuetsya zarezervirovannoe s etoj cel'yu imya leksemy error.
Primer:
a: b c d ; /*1*/
a: b c error; /*2*/
d: d1 d2 d3; /*3*/
Vtoroe pravilo ukazyvaet put' razbora v sluchae, esli pri
raspoznavanii neterminala a vstretitsya oshibka posle vydele-
niya elementov b i c.
yacc obrabatyvaet pravila, soderzhashchie leksemu error,
tak zhe, kak vse ostal'nye pravila. V rezul'tate v ryade sos-
toyanij postroennogo analizatora okazyvaetsya predusmotrennym
dejstvie dlya leksemy error (otlichnoe ot dejstviya error).
Budem govorit', chto v etih sostoyaniyah leksema error dopus-
tima. Rassmotrim poryadok raboty analizatora pri poyavlenii
vo vhodnom potoke oshibochnoj leksemy (t.e. leksemy, vvod
kotoroj v dannom sostoyanii vyzyvaet dejstvie error):
Fiksiruetsya sostoyanie oshibki; vyzyvaetsya funkciya yyer-
ror dlya vydachi soobshcheniya.
Putem obratnogo prosmotra projdennyh sostoyanij,nachinaya
s dannogo, delaetsya popytka najti sostoyanie, v kotorom
dopustima leksema error. Otsutstvie takogo sostoyaniya
govorit o nevozmozhnosti vosstanovleniya, i razbor prek-
rashchaetsya.
Osushchestvlyaetsya vozvrat v najdennoe sostoyanie (krome
sluchaya, kogda im yavlyaetsya neposredstvenno to sostoyanie,
v kotorom vstretilas' oshibka)
Vypolnyaetsya dejstvie, zadannoe v etom sostoyanii dlya
leksemy error. Ocherednoj vhodnoj leksemoj stanovitsya
leksema, vyzvavshaya oshibku.
Razbor prodolzhaetsya, no analizator ostaetsya v sostoyanii
oshibki do teh por, poka ne budut uspeshno prochitany i
obrabotany tri podryad idushchie leksemy. Pri nahozhdenii
analizatora v sostoyanii oshibki otlichie v obrabotke oshi-
bochnoj leksemy zaklyuchaetsya v tom, chto soobshcheniya ob
oshibke ne vydaetsya, a sama leksema ignoriruetsya.
- 30 -
Posle obrabotki treh dopustimyh leksem schitaetsya, chto
vosstanovlenie proizoshlo, i analizator vyhodit iz sos-
toyaniya oshibki.
Itak, grammaticheskij analizator, vstretiv oshibku, pyta-
etsya najti blizhajshuyu tochku vo vhodnom potoke, gde razreshena
leksema error. Pri etom snachala delaetsya popytka vozvrata v
ramkah pravila, po kotoromu shel razbor v moment poyavleniya
oshibochnoJ leksemy, zatem poisk rasprostranyaetsya na pravila
vse bolee vysokogo urovnya. V primere, privedennom v nachale
razdela, vvod nedopustimoj leksemy posle togo, kak prochitana
stroka b c d1 d2 vyzovet vozvrat k sostoyaniyu, harakterizuyu-
shchemusya konfiguraciyami:
a: b c_d;
a: b c_error;
i prodolzhenie razbora po pravilu (2).
CHasto pravila, uchityvayushchie vozmozhnost' oshibki, zadayutsya
na urovne osnovnyh strukturnyh edinic vhodnogo teksta. Nap-
rimer, dlya propuska v tekste oshibochnyh operatorov mozhet byt'
ispol'zovano pravilo
operator: error;
Pri etom vosstanovlenie iz sostoyaniya oshibki proizojdet posle
nahozhdeniya treh leksem, kotorye mogut sledovat' posle opera-
tora, naprimer, nachinat' novyj operator. Esli tochno raspoz-
nat' nachalo operatora nevozmozhno, to oshibochnoe sostoyanie
mozhet byt' podavleno prezhdevremenno, a obrabotka novogo ope-
ratora nachata s serediny oshibochnogo, chto, veroyatno, privedet
k povtornomu soobshcheniyu ob oshibke (na samom dele ne sushchestvu-
yushchej). Uchityvaya eto, bolee nadezhnogo rezul'tata sleduet ozhi-
dat' ot pravil vida:
operator: error ';'
Zdes' vosstanovlenie proizojdet tol'ko posle nahozhdeniya ";"
i dvuh nachal'nyh leksem sleduyushchego operatora; vse leksemy
posle najdennoj oshibochnoj do ";" budut otbrosheny.
S pravilami, vklyuchayushchimi leksemu error, mogut byt' svya-
zany dejstviya. S ih pomoshch'yu pol'zovatel' mozhet samostoya-
tel'no obrabotat' oshibochnuyu situaciyu. Krome obychnyh operato-
rov, zdes' mozhno ispol'zovat' special'nye operatory yyerror
i yyclearin, kotorye yacc na makrourovne rasshiryaet v nuzhnye
posledovatel'nosti. Operator yyerror annuliruet sostoyanie
oshibki. Takim obrazom, mozhno otmenit' dejstvie principa
"treh leksem". |to pomogaet predotvratit' maskirovanie novyh
oshibok v sluchayah, kogda konec oshibochnoj konstrukcii raspoz-
naetsya samim pol'zovatelem ili odnoznachno opredelyaetsya v
pravile po men'shemu chislu leksem.
- 31 -
Operator yyclearin stiraet hranimuyu analizatorom pos-
lednyuyu vhodnuyu leksemu, esli poisk nuzhnoj tochki dlya vozob-
novleniya vvoda obespechivaetsya v zadannom pol'zovatelem
dejstvii.
Privedem obshchuyu formu pravila s vosstanovitel'nym dejst-
viem
operator : error {resynch();
yyclearin;
yyerror;}
Predpolagaetsya, chto pol'zovatel'skaya procedura resynch()
prosmatrivaet vhodnoj potok do nachala ocherednogo operatora.
Vyzvavshaya oshibku leksema, hranimaya analizatorom v kachestve
vhodnoj leksemy, stiraetsya, posle etogo gasitsya sostoyanie
oshibki.
Pri postroenii analizatorov, rabotayushchih v interaktivnom
rezhime, dlya obrabotki oshibok rekomenduyutsya pravila vida:
vhodnaya_stroka : error '\n' {yyerrok;
printf("Povtorite poslednyuyu stroku \n");}
vhodnaya_stroka {$$=$4;}
V dejstvii, predusmotrennom posle vvoda oshibochnoj stroki,
pol'zovatelyu delaetsya podskazka, a sostoyanie oshibki gasitsya.
Znacheniem neterminala posle svertki zdes' stanovitsya znache-
nie povtorno vvedennoj stroki.
11. Diagnostika oshibok
yacc vydaet ryad soobshchenij ob oshibkah v sluchae nevozmozh-
nosti postroeniya grammaticheskogo analizatora. V tekste soob-
shcheniya, predvaryaemom zagolovkom "oshibka:", soderzhitsya ukaza-
nie prichiny oshibki i nomer prosmatrivaemoj v moment ee poyav-
leniya stroki specifikacionnogo fajla. Perechislim osnovnye
tipy fiksiruemyh yacc oshibok:
neverno zadannye flagi komandnoj stroki;
nevozmozhnost' otkrytiya vhodnogo ili vremennyh fajlov;
otsutstvie fajla /usr/lib/yaccpar s tekstom procedury
yyparse;
nevernaya struktura specifikacionnogo fajla;
oshibki v zadanii direktiv;
sintaksicheskie oshibki v opisanii grammaticheskih pravil,
nezavershennost' kommentariev, strok simvolov i dejst-
vij;
- 32 -
nekorrektnoe ispol'zovanie psevdoperemennyh;
neopredelennye neterminal'nye simvoly;
narushenie kolichestvennyh ogranichenij (po chislu termi-
nal'nyh ili neterminal'nyh simvolov, grammaticheskih
pravil, sostoyanij i proch.).
- 33 -
Prilozhenie 1
Nizhe priveden polnyj vhodnoj fajl dlya yacc, realizuyushchij
nebol'shoj nastol'nyj kal'kulyator; kal'kulyator imeet 26
registrov, pomechennyh bukvami ot a do z i razreshaet ispol'-
zovat' arifmeticheskie vyrazheniya, soderzhashchie operacii +, -,
*, /, % (ostatok ot deleniya), & (pobitovoe i), | (pobitovoe
ili) i prisvaivanie. Kak i v Si, celye chisla, nachinayushchiesya s
0, schitayutsya vos'merichnymi, vse ostal'nye - desyatichnymi.
V primere demonstriruyutsya sposoby ispol'zovaniya priori-
tetov dlya razresheniya konfliktov, a takzhe prostye operacii po
vosstanovleniyu iz sostoyaniya oshibki. Kal'kulyator rabotaet v
interaktivnom rezhime s postrochnym formirovaniem vyhoda.
%token DIGIT LETTER /* imena leksem */
%left '|' /* zadanie prioritetov */
%left '&' /* operacij */
%left '+' '-'
%left '*' '/' '%'
%left UMINUS /* ustanovka prioriteta
operacii unarnyj minus */
%{ /* opisaniya, ispol'zuemye */
int base, regs[26]; /* v dejstviyah */
%}
%% /* nachalo sekcii pravil */
list:
| list stat '\n'
| list stat error '\n' {yyerrok; }
stat:
expr {printf("%d\n",$1);}
| LETTER '=' expr {regs[$1]=$3; }
expr:
'(' expr ')' { $$=$2; }
| expr '+' expr { $$=$1+$3; }
| expr '-' expr { $$=$1-$3; }
| expr '*' expr { $$=$1*$3; }
| expr '/' expr { $$=$1/$3; }
| expr '%' expr { $$=$1%$3; }
| expr '&' expr { $$=$1&$3; }
| expr '|' expr { $$=$1|$3; }
| '-' expr %prec UMINUS { $$= -$2; }
| LETTER { $$=regs[$1]; }
| number;
number:
DIGIT { $$=$1; base=10;
if($1==0) base=8; }
- 34 -
| number DIGIT {$$=base*$1+$2; }
%% /* nachalo sekcii programm */
/*
* Programma leksicheskogo analiza
* dlya strochnyh latinskih bukv
* vozvrashchaet LETTER,
* znachenie yylval ot 0 do 25;
* dlya cifr - DIGIT,
* znachenie yylval ot 0 do 9;
* ostal'nye simvoly vozvrashchayutsya
* neposredstvenno
*/
yylex()
{
int c;
while( (c=getchar()) == ' ' );
if( c>='a' && c<='z' ) {
yylval = c - 'a';
return(LETTER);
}
if( c>='0' && c<='9' ) {
yylval = c - '0';
return(DIGIT);
}
return(c);
}
- 35 -
Prilozhenie 2
Analiz i preobrazovanie v matrichnuyu formu vhodnyh dan-
nyh dlya zadachi linejnogo programmirovaniya.
Vhodnaya informaciya iz obychnoj algebraicheskoj formy:
c1X1+c2X2+...+cnXn -> min(max)
a11x1+a12X2+...+a1nXn=b1
am1X1+am2X2+...+amnXn=bm
preobrazuetsya v matrichnuyu:
C: c1 c2 ... cn
A: a11 a12 ... a1n
...
am1 am2 ... amn
B: b1 b2 ... bm
Odnovremenno izmenyayutsya znaki koefficientov pri neizvestnyh
v ogranicheniyah s otricatel'nym svobodnym chlenom, a takzhe
znaki koefficientov linejnogo funkcionala v sluchae ego mak-
simizacii. S illyustrativnoj cel'yu dopuskayutsya nekotorye
varianty sintaksicheskoj zapisi. Predusmotrena vozmozhnost'
povtornogo zadaniya oshibochnyh strok.
%token chislo Xi optim
%%
zlp:funkcional '\n' sistema_ogranichenij
{final();}
| sistema_ogranichenij funkcional '\n'
{ final();}
funkcional: linejnaya_funkciya {stf();}
/* Po umolchaniyu - minimizaciya */
| optim '(' linejnaya_funkciya ')'
{if($1) conv(); stf();}
/* V sluchae maksimizacii vypolnit' conv() */
| linejnaya_funkciya '-''>' optim
{if($4) conv();stf();}
linejnaya_funkciya: elem1
| linejnaya_funkciya elem ;
elem: znak chislo Xi {stc($1*$2,$3); }
| znak Xi '*' chislo { stc($1*$4,$2);}
| znak Xi { stc($1,$2);}
/* Formy zapisi koefficientov */
elem1: elem
| chislo Xi { stc($1,$2);}
| Xi '*' chislo { stc($3,$1);}
- 36 -
| Xi { stc(1,$1); }
znak: '+' {$$=1; }
| '-' {$$= -1;}
sistema_ogranichenij: ogranichenie '\n'
| sistema_ogranichenij ogranichenie '\n'
| sistema_ogranichenij error '\n'
{aclear();yyerrok;
printf("povtorite poslednyuyu stroku\n");}
/* V sluchae oshibki: stiranie inf. o stroke,
vosstanovlenie i vydacha podskazki */
ogranichenie: linejnaya_funkciya '=' chislo
{ stcb($3);}
| linejnaya_funkciya '=' znak chislo
{ if($3<0) conv(); stcb($4);}
/* Esli bi<0, vypolnit' conv() */
%%
#include "stdio.h"
#define MAXM 100 /* predel'noe chislo */
#define MAXN 100 /* ogranichenij i perem.*/
int c[MAXN],b[MAXM],a[MAXM+1][MAXN],
/* Leksicheskij analizator vozvrashchaet:
* dlya celyh chisel - chislo,
* yylval ravno znach. chisla;
* dlya ident.vida xi, i=1,2,...XI*
* yylval ravno ego poryadk. nomeru;
* dlya max/min - optim,
* yylval ravno sootvetstvenno 1 ili 0
*/
yylex() {
char c,i;
while((c=getc(stdin))==' ');
switch(c) {
case'0':
case'1':
case'2':
case'3':
case'4':
case'5':
case'6':
case'7':
case'8':
case'9': yylval=c-'0';
while((c=getc(stdin))<='9'&&c>='0')
yylval=yylval*10+c-'0';
ungetc(c,stdin); return(chislo);
- 37 -
case'm': if((c=getc(stdin))=='i') yylval=0;
else if(c=='a') yylval=1;
else return('m');
while((c=getc(stdin))<='z'&&c>='a');
ungetc(c,stdin); return(optim);
case'X':
case'x': if((c=getc(stdin))<'0' || c>'9')
return('x');
yylval=0;
while(c<='9'&&c>='0')
{yylval=yylval*10+c-'0';c=getc(stdin);}
ungetc(c,stdin);
for(i=0;i<nx;i++)
if(x[i]==yylval){yylval=i;return(Xi);}
x[nx]=yylval; yylval=nx++;return(Xi);
}
return(c);
}
/* Pechat' usloviya zadachi v matrichnoj forme */
final() {
char i,j;
printf("c:\n");
for(i=0;i<nx;i++) printf("%8d",c[i]);
printf("\na:\n");
for(i=0;i<neqs;i++) {
for(j=0;j<nx;j++) printf("%8d",a[i][j]);
printf("\n"); }
printf("b:\n");
for(i=0;i<neqs;i++) printf("%8d",b[i]);
}
/* Izmenenie znakov koefficientov */
conv() {
char i;
for(i=0;i<nx;i++) a[neqs][i]*=(-1);
}
/* Zapominanie koefficientov funkcionala */
stf() {
char i;
for(i=0;i<nx;i++)
{ c[i]=a[neqs][i]; a[neqs][i]=0; }
}
/* Zapominanie ocherednogo koefficienta */
stc(nmb,adr) {
a[neqs][adr]=nmb; }
/* Zapominanie svobodnogo chlena */
stcb(nmb) {
b[neqs++]=nmb; }
- 38 -
/* Stiranie oshibochnoj stroki*/
aclear(){
char i;
for(i=0;i<nx;i++)
a[neqs][i]=0;
}
- 39 -
Prilozhenie 3
Formal'noe opisanie struktury specifikacionnogo fajla.
fajl_specifikacij:
sekciya_deklaracij '%''%'
'\n' sekciya_pravil '%''%'
'\n' sekciya_programm
| sekciya_deklaracij '%''%'
'\n' sekciya_pravil ;
sekciya_deklaracij:
| sekciya_deklaracij dir_ili_opisanie
'\n' ;
dir_ili_opisanie:
'%''{''\n'VNESHNIE_OPISANIYA
'\n''%''}'
| '%''s''t''a''r''t' IDENTIFIKATOR
| '%''t''o''k''e''n'spisok_im_leksem
| associativnost' spisok_leksem ;
associativnost':
'%''l''e''f''t'
| '%'''r''i''g''h''t'
| '%''n''o''n''a''s''s''o''c' ;
spisok_im_leksem:
| dekl_imeni_leksemy
| spisok_im_leksem
dekl_imeni_leksemy ;
spisok_leksem:
dekl_leksemy
| spisok_leksem dekl_leksemy ;
dekl_imeni_leksemy:
IDENTIFIKATOR
| IDENTIFIKATOR CELOE_BEZ_ZNAKA;
dekl_leksemy:
dekl_leksemy
| dekl_literala;
dekl_literala:
LITERAL
| LITERAL CELOE_BEZ_ZNAKA;
sekciya_pravil:
nabor_pravil
| '%''{''\n'SI_OPERATORY'\n''%''}'
'\n' nabor_pravil '\n' ;
nabor_pravil:
pravilo
| nabor_pravil ';' pravilo ;
pravilo:
levaya_chast' ':' al'ternativa
| pravilo '|' al'ternativa ;
levaya_chast': IDENTIFIKATOR ;
al'ternativa:
- 40 -
pravaya_chast'
| pravaya_chast' izm_prior
| pravaya_chast' izm_prior dejstvie
| pravaya_chast' dejstvie ;
pravaya_chast':
| pravaya_chast' lit_ili_ident
| pravaya_chast' dejstvie lit_ili_ident;
izm_prior:
sekciya_programm:
PROGRAMMNYE_KOMPONENTY ;
Pri opisanii struktury specifikacionnogo fajla ne ras-
shifrovyvalis' nekotorye ishodnye konstrukcii, sovpadayushchie s
analogichnymi konstrukciyami Si: identifikator, literal, celoe
bez znaka. Ne opisany takzhe i bolee slozhnye konstrukcii,
yavlyayushchiesya fragmentami Si-programm, perenosimymi v tekst
analizatora (vneshnie opisaniya, Si-operatory). Pod rasshiren-
nymi Si-operatorami ponimayutsya operatory s vozmozhnym ispol'-
zovaniem psevdoperemennyh. PROGRAMMNYE_KOMPONENTY vklyuchayut
operatory preprocessora, opisaniya vneshnih peremennyh i funk-
cij (vozmozhnyj sostav ih privoditsya v razdele 4.3).
- 41 -
SODERZHANIE
. Annotaciya ......................................... 2
1. Principy raboty yacc .............................. 3
2. Vhodnye i vyhodnye fajly, struktura grammaticheskogo
analizatora ....................................... 4
3. Procedura postroeniya grammaticheskogo analizatora .. 5
4. Zadanie vhodnoj informacii yacc ................... 6
4.1. Struktura specifikacionnogo fajla ............... 6
4.2. Sekciya pravil ................................... 7
4.3. Sekciya deklaracij ............................... 12
5. Deklaraciya imen leksem ............................ 13
6. Deklaraciya prioritetov i associativnosti leksem ... 13
7. Deklaraciya imeni nachal'nogo simvola ............... 15
7.1. Sekciya programm ................................. 15
7.2. Dejstviya s ispol'zovaniem psevdoperemennyh ...... 17
8. Konflikty grammaticheskogo razbora ................. 20
9. Struktura informacionnogo vhodnogo fajla
y.output .......................................... 27
10. Obrabotka oshibok pri grammaticheskom razbore ....... 29
11. Diagnostika oshibok ................................ 32
Prilozhenie 1 ...................................... 34
Prilozhenie 2 ...................................... 36
Prilozhenie 3 ...................................... 40
- 42 -
Last-modified: Mon, 29 Jun 1998 14:15:22 GMT