emy "-" 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®em
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],
neqs,nx,x[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 ra