Kanonski LR analizator ili LR(1) je LR-analizator čije se tabice analize konstruišu slično kao kod LR(0) analizatora osim što ajtemi u ajtem-skupovima takođe sadrže i Sledeći tj. terminal koji analizator očekuje posle desne strane pravila. Skup Sledeći(-{A}-) za dati neterminal -{A}- sadrži sve završne simbole koji se mogu pojaviti neposredno iza simbola -{A}-, bez obzira na kontekst. Na primer, za pravilo -{A → B C}- ajtem bi mogao biti -{A → B · C, a}- što znači da je analizator pročitao nisku kojoj odgovara neterminal -{B}-, da očekuje nisku kojoj odgovara neterminal -{C}- iza koga sledi terminal -{'a'}-. LR(1) analizator može da obradi veoma veliku klasu gramatika, međutim problem je što su često tablice analize jako velike. To se najčešće rešava spajanjem ajtem-skupova ukoliko su identični do na Sledeći. To su onda LALR-analizatori.

Konstruisanje LR(1) analizatora

LR(1)-ajtem se sastoji od LR(0)-ajtema -{A→α•β}- i preduvidnog simbola -{x}- a obično se predstavljaju u obliku -{A→α•β ,x }- Intuitivno, takav ajtem nam govori koliko smo do sada pročitali (α), šta možemo da očekujemo (β), i preduvid koji se slaže sa onim što bi sledilo ukoliko bismo izvršili svođenje po pravilu -{A→α•β}-. Time što smo dodali preduvidnu informaciju pri formiranju ajtema, omogućava nam da donesemo pametniju odluku o svođenju. Preduvid LR(1)-ajtema je direktno koristi jedino kad razmišljamo o akciji svođenja (na primer, kad je metasimbol • sa desnom kraju).

Jezgro LR(1)-ajtema (-{A→α•β ,x }-) je LR(0)-ajtem (-{A→α•β}-). Različiti LR(1)-ajtemi mogu imati isto jezgro, a razlikovati se zbog preduvidnog simbola. Koristimo prednost tog preduvidnog simbola da odlučimo koje svođenje da koristimo. (Jer bi ista situacija kod SLR analizatora možda dovela do svođenje/svođenje konflikta.)

Početni ajtem

Uvodimo početni ajtem -{[S’ → · S, ┤]}-. Oznaka-{ ┤}- označava kraj ulaza.

Pravilo zatvorenja

Ako stanje sadrži ajtem: -{[A → α · B β, a]}- onda su u tom stanju i ajtemi oblika : -{[B → · γ,}- Prvi-{(βα)]}- za svako -{B}--pravilo gramatike.

Pravilo prelaza

Pravilo prelaza je ostalo isto. Ako neko stanje sadrži ajtem: -{[A → α · B β, a]}- tada postoji prelaz po simbolu -{B}- iz stanja koje sadrži taj ajtem u stanje koje sadrži ajtem: -{[A → α B · β, a] }- Akcija prebacivanja

Akcije prebacivanja se takođe nisu menjale. Ukoliko je ajtem -{[A → α · b β, a]}- u stanju -{Ik i Ik}- prelazi u stanje Ij po simbolu 'b', onda dodajemo akciju : -{T[k ,a]}-=(prebacivanje, -{j }-)

Akcija Svođenja

Ukoliko je -{[A → α · , a]}- u stanju -{Ik}-, onda dodajemo akciju (svođenje, -{A→α}-). Primetimo da se više ne koristi informacija iz skupa Sledeci(-{A}-).

Primer

Za gramatiku izraza:

E→E + T |T T→T * F |F F→( E ) |a}-

početni ajtem je: -{S→•E {┤}}-

a graf za skup Prvi: -{ S → E → T → F → (,b}-

tj. Prvi( -{E}- ) = Prvi( -{T}- ) = Prvi( -{F}- ) = { (, -{b}- }

Početni ajtem se nalazi u stanju 0. Primenjujući na njega pravilo zavorenja dobijamo: Stanje 0: -{S→•E {┤}}- -{E→•E+T {┤}}- -{E→•T {┤}}-

Međutim, pravilo zatvorenja se sad primenjuje na dodate ajteme. Time dobijamo da je Stanje 0: -{S→•E {┤}}- -{E→•E+T {┤}}- -{E→•T {+}}- -{E→•E+T {+}}- -{E→•T {┤}}- -{T→•T * F {┤}}-

Ovo i dalje nije potpuno stanje 0, jer se postupak nastavlja sve dok nijedan novi LR(1)-ajtem ne može da se doda stanju 0. Drugim rečima,prva tri stanja izgledaju:

Stanje 0: -{S→•E {┤}}- -{E→•E+T {┤,+}}- -{E→•T {┤,+}}- -{T→•T * F {┤,+,*}}- -{T→•F {┤,+,*}}- -{F→•(E) {┤,+,*}}- -{F→•b {┤,+,*}}- Stanje 1: -{S→E• {┤}}- -{E→E•+T {┤,+}}- Stanje 2: -{E→T• {┤,+}}- -{T→T• * F {┤,+,*}}-

I slično za ostala stanja.

Категорија:Преводиоци (рачунарство)