ex & bison

Zorica Suvajdin Raki Predrag Raki septembar 2013

Sadraj
Predgovor 1 Uvod
1.1 1.2 Istorijat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Leksika analiza i sintaksna analiza 1.2.1 1.2.2 Skeniranje i regularni izrazi Parsiranje i gramatike 1.2.2.1

iv 1
1 2 3 3 4

. . . . . . . . . . . . . . . . . .

BNF gramatike . . . . . . . . . . . . . . . . .

Flex
2.1 Format 2.1.1 2.1.2

ex

specikacije

. . . . . . . . . . . . . . . . . . . . .

8 8 9 10 10 11 11 11 13 14 16

Denicije

. . . . . . . . . . . . . . . . . . . . . . . . .

Pravila . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2.1

ex

regularni izrazi

. . . . . . . . . . . . . .

2.1.3 2.1.4 2.2

Korisniki kod

. . . . . . . . . . . . . . . . . . . . . .

Komentari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ex

skeneri

2.2.1 2.2.2 2.2.3 2.2.4

Bez ijednog pravila . . . . . . . . . . . . . . . . . . . . Obrasci Akcije . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Upotreba skenera sa parserom . . . . . . . . . . . . . . i

2.3

Primeri 2.3.1 2.3.2 2.3.3 2.3.4 2.3.5 2.3.6 2.3.7

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19 19 20 21 22 24 25 26 27

Broj rei, karaktera i redova u tekstu . . . . . . . . . . Ispravan kraj reenice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Izostavljanje komentara iz programa

Pretvaranje binarnih u dekadne brojeve

Interpreter jednostavnih komandi . . . . . . . . . . . . Izmena formata datuma . . . . . . . . . . . . . . . . . Skeniranje teksta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.4

Vebe

Bison
3.1 LR parseri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 3.2 Format 3.2.1 3.2.2 3.2.3 3.3 Generatori LR parsera . . . . . . . . . . . . . . . . . .

29
29 30 31 31 31 33 33 37 38 40 41 41 43 45 45 47 50 52

bison

specikacije

. . . . . . . . . . . . . . . . . . . .

Denicije

. . . . . . . . . . . . . . . . . . . . . . . . .

Pravila . . . . . . . . . . . . . . . . . . . . . . . . . . . Korisniki kod . . . . . . . . . . . . . . . . . . . . . .

Parsiranje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 3.3.2 Akcije . . . . . . . . . . . . . . . . . . . . . . . . . . . parsiranje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Shift-reduce

3.4 3.5

Leva i desna rekurzija Primeri 3.5.1 3.5.2

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Broj rei i reenica u ulaznom tekstu . . . . . . . . . . Rei iz ulaznog teksta 3.5.2.1 3.5.2.2 . . . . . . . . . . . . . . . . . . . . .

Ispravan redosled rei iz ulaznog teksta

Tekst u zagradama . . . . . . . . . . . . . . .

3.5.3 3.5.4 3.6 Vebe

Izmena formata datuma . . . . . . . . . . . . . . . . . Strukturirana datoteka sa meteorolokim podacima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii

4 Konikti i njihovo razreavanje

4.1 4.2 Primer konikta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Razreenje konikta

55
55 56

5 Rukovanje grekama i oporavak

5.1 5.2 Rukovanje grekama . . . . . . . . . . . . . . . . . . . . . . . Oporavak od greke . . . . . . . . . . . . . . . . . . . . . . . .

59
59 60

Spisak primera Spisak slika Indeks A Renik

61 62 63 67

iii

iv

Predgovor
Ova zbirka zadataka je napisana za potrebe kursa Programski prevodioci na Fakultetu tehnikih nauka, Univerziteta u Novom Sadu. Namera zbirke je da prenese konkretne tehnike i alate koji se koriste za implementaciju kompajlera.

Flex

bison

su alati namenjeni za pisanje kompajlera i interpretera, iako

su korisni i za mnoge aplikacije koje e zanimati i one koji se ne bave kompajlerima. Svaka aplikacija koja trai obrasce ( ima ulazni ili komandni jezik je dobar kandidat za tavno odravanje programa.

pattern ) u svom ulazu ili ex i bison. Osim toga,

oni omoguavaju brzu izradu prototipa aplikacije, lake modikacije i jednos-

Kompletni primeri su numerisani, sa naznaenim imenom datoteke u kojoj se nalaze.

Neproporcionalnim fontom, radi bolje preglednosti, navedeni su

primeri, pokretanja programa i gramatika mC jezika. Svako poglavlje, na kraju, sadri vebe, koje nude dodatni rad za one koji to ele.

Pregled
Uvod, prua istorijski pregled alata lex i yacc, kao i njihovih potomaka ex i bison, i daje pregled kako i u kojim situacijama se koriste ex i bison.
Poglavlje 1, Poglavlje2, Poglavlje3, Poglavlje 4,

Flex, detaljno opisuje nain upotrebe ex-a kroz nekoliko primera. Bison, daje potpune primere koji koriste i ex i bison.

Konikti i njihovo razreavanje, objanjava dvosmislenosti i konikte u bison-u, i probleme u gramatici koji onemoguuju bison da napravi
v

parser. Predstavljene su metode za lociranje i razreavanje konikata.

Poglavlje 5,

Rukovanje grekama i oporavak,

opisuje tehnike za lociranje,

prepoznavanje i prijavljivanje greaka u ulaznoj datoteci. Renik sadri tehnike pojmove iz teorije kompajlera. Pretpostavlja se da je italac familijaran sa programskim jezikom C, jer su svi primeri na C-u,

ex-u i bison-u.

Kako preuzeti ex i bison

Flex i bison
su savremene zamene za klasine alate

lex i yacc.

GNU Project od strane Free Software Foundation zajednice distribuira i on je ukljuen u sve uobiajene distribucije Linux (poslednju) verziju, moete je nai na

web

bison, -a, ali ako elite aktuelnu

stranici:

http://www.gnu.org/software/bison/

ator ), u uobiajenim distribucijama Linux-a, ali ako elite poslednju verziju, moete je nai na web stranici:
http://flex.sourceforge.net/

BSD i GNU Project takoe distribuiraju

ex (Fast Lexical Analyzer Gener-

Zahvalnica
Autori ele da se zahvale studentima koji su imali u rukama

draft

verziju

zbirke zadataka na kursu Programski prevodioci i koji su nali brojne slovne i druge greke u prvim verzijama materijala, i uinili ovaj materijal itljivijim i zanimljivijim. Autori

vi

Poglavlje 1

Uvod
Flex
ulaz. i

bison

su alati za pravljenje programa koji procesiraju strukturiran

Izvorno, to su alati za pravljenje kompajlera, ali su se dokazali kao

veoma korisni i u mnogim drugim oblastima. Evo nekoliko primera za ta se mogu koristiti

ex i bison

(ili njihovi preci

lex i yacc ), da razviju [5]:

desktop

kalkulator

domenske jezike za odreenu aplikaciju alate za preprocesiranje raznih dokumenata programske kompajlere, npr. C kompajler sam

ex

U ovom poglavlju emo se upoznati sa istorijatom ovih alata i sa osnovnim teorijskim postavkama koje stoje iza ovih alata.

1.1 Istorijat
Bison
je potomak programa

yacc

[3], generatora parsera.

Napravio ga je Kao to - jo jedan

Stiven C. Johnson iz Bell Labs, u periodu izmeu 1975 i 1978. samo ime

yacc

kae (skraeno od

yet another compiler compiler

kompajler kompajlera), u to vreme su mnogi ljudi pisali generatore parsera. Johnson je svoj alat zasnovao na vrstoj teorijskoj osnovi i na radu D. E. Knuth-a, koja je proizvela izuzetno pouzdane parsere. Ova pouzdanost je poveala

bison-ovu

popularnost meu korisnicima UNIX sistema, iako je

restriktivna licenca, pod kojom je Unix distribuiran u to vreme, ograniavala njegovo korienje izvan univerziteta i Bell laboratorija. 1

POGLAVLJE 1.

UVOD

yacc koristei donekle naprednije algoritme i razvio Berkli yacc (Byacc, Berkeley yacc )[2]. Poto je njegova verzija bila bra od Bell-ovog yacc -a, a i deljen je pod eksibilnijom Berkli licencom, brzo je postao najpopularnija verzija yacc -a. Richard Stalman, iz FSF (Free
Berkliju, je reimplementirao Software Foundation), je adaptirao Corbett-ov rad za korienje u GNU projektu. Alat je proiren mnogobrojnim novim karakteristikama i evoluirao je u trenutnu verziju pod GNU javnom licencom (

Oko 1990, Robert Corbett, postdiplomac na Univerzitetu u Kaliforniji, na

bison -a. Bison je sada projekat FSF-a i distribuira se GNU Public Licence ) [7]. 1975 godine, Majk Lesk i pripravnik Eric Schmidt su napisali lex, generator
leksikih analizatora [4].

yacc -a. Lex

Videli su ga i kao samostalni alat i kao pratilac

je takoe postao veoma popularan, uprkos tome to je relativno

spor i bagovit. Oko 1987, Vern Paxson iz Lawrence Berkeley Lab je uzeo verziju na C i nazvao ga

lex -a

fast lexical analyzer generator ) [6]. Poto lex -a i dostupan pod Berkli licencom, potpuno je zamenio originalni lex. Flex je sada SourceForge projekat,
(skraeno od je bio bri i pouzdaniji od AT&T verzije jo uvek pod Berkli licencom.

pisanog na proirenom Fortran jeziku (popularnom u to vreme), preveo ga

ex

1.2 Leksika analiza i sintaksna analiza

Najraniji kompajleri, tokom 1950-tih godina, koristili su potpuno tehnike za analizu sintakse izvornog koda. analiza postala ve dobro istraeno polje. Jedan od kljunih uvida bio je da se posao prevoenja podeli na dva dela: leksika analiza (koja se naziva jo i skeniranje) i sintaksna analiza (ili parsiranje). Grubo govorei, skeniranje deli ulaz na atomske delove, koji se zovu jo i tokeni, a parsiranje analizira kako su ti tokeni meusobno povezani. primer, sledei deo C koda: Na

ad hoc

Tokom 1960-ih, ovo polje je

dobilo mnogo panje akademske zajednice, pa je ranih 1970-ih sintaksna

a = b + c;
skener deli u tokene:

a, znak jednakosti, b, znak plus, c i znak taka-zarez. Zatim parser utvruje da je b + c izraz, a da se izraz dodeljuje promenljivoj a.

1.2.

LEKSIKA ANALIZA I SINTAKSNA ANALIZA

1.2.1 Skeniranje i regularni izrazi

Skeneri rade tako to trae ablone karaktera u ulazu. Na primer, u C programu, celobrojna konstanta je niz od jedne ili vie cifara, ime promenljive je slovo iza kog sledi nula ili vie slova ili cifara, dok su razni operatori pojedinani karakter ili parovi karaktera. Ovi abloni se mogu na jednostavan nain opisati regularnim izrazima ( skraeno zovu

regex ex

ili

regexp.

regular expressions ),

koji se esto

Flex

program (

specikacija) se u osnovi sastoji od liste regularnih izraza.

Uz svaki regualrni izraz stoji uputstvo o tome ta skener treba da radi kada ulazni string odgovara tom regularnom izrazu. Ova uputstva se zovu akcije. Skener koji se izgenerie iz varajuu akciju. formu

ex-a

ita ulazni tekst s leva na desno i pokuava

da prepozna neki od regularnih izraza, a u sluaju prepoznavanja vri odgo-

1 koja omoguava da se istovremeno proverava slaganje ulaza sa svim

Flex

sve regularne izraze prevodi u ekasnu unutranju jednako brz za 100 obrazaca kao i za jedan.

obrascima. Zato je

ex

1.2.2 Parsiranje i gramatike

Zadatak parsera je da shvati povezanost izmeu ulaznih tokena [5, 1]. Uobiajen nain da se takva veza prikae je stablo parsiranja ( primer, uz uobiajena airtmetika pravila, aritmetiki izraz

+ 5

1 * 2 + 3 * 4

parse tree ).

Na

bi imao stablo parsiranja kao na slici 1.1.

Slika 1.1: Stablo parisiranja za izraz

1*2+3*4+5
nite automation,

Unutranja forma je deterministiki konani automat (deterministic

DFA)

POGLAVLJE 1.

UVOD

Mnoenje ima vei prioritet od sabiranja, pa su prva dva izraza 1 * 2 i 3 * 4 listovi tog stabla. Onda se ta dva izraza sabiraju, pa se na tu sumu dodaje 5. Svaka grana stabla pokazuje odnos izmeu tokena ili podstabla ispod nje. Struktura ovog konkretnog stabla je vrlo jednostavna.

Bison

pravi

stablo parsiranja dok parsira ulazni tekst. Ovo stablo je samo implicitno, u sekvenci operacija koje parser vri, ali sam korisnik moe eksplicitno kreirati stablo, kao strukturu podataka u memoriji.

1.2.2.1 BNF gramatike

Da bi se napisao parser, potrebno je na neki nain opisati pravila po kojima e parser niz tokena pretvoriti u stablo parsiranja. Uobiajena vrsta jezika koju koriste parseri je kontekstno nezavisna gramatika (

grammar,

context-free
Simbole

CFG). Gramatika je skup pravila za pisanje programa na nekom

jeziku. Gramatika opisuje sintaksu jezika, ali ne i semantiku. Gramatika se sastoji od pravila, simbola (

terminals )

i pojmova (

nonterminals ).

prepoznaje skener, dok pojmove i ispravnost redosleda pojmova prepoznaje parser. Standardna forma u kojoj se piu CFG gramatike je Bakus-Naurova forma (

Backus-Naur Form, BNF). U nastavku je dat BNF zapis aritmetikih

exp ::= factor | exp + factor

izraza koji su koriteni u primeru, na slici 1.1:

factor ::= NUMBER | factor * NUMBER

Svaka linija predstavlja pravilo koja opisuje kako se moe napraviti jedna grana stabla parsiranja. strane znaka U BNF formi,

::=

se ita kao je ili postaje,

a uspravna crta | se ita kao ili.

Ime sa leve strane pravila (sa leve

::=) je pojam.

Po konvenciji, svi tokeni se smatraju simbolima.

BNF pravilo moe biti rekurzivno, to znai da se ime sa leve strane pravila denie pomou samog sebe (pa se isto ime pojavljuje i na desnoj strani pravila). U primeru su oba pravila, i

exp i factor,

denisana rekurzivno.

Flex i bison nasuprot runo pisanim skenerima i

parserima
Tehnika prepoznavanja obrazaca (ablona, paterna) koju koristi brza i obino je iste brzine kao runo napisan skener.

ex je veoma

Za kompleksnije

1.2.

LEKSIKA ANALIZA I SINTAKSNA ANALIZA

skenere, sa puno obrazaca,

ex

skener je verovatno bri, jer runo napisani

Flex

skener verovarno ima puno poreenja karaktera, dok

ex

uvek radi jedno.

verzija skenera je sigurno mnogo kraa nego ekvivalentni C skener, to

olakava pronalaenje greaka. Uopteno, ako se pravila za podelu ulaznog teksta u tokene moe opisati regularnim izrazima, Takoe,

ex

je pravi izbor.

bison

parser je mnogo krai i lake se otkrivaju greke nego u ekvi-

valentnom runo pisanom parseru, naroito zato to nedvosmilenosti gramatike.

bison

radi verikaciju

POGLAVLJE 1.

UVOD

Poglavlje 2

Flex
Leksiki analizator (skener) je program namenjen za leksiku analizu (skeniranje) teksta. Skener radi tako to ita tekst, karakter po karakter, i pokuava da prepozna neku od zadatih rei. Kada prepozna re (sekvencu karaktera) izvri zadatu akciju. Skener se moe napraviti (isprogramirati) runo ili korienjem alata za generisanje skenera. era je program

ex . Flex

Jedan od esto korienih alata za generisanje skengenerie skener na osnovu pravila zadatih u

ex

specikaciji. Specikaciju kreira korisnik u posebnoj datoteci koja po konvenciji ima ekstenziju

.l.

Ova datoteka sadri pravila koja opisuju rei

koje skener treba da prepozna. Pravila se zadaju u obliku regularnih izraza. Svakom regularnom izrazu mogue je pridruiti akciju (u obliku

C koda) koja

e se izvriti kada skener prepozna dati regularni izraz. Uobiajena akcija je vraanje oznake simbola, odnosno tokena za taj simbol. Token je numerika oznaka grupe (vrste) simbola. Na primer: token broj (i

2 i 359),

dok token

IF

NUMBER

oznaava bilo koji

oznaava jedino kljunu re

if.

.l

datoteka se prosleuje

alnoj funkciji izrazima u raju) u

yylex() u datoteci lex.yy.c. Akcije, pridruene regularnim .l datoteci, su delovi C koda koji se direktno prenose (kopilex.yy.c. Ovako generisan C kod moe da se prevede i C i C++ yylex(), lanici klase yyFlexLexer ili lanici

ex -u,

koji generie skener na jeziku C, u glob-

kompajlerom (tj. moe da se ukljui u C ili u C++ program). Ako se za generisanje skenera, umesto programa biva generisan u C++ funkciji

ex

pozove program

ex++ 1 , skener

1
`+`.

U pitanju je isti program, samo se drugaije ponaa kada mu se ime zavrava znakom

POGLAVLJE 2.

FLEX

klase proizvoljnog imena koja nasleuje klasu

yyFlexLexer.

Ovako gener-

isan skener moe da se ukljui samo u C++ program. Ovakav program predstavlja leksiki analizator koji transformie ulazni tekst u niz tokena (u skladu sa pravilima zadatim u specikaciji). Korienje programa

ex

je prikazano na slici 2.1:

Slika 2.1: Korienje

ex -a

Prilikom izvravanja, skener e traiti pojavu stringa u ulaznom tekstu koji odgovara nekom regularnom izrazu. Ako ga pronae, izvrie akciju (kod) koju je korisnik pridruio tom regularnom izrazu. U suprotnom, podrazumevana akcija za tekst koji ne odgovara ni jednom regularnom izrazu je kopiranje teksta na standardni izlaz.

2.1 Format ex specikacije

Specikacioni oznakom

%%:

ex

datoteka se sastoji od tri dela, meusobno razdvojena

1. denicije 2. pravila i 3. korisniki kod.

2.1.1 Denicije
Prvi deo se obino koristi za ukljuivanje zaglavlja i denicije promenljivih (pri emu ovakav kod mora biti okruen specijalnim zagradama ovom delu se navode jo i regularne denicije, obavezan.

ex

%{ i %}).

makroi, poetni uslovi,

kao i opcije za upravljanje radom generatora. Ovaj deo

ex

specikacije nije

ex

nudi razne opcije za pravljenje skenera. Veina se moe navesti u oliku u prvom delu specikacije, ili kao

%option name

2.1.

FORMAT FLEX SPECIFIKACIJE

--name

u komandnoj liniji prilikom poziva

ex -a.

Da bi se neka opcija iskljuila, pre imena opcije treba dodati string  no, kao na primer:

%option noyywrap --noyywrap

ili

Opcije koje emo koristiti su:

%option noyywrap

( noyywrap) Ovom opcijom korisnik kae

eli da denie funkciju

yywrap().

ex -u

da ne

Ovu funkciju poziva skener U njoj korisnik moe da

kada doe do kraja ulazne datoteke.

opie ponaanje skenera posle itanja datoteke (npr. da nastavi itanje neke druge datoteke). Ako funkcija

yywrap()

nije den-

isana, podrazumeva se da e skener preuzeti i itati samo jednu ulaznu datoteku i da e nakon itanja kraja datoteke vratiti pozivaocu vrednost

0.
Zgodno je znati broj skenirane linije u

%option yylineno (--yylineno)

ulaznoj datoteci kada, na primer, treba prijaviti leksiku greku.

ex

denie promenljivu

ije i automatski je aurira svaki put kada proita karakter mora dodeliti vrednost datoteke.

yylineno koja sadri broj trenutne lin\n.

Skener ne inicijalizuje ovu promenljivu, pa joj zato korisnik sam

1 svaki put kada zapoinje itanje ulazne

2.1.2 Pravila
Drugi deo specikacije sadri niz pravila koja opisuju ponaanje skenera. Na osnovu ovih pravila obliku:

ex

generie kod skenera. Svako pravilo se zadaje u

obrazac

[ akcija ]

Obrasci se zadaju korienjem proirenog skupa regularnih izraza (datog u nastavku), a akcije blokom C (ili C++) koda koji e se izvriti kada skener prepozna obrazac. Obrazac mora da pone u prvoj koloni, a akcija ne mora da postoji. Ako akcija postoji, njena denicija mora da pone u istom redu u kojem je denisan obrazac. Ovaj deo

ex

specikacije je obavezan.

10

POGLAVLJE 2.

FLEX

2.1.2.1

ex regularni izrazi

U tabeli 2.1 su dati operatori koji se koriste za pisanje regularnih izraza u

ex -u.

Da bi karakter koji predstavlja nicima ().

znaenje, ispred njega treba staviti kosu crtu (\) ili ga navesti pod navodTako, na primer, regularni izraz osim

ex metasimbol mogao da ima i svoje prirodno

a\.b
opisuje string

(taka se tretira kao obian karakter), dok regularni izraz

a iza kojeg sledi bilo koji karakter b (taka se tretira kao operator).

newline

a.b opisuje string

a.b

iza kojeg sledi karakter

regularni izraz
x "x" \x x? x* x+ x|y [xy] [x-z] [^x] . ^x x$ (x) x/y {xx} x{m,n} x, x,

znaenje
karakter ak i ako je ak i ako je

opciono

x x

x
operator operator

(0 ili 1 instanca)

0 ili vie instanci 1 ili vie instanci

y ili y karakteri x, y
ili

x x

x x z

ili

bilo koji karakter osim bilo koji karakter osim

x x

x newline

na poetku linije

na kraju linije

x n x

ali ako i samo ako iza njega sledi

pravilo za

xx m

iz prvog dela specikacije do pojava

Tabela 2.1: Regularni izrazi u

ex -u

2.1.3 Korisniki kod

U ovom opcionom delu korisnik moe da denie proizvoljan blok koda (funkcija

main(),

druge funkcije, globalne promenljive, . . . )

koji e biti

bez izmena prekopiran na kraj generisanog skenera. Ovaj deo datoteke omoguava da se ceo program smesti u samo jednu (.l) datoteku. Kompleksni programi se svakako (zbog itljivosti) rasporeuju u

2.2.

FLEX SKENERI

11

vie izvornih datoteka, pa tada ovaj deo, uglavnom, i ne postoji.

2.1.4 Komentari
U

ex -u se koriste komentari iz C programskog jezika:

jednolinijski komentar vielinijski komentar

// /*...*/

Komentari se u

ex -u piu uvueni (indentovani) bar za jedno prazno mesto.

2.2 ex skeneri

U ovom delu su prikazane osnovne karakteristike programa

ex

kroz nekoliko

jednostavnih primera skenera. Primeri su implementirani na jeziku C.

2.2.1 Bez ijednog pravila

Najjednostavnija listingu 2.1: Listing 2.1:

ex

specikacija (ovde nazvana

zero.l)

je prikazana u

zero.l

%%
Ova datoteka sadri samo oznaku

%%.

Skener izgenerisan iz ove specikacije

(koja ne sadri nijedno pravilo) prihvata karaktere sa standardnog ulaza i kopira ih na standardni izlaz (karakter po karakter). Iz ovog jednostavnog primera se vidi da e svi karakteri iz ulaznog teksta, koji ne budu prepoznati (koji se ne uklapaju ni u jedan od zadatih obrazaca), biti ispisani na standardnom izlazu. Skener se generie, kompajlira i pokree naredbama:

$ flex -- noyywrap zero . l $ gcc -o zero lex . yy . c -l l $ ./ zero

12

POGLAVLJE 2.

FLEX

U prvoj liniji pokreemo

ex

koji preuzima specikaciju iz datoteke

i generie skener u datoteci Svi

lex.yy.c.

zero.l

--noyywrap, prosleen ex -u, kae da korisnik ne eli da denie funkciju yywrap().
U drugoj liniji pozivamo

gcc

kompajler i prosleujemo mu

toteku sa skenerom u funkciji Svi

yylex().

lex.yy.c

da-

--o

prosleen

gcc-u

omoguava korisniku da iza svia navede ime pro-

grama koji e biti izgenerisan. Ukoliko se ne upotrebi ovaj svi, kompajler e napraviti izvrnu datoteku sa imenom Uz program funkcija

a.out.
U ovoj biblioteci je denisana

main(),

ex

dolazi i biblioteka

libl.a.

koja jedino poziva skener, odnosno funkciju

yylex():

int main () { while ( yylex () != 0) ; return 0; }

Ako u programu nije denisana funkcija Svi

main() koristi se ona iz biblioteke. -l govori linkeru da pogleda u biblioteku ije ime je navedeno iza svia. Tom prilikom se iz imena biblioteke izostavljaju prva tri slova: `lib` (jer se 2 ona podrazumevaju ) i ekstenzija. Otuda, -l l u pozivu gcc-a. ./zero
se izgenerisani skener pokree u interak-

U treoj liniji naredbom

tivnom reimu, to znai da se ulaz oekuje preko tastature, a da se program zavrava kada se na ulazu pavi kombinacija

^D.

Ukoliko elimo skeneru da prosledimo datoteku (test.txt) na skeniranje, upotrebiemo redirekciju standardnog ulaza:

$ ./ zero < test . txt

A ako pokrenemo skener u interaktivnom reimu, to moe da izgleda ovako:

$ ./ zero tekst tekst se prekopira se prekopira na standardni izlaz na standardni izlaz ^D $

2
Konvencija je da nazivi svih biblioteka poinju slovima `lib`.

2.2.

FLEX SKENERI

13

2.2.2 Obrasci
Obrasci opisuju sekvence (nizove) karaktera koje skener treba da prepozna. Kada je potrebno prepoznati samo jednu sekvencu karaktera (kao na primer kljunu re

if

ili kao u listingu 2.2 re

njam),

tu sekvencu je mogue

eksplicitno zadati. Ako se prethodno prikazan

ex

datoteka

proiri jednim pravilom koje prepoznaje

zero.l preimenuje u njam.l i re njam, dobije se ex datoteka

prikazan na listingu 2.2. Kada se prepozna, ova re e biti ignorisana. Listing 2.2:

njam.l

%% njam
Ako se zatim, ponovo izgenerie, kompajlira i pokrene, program ponaa sliano programu

zero

njam

se

- veinu karaktera koje primi na ulazu on

prosledi na izlaz. Ako se na ulazu pojavi niz karaktera interaktivna sesija programa

njam

oni nee biti

prosleeni na izlaz, ve e nestati (pojee ih skener - otuda `njam`). Jedna

njam

izgleda ovako:

$ ./ njam Ovo prolazi bez izmena . Ovo prolazi bez izmena . njam Cunjam ovuda . Cu ovuda .
Kada je potrebno prepoznati sve sekvence karaktera iz neke klase (kao na primer: broj, kao niz od jedne ili vie cifara), tada se za specikaciju obrasca koriste sloeniji izrazi, iz proirenog skupa regularnih izraza. Sledi primer (listing 2.3) specikacije skenera koji prepoznaje prirodne brojeve. Listing 2.3:

num.l

%% [0 -9]+
Uglaste zagrade opisuju klasu karaktera  bilo koji karakter u rasponu od ASCII karaktera 0 do ASCII karaktera 9 (tj. postojati). Izlaz ovog programa moe da izgleda ovako: bilo koja cifra), a operator + kae da se cifra moe ponavljati jednom ili vie puta (bar jedna mora

14

POGLAVLJE 2.

FLEX

$ ./ num 1 i jedan jesu 2. i jedan jesu . 9 + 11 = 20 + =

2.2.3 Akcije
Akcija je

C (ili C++) kod koji skener izvrava kada prepozna string koji odgo-

varaju obrascu. Na listingu 2.4 je prikazan skener sa samo jednim pravilom koji prepoznaje beline (proizvoljno dugake sekvence praznih mesta i tabova) i zamenjuje ih samo jednim praznim mestom. Listing 2.4:

ws.l

%% [ \ t ]+ { putchar ( ' ') ; }

Obrazac je regularni izraz koji opisuje: ili razmak ili tab jednom ili vie puta. Akcija je poziv C funkcije koja ispisuje jedan karakter - jedno prazno mesto na standardni izlaz. praznim mestom. Upotreba ovog programa: Kako se ova akcija izvrava svaki put kada skener prepozna niz razmaka i/ili tabova, dobija se efekat zamene belina jednim

$ ./ ws Neko pise reci odvojene jednim razmakom a neko Neko pise reci odvojene jednim razmakom a neko ne . ^D $

ne .

Na listingu 2.5 je prikazan skener sa samo jednim pravilom, koji prepoznaje karaktere za novi red (newline) i broji ih. Listing 2.5:

lines.l

%{ %} %%

int lines = 0;

2.2.

FLEX SKENERI

15

\n %%

{ lines ++; }

main () { yylex () ; printf ( " \ nlines : % d .\ n " , lines ) ; }

U prvom delu specikacije je denisana brojaka promenljiva e uvati broj linija i inicalizovana je na vrednost red, pa se dobija efekat brojanja linija. U treem delu je navedena denicija funkcije samo skener, tj. funkciju funkcije

0.

Promenljiva

lines koja lines se

inkrementira unutar akcije, tj. svaki put kada se prepozna karakter za novi

Ako ovom programu prosledimo ulaznu datoteku Listing 2.6:

main()), ve nakon toga jo i ispie broj redova u proitanom tekstu. test.txt, sa sadrajem: test.txt

main, koja sada ne poziva yylex() (kao to to radi biblioteka implementacija

If I can dream it , I can live it .

izlaz e biti:

$ ./ lines < test . txt If I can dream it , I can live it . lines : 2. $

Prethodni primer se moe proiriti pravilom koji prepoznaje rei i ispisuje one rei koje poinju velikim slovom (listing 2.7). Listing 2.7:

words.l

[a - zA - Z ]+ .

{ if ( isupper ( yytext [0]) ) printf ( " % s \ n " , yytext ) ; } { /* do nothing */ }

Obrazac za re opisuje stringove ili malo ili veliko slovo jednom ili vie puta. Svaki put kada se prepozna re, izvrava se akcija koja je vezana za taj obrazac. globalnoj Provera da li je prvo slovo prosleenog stringa veliko se vri rei se nalazi u je tipa pomou funkcije

isupper(). String prepoznate promenljivoj yytext. Ova promenljiva

char*

ex -ovoj

i u svakom

trenutku sadri string poslednjeg prepoznatog obrasca.

16

POGLAVLJE 2.

FLEX

U prethodnim primerima smo videli da se svi neprepoznati karakteri sa ulaza prosleuju na izlaz. Ukoliko ne elimo da se, pored rei sa prvim velikim slovom, ispisuju i ostali (neprepoznati) simboli, potrebno je dodati pravilo koje prepoznaje bilo koji karakter (operator

.)

i nema nikakvu akciju.

Ukoliko se ovakav program pokrene sa ulaznom datotekom prethodnog primera, dobie se izlaz:

test.txt

iz

$ ./ words < test . txt If I I lines : 2. $

2.2.4 Upotreba skenera sa parserom

Skener, kreiran pomou

ex -a,

u kombinaciji sa parserom se ponaa na

sledei nain: kada parser aktivira leksiku analizu, skener poinje sa itanjem preostalog ulaznog teksta, jedan po jedan karakter, dok ne nae najdui niz karaktera koji odgovara nekom obrascu. pridruena prepoznatom obrascu. ukoliko se u njoj izvri naredba vraanje kontrole parseru. Tada, izvrava akciju koja je Akcija moe da vrati kontrolu parseru

return.

Ako do toga ne doe, leksiki

analizator nastavlja da ita ostatak ulaznog teksta, dok akcija ne izazove Ponavljanje traenja stringova dok se kontrola eksplicitno ne vrati parseru, olakava skeneru obradu praznina i komentara. Skener parseru ne prosleuje npr. string prepoznatog simbola, ve token za taj simbol (slika 2.2). Token je numerika oznaka kategorije (vrste) simbola (npr. token

IF

opisuje kljunu re

if,

token

NUM

opisuje brojeve, token

ID

opisuje identikatore odnosno imena).

Slika 2.2: Komunikacija izmeu skenera i parsera Na listingu 2.8 sledi primer prepoznavanja kljune rei

if, prirodnih brojeva

i rei. Tokeni su denisani u enumeraciji u prvom delu Listing 2.8:

ex

specikacije.

return.l

%{

enum { IF = 1 , NUM , WORD };

2.2.

FLEX SKENERI

17

%} %% if [0 -9]+ [a - zA - Z ]+ %% int main () { int tok ; while ( tok = yylex () ) { switch ( tok ) { case IF : printf ( " IF " ) ; break ; case NUM : printf ( " NUM " ) ; break ; case WORD : printf ( " WORD " ) ; break ; } } }
Svaka od akcija vraa odgovarajui token prepoznatog simbola. U praksi, funkciju skenera najee poziva parser, dok u ovom primeru to radi funkcija

{ return IF ; } { return NUM ; } { return WORD ; }

main().

Kada joj skener isporui token, ona ga ispie na ekran.

Primer pokretanja ovog programa:

$ ./ return if 123 abc 5 abc ! IF NUM WORD NUMWORD ! $

if IF, za string 123 vraa NUM, za string abc token WORD). Za string 5abc, vidimo da skener vraa 2 tokena: prvo za string 5 vraa token NUM, a zatim za string abc vraa token WORD. Skener je, krenuvi od karaktera 5, pokuao da pronae najdui string koji se poklapa sa nekim obrascem. Naao je samo jedan obrazac koji zapoinje brojem ([0-9]+). Preuzeo je sledei karakter a, ali je zakljuio da se on ne uklapa u obrazac za broj, pa
Za svaki pojedinani string skener vraa odgovarajui token (za string vraa token ga je vratio nazad na standardni ulaz - odakle ga je i preuzeo (da bi se taj karakter obradio u okviru sledeeg simbola). Skener je uspeo da prepozna

NUM. Dalje nastavlja skeniranje tamo gde je stao i preuzima ponovo karakter a, zatim b i onda c, prepoznaje to kao re i vraa token WORD. Svi neprepoznati karakteri (npr: !) se samo prosleuju na standardni izlaz.
broj koji se sastoji samo od 1 cifre i za njega vraa token Skener parseru, osim tokena, moe da vrati i neku vrednost koja preciznije

18

POGLAVLJE 2.

FLEX

opisuje svojstva tokena. U sluajevima kada skener prepozna jednostavne rei, kao to su kljune rei (npr.

if, while, ...)

parseru je dovoljno proslediti

(vratiti) token te kljune rei. U sluaju kada skener prepozna identikator ili broj, parseru je, osim tokena, potrebno proslediti i konkretan string imena odnosno vrednost konkretnog broja. Ova vrednost se prosleuje preko globalne promenljive a uobiajeno je da se ova promenljiva denie kao unija (union), jer se za razliite simbole vezuje razliita vrednost (drugaijeg tipa). Unija je promenljiva koja moe uvati objekte razliitih tipova i veliina, odnosno to je jedna promenljiva koja moe sadrati vrednost jednog od nekoliko tipova (a programer je duan da vodi rauna o tome koji tip vrednosti se trenutno uva u uniji). Za prethodni primer, potrebno je u prvom delu specikacije, denisati uniju. Listing 2.9:

yylval.

Podrazumevani tip ove promenljive je

int,

union.l

- unija

union { int n; char * s ; } yylval ;

Uz token

if

IF

se ne prosleuje dodatna vrednost simbola, jer se kljuna re

moe napisati na jedan jedini nain.

Uz token

NUM

se prosleuje konkretna vrednost broja (C funkcija

hvata string i konvertuje ga u jer je ono tipa

int.

int).

Ova vrednost se smea u polje

atoi prin unije

Listing 2.10:

union.l

- pravila

if [0 -9]+ [a - zA - Z ]+
Uz token

{ return IF ; } { yylval . n = atoi ( yytext ) ; return NUM ; } { yylval . s = yytext ; return WORD ; }
se prosleuje konkretni string rei, jer se rei mogu razliito

WORD

napisati. Ovaj string se smea u polje Izmena funkcije 2.11). Listing 2.11:

promenljive

yylval.

main() bi bila u tome da ispisuje na ekran sve vrednosti koje

dobije od skenera: tokene i vrednosti koje su prosleene uz token (listing

union.l - main()

case IF : printf ( " IF " ) ; break ; case NUM : printf ( " NUM : % d " , yylval . n ) ; break ; case WORD : printf ( " WORD : % s " , yylval . s ) ; break ;

2.3.

PRIMERI

19

2.3 Primeri
2.3.1 Broj rei, karaktera i redova u tekstu
Napraviti skener koji preuzme sve karaktere sa ulaza i ispie:

  

koliko je bilo rei koliko je bilo karaktera koliko je bilo redova. Listing 2.12:

wclc.l

% option noyywrap %{ int chars = 0; int words = 0; int lines = 0;

%} %%

[a - zA - Z ]+ \n . %%

{ words ++; chars += strlen ( yytext ) ; } { chars ++; lines ++; } { chars ++; }

main () { yylex () ; printf ( " chars : %d , words : %d , lines : % d .\ n " , chars , words , lines ) ; }
Prvi deo specikacije sadri opciju za iskljuivanje funkcije efekat smo u ranijim primerima postizali navoenjem svia komandnoj liniji prilikom poziva

ex -a.

yywrap. Isti --noyywrap u

U prvom delu specikacije se nalaze i denicije 3 promenljive koje e uvati broj karaktera, rei i linija. Prvi obrazac

[a-zA-Z]+

opisuje re. Karakteri u zagradama opisuju jedno

malo ili veliko slovo, a karakter i karaktera. Promenljiva

opisuje jednu ili vie pojava slova. Znai,

ceo obrazac opisuje niz slova, tj. re. Akcija inkrementira broj vienih rei

yytext pokazuje na string iz ulaznog teksta koji je

prepoznat na osnovu tog obrasca. U ovom sluaju, ne zanima nas koji je to string, ve koliko karaktera ima u njemu.

20

POGLAVLJE 2.

FLEX

Drugi obrazac

\n

opisuje karakter za novi red, a pridruena akcija inkre-

mentira broj karaktera i broj redova. Trei obrazac je regularni izraz koji opisuje bilo koji karakter osim karaktera za novi red. Akcija inkrementira broj karaktera.

main

funkcija poziva skener, tj.

funkciju

yylex()

i ispisuje vrednosti 3

brojaa.

Ako skeneru ne damo ulaznu datoteku, on e ulazni tekst itati

sa tastature:

$ flex wclc . l $ gcc lex . yy . c $ ./ a . out Eci peci pec ti si mali zec ^D chars : 28 , words : 7 , lines : 2. $
Prvo kaemo

(C program koji je izgenerisan), pokrenemo program i otkucamo mali ulaz za skener. Izgleda da radi.

ex -u

da prevede skener na

C,

zatim kompajliramo

lex.yy.c

Neki ozbiljniji program, koji broji rei i karaktere, bi imao malo drugaiju deniciju rei: niz karaktera koji nisu belina, pa bi izgleda ovako:

ex

pravilo moglo da

[^ \ t \ n \ r \ f \ v ]+
Operator

{ words ++; chars += strlen ( yytext ) ; }

^ na poetku zagrada znai prepoznaj bilo koji karakter osim onih

Ovo pokazuje snagu i eksibilnost

koji su navedeni u zagradama.

jednostavno napravite izmene u obrascu, a zatim pustite izmenama u izgenerisanom kodu skenera.

ex

ex -a:

da brine o

2.3.2 Ispravan kraj reenice

Napraviti skener koji prepravlja ulazni tekst tako da ne dozvoljava beline pre take, a ubacuje samo jedan razmak posle take. Listing 2.13:

wsdot.l

%% [ \ t \ n ]* ". " [ \ t \ n ]* . { printf ( " . " ) ; } { ECHO ; }

2.3.

PRIMERI

21

Ovaj skener treba da reaguje na beline pre i posle take, a sve ostale karaktere da proputa na izlaz. Zato pravimo dva pravila. Prvo pravilo opisuje prepoznavanje 0 ili vie belina pre take, iza kojih sledi taka, iza koje sledi niz od 0 ili vie belina. Akcija koja se izvrava u sluaju da se pronae taka okruena belinama je da se ceo string zameni stringom  . , ime zadovoljavamo zahtev zadatka da posle take treba da stoji samo jedno prazno mesto. Drugo pravilo kae da svi karakteri, koji ne odgovaraju prvom pravilu, treba da prou na izlaz neizmenjeni. To se dobije akcijom koja radi eho ulaznog stringa na izlaz (ECHO). Ovaj program bi se ponaao isto i da smo izostavili drugo pravilo, jer

ex

ima predenisano ponaanje, da svaki karakter, koji

se ne uklapa ni u jedno pravilo, ispie na izlaz. Primer pokretanja ovog programa:

$ ./ wsdot Prva recenica . Druga recenica . Treca recenica . Cetvrta Prva recenica . Druga recenica . Treca recenica . Cetvrta . ^D $

2.3.3 Izostavljanje komentara iz programa

Napraviti skener koji brie komentare iz C i C++ programa. Listing 2.14:

comments.l

% x COMMENT %% " /* " /* Blok komentari */ { BEGIN COMMENT ; /* predji u stanje COMMENT */ } { /* preskoci tekst komentara */ } { BEGIN INITIAL ; /* vrati se u normalno stanje */ }

< COMMENT >.|\ n < COMMENT > " */ "

/* Linijski komentari */ " // " .*

U prvom delu se nalazi i denicija (ekskluzivnog) stanja se mogu prepoznavati.

%x COMMENT.

To

znai da kada je to stanje aktivno, samo obrasci koji su vezani za to stanje

22

POGLAVLJE 2.

FLEX

Prva tri pravila slue za prepoznavanje blok komentara. Prvo pravilo ulazi u

COMMENT kada prepozna /*, a tree pravilo se vraa nazad u normalno INITIAL stanje kada prepozna */. Drugo pravilo prepoznaje sve to se nalazi
stanje izmeu, odnosno tekst komentara. Ako bismo dodali jo i pravilo

< COMMENT > < < EOF > > { printf ( " line % d : Unterminated comment \ n " , yylineno ) ; return 0; }
mogli bismo da detektujemo i prijavimo nezavrene komentare. Poslednje pravilo opisuje jednolinijske komentare (dva kojih moe da sledi proizvoljan broj karaktera). Za ulaznu datoteku

slash

karaktera iza

test-comment.c,
Listing 2.15:

koja sadri jednu C funkciju:

test-comment.c

/* vraca vrednost 1 ako se vrednost prvog parametra nalazi u navedenim granicama . Inace vraca 0. */ int interval ( int x , int lower , int upper ) { if ( x >= lower && x <= upper ) return 1; // vrati bool vrednost true else return 0; // vrati bool vrednost false }
program daje izlaz: Listing 2.16:

out.c

int interval ( int x , int lower , int upper ) { if ( x >= lower && x <= upper ) return 1; else return 0; }

2.3.4 Pretvaranje binarnih u dekadne brojeve

Napraviti skener koji u ulaznom tekstu pronalazi binarne brojeve i prevodi ih u dekadne brojeve. Primer binarnog broja je

0B0110.

2.3.

PRIMERI

23

Listing 2.17:

2to10.l

%{ %} %%

unsigned val = 0; char * i ;

0[ bB ][01]{1 ,32}

} {

for ( i = yytext +2; * i !=0; ++ i ) { val < <= 1; val += * i - '0 '; } printf ( " % d " , val ) ; val = 0; ECHO ; }

Prvi deo specikacije sadri denicije dve promenljive: naenu

celobrojnu neoz-

koja

val, koja e sluiti za konverziju vrednosti, i pokazivaku promenljivu e sluiti kao iterator for petlje. b, '0'
zatim malo ili a zatim minimalno jedna, a maksimalno 32 binarne cifre.

Prvo pravilo prepoznaje binarne brojeve kao karakter veliko slovo ator

Akcija koja prati ovo pravilo radi konverziju binarnog u dekadni broj. Iter-

for

petlje poinje konverziju od treeg karaktera ulaznog stringa, jer

preskae

0b.

Promenljiva

val se resetuje nakon ispisa, da bi bila spremna ECHO).

za ispravnu konverziju sledeeg broja. Drugo pravilo preusmerava sve ostale karaktere na izlaz (poziva makro Primer pokretanja bi mogao da izgleda:

$ ./2 to10 123 123 0 b01 1 0 B0110 6 ^D $

Prvi broj

123

se ispisuje neizmenjen jer nije binarni broj.

Varijacije primera: prevesti heksa broj u dekadni.

24

POGLAVLJE 2.

FLEX

2.3.5 Interpreter jednostavnih komandi

Napraviti skener koji ita neka od komandi:

float vrednosti sa ulaza, dok se na ulazu ne pojavi

  
%{ %} %%

re  sum - vraa pozivaocu sumu unetih vrednosti re  mean - vraa pozivaocu srednju vrednost unetih vrednost re quit - dovodi do zavretka programa. Listing 2.18:

cmd.l

double sum = 0; int count = 0;

[0 -9]+\.[0 -9]* " sum "

{ sum += atof ( yytext ) ; count ++; } { printf ( " Sum : % f " , sum ) ; sum = 0; count = 0; } { printf ( " Mean : % f " , sum / count ) ; sum = 0; count = 0; } { return 0; } { }

" mean "

" quit " .

Prvo pravilo prepoznaje

float brojeve kao jednu ili vie cifara, iza ega sledi
To znai da su taka i cifra

taka, iza ega opciono sledi 0 ili vie cifara. sabira vrednost broja u promenljivoj

ispred take obavezni, a cifre iza take nisu. Akcija, dodeljena ovom pravilu,

sum.

Drugo i tree pravilo opisuju prepoznavanje stringa komande i izvravaju akciju: ispisuju rezultat komande i resetuju promenljive. etvrto pravilo vraa vredost izuje komandu

quit.

0,

to dovodi do kraja skeniranja i time real-

Poslednje pravilo sve ostale karaktere prosleuje na izlaz. Primer pokretanja programa:

$ ./ cmd

2.3.

PRIMERI

25

1.1 2.2 sum Sum : 3.300000 5.5 3.5 6. mean Mean : 5.000000 quit

2.3.6 Izmena formata datuma

Napraviti skener koji procesira tekst i ako naie na datum u obliku menja ga u oblik

dd-mmm-yyyy.
Listing 2.19:

dd/mm/yyyy,

date.l

% option noyywrap yylineno %{ %} %% char * months [] = { " " , " jan " , " feb " , " mar " , " apr " , " maj " , " jun " , " jul " , " avg " , " sep " , " okt " , " nov " , " dec " };

[0 -9]{2}\/[0 -9]{2}\/[0 -9]{4} { printf ( " %d -% s -% d " , atoi ( yytext ) , months [ atoi ( yytext +3) ] , atoi ( yytext +6) ) ; }

U prvom delu specikacije denisan je niz stringova indeksu u nizu.

months, koji oznaavaju

mesece u godini, tako da redni broj meseca u godini odgovara njegovom

Pravilo za datum prepoznaje po 2 ili 4 cifre razdvojene Poto je

slash

karakter jedan of

ex

slash

karakterom

operatora, u pravilu se pie

\/.

/.

Kada

se prepozna datum u prvobitnom obliku, ispisuje se datum u novom obliku, sa crticama. Promenljiva indeksu 6. Funkcija

yytext

sadri ceo prepoznat string, pa se broju

dana pristupa od karaktera na indeksu 0, mesecu na indeksu 3 i godini na

atoi()

vri konverziju stringa u celobrojnu vrednost.

Evo jednog izvravanja ovog programa:

$ ./ date Danas je utorak 06/11/2012 godine . Danas je utorak 6 - nov -2012 godine . ^D $

26

POGLAVLJE 2.

FLEX

2.3.7 Skeniranje teksta

Tekst se sastoji od 0 ili vie reenica. Reenica zapoinje reju na ijem poetku je veliko slovo. Zatim mogu da slede rei koje zapoinju bilo velikim bilo malim slovom. Na kraju stoji taka. Skener za ovaj zadatak, znai, treba da prepozna:

 

rei koje poinju velikim slovom: prvo jedno veliko slovo, a zatim 0 ili vie malih slova:

[A-Z][a-z]*

rei koje poinju malim slovom: 1 ili vie malih slova:

[a-z]+

U nastavku je data implementacija ovog skenera: Listing 2.20:

text.l

% option noyywrap yylineno %{ char * yylval ; # define _DOT # define _CAPITAL_WORD # define _WORD

1 2 3

%} %%

static char * tokens [] = { " " , " _DOT ", " _CAPITAL_WORD " , " _WORD " };

[ \ t \ n ]+ "." [A - Z ][ a - z ]* [a - z ]+ . %%

{ /* skip */ } { return _DOT ; } { yylval = yytext ; return _CAPITAL_WORD ; } { yylval = yytext ; return _WORD ; } { printf ( " \ nline % d : LEXICAL ERROR on char % c " , yylineno , yytext [0]) ; }

main () { int token = -1; while (( token = yylex () ) != 0) { printf ( " \ n %16 s TOKEN : %s " , yytext , tokens [ token ]) ; if ( token == _CAPITAL_WORD || token == _WORD ) { printf ( " value : % s " , yylval ) ; } }

2.4.

VEBE

27

}
Prvi deo specikacije sadri opcije za iskljuivanje funkcije ukljuivanje brojanja linija

yylineno.

yywrap

i za

U nastavku su denisani tokeni sa

vrednostima 1, 2 i 3. Dalje su denisani stringovi koji odgovaraju imenima tokena, i slue za tampanje izlaza programa. Vrednosti tokena odgovaraju indeksima njihovih stringova. Prvo pravilo preskae beline. Drugo pravilo prepoznaje taku i vraa samo token. Tree i etvrto pravilo prepoznaju rei i vraaju i token i string simbola kroz promenljivu denisana

yylval. Zato kao char* .

je promenljiva

yylval

u prvom delu specikacije

Poslednje pravilo slui za prijavljivanje leksike greke: ako je neki karakter dospeo u ovo pravilo, znai da nije odgovarao nijednom prethodnom pravilu, a to znai da njegova pojava nije ni predviena. Funkcija

main

prihvata tokene i vrednosti simbola i ispisuje ih.

Jedan primer izvravanja ovog programa moe biti:

$ ./ a . out Ovo je tekst . Za skeniranje . Ovo je tekst . Za skeniranje . TOKEN : TOKEN : TOKEN : TOKEN : TOKEN : TOKEN : TOKEN : _CAPITAL_WORD _WORD _WORD _DOT _CAPITAL_WORD _WORD _DOT value : Ovo value : je value : tekst value : Za value : skeniranje

^D $

2.4 Vebe
1. Proiriti prvi primer (sa listinga 2.7), tako da posebno ispie broj rei koje poinju velikim slovom i broj rei koje poinju malim slovom. 2. Napraviti skener (slian primeru 2) koji prepravi ulazni tekst tako da se iza take uvek nalazi veliko slovo. Ispravka treba da se primeni samo u sluaju da reenica poinje reju, a ne, recimo, brojem. Na primer, ulaz:

Petak. to je divan dan. treba da postane Petak. To je divan dan..

28

POGLAVLJE 2.

FLEX

3. Prepraviti primer 3, tako da menja datume iz oblika

mmmm dd, yyyy.

Decembar 31, 2012.

dd/mm/yyyy

Na primer, ulaz

31/12/2012

treba da se izmeni u

4. Napraviti skener koji u ulaznom tekstu prepravlja vreme iz oblika

HH:MM (gde su sati predstavljeni brojevima 0-24) u oblik HH:MM AM ili HH:MM PM (gde su sati predstavljeni brojevima 0-12). Na primer,
ulazni tekst se izmeni u

16:55 treba 2:55 AM.

da se izmeni u

4:55 PM,

dok ulaz

2:55

treba da

5. Napraviti skener, koji prima tekst napisan na amerikom engleskom jeziku, i menja neke rei na britanski engleski jezik. Rei koje treba zameniti su: am color fall cookie fries freeway br colour autumn biscuit chips motorway

Poglavlje 3

Bison
Sintaksa jezika opisuje pravila po kojima se kombinuju simboli jezika (npr. u

while iskazu se prvo navede kljuna re while, zatim se u malim zagradama navodi logiki izraz, a iza zagrada slede naredbe koje ine telo while iskaza).
Sintaksa se opisuje gramatikom, obino pomou BNF notacije. Svako pravilo se sastoji od leve i desne strane. Sintaksna analiza ima zadatak da proveri da li je ulazni tekst sintaksno ispravan. Ona to ini tako to preuzima niz tokena od skenera i proverava da li su tokeni navedeni u ispravnom redosledu. Ako jesu, to znai da je ulazni tekst napisan u skladu sa pravilima gramatike korienog jezika, tj. da je sintaksno ispravan. U suprotnom, sintaksna analiza treba da prijavi sintaksnu greku i da nastavi analizu. Opisani proces se vri u delu kompajlera koji se zove parser i naziva se parsiranje. U toku parsiranja gradi se stablo parsiranja.

3.1 LR parseri
LR parseri spadaju u grupu

bottom-up

parsera, to znai da grade stablo

parsiranja od listova ka korenu stabla. U toku parsiranja se prvo preuzimaju simboli (tokeni) sa ulaza i parser pokuava da prepozna desnu stranu nekog pravila i da ga zameni levom stranom pravila. Cilj je da se stigne do korena stabla, tj. do polaznog pojma gramatike. To je trenutak kada je parsiranje uspeno zavreno. L (left) oznaava da se ulaz ita s eva na desno, a R (right) oznaava da se koristi

l desno izvoenje na gore.

29

30

POGLAVLJE 3.

BISON

LR parseri koriste dve vrste akcija koje se odnose na ulazni tekst i njihov stek:

shift : reduce :

simbol se proita iz ulaznog teksta i stavi se na stek gornjih N elemenata steka uvaju simbole identine sa N simbola koji se nalaze sa desne strane odreenog pravila. Reduce akcijom se ovih N simbola zamenjuje pojmom koji se nalazi sa leve strane tog pravila.

Zbog ovih akcija LR parseri se nazivaju jo i

shift-reduce

parseri. Osim ove

dve akcije postoje jo dve koje se koriste u procesu LR parsiranja:

accept : error :

ova akcija se izvrava kada je proitan ceo ulazni tekst, a na steku se nalazi samo jedan, i to poetni, pojam gramatike ako ulazni tekst nije u skladu sa gramatikom, parser nee moi da primeni ni greku.

shift

ni

reduce

akciju, pa e se zaustaviti i prijaviti

3.1.1 Generatori LR parsera

Jedan od najee korienih alata za generisanje parsera je rienje

bison -a je prikazano na slici 3.1.

bison .

Ko-

Slika 3.1: Korienje

bison -a
Speci-

Prvi korak u generisanju parsera je priprema njegove specikacije.

kaciju kreira korisnik u posebnoj datoteci koja po konvenciji ima ekstenziju

.y

. Ova datoteka sadri gramatiku koju parser treba da prepozna. Prav-

ila se zadaju u BNF obliku. Svakom pravilu je mogue pridruiti akciju (u obliku

koda) koja e se izvriti kada parser prepozna dato pravilo.

.y datoteka se prosleuje bison -u, koji kao izlaz, generie C program y.tab.c.
Kod koji je izgenerisao

bison, sadri tabelarnu reprezentaciju dijagrama do.y

datoteci su delovi Na kraju,

bijenih iz opisa pravila. Akcije pridruene pravilima u

C koda koji se direktno prenose (kopiraju) u y.tab.c.

y.tab.c se

3.2.

FORMAT BISON SPECIFIKACIJE

31

prosleuje

kompajleru da bi se kao izlaz dobio program

a.out.

Ovaj pro-

gram predstavlja parser koji proverava sintaksnu ispravnost ulaznog teksta (na osnovu pravila gramatike). Prilikom izvravanja, parser e od skenera traiti naredni token iz ulaznog teksta i proveriti da li je njegova pojava na datom mestu dozvoljena (da li je u skladu sa gramatikom). Ako jeste nastavie parsiranje, a ukoliko nije, prijavie greku, pokuae da se oporavi od greke i da nastavi parsiranje. U momentu kada parser prepozna celo pravilo, parser e izvriti akciju koja je pridruena tom pravilu.

3.2 Format bison specikacije

%%:

Bison

specikacija se sastoji od tri dela, meusobno razdvojena oznakom

1. denicije 2. pravila i 3. korisniki kod.

3.2.1 Denicije
Prvi deo se obino koristi za ukljuivanje zaglavlja i denicije promenljivih (pri emu ovakav kod mora biti okruen specijalnim zagradama rei

%{

%}).

U ovom delu se deniu i tokeni tako to se ime tokena navede iza kljune

%token.

Uopteno, u ovom delu se navode opcije za upravljanje radom

generatora. Ovaj deo datoteke nije obavezan.

3.2.2 Pravila
Drugi deo specikacije sadri gramatiku, odnosno pravila koja opisuju sintaksu jezika. Gramatika svakog jezika obuhvata: simbole, pojmove, pravila i polazni pojam. Na osnovu ovih pravila pravilo se zadaje u obliku:

bison

generie kod parsera. Svako

pravilo

[ akcija ]

Pravila se piu na formalan nain u BNF obliku, a akcije blokom C (ili C++) koda koji e se izvriti kada skener prepozna pravilo. Obrazac mora da pone u prvoj koloni, a akcija ne mora da postoji. Ako akcija postoji,

32

POGLAVLJE 3.

BISON

njena denicija mora da pone u istom redu u kojem je denisan obrazac. Ovaj deo opisa Pravila ( simbola:

bison

programa je obavezan.

production ) odreuju dozvoljene naine reanja/pisanja pojmova i

pojam ::= pojmovi i / ili simboli

Leva strana pravila (pre znaka

::=)

sadri pojam koji moe biti zamenjen

sekvencom pojmova i/ili simbola koje sadri desna strana pravila (iza znaka

::=).

To znai da se leva strana pravila moe zameniti desnom stranom Jedan od pojmova predstavlja polazni pojam i on se

pravila, i obrnuto.

navodi kao prvo pravilo. Na primer,

IF-ELSE

iskaz u C programskom jeziku ima formu:

IF ( expr ) stmt ELSE stmt

Drugim reima, to je konkatenacija: izraza kljune rei

expr,

zatvorene zagrade

jo jednog iskaza Sintaksa

stmt.

),

iskaza

stmt,

IF,

otvorene zagrade

kljune rei

ELSE,

(,

i na kraju,

IF-ELSE

iskaza napisana BNF notacijom ima izgled (imena pojo-

mova su napisana malim slovima, a simbola velikim):

stmt ::= IF ( expr ) stmt ELSE stmt

ili

stmt -> IF ( expr ) stmt ELSE stmt

Bison

ovakvu gramatiku prihvata u malo modikovanom obliku BNF no-

tacije: umesto oznake

::=

ili strelice

->

pie se dvotaka i na kraju pravila

se pie karakter taka-zarez:

stmt : IF ( expr ) stmt ELSE stmt ;

Dvotaka se ita moe imati oblik. stranu, na primer: Vie pravila, koja imaju istu levu

list : + digit ; list : - digit ; list : digit ;

mogu se grupisati zajedno, tako to se razdvoje vertikalnom linijom koja ima znaenje ili:

list : + digit | - digit | digit ;

3.3.

PARSIRANJE

33

Ako se ovo napie malo drugaije, postaje itljivije:

list : + digit | - digit | digit ;

Ovo je uobiajeni nain pisanja grupe pravila u

bison

specikaciji.

3.2.3 Korisniki kod

U ovom opcionom delu korisnik moe da denie proizvoljan blok koda (funkcija

main(),

druge funkcije, globalne promenljive, . . . )

koji e, bez

izmena, biti prekopiran na kraj generisanog parsera.

3.3 Parsiranje
Bison
preuzima gramatiku iz specikacije i pravi parser koji prepoznaje reenice, odnosno iskaze te gramatike. Programi mogu biti sintaksno ispravni, ali semantiki neispravni (na primer, C program koji

string

dodeljuje

int

promenljivoj).

Bison

rukuje samo

sintaksnom, a sve ostale validacije su ostavljene korisniku. Postupak parsiranja e biti opisan na primeru gramatike za jednostavni kalkulator:

e : NUMBER PLUS NUMBER | NUMBER MINUS NUMBER ;

gde pojam Simbolu

e opisuje izraz (expression ). NUMBER, PLUS i MINUS su simboli. NUMBER odgovara broj (niz cifara), simbolu PLUS karakter +, a simbolu MINUS karakter -. Vertikalna crta (|) znai da za isti pojam postoje dve
razliite mogunosti i opisuje se reju ILI. U ovom sluaju, izraz moe biti ili sabiranje ili oduzimanje. Svi pojmovi koji se koriste u gramatici moraju biti denisani, odnosno mora postojati bar jedno pravilo u kom se taj pojam nalazi na levoj strani. Na levoj strani pravila se ne sme nai token (to je greka). Uobiajeni nain da se predstavi isparsiran tekst je stablo. Na primer, ako se parsira ulaz:

2+3

ovom gramatikom, stablo izgleda kao na slici 3.2.

34

POGLAVLJE 3.

BISON

Slika 3.2: Stablo parsiranja za izraz

2+3

Parser ne kreira automatski ovakvo stablo kao strukturu podataka, iako je relativno jednostavno da korisnik to uradi. Pravila mogu da pozivaju, direktno ili indirektno, sama sebe, pa se zovu rekurzivna pravila. Time je omogueno parsiranje proizvoljno dugakih ulaznih nizova. Ako prethodnu gramatiku malo izmenimo, dobiemo:

lines : | lines e NEWLINE ; e : e PLUS NUMBER | e MINUS NUMBER | NUMBER ;

opisuje izraz, a

gde

lines

opisuje (prazne redove ili) redove koji sadre Simbolu

po jedan izraz (i karakter za novi red). simboli, a red

\n.

e i lines su pojmovi.

Ako se ovom gramatikom

NUMBER, NEWLINE, PLUS i MINUS su NEWLINE odgovara karakter za novi parsira ulaz 2+3\n, stablo izgleda kao na

slici 3.3.

Slika 3.3: Stablo parsiranja za ulaz

2+3\n

3.3.

PARSIRANJE

35

U ovom primeru,

2+3 je izraz, a e NEWLINE (ili e\n) je iskaz. lines.

Svaka gramatika U

ima poetni pojam, onaj koji mora da bude koren stabla parsiranja. ovoj gramatici poetni pojam je poetnim, treba da bude naveden kao prvo pravilo u se ime poetnog pojma navede iza kljune rei specikacije, na primer:

Da bi neki pojam bio proglaen

%start,

bison

specikaciji ili da

u prvom delu

bison

% start lines
U naem primeru pravilo

e je sada rekurzivno denisano, i to levo rekurzivno.

To znai da se ime pravila nalazi na poetku (na levom kraju) desne strane pravila. Zbog ove osobine, mogue je parsirati izraz primenom pravila prikazano je na slici 3.4).

2+3-4+5 ponovljenom e (deo stabla parsiranja koji se odnosi na ovaj ulazni izraz

Slika 3.4: Deo stabla parsiranja za izraz Listing 3.1 sadri vanje iskaza. Listing 3.1:

2+3-4+5

ex,

a listing 3.2

bison

implementaciju prethodne gra-

matike: potreban je skener za prepoznavanje simbola i parser za prepozna-

calc1.l

%{ %} %%

# include " calc1 . tab . h "

[ \ t ]+ [0 -9]+

{ yylval = atoi ( yytext ) ; return NUMBER ; }

36

POGLAVLJE 3.

BISON

"+" " -" \n .

{ { { {

return PLUS ; } return MINUS ; } return NEWLINE ; } printf ( " Unknown char % c \ n " , * yytext ) ; }

U prvom delu specikacije potrebno je ukljuiti datoteku proizvodi skeneru.

bison,

calc1.tab.h koju

jer se u njoj nalaze izgenerisani tokeni koji se koriste u

U pravilima se prepoznaje broj kao niz cifara i uz token se prosleuje konkretna vrednost broja (podrazumevanti tip promenljive

PLUS, MINUS i NEWLINE

ulaznom tekstu.

yylval je int).

Za simbole

se prosleuje samo token.

Za sve ostale karak-

tere prijavljuje se greka, jer gramatikom nije predviena njihova pojava u

Listing 3.2:

calc1.y

%{

%}

# include < ctype .h > # include < stdio .h > int yyparse ( void ) ; int yylex ( void ) ; NUMBER PLUS MINUS NEWLINE

% token % token % token % token %%

lines : | lines NEWLINE | lines e NEWLINE ; e : | | ; e PLUS NUMBER e MINUS NUMBER NUMBER

%% int main () { return yyparse () ; }

3.3.

PARSIRANJE

37

int yyerror ( char * s ) { fprintf ( stderr , " % s \ n " , s ) ; return 0; }

U prvom delu su denisana 4 tokena za 4 simbola gramatike. Pravilo

lines

opisuje prazan red ili red u kojem se nalazi izraz iza kog sledi karakter za novi red. Izraz je rekurzivno denisan kao jedan broj, ili sabiranje ili oduzimanje dva broja.

main()

funkcija jedino poziva parser.

Ukoliko doe do sintaksne greke,

pozvae se funkcija

yyerror()

koja ispisuje poruku o greki.

Generisanje skenera i parsera i pokretanje programa se odvija ovako:

$ bison -d calc1 . y $ flex -- noyywrap calc1 . l $ gcc -o calc1 calc1 . tab . c lex . yy . c $ ./ calc1 2+3 5 -2 ^D $
Prvo se pokrene

bison sa opcijom -d (za generisanje .h datoteke sa denicijama)

calc1.tab.c i calc1.tab.h. Zatim se pokrene lex.yy.c. Na kraju se pozove gcc kompajler da napravi calc1. Pokretanjem programa vidimo da kalkulator prih-

koji e napraviti datoteke

ex

koji napravi

izvrni program

vata izraze, ali ne izvrava sabiranje i oduzimanje, jer pravilima jo nismo pridruili akcije, tj. nismo mu rekli ta da radi kada prepozna izraz i liniju.

3.3.1 Akcije
Hajde da pravilima u prethodnoj 3.3): Listing 3.3:

bison

specikaciji dodamo akcije (listing

calc2.y

lines : | lines NEWLINE | lines e NEWLINE ; e : e PLUS NUMBER

{ printf ( " % d \ n " , $2 ) ; }

{ $$ = $1 + $3 ; }

38

POGLAVLJE 3.

BISON

| | ;

e MINUS NUMBER NUMBER

{ $$ = $1 - $3 ; } { $$ = $1 ; }

U akcijama se koriste meta-promenljive, ija imena poinju karakterom a iza nje sledi broj. desnoj strani pravila. Tako se meta-promenljiva simbola je u parser stigla preko promenljive Meta-promenljiva

'$',

Ovaj broj oznaava redni broj simbola ili pojma na

$1

odnosi na vrednost poa poslao ju je skener.

jma/simbola koji se nalazi prvi naveden na desnoj strani pravila. Vrednost

yylval,

Vrednost pojma se denie u parseru, u akciji pravila za dotini pojam.

$$

se odnosi na pojam sa leve strane pravila, odnosno

sadri njegovu vrednost. To znai da, kada elimo da deniemo vrednost nekog pojma, u njegovom pravilu emo imati akciju Krenuemo od poslednjeg pravila za izraz akciju

{ $$ = ...

; }.

e dobija istu onu NUMBER, a to je konkretna vrednost prepoznatog broja, jer smo u skeneru, uz token NUMBER preko yylval, prosledili i vrednost
Ova akcija kae da vrednost pojma vrednost koju ima simbol broja (slika 3.5).

{ $$ = $1; }.

e : NUMBER

kojem smo dodali

Slika 3.5: Prenoenje vrednosti simbola iz skenera u parser U pravilu za oduzimanje dodali smo akciju oduzeti 2 broja. a

$3

$1

{ $$ = $1 - $3; },

gde emo

sadri vrednost prvog broja (to je vrednost pojma

e),

sadri vrednost drugog broja (koji se nalazi na treoj poziciji desne Vrednosti pojma

strane pravila, pa se njegovoj vrednosti pristupa preko meta-promenljive

$3).

(kojoj se pristupa preko meta-promenljive

$$)

se

dodeljuje rezultat oduzimanja. Slino se deava i u pravilu za sabiranje. U pravilu za

lines dodali smo akciju { printf("%d\n", $2); } koja, nakon lines,

jer su to pravila za prepoz-

prepoznavanja jedne linije sa izrazom, ispisuje vrednost izraza. Ovu akciju ne treba dodati u ostala dva pravila za navanje praznih linija, bez izraza, pa nema ni izraunavanja ni ispisivanja.

3.3.2 Shift-reduce parsiranje

Bison
radi tako to proverava da li postoji pravilo (desna strana pravila) Dok koje odgovara tokenima koje je do sada primio.

bison

pravi parser,

3.3.

PARSIRANJE

39

on kreira skup stanja, od kojih svako odraava poziciju u pravilu koje se parsira. Dok parser ita tokene, svaki put kada proita token kojim se jo nije kompletiralo pravilo, on ga stavi na interni stek i pree u novo stanje. Ova akcija se zove

shift .

Kada parser pronae sve simbole koji ine desnu

stranu pravila, on ih sve ukloni sa steka i umesto njih na stek stavi pojam sa leve strane pravila, a zatim pree u novo stanje. Znai, zamenio je desnu stranu pravila na steku levom. Ova akcija se zove elemenata na steku. Kad god

bison

prepozna

reduce, jer smanjuje broj pravilo (reduce ), on izvri

Parsiranje emo pratiti

akciju koja je pridruena tom pravilu. Da vidimo kako e parser parsirati ulaz

1+2\n.

kroz izmene na steku stanja i steku vrednosti (vrhovi oba steka su gore). Na poetku parsiranja, oba steka su prazna (slika 3.6.a). Pre preuzimanja prvog karaktera, deava se redukcija po prvom pravilu, koja prazan red pretvara u

lines

(slika 3.6.b). Poto ne moe da izvri vie ni jednu redukciju, parser

poziva skener i od njega dobija prvi simbol iz ulaznog teksta, a to je sa vrednou

1.

Parser smeta simbol

na stek vrednosti stavlja vrednost

NUMBER

NUMBER,

(iftuje ga) na stek stanja, a

(stek sada izgleda kao na slici 3.6.c).

Zatim, parser proverava da li neka sekvenca na vrhu steka odgovara desnoj

e, pa izvrava redukciju. Sa steka stanja uklanja NUMBER i menja ga pojmom e, a sa steka vrednosti uklanja vrednost 1 i stavlja vrednost pojma e. Vrednost
strani nekog pravila. Konstatuje da ini desnu stranu pravila za pojma se rauna u akciji koja je pridruena tom pravilu i koja se izvrava u toku redukcije. U toj akciji pie da vrednost pojma simbola

NUMBER

NUMBER ($1),

a to je vrednost

e ($$)

dobija vrednost

(vidi 3.6.d).

Slika 3.6: Primer rada parsera za ulaz

1+2\n

Poto ne moe da izvri vie nijednu redukciju, parser se ponovo obraa skeneru za token. Dobija token 3.6.e). Uz token

PLUS

PLUS kog iftuje (smeta) na stek stanja (vidi

U ovom trenutku

iz skenera nije poslata vrednost.

elementi na vrhu steka ne formiraju nijedno pravilo, pa parser poziva skener

40

POGLAVLJE 3.

BISON

i dobija token

NUMBER

i vrednost

(vidi 3.6.f ).

Sada poslednja 3 elementa na vrhu steka ine desnu stranu pravila da uklanja 3 elementa sa steka stanja i stavlja pojam uklanja 3 elementa i stavlja novu vrednost

za

sabiranje izraza. Parser moe da uradi redukciju po tom pravilu, to znai

3.

e, a sa steka vrednosti

Ovu, novu, vrednost pojma

dobio je izvravanjem akcije uz ovo pravilo, koja opisuje da se vrednost

e dobija kao zbir prvog operanda ($1 - u naem sluaju vrednost 1) i drugog operanda ($3 - u naem sluaju vrednost 2). Vrednosti simbola NUMBER se pristupa preko meta-promenljive $3, jer se simbol nalazi na treem
pojma mestu na desnoj strani pravila, a istovremeno je trei element koji je skinut sa steka (vidi 3.6.g). Parser dalje iftuje simbol uradi redukciju po pravilu (vidi 3.6.i). Nakon toga, iftuje da uradi

NEWLINE (vidi 3.6.h) i sada je u mogunosti da lines : lines e NEWLINE. U procesu redukcije uklanja po 3 elementa sa svakog steka i stavlja pojam lines na steku stanja EOF karakter, jer je stigao do kraja datoteke i u prilici je EOF
karakter (3.6.j, 3.6.k). U ovom

accept

akciju. Ova akcija je mogua u trenutku kada se na steku

nalazi samo polazni pojam, a iza njega

sluaju parser objavljuje uspeno parsiranje.

3.4 Leva i desna rekurzija

Kada se pie rekurzivno pravilo, rekurzivna referenca se moe staviti na levi kraj, pa se zove leva rekurzija

exp_list : exp_list ' , ' exp ;

ili se moe staviti na desni kraj pravila, pa se zove desna rekurzija

exp_list : exp ' , ' exp_list ;

U veini sluajeva, gramatika se moe pisati na oba naina. levom rekurzijom mnogo ekasnije nego desnom.

Bison

rukuje

To je zato to na svom

steku uva sve simbole koji su dotad vieni za sva delimino isparsirana pravila. Ako se koristi desno rekurzivna verzija pravila

exp_list

i na ulazu

se pojavi lista od 10 izraza, kad se bude proitao 10-ti izraz, na steku e biti ve 20 elemenata: izraz i zarez za svih 10 izraza. Kada se lista zavri, svi ugnjedeni

exp_list

pojmovi e biti redukovani, s desna na levo. S druge

strane, ako se koristi levo rekurzivna varijanta pravila

exp_list

e biti redukovano posle svakog

exp,

exp_list,

pravilo

tako da lista nikad nee

imati vie od tri elementa na steku.

3.5.

PRIMERI

41

3.5 Primeri
3.5.1 Broj rei i reenica u ulaznom tekstu
Data je gramatika teksta: Tekst se sastoji od 0 ili vie reenica. Reenica zapoinje reju na ijem poetku je veliko slovo. Zatim mogu da slede rei koje zapoinju bilo velikim bilo malim slovom. Na kraju stoji taka. Napraviti parser koji e izbrojati rei i reenice koje se pojave u ulaznom tekstu. Tekst gramatika u

bison -BNF obliku izgleda ovako:

Listing 3.4: Gramatika teksta

text : | ;

/* empty text */ text sentence

sentence : _CAPITAL_WORD words _DOT ; words : /* empty */ | words _WORD | words _CAPITAL_WORD ;
Skener, koji predstavlja deo reenja ovog primera, je ve dat na listingu 2.20 (glava 2.3.7). Razlika je u tome, to je prethodni skener napravljen kao samostalni program, pa sadri svoju je listingu 3.5. Listing 3.5:

main()

funkciju i sopstvenu deniciju

tokena. Skener za ovaj primer se koristi u kombinaciji sa parserom i prikazan

count1.l

% option noyywrap yylineno %{ # define YYSTYPE char * # include " count1 . tab . h " %} %% [ \ t \ n ]+ { /* skip */ }

"." { return _DOT ; } [A - Z ][ a - z ]* { yylval = yytext ; return _CAPITAL_WORD ;}

42

POGLAVLJE 3.

BISON

[a - z ]+ .

{ yylval = yytext ; return _WORD ; } { printf ( " \ nline % d : LEXICAL ERROR on % c " , yylineno , * yytext ) ; }

Parser treba da prebroji rei i reenice, pa su zato potrebne 2 brojake promenljive:

word_counter i sentence_counter (listing 3.6). sentence.

Broja reenica

se inkrementira svaki put kada se prepozna cela reenica, a to se deava u akciji koja sledi iza pravila re reenice (pravilo Broja rei se inkrementira svaki kada dobije prvu put kada parser dobije od skenera token za neku re: dini reenice (pravilo

_CAPITAL_WORD (pravilo sentence), kada dobije _WORD u sreword) i kada dobije _CAPITAL_WORD u sredini reenice word).
Listing 3.6:

count1.y

%{

# include < stdio .h > # define YYSTYPE char * int yylex ( void ) ; int yyparse ( void ) ; int word_counter = 0; int sentence_counter = 0; extern int yylineno ;

%}

% token _DOT % token _CAPITAL_WORD % token _WORD %% text : | ; /* empty text */ text sentence

sentence : _CAPITAL_WORD words _DOT { word_counter ++; sentence_counter ++; } ; words : /* empty */ | words _WORD { word_counter ++; }

3.5.

PRIMERI

43

| ; %%

words _CAPITAL_WORD { word_counter ++; }

main () { yyparse () ; printf ( " Total words : % d .\ n " , word_counter ) ; printf ( " Total sentences : % d .\ n " , sentence_counter ) ; } yyerror ( char * s ) { fprintf ( stderr , " line %d : SYNTAX ERROR % s \ n " , yylineno , s ) ; }
Kada se ovaj program pokrene, njegov izlaz e izgledati ovako:

$ ./ count1 Marko se igra . Mile spava . ^D Total words : 5. Total sentences : 2. $

3.5.2 Rei iz ulaznog teksta

Proiriti prethodni primer tako da parser, osim to prebroji rei i reenice, jo i ispie sve rei iz ulaznog teksta. Za reenje ovog zadatka, parseru su potrebni stringovi rei koje treba da ispie. Ove stringove prepoznaje skener, pa ih je na neki nain potrebno proslediti parseru. Zato je potrebno malo modikovati skener iz prethodnog primera, tako to e se sauvati string rei koju skener prepozna (listing 3.7). Za tokene

_WORD i _CAPITAL_WORD se, pored tokena, parseru prosleuju strdup()

i stringovi rei, kao vrednosti simbola, preko globalne

yylval.

bison

promenljive

String se kopira pomou funkcije

koja radi i alokaciju

memorije i kopiranje.

Zato je potrebno da se u parseru uradi dealokacija

dotine memorije, u trenutku kada ti stringovi vie ne trebaju. Listing 3.7:

count2.l

- modikacija

[A - Z ][ a - z ]* { yylval = strdup ( yytext ) ; return _CAPITAL_WORD ;} [a - z ]+ { yylval = strdup ( yytext ) ; return _WORD ; }
Ispis rei se vri svaki put kada u parser stigne neka re. Nakon svakog ispisa rei sledi oslobaanje memorije koju je u skeneru zauzela funkcija

strdup().

44

POGLAVLJE 3.

BISON

Listing 3.8:

count2.y

- pravila

text : | ;

/* empty text */ text sentence

sentence : _CAPITAL_WORD words _DOT { word_counter ++; sentence_counter ++; printf ( " % s \ n " , $1 ) ; free ( $1 ) ; } ; words : /* empty */ | words _WORD { word_counter ++; printf ( " % s \ n " , $2 ) ; free ( $2 ) ; } | words _CAPITAL_WORD { word_counter ++; printf ( " % s \ n " , $2 ) ; free ( $2 ) ; }

Kada se ovaj program pokrene, njegov izlaz e izgledati ovako:

$ ./ count2 Danas je predivan dan . je predivan dan Danas ^D Total words : 4. Total sentences : 1. $
Osim prve rei, sve rei su ispisane u redosledu u kom su se pojavile u ulaznom tekstu. Prva re je ispisana na kraju. Ovo se deava zato to se kod, koji vri ispis prve rei u reenici, nalazi u akciji koja se izvrava tek kada se zavri parsiranje cele reenice (pa se i ispis prve rei vri kada je prepoznata cela reenica). U tekstu zadatka se ne trai da se rei ispiu u redosledu u kom su se pojavile u ulaznom tekstu, pa se ovo reenje moe smatrati zadovoljavajuim. Sledei primer reava pitanje redosleda ispisivanja rei.

3.5.

PRIMERI

45

3.5.2.1 Ispravan redosled rei iz ulaznog teksta

Jedina izmena je u pravilu

sentence.

Akciju, koja ispisuje prvu re je

potrebno prebaciti odmah nakon preuzimanja tokena

_CAPITAL_WORD.

ovom sluaju, prva re u reenici e biti ispisana im dospe u parser, a ne, kao u prethodnom primeru, kada se prepozna cela reenica. Listing 3.9:

count3.y

- pravilo

sentence

sentence : _CAPITAL_WORD { word_counter ++; printf ( " % s \ n " , $1 ) ; free ( $1 ) ; } words _DOT { sentence_counter ++; ;

Kada se ovaj program pokrene, njegov izlaz e izgledati ovako:

$ ./ count3 Danas je lep dan . Danas je lep dan ^D Total words : 4. Total sentences : 1. $

3.5.2.2 Tekst u zagradama

Proiriti prethodnu tekst gramatiku tako da omogui da se jedna ili vie rei pie u malim zagradama. Ispred prve rei ne sme da se pojavi zagrada. Prazne zagrade su dozvoljene. Zagrade moraju biti u paru. Mogu da postoje ugnjedene zagrade (zagrade u zagradama). Za reenje moemo preuzeti skener iz prethodnog primera i dodati mu pravila za prepoznavanje otvorene i zatvorene male zagrade (listing 3.10). Listing 3.10:

count4.l

- male zagrade

"(" ")"

{ return _LPAREN ; } { return _RPAREN ; }

46

POGLAVLJE 3.

BISON

Moemo preuzeti i parser iz prethodnog primera pa mu dodati denicije tokena (listing 3.11). Listing 3.11:

count4.y

- tokeni

% token % token

_LPAREN _RPAREN

i proiriti pravilo

words

novim pravilom koje sadri zagrade (listing 3.12).

Listing 3.12:

count4.y

- pravilo

words

words : /* empty */ | words _WORD { word_counter ++; printf ( " % s \ n " , $2 ) ; free ( $2 ) ; } | words _CAPITAL_WORD { word_counter ++; printf ( " % s \ n " , $2 ) ; free ( $2 ) ; } words _LPAREN words _RPAREN

| ;

Novo rekurzivno pravilo opisuje da se par zagrada moe nai oko bilo koje grupe rei. prazne. Poto

nae samo jedna re, a opet,

words moe biti samo jedna re, pa je mogue da se izmeu zagrada words se moe sastojati od vie rei, pa smo words
ne opisuje prvu re u reenici, obezbedili smo da se u pravilu

words

moe biti i prazan, znai da i zagrade mogu biti

time omoguili da se izmeu zagrada nae i vie od jedne rei. Kako pojam token

zagrade ne mogu nai ispred prve rei u reenici (prvu re u reenici opisuje

_CAPITAL_WORD

sentence). words,
omoguena je pojava

Time to je par zagrada denisan u pravilu ugnjedenih zagrada.

Kada se ovaj program pokrene, izlaz e izgledati kao na sledeem listingu:

$ ./ count4 Danas ( utorak ) je lep dan ( nije hladno ( i vedro je ) ) () . Danas utorak je lep dan

3.5.

PRIMERI

47

nije hladno i vedro je Nezavrsene ( zagrade u tekstu . Nezavrsene zagrade u tekstu line 2: SYNTAX ERROR syntax error Total words : 14. Total sentences : 1. $
Prva reenica je sintaksno ispravna. Testirali smo varijante: jedna re u

zagradama, vie rei u zagradama, ugnjedene zagrade i prazne zagrade. Druga reenica je sintaksno neispravna, jer ne sadri zatvorenu zagradu. Parser je preuzimao simbole sa ulaza dok nije stigao do kraja datoteke, a zatim je ispisao poruku da je detektovao sintaksnu greku (jer nije pronaao zatvorenu zagradu), i zavrio svoju aktivnost.

3.5.3 Izmena formata datuma

Proiriti osnovnu tekst gramatiku (iz primera 3.5.1, na listingu 3.4) datumima u obliku menja formu datuma u

dd/mm/yyyy. Napraviti parser koji procesira ulazni tekst i dd-mmm-yyyy. Ostatak teksta se ne menja (ispisuje
Listing 3.13:

se na izlazu u neizmenjenom obliku).

date.l

% option noyywrap yylineno %{ # include " date . tab . h " %} %% [ \ t \ n ]+ "/" [0 -9]{2} [0 -9]{4} "." [A - Z ][ a - z ]* { /* skip */ } { return _SEPARATOR ; } { yylval . i = atoi ( yytext ) ; return _2D ;} { yylval . i = atoi ( yytext ) ; return _4D ; } { return _DOT ; } { yylval . s = yytext ; return _CAPITAL_WORD ; }

48

POGLAVLJE 3.

BISON

[a - z ]+

{ yylval . s = yytext ; return _WORD ; }

U skeneru se kao deo datuma prepoznaju simboli od 2 i od 4 cifre. Za njih su vezani tokeni

_2D i _4D,

a vrednosti ovih simbola su konkretne vrednosti

brojeva, koje se smetaju u polje denisan je karakter

i unije yylval. Kao separator ovih simbola / i za njega je vezan token _SEPARATOR. Ostali simboli s
unije

su, kao u prethodnim primerima, simboli tekst gramatike (jedina razlika je to se ovde stringovi rei prenose preko polja Unija u ovom parseru treba da ima jedan i

yylval).
(jer se uz tokene

_4D

integer

alju konkretni brojevi) i jedan pokaziva na

kene

_CAPITAL_WORD i _WORD

string

_2D

(jer se uz to-

alju stringovi). Kada se promenljiva

yylval
a uz

denie kao unija, za svaki token koji ima vrednosti, se mora rei kog tipa je ta vrednost. Zato uz deniciju tokena deniciju tokena

_CAPITAL_WORD i _WORD
Listing 3.14:

_2D

_4D

stoji oznaka

stoji oznaka

<s>.

<i>,

date.y

%}

int yylex ( void ) ; int yyparse ( void ) ; extern int yylineno ; char * months [] = { " " , " jan " , " feb " , " mar " , " apr " , " maj " , " jun " , " jul " , " avg " , " sep " , " okt " , " nov " , " dec " };

% union { int i; char * s ; } % token % token % token % token % token % token %% text : | ; /* empty text */ text sentence _SEPARATOR <i > _2D <i > _4D _DOT <s > _CAPITAL_WORD <s > _WORD

sentence : _CAPITAL_WORD { printf ( " % s " , $1 ) ; } words _DOT

3.5.

PRIMERI

49

printf ( " . " ) ; }

words : /* empty */ | | | ; date : words _WORD { printf ( " % s " , $2 ) ; } words _CAPITAL_WORD { printf ( " % s " , $2 ) ; } words date

_2D

; %%

{ printf ( " %d - " , $1 ) ; } _SEPARATOR _2D { printf ( " %s - " , months [ $4 ]) ; } _SEPARATOR _4D { printf ( " % d " , $7 ) ; }

int main () { yyparse () ; printf ( " \ n " ) ; } int yyerror ( char * s ) { fprintf ( stderr , " line %d : % s \ n " , yylineno , s ) ; }
Parser je proiren u pravilu dini reenice.

words,

tako da prima i datume, bilo gde u sre-

im se prepoznaju dve cifre koje oznaavaju dan, izvrava

se akcija koja ispisuje taj broj na ekran (vrednost meta-promenljive a iza njega novi separator. koje oznaavaju mesec, pomou niza stringova

$1),

Zatim, kada se prepoznaju sledee dve cifre,

months,

denisanog u pr-

vom delu specikacije, se ispisuje tekstualna forma meseca i novi separator. Nakon to se prepoznaju 4 cifre za godinu, one se ispiu na ekran (vrednost meta-promenljive

$7).

Sve rei (i taka), koje se prepoznaju u tekstu, se

neizmenjene ispiu na izlaz. Primer pokretanja ovog programa je prikazan na sledeem listingu:

$ ./ date

50

POGLAVLJE 3.

BISON

Danas je 06/11/2012 godine , a za dva meseca ce biti 06/01/2013. Danas je 6 - nov -2012 godine , a za dva meseca ce biti 6 - jan -2013. ^D $

3.5.4 Strukturirana datoteka sa meteorolokim podacima

Napraviti program koji analizira ulaznu datoteku sa klimatskim podacima za jedan mesec i ispisuje koliko je bilo dana sa temperaturom iznad 12 stepeni Celzijusa. Datoteka se sastoji od vie slogova, a slog ima sledeu strukturu:

temperatura : pritisak : pravac vetra : brzina vetra : vlaznost :

13 1004.9 E 3 67

Listing 3.15 sadri skener a listing 3.16 parser ovog primera. Listing 3.15:

meteo.l

% option noyywrap yylineno %{ # include " meteo . tab . h " %} %% [ \ t \ n ]+ { /* skip */ } { { { { { { { { { return _TEMPERATURA ; } return _PRITISAK ; } return _PRAVAC_VETRA ; } return _BRZINA_VETRA ; } return _VLAGA ; } return _DVOTACKA ; } yylval . i = atoi ( yytext ) ; return _INT ;} yylval .f = atoi ( yytext ) ; return _FLOAT ; } return _VETAR ; }

" temperatura " " pritisak " " pravac vetra " " brzina vetra " " vlaznost " ":" [0 -9]+ [0 -9]+\.[0 -9]* E | NE | SE | W | NW | SW

Skener prepoznaje sve kljune rei iz sloga, kao i dvotaku, i za njih alje samo token. Prilikom prepoznavanja celog i razlomljenog broja, on alje odgovarajui token (_INT ili i

int

_FLOAT) i vrednost broja. Unija sadri tipove float, da bi mogle da se prenesu konkretne vrednosti ovih brojeva. Tokenu _INT je dodeljen tip <i>, a tokenu _FLOAT tip <f>. Token _VETAR se NE, SE, W, NW, SW).

alje kada skener prepozna neku kombinaciju karaktera, koja oznaava smer vetra (E,

3.5.

PRIMERI

51

Primenjena gramatika opisuje da se jedan fajl sastoji od jednog ili vie slogova, a da jedan slog redom sadri: opis temperature, pritiska, pravca vetra, brzine vetra i vlanosti. Deo sloga koji opisuje temperaturu se sastoji prvo od kljune rei  temperatura, zatim sledi dvotaka, pa zatim ceo broj koji sadri vrednost temperature (listing 3.16). Listing 3.16:

meteo.y

%{

%}

# include < stdio .h > int yylex ( void ) ; int yyparse ( void ) ; extern int yylineno ; int temp = 0;

% union { int i; float f ; } % token % token % token % token % token % token % token % token % token %% fajl : | ; slog : ; slog fajl slog _TEMPERATURA _PRITISAK _PRAVAC_VETRA _BRZINA_VETRA _VLAGA _DVOTACKA <i > _INT <f > _FLOAT _VETAR

temperatura pritisak pravac_vetra brzina_vetra vlaga

temperatura : _TEMPERATURA _DVOTACKA _INT { if ( $3 > 12) temp ++; } ; pritisak

52

POGLAVLJE 3.

BISON

: ;

_PRITISAK _DVOTACKA _FLOAT

pravac_vetra : _PRAVAC_VETRA _DVOTACKA _VETAR ; brzina_vetra : _BRZINA_VETRA _DVOTACKA _INT ; vlaga : _VLAGA _DVOTACKA _INT ; %% int main () { yyparse () ; printf ( " U ovom mesecu bilo je % d dana sa t > 12 C .\ n " , temp ) ; } int yyerror ( char * s ) { fprintf ( stderr , " line % d: % s \ n " , yylineno , s ) ; }
Da bi izraunali koliko je dana bilo sa temperaturom preko 12 stepeni, treba

temp). Nakon _INT (to je ujedno i kraj pravila temperatura), smetamo akciju koja inkremetira promenljivu temp, ako je vrednost temperature > 12. Vrednosti broja pristupamo preko meta-promenljive $3 (jer elimo da proitamo vrednost uz token _INT koji se nalazi na 3-oj poziciji na desnoj strani pravila). Ispis broja dana se vri iz main funkcije, nakon parsiranja
nam promenljiva u kojoj emo brojati takve dane (promenljiva prepoznavanja tokena svih slogova.

3.6 Vebe
1. Proiriti kalkulator tako da prihvata i linijske komentare. 2. Proiriti kalkulator tako da prihvata i heksa i decimalne brojeve. Uputstvo: u skeneru dodati obrazac koji se prenosi preko funkcije cifara, a u akciji koristiti funkciju

printf

yylval,

0x[a-f0-9]+ za prepoznavanje heksa strtol za konverziju stringa u broj vratiti token NUMBER. Prilagoditi poziv

tako da moe da ispie rezultat i kao decimalni i kao

heksa broj.

3.6.

VEBE

53

3. Proiriti kalkulator operatorima na nivou bita, kao to su 5. Napisati gramatike za svaki od ovih jezika:

AND i OR.

4. Proiriti primer 3 tako da izrauna prosenu temperaturu. (a) Svi nizovi rei da i ne koji sadre isti broj rei da i rei ne (u bilo kom redosledu). (b) Svi nizovi rei da i ne koji sadre duplo vie rei da od ne.

54

POGLAVLJE 3.

BISON

Poglavlje 4

Konikti i njihovo razreavanje

Za sve, osim najjednostavnijih gramatika, korisnik generatora LR parsera treba da oekuje prijavu konikata, kada prvi put propusti gramatiku kroz generator. Ovi konikti mogu biti posledica dvosmislenosti gramatike ili U oba sluaja, konikti se mogu eliminogranienja metode parsiranja.

isati prepravljanjem gramatike ili deklarisanjem prednosti operatora. ini gramatiku i parser manjim i jednostavnijim za odravanje.

Bison

prua mogunost da se prednost operatora opie odvojeno od pravila, to

Veina generatora moe pruiti informacije pomou kojih se moe locirati mesto u gramatici na kom se nalazi problem. Pokretanjem jom (sviem)

-v (verbose ), generie se datoteka name.output.

bison -a sa opciOva datoteka

sadi spisak konikata, kao i opis u kom stanju parsera se desio konikt.

4.1 Primer konikta

Ako prethodnu gramatiku za izraze proirimo operacijama mnoenja, deljenja i unarnim minusom:

e : | | | | | ;

e "+" e e " -" e e "*" e e "/" e " -" e NUMBER

dobiemo dvosmislenu gramatiku. Na primer, ulaz 2+3*4 moe znaiti (2+3)*4 ili 2+(3*4), a ulaz 3-4-5-6 moe znaiti 3-(4-(5-6)) ili (3-4)-(5-6) 55

56

POGLAVLJE 4.

KONFLIKTI I NJIHOVO RAZREA VANJE

i jo mnogo slinih mogunosti. Slika 4.1 pokazuje dva mogua stabla parsiranja za primer

2+3*4.

Slika 4.1: Dva mogua stabla parsiranja za primer

2+3*4

4.2 Razreenje konikta

bison -u, on e nam saoptiti da postoji shift /reduce konikata. To su stanja gde on moe da uradi i shift i reduce akciju (da iftuje token ili da uradi redukciju po nekom pravilu), a
Ako ovakvu gramatiku prosledimo vie ne zna za ta da se odlui. Kada parser parsira prethodni primer prolazi kroz korake prikazane na slici 4.2.

2+3*4

on

Slika 4.2: Primer konikta za izraz

2+3*4

4.2.

RAZREENJE KONFLIKTA

57

Nakon koraka g, parser vidi

(2+3)

po pravilu

oekujui da e

* i moe da uradi redukciju poslednja 3 elementa e : e '+' e, a moe da uradi i iftovanje operatora *, moi kasnije da uradi redukciju po pravilu e : e '*' e.

Problem je nastao zbog toga to

bison -u
a

nismo nita rekli o prioritetu i

asocijativnosti operatora. Prioritet upravlja redosledom izvravanja izraza. Mnoenje i deljenje imaju prednost nad sabiranjem i oduzimanjem, tako da izraz

a+b*c

ima znaenje

a+(b*c),

d/e-f

znai

(d/e)-f.

U bilo kojoj

gramatici izraza, operatori su grupisani u nivoe prioriteta od najnieg ka najviem. Postoje dva nana da se deniu prioritet i asocijativnost u gramatici: implicitno i eksplicitno. Implicitna denicija prioriteta podrazumeva deniciju zasebnih pojmova za svaki nivo prioriteta. Naa gramatika bi u ovom sluaju izgledala:

mul_exp : num_exp "* " num_exp | num_exp " / " num_exp ; num_exp : exp " + " exp | exp " -" exp ; exp
Meutim, eratora.

: NUMBER ;

bison

prua mogunost i eksplicitnog denisanja prioriteta op-

Dodavanjem linija sa listinga 4.1 u prvi deo

bison

specikacije,

saoptavamo parseru kako da razrei konikte. Listing 4.1:

calc4.y

- prioritet operatora

% left PLUS MINUS % left MULTIPLY DIVIDE % right UMINUS

Svaka od ovih deklaracija denie nivo prioriteta, a redosled navoenja

%left, %right,

%nonassoc

declaracija denie redosled prioriteta od na-

jnieg ka najviem. da je

One kau

najniim prioritetom, da su prioritet.

UNIMUS, pseudotoken za unarni minus, desno asocijativan i ima najvii

dodeljuje svakom pravilu prioritet krajnje desnog tokena na desnoj

bison -u
/

da su

levo asocijativni i sa

levo asocijativni i sa viim prioritetom i

Bison

strani pravila. Ako taj token nema pridruen prioritet, ni pravilo nema svoj prioritet. Kada

bison

naie na

shift/reduce

konikt, konsultuje tabelu pri-

oriteta i, ako sva pravila koja uestvuju u koniku imaju dodeljen prioritet, koristi taj prioritet za razreavanje konikta.

58

POGLAVLJE 4.

KONFLIKTI I NJIHOVO RAZREA VANJE

U naoj gramatici, svi konikti se pojavljuju u pravilima oblika

exp,

exp OP

tako da denisanje prioriteta ova 4 operatora omoguuje razreavanje

svih konikata. Parser koji koristi eksplicitne denicije prioritera operatora je malo manji i bri od onog koji sadri dodatna pravila sa implicitnom denicijom prioriteta, jer ima manje pravila za redukciju. Listing 4.2:

calc4.y
{ { { { { { $$ $$ $$ $$ $$ $$

- prioritet pravila

: | | | | | ;

e PLUS e e MINUS e e MULTIPLY e e DIVIDE e MINUS e % prec UMINUS NUMBER

= = = = = =

$1 + $3 ; $1 - $3 ; $1 * $3 ; $1 / $3 ; - $2 ; } $1 ; }

} } } }

Na listingu 4.2 pravilo za negaciju sadri ovom pravilu je Oznaka

- (minus),

%prec UMINUS.

Jedini operator u

koji ima nizak prioritet. Meutim kada ga koris-

timo kao unarni minus, elimo da ima vii prioritet od mnoenja i deljenja.

%prec

kae

bison -u da korisiti prioritet UMINUS za ovo pravilo.

Prioritet operatora treba koristiti u gramatikama koje opisuju izraze. Inae, treba popraviti gramatiku tako da konikt nestane. znai da lena.

bison

Postojanje konikta

ne moe da napravi parser za gramatiku jer je ona dvosmis-

Poglavlje 5

Rukovanje grekama i oporavak

5.1 Rukovanje grekama
Kada bi kompajler trebao da obrauje samo ispravne programe, njegovo osmiljavanje i implementacija bi bili znatno pojednostavljeni. Meutim, programeri esto piu neispravne programe, pa dobri kompajleri treba da pomognu programeru u identikovanju i lociranju greaka. Programi mogu sadrati greke na razliitim nivoima. Na primer, greke mogu biti:

   

leksike (pogreno napisano ime, kljuna re ili operator) sintaksne (logiki izraz sa nepotpunim parom zagrada) semantike (operator primenjen na nekompatibilni operand) logike (beskonaan rekurzivni poziv).

Rukovaoc grekama u parseru ima nekoliko ciljeva:

  

da saopti prisustvo greaka jasno i ispravno da se oporavi od greke dovoljno brzo da bi mogao da detektuje naredne greke da ne usporava bitno obradu ispravnih programa.

U svakoj fazi kompajliranja se moe pojaviti greka, pa zato svaka faza mora postupiti sa grekom tako, da se proces kompajliranja moe nastaviti, sa ciljem detekcije jo novih greaka. Najveim brojem greaka (koje kompajler moe da otkrije) rukuju sintaksna i semantika analiza. 59

60

POGLAVLJE 5.

RUKOV ANJE GREKAMA I OPORAVAK

5.2 Oporavak od greke

Kada parsiranje (zavri program). Ukoliko korisniku to nije dovoljno, mogunost oporavka od greke pomou tokena Specijalni pseudo-token

bison -ov parser detektuje greku, ispie string syntax error i zavri bison nudi
error. error
oznaava mesto oporavka od greke. Kada

parser detektuje greku, on poinje da odbacuje simbole sa steka sve dok ne dostigne mesto gde e

error

token biti validan. Parser odbacuje ulazne Ako parsiranje ponovo detektuje Da bi se

tokene sve dok ne pronae jedan koji moe iftovati u trenutnom stanju i tada nastavlja parsiranje od te take. greku, odbacuje se jo simbola sa steka i jo ulaznih tokena, sve dok ne postane mogu nastavak parsiranja ili dok se stek ne isprazni. izbeglo puno suvinih (neadekvatnih) poruka o grekama, parser, posle prve greke, prestane da prijavljuje poruke sve dok ne uspe da iftuje tri tokena jedan za drugim. U nastavku je dat primer kalkulatora koji detektuje greku unutar izraza, oporavlja se od greke i nastavlja parsiranje (listing 5.1). Ovaj primer nastao je proirenjem prethodnog primera novim pravilom za pojam Listing 5.1:

lines.

calc3.y

lines : | lines NEWLINE | lines e NEWLINE | lines error NEWLINE ;

{ printf ( " % d \ n " , $2 ) ; } { yyerror ( " reenter last line :\ n " ) ; yyerrok ; }

Dodali smo jo jedno pravilo sa tokenom

error.

Pozicija ovog tokena opisuje

pojavu bilo kakve sintaksne greke unutar linije, pre karaktera za novi red. Ukoliko se na ulazu pojavi greka, parser e uraditi redukciju po ovom pravilu, i u naem sluaju, ispisati poruku korisniku da ponovo unese izraz. Nakon novog unosa, parser nastavlja sa parsiranjem. Za ispis greke koristi se funkcija Makro

yerror().

yyerrok u akciji kae parseru da je oporavak zavren i da se naredne

poruke o grekama mogu prijavljivati. U cilju detekcije to vie greaka mogue je dodati puno pravila koja opisuju greke, ali u praksi retko postoji vie od nakoliko pravila sa grekama.

Listinzi
2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 2.11 2.12 2.13 2.14 2.15 2.16 2.17 2.18 2.19 2.20 3.1

zero.l njam.l num.l ws.l

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11 13 13 14 14 15 15 16 18 18 18 19 20 21 22 22 23 24 25 26 35

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

lines.l test.txt words.l return.l union.l union.l wclc.l

- unija . . . . . . . . . . . . . . . . . . . . . . . . . . - pravila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

union.l - main() wsdot.l

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

comments.l out.c cmd.l date.l text.l

test-comment.c 2to10.l

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

calc1.l

62

LISTINZI

3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15 3.16 4.1 4.2 5.1

calc1.y calc2.y count1.l count1.y count2.l count2.y count3.y count4.l count4.y count4.y date.l date.y

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36 37 41 41 42 43 44 45 45 46 46 47 48 50 51 57 58 60

Gramatika teksta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . - modikacija - pravila - pravilo . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . .

sentence

. . . . . . . . . . . . . . . . . .

- male zagrade . . . . . . . . . . . . . . . . . . . . . - tokeni . . . . . . . . . . . . . . . . . . . . . . . . . - pravilo

words

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . - prioritet operatora . . . . . . . . . . . . . . . . . .

meteo.l meteo.y calc4.y calc4.y calc3.y

- prioritet pravila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Slike
1.1 Stablo parisiranja za izraz

1*2+3*4+5

. . . . . . . . . . . . . .

2.1 2.2

Korienje

ex -a

. . . . . . . . . . . . . . . . . . . . . . . . .

8 16

Komunikacija izmeu skenera i parsera . . . . . . . . . . . . .

3.1 3.2 3.3 3.4 3.5 3.6

Korienje

bison -a

. . . . . . . . . . . . . . . . . . . . . . . .

30 34 34 35 38 39

Stablo parsiranja za izraz Stablo parsiranja za ulaz

2+3

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2+3\n

Deo stabla parsiranja za izraz

2+3-4+5

Prenoenje vrednosti simbola iz skenera u parser Primer rada parsera za ulaz

1+2\n

. . . . . . . . . . . . . . .

4.1 4.2

Dva mogua stabla parsiranja za primer Primer konikta za izraz

2+3*4

. . . . . . . .

56 56

2+3*4

. . . . . . . . . . . . . . . . .

63

Indeks
.l, 7 .output, 55 funkcije noyywrap, 12 yywrap(), 9 opcije, 8 noyywrap, 9, 12 yylineno, 9 promenljive yylineno, 9 yylval, 18 yytext, 15 specikacija, 8, 11 gramatika, 29, 33, 37 dvosmislena, 55 greka leksika greka, 9, 27, 36 sintaksna greka, 29 iskaz, 35 izraz, 3335 konikt razreenje, 55 leksika analiza, 7 leksika greka, 9, 27, 36 leksiki analizator, 7

.y,

30

bison, 30
$$, 38 $1, 38 .y, 30 asocijativnost operatora, 57 opcije -d, 37 -v, 55 oporavak od greke, 60 pravila, 31 prioritet operatora, 57 prioritet operatora, 57

ex

reduce, 39 shift, 39 bison

%union, error,
60

48

.output, 55 parser, 33 specikacija, 30, 31

yyerrok, 60 yyerror(), 37
BNF notacija, 29 deterministiki konani automat, 3 DFA, 3

lex.yy.c,
LR parser

7, 12, 37

ex, 7
.l, 7 64

accept, 30 error, 30 reduce, 30 shift, 30

INDEKS

65

parser, 29, 59 konikt, 55 LR parser, 29 oporavak od greke, 60

reduce, 39 shift, 39
parsiranje, 29 pojam, 33

poetni, 35 rekurzivno pravilo, 34, 35, 40 rukovanje grekama, 59 simbol, 37 sintaksa, 29 sintaksna analiza, 29 sintaksna greka, 29 skener, 7 skeniranje, 7 stablo parsiranja, 29, 3335 token, 16, 17 token

error,

60

unija, 18, 48, 50 yerror(), 60

yyerrok, 60 yyerror(), 37 yylex(), 7

66

INDEKS

Dodatak A

Renik
akcija
C ili C++ kod pridruen obrascu u kaciji. kod pridruene akcije.

ex

specikaciji ili pravilu u

bison

speci-

Kada se u ulaznom nizu prepozna obrazac ili pravilo, izvrava se

ASCII

American Standard Code for Information Interchange ; skup od 128 simbola

koji predstavljaju simbole Amerikog alfabeta: mala slova, velika slova, cifre, znaci interpunkcije i dodatni karakteri za formatiranje.

bison
Program koji prevodi gramatiku, napisanu u posebnom obliku BNF notacije, u LALR(1) parsere. Vidi LALR(1).

BNF

Backus-Naur Form ;
Ulazna sintaksa za

nain predstavljanja kontekstno nezavisnih gramatika. je pojednostavljena verzija BNF-a.

Obino se koriste za specikaciju formalnih gramatika programskih jezika.

bison

dvosmislenost
Dvosmislena gramatika je ona koja sadri vie od jednog pravila ili skupa pravila kojima se moe prepoznati isti ulazni string. U dvosmilsena pravila dovode do pojave ikta. Mehanizam parsiranja, koji

bison-ovoj gramatici, shift/reduce ili reduce/reduce konbison uobiajeno koristi, ne moe da

razrei dvosmislene gramatike. Programer moe da denie prioritet operatora i prioritet pravila da bi razreio konikte, ili da preformulie gramatiku. 67

68

DODATAK A.

RENIK

epsilon
Specijalan sluaj ulaznog stringa sa nula simbola, tj. prazan string.

ex
Program koji generie leksike analizatore (skenere), koji prepoznaju obrasce (denisane regularnim izrazima) u ulaznom tekstu.

gramatika
Skup pravila koji zajedno deniu jezik.

interpreter
Program koji ita program napisan na jeziku visokog nivoa i izvrava ga. Uporedi sa kompajlerom.

jezik
Formalno: denisan skup stringova iz nekog alfabeta, a neformalno: skup instrukcija za opis zadataka koji se mogu izvriti na raunaru.

kompajler
Program koji prevodi program, napisan na jeziku visokog nivoa, na ekvivalentan program na jeziku niskog nivoa. interpreterom. Obino, izlaz iz kompajlera je na mainskom jeziku koji se moe direktno izvravati na raunaru. Uporedi sa

konani automat

Finite automaton ; apstraktna maina koja se sastoji od konanog broja instrukcija (prelaza). Konani automati su korisni za modelovanje uobiajenih raunarskih procesa a imaju i korisna matematika svojstva. prave skenere i parsere na osnovu konanih automata.

Flex

bison

konikt
Greka u

bison

gramatici koja se pojavljuje u situaciji kada se, za isti ulazni Postoji dve vrste

niz tokena, mogu izvriti dve ili vie akcija parsiranja. konikata:

shift/reduce i reduce/reduce. Vidi dvosmislenost. kontekstno nezavisna gramatika Context-free grammar ; gramatika u kojoj svako pravilo ima samo jedan pojam sa leve strane pravila.

LALR(1)

Look Ahead Left to Right ; tehnika parsiranja koju bison obino oznaava da je lookahead limitiran na 1 token. Vidi lookahead.

koristi. (1)

69

leksiki analizator
Program koji konvertuje niz karaktera u niz tokena. Zove se jo i skener ili lekser.

lex
Program koji generie leksike analizatore (skenere). mu je

ex.

Savremeni naslednik

Vidi leksiki analizator.

lookahead
Ulaz koji je proitan od strane parsera ili skenera, ali jo nije prepoznat kao deo obrasca ili pravila.

ex-ovi
U

Bison-ovi

parseri imaju jedan

lookahead

token, dok

skeneri mogu imati neodreeno mnogo ovakvih tokena.

obrazac

ex-ovom

skeneru, obrazac se opisuje pomou regularnih izraza. Skener

pretrauje ulazni tekst da pronae string koji odgovara datom regularnom izrazu, odnosno obrascu.

parsiranje
Proces preuzimanja niza tokena i provere ispravnosti njihovog redosleda.

pojam
Pojmovi (

nonterminals ) su elementi gramatike koji se ne pojavljuju u ulaznom

tekstu nego se deniu pravilima. Vidi i simbol.

poetni pojam
Jedan pojam koji predstavlja cilj parsiranja ulaznog teksta. Pravilo koje na levoj strani ima poetni pojam se zove poetno pravilo.

pravilo
U

bison-u,

pravila su apstraktni opis gramatike. Pravilo ima levu i desnu

stranu, razdvojenu znakom :, dok na kraju pravila stoji znak ;. Na levoj strani se nalazi samo jedan pojam (koji se denie) a na desnoj strani niz simbola i pojmova (koji ga deniu).

prioritet
Redosled u kom se neke odreene operacije vre. Na primer, kada se interpretiraju matematike naredbe, mnoenje i deljenje imaju vii prioritet od sabiranja i oduzimanja. Tako izraz

2+3*4

rezultira vrednou

14

a ne

20.

program

70

DODATAK A.

RENIK

Skup instrukcija koje izvravaju odreeni zadatak.

reduce
Kada se u ulaznom tekstu prepozna niz simbola koji ini desnu stranu nekog pravila, pravila.

bison-ov

parser vri

reduce

akciju, odnosno uklanja elemente koji

obrazuju desnu stranu pravila sa steka i zamenjuje ih pojmom sa leve strane

reduce/reduce konikt
Situacija u kojoj istom nizu tokena odgovaraju dva ili vie pravila. razreava konikt tako to vri deno u gramatici.

reduce

Bison

akciju po pravilu koje je ranije nave-

regularni izraz
Jezik za opisivanje obrazaca koji slue za prepoznavanje niza karaktera.

shift
Akcija u toku parsiranja u kojoj stavlja ga na stek.

bison-ov

parser preuzima ulazni simbol i

shift/reduce konikt
Situacija u kojoj

Shift/reduce
simbol

bison-ov

parser moe da uradi i

shift

reduce

akciju.

konikti se javljaju ili zbog dvosmislenosti gramatike ili je

parseru potrebno vie od jednog ciju da primeni.

Bison, u ovakvoj sitaciji, podrazumevano vri shift

lookahead

tokena da bi odluio koju akakciju.

terminals ) se prepoznaju u skeneru i alju se parseru. Vidi pojam nonterminal ). specikacija Flex specikacija je skup obrazaca po kojima se pretrauje ulazni tekst. Ovakvu specikaciju ex pretvara u skener. stek parsera U bison-ovom parseru, simboli i pojmovi delimino prepoznatog pravila se
Simboli ( (

shift akciju i uklanjaju sa njega kada parser vri reduce tabela simbola
vri

smetaju na interni stek. Simboli i pojmovi se dodaju na stek kada parser akciju.

Struktura podataka koja sadri informacije o imenima koja se pojavljuju u programu (ulaznom tekstu) tako da sve reference na isto ime mogu biti vezane za isti objekat.

71

tokenizacija
Proces konvertovanja niza karaktera u niz tokena. Skener tokenizuje ulazni tekst.

ulaz
Podaci koje ita program. Na primer, ulaz za dok je ulaz za

bison-ov

ex-ov

skener je niz bajtova,

parser niz tokena (dobijenih od skenera).

vrednost
Skener parseru alje token i, opciono, neku semantiku vrednost simbola.

yacc
Yet Another Compiler Compiler ;
predak

bison-a,

program koji generie

parser iz gramatike napisane u (modikovanom) BNF formatu.

72

DODATAK A.

RENIK

Bibliograja
[1] A.V. Aho, R. Sethi, and J.D. Ullman.

and tools.

Compilers, principles, techniques,

Addison-Wesley series in computer science. Addison-Wesley

Pub. Co., 1986. [2] Robert Corbett. Byacc. Technical report, 1990. [3] Stephen C. Johnson. report, 1979. [4] M. E. Lesk and E. Schmidt. Unix vol. ii. chapter Lex - a lexical analyzer generator, pages 375387. W. B. Saunders Company, Philadelphia, PA, USA, 1990. [5] J. Levine. Yacc: Yet another compiler-compiler. Technical

ex & bison.

Oreilly Series. O'Reilly Media, 2009.

[6] Vern Paxson. Flex, http://ex.sourceforge.net/. Technical report, 1987. [7] Richard Stallman. Technical report. Gnu bison, http://www.gnu.org/software/bison/.

73