Analiza naviše

Analiza naviše (engl. bottom-up parsing) je strategija koja se koristi za analiziranje odnosa između podataka. Prvo se identifikuju osnovne jedinice, a zatim se postepeno, naviše, izgrađuje struktura koja prikazuje odnos između podataka. Ova strategija se primenjuje kako u analizi prirodnih jezika, tako i u analizi programskih jezika. U računarstvu, umesto pojma analize naviše, koristi se i pojam shift – reduce analiza.

Lingvistika

U lingvistici, analiza naviše se koristi u analizi rečenica. Prvo se identifikuju reči u rečenici, a zatim se na osnovu svojstva reči gradi drvo analize koje prikazuje zavisnosti između reči. Izgradnja drveta analize počinje od dna prema vrhu, tj. prema početnom simbolu.

Računarstvo

U računarstvu, analiza naviše se primenjuje u izgradnji kompajlera. Ovaj metod se zasniva na identifikaciji terminalnih simbola koji zatim učestvuju u stvaranju neterminalnih simbola. Rezultati analize se koriste u izgradnji drveta analize programa napisanog na izvornom jeziku. Različiti programski jezici zahtevaju različite tehnike analize, nije neuobičajeno da se u analizi koriste tehnike koje su moćnije od zahtevanih.

U praksi se često koriste analizatori naviše (engl. bottom-up parsers) opšte primene, koji mogu da analiziraju dati jezik ili mogu da generišu analizator za programski jezik koji je zadat svojom gramatikom. Najpoznatiji alati koji generišu analizatore za programske jezike su Yacc i GNU bison.

Primer ilustruje kako se gradi drvo analize

Ovaj trivijalan primer ilustruje razlike u analizi naniže i naviše. Neka je gramatika zadata sa:

S → Ax
A → a
A → b

Za ulaznu nisku ax, najlevlje izvođenje je

S → Ax → ax

To je ujedno i najdešnje izvođenje, obzirom na to da postoji samo jedan neterminal koji se zamenjuje u rečeničnoj formi.

Rad LL(1) analizatora počinje od simbola S, postavlja se pitanje koje će se izvođenje primeniti iz ovog simbola. U ovom slučaju ne postoji konflikt jer postoji samo jedno izvođenje iz početnog simbola. Zatim se poziva metod A (rekurzivna LL analiza) koji treba dalje da poredi ulaz. U ovom slučaju potrebno je razmatrati preduvidni simbol na osnovu kojeg se donosi odluka o pravilu koje će se primeniti u izvođenju. Kako je preduvidni simbol a, tada:

A → a

Analizator prepoznaje a, vraća nazad u S i to je kraj. Drvo izvođenja je sledeće:

  S
 / \
A   x
|
a

U analizi naviše se izvode identični koraci, ali u obrnutom redosledu:

ax → Ax → S

Intuitivno, analizator naniže pokušava da proširi neterminale tako što ih zamenjuje njihovim desnim stranama, dok analizator naviše pokušava da redukuje desne strane tako što ih zamenjuje odgovarajućim neterminalom.

Prva akcija koju će analizator u ovom slučaju primeniti je zamena terminala a neterminalom A. Zatim se Ax zamenjuje sa S. Kada se dobije rečenična forma koja se sastoji samo od simbola S, to znači da je analizator uspešno završio rad.

Kao i kod analize naniže i ovde se možemo poslužiti grubom silom. Odnosno, može se nezavisno od preduvidnog simbola pokušavati sa svođenjem simbola sve dok ne ponestane simbola koji se mogu svesti ili dok ne pojavi rečenična forma koja sadrži samo simbol S. Ovaj algoritam je neefikasan, poznat je kao bektreking. Dakle, može se zaključiti da se uključivanjem preduvidnog simbola znatno smanjuje broj neuspelih pokušaja.

Tipovi analizatora naviše

LR analizator
- SLR (1), (engl. Simple LR) - Koristi jedan preduvidni simbol
- LALR (1), (engl. Lookahead) – Jednostavnija od LR (1), pogodna je za implementaciju. Yacc implementira ovaj jezik
- LR (1) – opštiji jezik od prethodnih, složen je za implementaciju
- LR (n), n je pozitivan ceo broj - Mogu se izgraditi jezici koji zahtevaju n preduvidnih simbola, uobičajeno je da ovakvi jezici zahtevaju veliki broj linija koda i prostora za podatke, pa se iz tih razloga u praksi retko koriste.

Shift-reduce analizatori

Uobičajeni analizatori naviše su shift-reduce analizatori. Njihov rad se zasniva na ispitivanju ulaznog tokena, akcije koje se zatim mogu preduzeti su shift, odnosno prebacivanje tokena na stek, i reduce, odnosno svođene desne strane pravila na odgovarajuću levu.

Action tablice

Action tablice služe za određivanje narednog koraka u radu analizatora. Akcije koje se nalaze u tablici su:

Prebacivanje (engl. shift) - token se postavlja na stek
Svođenje (engl. reduce) - ručka se uklanja sa steka, i zamenjuje odgovarajućim neterminalom
Prihvatenje (engl. accept) – rečenica je prihvaćena, ulazna linija je prazna a na steku se nalazi jedinstveni simbol
Greška (engl. error) - do greške dolazi ukoliko ništa od prethodnog nije moguće uraditi, odnosno ulazna niska tada nije rečenica jezika

Shift – Reduce

Tokom rada analizatora vrše se akcije prebacivanja simbola sa ulaza na stek, kao i akcije svođenja simbola na steku. Ukoliko prefiks simbola na vrhu steka odgovara desnoj strani nekog pravila gramatike, tada se vrši akcija svođenja, odnosno desna strana pravila gramatike sa vrha steka se smenjuje odgovarajućom levom stranom. Postupci prebacivanja i svođenja simbola se ponavljaju sve dok analizator ne završi sa radom. Moguće su dve situacije koje označavaju kraj rada analizatora. U prvom slučaju niska je uspešno prihvaćena, a u drugom slučaju analizator je završio sa radom usled greške koja se pojavila na ulazu.

Uopšteno, analizator predstavlja mehanizam koji upravlja stekom, i koji ima nekoliko diskretnih stanja. U praksi se često na steku čuvaju oznake stanja analizatora umesto simbola gramatike.

Primer shift-reduce analize

Početna rečenična forma je rečenica koja se analizira
Dok se ne pojavi rečenična forma koja je sastoji samo od početnog simbola ponavljaju se sledeći koraci
1. Ulaz se skenira dok se ne prepozna ručka
2. Desna strana pravila se zamenjuje odgovarajućom levom stranom

Analizator čiji se rad zasniva na primenama koraka 2.1 i 2.2 naziva se shift-reduce analizator. U praksi su često implementirani pomoću steka. Dakle, rad shift-reduce analizatora se zasniva na primeni sledećih akcija:

Na početku je stek prazan
Shift akcija odgovara prebacivanju ulaznih simbola na stek
Reduce akcija se primenjuje kada se na vrhu steka nalazi ručka. Tada se ručka skida sa steka, a na stek se postavlja neterminal koji odgovara levoj stani pravila

Primer 1


 Rečenica -> Imenski_deo Glagol

 Imenski_deo -> Pridev Imenica

 Pridev -> lep | veseo | umoran | …

 Glagol -> skače | peva | igra | …

 Imenica -> pas | čovek | dečak | … 


    Neka je ulaz sledeća rečenica: 
    veseo dečak peva 


 Sledeća tabela predstavlja simulaciju rada analizatora naviše:

stek				ulaz			akcija
()				()			
(veseo)				(dečak peva)		shift
(Pridev)			(dečak peva)		reduce
(Pridev dečak)			(peva)			shift
(Pridev Imenica)		(peva)			reduce
(Imenski_deo)			(peva)			reduce
(Imenski_deo peva)		()			shift
(Imenski_deo Glagol)		()			reduce
(Rečenica)			()			uspeh

Primer 2


Izraz --> Term | Term + Izraz

Term --> Faktor | Faktor * Term

Faktor --> [ Izraz] | 0 … 9


stek				ulaz			akcija
()				(2 * [ 1 + 3] )		
(2)				(* [ 1 + 3] )        shift
(Faktor) 			(* [ 1 + 3] )	          reduce
(Faktor * )			([ 1 + 3] )	      shift
(Faktor  * [ )			(1 + 3] )            shift
(Faktor  * [ 1 )		(+ 3] )              shift
(Faktor  * [ Term )		(+ 3] )                 reduce
(Faktor  * [ Term + )		(3] )               shift
(Faktor  * [ Term + 3 )		(] )                  shift
(Faktor  * [ Term + Izraz)	(] )                      reduce
(Faktor * [ Izraz )		(] )                      reduce
(Faktor * [ Izraz] )		()                   shift
(Faktor * Faktor )		()                       reduce
(Faktor * Term )		()                       reduce
(Term )			        ()                       reduce
(Izraz ) 			()                       reduce
(Izraz ) 			()                     uspeh

Razlike u analizi naniže i analizi naviše

U analizi naniže donose se odluke samo o tome koje sledeće pravilo treba primeniti u izvođenju niske nalevo. Tokom analize naviše donose se odluke o tome da li simbol treba da se prebaci na stek ili je potrebno izvršiti redukciju, u slučaju redukcije donosi se odluka o pravilu na osnovu koga će se izvršiti redukcija.