LALR
U računarstvu i informatici LALR parser, što je skraćenica od engl. termina “lookahed LR parser” je poseban oblik LR parsera koji može da izađe na kraj sa više kontekstno slobodnih gramatika nego SLR parser (skraćeno od engl. simple LR parser). LALR parser je vrlo popularan tip parsera zato što pravi dobar kompromis između broja gramatika za koje je primenljiv i veličine tablice sintaksne analize koju zahteva. Kompilatori najčešće koriste ovaj tip parsera, takvi su na primer YACC i GNU bison.
Kao i SLR, LALR таблица синтаксне анализе се добија поправком технике конструкције таблице LR(0) sintaksne analize.
Razlikuju se sledeće potklase {LR} gramatika:
- LR(0), ako su tablice analize formirane bez obzira na preduvidni simbol, a u procesu analize se ne javljaju konflikti;
- SLR(1), ako je konflikte koji se javljaju u LR(0) analizi moguće otkloniti uzimajući u obzir sve skupove Sledeći simbola gramatike;
- LALR(1), ako je konflikte koji su se pojavili u SLR(1) analizi moguće otkloniti ograničavanjem skupova Sledeći samo na one simbole koji su neophodni da bi se izvršila akcija svođenja;
- (kanonska) LR(1) ako je za rešavanje konflikta u LALR(1) analizi potrebno jednoj rečeničnoj formi dodeliti više stanja automata;
Skup Sledeći(A) za zadati nezavršni simbol A sadrži sve završne simbole koji se mogu pojaviti neposredno iza simbola A, bez obzira na kontekst. Priroda konačnog automata kakav je konstruisan za LR(0) ajteme je takva da se ne zahteva poznavanje svih simbola koji mogu slediti za nekim simbolom A. Dovoljno je poznavati skup onih završnih simbola koji se mogu pojaviti na ulazu kada se izvrši svođenje po nekom A pravilu. U takvom slučaju skup relevantnih preduvidnih simbola je podskup skupa Sledeći(A) koji ćemo nazvati Preduvidni skup.
Preduvidni skup za pomoćni simbol A se konstruiše tako što se u konačnom automatu posmatraju samo oni završni simboli koji se mogu pojaviti iza A neposredno posle akcije svođenja na A. U slučaju pojave konflikta prebacivanje-svođenje, za njegovo razrešavanje su od značaja samo one sekvencije u ajtemima koje su oblika:
•Aa
gde je a neki završni terminal. Analizom ovih sekvencija omogućava se da konačni automat može da prepozna da li je potrebno izvršiti svođenje ili ne.
Dakle, dok SLR korsti skupove Sledeći za određivanje akcija svođenja, LALR koristi preduvidne skupove. Kako je za dati LR(0) ajtem I, skup Sledeći(I) u stvari unija svih Preduvidnih skupova za sve LR(0) ajteme sa istom levom stranom kao I, i kao takav nezavisan od stanja parsera i desne strane ajtema, pa time ne nosi informacije o kontekstu. Sa druge strane skup Preduvidni u zavisnosti od konteksta omogućava finije razrešavanje konflikata.
Konstrukcija LALR(1) se može izvršiti tako što se prvo konstruiše SLR(1) automat kome se zatim dodaju preduvidni simboli. Oni se dodaju tako što se identifikuju simboli koji prate jedan ajtem. U slučaju svođenja, ti simboli imaju ulogu skupa Sledeći u slučaju SLR(1) analize. Ovakva konstrukcija je efikasnija od konstruisanja kanonskog LR(1) automata, a zatim stapanja njegovih stanja.
Primer
uredi- Neka na ulazu imamo nisku { a + b = c ; } EOF
- Počinjemo postavljajući stanje 0 na vrh steka.
- Evo kako LALR parser izlazi na kraj sa njom:
| stanja na steku | ajtemi | akcija | preostali ulaz |
| 0 | program → • { naredbe EOF } | prebacivanje | { a = b + c ; } EOF |
| 1 0 | program → { • naredbe EOF }
naredbe → • naredba naredbe naredbe → • e naredba → • ID=izraz naredba → • IF izraz |
prebacivanje | a = b + c ; } EOF |
| 4 1 0 | naredba → ID • = izraz | prebacivanje | = b + c ; } EOF |
| 8 4 1 0 | naredba → ID = • izraz
izraz → • izraz + ID izraz → • izraz - ID izraz → • ID |
-prebacivanje- | b + c ; } EOF |
| 12 8 4 1 0 | izraz → ID • | svedi po 8 | + c ; EOF |
| 11 8 4 1 0 | naredba → ID = izraz •
izraz → izraz • + ID izraz → izraz • - ID |
prebacivanje | + c ; } EOF |
| 15 11 8 4 1 0 | izraz → izraz + • ID | prebacivanje | c ; } EOF |
| 18 15 11 8 4 1 0 | izraz → izraz + ID • | svedi po 6 | ; } EOF |
| 11 8 4 1 0 | naredba → ID = izraz • ;
izraz → izraz • + ID izraz → izraz • - ID |
prebacivanje | ; } EOF |
| 14 11 8 4 1 0 | naredba → ID = izraz ; • | svedi po 4 | } EOF |
| 3 1 0 | naredbe → naredba • naredbe
naredbe → • naredba naredbe naredbe → e • naredba → • ID = izraz naredba → • IF ( izraz ) |
svedi po 3 | } EOF |
| 7 3 1 0 | naredbe → naredba naredbe • | svedi po 2 | } EOF |
| 2 1 0 | program → { naredbe EOF • } | prebacivanje | } EOF |
| 6 2 1 0 | program → { naredbe • EOF } | prihvati | EOF |
LALR(1) gramatike
urediFormalna definicija LALR(1) gramatike ne može se jednostavno upakovati u skup pravila. Umesto formalne definicije, možemo reći da je gramatika LALR(1) ako postoji njoj odgovarajući LALR(1) parser sa odsustvom konflikta, i obrnuto. LALR(1) je potklasa od LR(1) i natklasa od SLR(1). Gramatika koja nije LR(1) definitivno nije ni LALR(1), jer koji god konflikt da je prisutan za originalni LR(1) parser, biće prisutan i za LALR(1) parser. Gramatika koja je LR(1) može ali ne mora biti LALR(1) u zavisnosti od toga da li stapanje proizvodi konflikte ili ne. Gramatika koja je SLR(1) je definitivno i LALR(1). Gramatika koja nije SLR(1) može i ne mora biti LALR(1) u zavisnosti od toga da li precizniji Preduvidni skupovi razrešavaju SLR(1) konflikte.
LALR(1) parser se pokazao kao najčešća varijanta familije LR parsera. Slabosti SLR(1) i LR(0) parsera su u tome što su sposobni da izađu na kraj sa relativno malim skupom gramatika. Ekspanzivne memorijske potrebe LR(1) parsera učinile su da je godinama bio teoretski interesantan ali postepeno praktično sve približniji. Prednost LALR(1) parsera ogledala se u tome što je ponudio dobar balans između moći skupova Preduvida i veličine tablice sintaksne analize. Većina konstrukcija nad programskim jezicima može biti opisana LALR(1) gramatikom.
Literatura
uredi- Vitas, Duško M., „Prevodioci i interpretatori (Uvod u teoriju i metode kompilacije programskih jezika )“, Matematički fakultet, Beograd 2006.
- [1] LALR Parsing, written by Maggie Johnson and revised by Julie Zelenski and Keith Schwarz, July 11, 2012