Elektrotehniški vestnik 85(1-2): 49-53, 2018 Izvirni znanstveni članek
O optimalnosti izračuna semantičnih pravil po strategiji od-zgoraj-navzdol
Boštjan Slivnik
Univerza v Ljubljani, Fakulteta za računalništvo in informatiko, VeČina pot 113, 1000 Ljubljana, Slovenija E-pošta: bostjan.slivnik@fri.uni-lj.si
Povzetek. Pri implementaciji sintaksno usmerjenega prevajanja na podlagi kontekstno neodvisnih gramatik pogosto stremimo k (implicitni) gradnji drevesa izpeljav po strategiji od-zgoraj-navzdol, pri cemer poddrevesa gradimo rekurzivno od leve proti desni. V primerjavi z drugimi ta strategija omogoča naravnejši zapis semantičnih pravil in učinkovitejše reševanje iz napak, pri teoretični obravnavi sintaksne analize pa ji ustreza izračun leve sledi izpeljave. V tem članku je definiran kriterij za optimalnost izračuna leve sledi izpeljave glede na kolicšino prepletanja izvajanja posameznih korakov sintaksne analize in izpisa posameznih produkcij leve sledi izpeljave; to ustreza izračunu semantičnih pravil. Prepletanje je v določenih primerih čelo nujno potrebno za pravilno delovanje samega sintaksnega analizatorja, hkrati pa pogosto še izboljša reševanje iz napak in tvorjenje smiselnih obvestil o napakah. Kriterij je v članku uporabljen za primerjavo nekaterih najpomembnejših sodobnih algoritmov sinataksne analize, pri čšemer pokazšemo, da le redki algoritmi podpirajo popolno prepletanje.
Ključne besede: sintaksna analiza, leva sled izpeljave, prepletanje izračuna, kriterij optimalnosti
On the optimal top-down evaluation of semantic rules
In syntax-directed translation based on context-free grammars, a top-down construction of a derivation tree, where subtrees are constructed from left to right, is often preferred to other strategies. It makes formulation of semantic rules simpler and provides a better foundation for error recovery. In the parsing theory, it is modelled by computation producing the left parse of the input string derivation. in this paper, a criterion for the optimal printout of the left parse is defined regarding the interleaving of parser actions and printout of individual productions comprising the resulting left parse. in some cases, parsing cannot be done at all without at least some semantic rule evaluation, while in most cases interleaving of parsing and semantic rule evaluation can significantly improve error recovery and the quality of error messages. Finally, the criterion is applied to some of the most important contemporary parsing algorithms. it is shown that not all algorithms support full interleaving.
Keywords: parsing, left parse, computation interleaving, opti-mality critetion
1 Uvod
Sintaksni analizatorji na podlagi kontekstno neodvisnih gramatik se večinoma, se zlasti pa pri prevajanju programskih jezikov, uporabljajo kot osnova za implementacijo sintaksno usmerjenega prevajanja [1]. Za opis le-tega se ponavadi uporabljajo atributne gramatike [1], [2], pri katerih simbolom gramatike pripišemo atribute, v produkcije pa vstavimo semanticna pravila za izracun vrednosti atributov. Med sintaksno usmerjenim prevajanjem izracunane vrednosti atributov sestavljajo prevod.
Prejet 25. oktober, 2017 Odobren 13. december, 2017
Semantična pravila lahko opisujejo zgolj graditev abstraktnega sintaksnega drevesa, lahko pa vsebujejo tudi druge, zahtevnejše izračune. Ti omogočajo boljše reševanje iz napak, lahko pa tudi povratno vplivajo na sintaksno analizo, kar je v nekaterih primerih čelo nujno za njen pravilni potek.
Trenutek izračšuna semantičšnega pravila je določšen z mestom pravila v produkčiji in s samim algoritmom sintaksne analize. Zato morajo biti semantična pravila vstavljena na točno določena mesta: če se izračun semantičnega pravila sprozi prekmalu, sintaksni analizator morda sploh še ni prebral vseh za izračun potrebnih vhodnih simbolov, če pa se sprozi prepozno, ne more podpreti morebitnega reševanja iz napak in/ali povratno vplivati na sintaksno analizo.
V zadnjem času seje pojavilo nekaj novih algoritmov sintaksne analize [3], [4], [5], [6], [7], [8], [9], pri katerih tako kot pri LL analizi vrstni red izračuna semantičnih pravil ustreza obhodu (impličitno zgrajenega) drevesa izpeljav po strategiji od-zgoraj-navzdol (in od-leve-proti-desni), le da vsi presegajo desetletja staro omejitev na LL gramatike. Ponavadi se avtorji pri primerjavi osredotočijo na razred gramatik, za katere so posamezni algoritmi primerni, v tem delu pa nas bo zanimala primerjava glede na fleksibilnost izračuna se-mantičšnih pravil med samim potekom sintaksne analize.
2 Osnovni pojmi in notacija
Uporabljeno je uveljavljeno izrazoslovje teorije formalnih jezikov in sintaksne analize, notačija pa je vzeta iz del Sippuja in Soisalon-Soininena [10], [11]. Od bralča
se pričakuje poznavanje LL in LR sintaksne analize.
Množica A* vsebuje vse nize končne dolZine, ki so sestavljeni iz elementov množice A. Prazen niz označimo z e. Zapisi |w|, wR in wn označujejo dolzino niza w, obratni niz niza w in n-kratno ponovitev niza, k:w pomeni prefiks niza w dolzine k (ali kar w če je |w| < k). Zapis u c w (oz. u C w) pove, da je niz u pravi podniz (oz. podniz ali enak) niza w.
Naj končni mnoziči N in T, za kateri velja NnT = 0, vsebujeta vmesne in končne simbole, zaporedoma, in naj končna mnoziča P C N x (N U T)* vsebuje produkčije, ki jih pišemo v obliki [A —> a] pri (A, a) G P. Tedaj je G = (N, T, P, S) kontekstno neodvisna gramatika z začetnim simbolom S G N.
Skrajno leva izpeljava po produkčiji [A —> a] gramatike G je definirana kot relačija
(=^G,im) = {(xA5, iai) ; x G T * A 5 G (V U T )*}. Izpeljava po levi sledi n g P * je definirana kot
(=^G,lm) =idV *
(=^G?lm) = (=^G,lm) ° (=^G,lm)
Ce sled izpeljave ni pomembna, v znaku za relačijo izpeljave po levi sledi uporabimo * namesto imena sledi. Ekvivalentno definiramo tudi skrajno desno izpeljavo po produkčiji in po desni sledi izpeljave. Jezik kontekstno neodvisne gramatike G je definiran kot L(G) = {w G T * ; 3n G P *: S =^£,lm w}.
3 Kriterij optimalnosti
Da premostimo razliko med teoretično obravnavo sin-taksne analize in sintaksno usmerjenim prevajanjem, definiramo na podlagi gramatike G = (N, T, P, S) gramatiko G = (N, T, P, S) z mnozičo vmesnih simbolov
N = N U {pi ; p = [A —> a] G P A 0 < i < |a|} in mnozšičo produkčij
P = {[A -> PoXIPIX2P2 . . .Pn-iX„p„] ;
p = [A XiX2 ...!„] G P} U {[pi e] ; pi G N \ N}
Produkčije [pi —> e] nastopajo v gramatiki G na mestih, kjer lahko nastopajo semantičšna pravila v gramatiki G: v trenutku, ko se med sintaksno usmerjenim prevajanjem na podlagi gramatike G sprozši semantičšno pravilo na mestu pi, sintaksni analizator za G izpiše produkčijo [pi —> e] na izhod. (Ta pristop je v jedru zelo podoben kontekstno neodvisnim prevodnim gramatikam [12], le da kljub preprostejšemu zapisu na tem mestu povsem zadošča.)
Primer 1: Dana naj bo gramatika G1 s produkčijami
p1 = [S —> aABb], p2 = [A —> a] in p3 = [B —> b].
Pripadajoča gramatika Gi vsebuje produkčije
p>i = [S —> pi,o api,i Api,2 Bpi,3 bpi,4], p2 = [A —> p2,0 ap2,i], p3 = [B —>• p3,0 bp3,i] in pij = [pi,j —> e]
za vse simbole pi,j, ki nastopajo v p, p2 in p3.
Izhod LL(1) analizatorja za gramatiko Gi tik pred pomikom drugega a-ja na sklad vsebuje levo sled
ni = pi pi,o p>i,i p2 p2,0,
v kateri produkčije p^o, ^i,i, in p2,0 povedo, katera se-mantičšna pravila in v kaksšnem vrstem redu bi se izvedla med sintaksno usmerjenim prevajanjem, ki bi temeljilo na gramatiki Gi in sintaksni analizi vrste LL(1). □ Za gramatike brez nekoristnih simbolov lahko takoj zapisšemo naslednje tri ugotovitve: Trditev 1: L(G) = L(G). (Dokaz očiten.)	□
Trditev 2: Vk > 0: G G LL(k) G G LL(k). Dokaz: Noben simbol pi G N \ N ne more povzročiti LL(k) nasprotja, saj zanj obstaja ena sama produkčija.
Predpostavimo, da v G obstajata produkčiji 5 in p2, ki obe razvijata isti simbol A g NnN in sta napovedani na isto vsebino vhodnega okna x. Tedaj se na isti x prozita tudi izvirni produkčiji pi in p2, kar je v nasprotju s predpostavko G g LL(k).	□
Trditev 3: Vk > 0: G G LL(k) G G LR(k). Dokaz: Po trditvi 2 velja G G LL(k), torej velja tudi G g LR(k) ([11], izrek 8.57).	□
Kot je omenjeno ze v uvodu, se izračun semantičnega pravila ne sme začšeti, dokler sintaksni analizator ni prebral vseh vhodnih simbolov, katerih atributi nastopajo v pravilu.
Primer 2: Vzemimo ponovno gramatiko Gi iz primera 1. Hipotetični sintaksni analizator bi lahko takoj na začetku analize izpisal levo sled pip2p3, potem pa svojo napoved preveril tako, kot svoje napovedi preverja na primer LL(1) analizator. Enak sintaksni analizator za Gi bi napovedal levo sled
pi pi,0 pi,i p2 p2,0 p2,i p>i,2 p3 p3,0 p3,i pi,3 pi,4.
A takoj na začetku sintaksno usmerjenega prevajanja, torej pred branjem prvega a-ja, se lahko izvede le semantično pravilo na mestu produčkije p^o — ze pravilo na mestu ^i,i zahteva prvi a (če ga ne, naj ga snovaleč pridruzi pravilu p^o). Napoved preostanka je s stališča sintaksno usmerjenega prevajanja brez smisla. □ Da zagotovimo opis smiselnega prefiksa leve sledi pri ze prebranem prefiksu vhodne besede, definiramo relačijo skrajno leve izpeljave prefiksa u po produkciji p = [A —> a] kot
(=^G>:lm) = {(xA5,xa5) G (=^G,lm) ; X C u}
in jo po običajni poti posplošimo še na izpeljave po levi sledi n. Ce je jasno iz konteksta, oznako gramatike izpustimo.
Primer 3: Vrnimo se k primeru 2. Tik pred branjem prvega simbola je prebrani prefiks vhodne besede enak e. Najdaljša izpeljava za prefiks e po gramatiki G1 je S	aABb, po gramatiki G1 pa
S :
PilmPi,0 api,l Api,2 Bpi,3 bpi,4 ^api,i Api,2 Bpi,3 bpi,4,
£
kar ustreza izvedbi semantičnega pravila na mestu produkcije jŠ1,o.
Podobno velja za veljavni prefiks a. Tik pred pomikom drugega a-ja je prebrani prefiks zgolj a, zato izpeljava po relaciji (=^-lm) ustreza ravno levi sledi n 1 iz primera 1:
S =^a1lm aap2,iPl,2 Bpi,3 bpi,4.
To pomeni, da se bodo izvedla semanticšna pravila na mestu produkcij jš1,0, jš1,1 in p2,0, za kaj več pa mora sintaksni analizator prebrati naslednji a z vhoda. □ Predpostavimo, da je sintaksni analizator ze prebral prefiks u, niz z dolzine k pa je v vhodnem oknu. Leva sled izpeljave poljubne vhodne besede, ki se zacšne s prefiksom uz, se lahko začne s katerokoli levo sledjo iz mnozšice
n
{n
S
u:lm
uJ A z G FIRSTk(J)}.
S
[S—^Ab] a:lm
A6:
>[A—
a:lm
Aa]
Aa*b =
JA-
.:lm
^a] ai+i
b,
kar pomeni, da velja
nan,a = {[S Ab][A

a] ; i > n}
in
[S Ab][A Aa]n.
Skratka, ko je analizator prebral an in je v vhodnem oknu a, se leva sled izpeljave vhodnega niza gotovo začne s nan,a. A ker je na vhodu lahko beseda amb
pri m > n +1, analizator še ne sme izpisati produkcije [A a].	□
Definicija optimalnega izpisa leve sledi seveda velja tudi za pripadajoco gramatiko G, kar pomeni, da lahko na podlagi te definicije ocenimo ustreznost posameznega sintaksnega analizatorja za izracšun semanticšnih pravil.
4 Ocena različnih metod
izračuna leve sledi
4.1 Sintaksna analiza vrste LL
LL analiza je standardni postopek za izracun leve sledi izpeljave [13], [11]. Osnovni rezultat LL analize pravi, da pri analizi vhodnega niza w = uv, za katerega po gramatiki G obstaja izpeljava
S

[Alm
>a]
uaJ
lm
w,
To pomeni, da lahko ob prebranem prefiksu u in vsebini vhodnega okna z izhod sintaksnega analizatorja vsebuje kvečjemu najdaljši skupni prefiks
nu,z = max {n G P * ; W„ G n„,z: C n}
vseh levih sledi iz mnoZice nu z. Če bi vseboval daljšo levo sled od nu z, bi to lahko pri nekaterih sufiksih v, pri z C v, vodilo do napak.
Zato pravimo, da sintaksni analizator z vhodnim oknom dolZine k optimalno izpise levo sled izpeljave po gramatiki G natanko tedaj, ko njegov izhod za vsak prefiks u poljubne vhodne besede w = uv g L (G) vsebuje prefiks nu,z pri z = k:v.
Definicija optimalnosti izpisa leve sledi izpeljave seveda ni vezana zgolj na LL gramatike in sintaksno analizo vrste LL.
Primer 4: Vzemimo gramatiko G4 G LL s produkcijami [S —> Ab], [A —> Aa] in [A —> a]. Za vsak i > 0 obstaja izpeljava
vsebuje izhod sintaksnega analizatorja vrste LL(k) v trenutku, ko je prebran prefiks u in je niz k:v v vhodnem oknu, levo sled nu ([11], lemi 8.32 in 8.33). Povedano drugace, vsakic, ko je simbol A na vrhu sklada LL analizatorja, ta napove in izpiše produkcijo [A —> a]; izhod zato vsebuje levo sled nu[A —> a].
Ker w g T*, obstaja taka izpeljava gornje oblike, da velja bodisi a = aa' pri a g T bodisi aJ = e. Tedaj velja nu,z = nu[A —> a] pri z = k:v.
LL analizator torej vedno optimalno izpisše levo sled. To je seveda pricšakovano, saj je dobro znano, da se pri LL analizi vsako semanticšno pravilo izvede v trenutku, ko sintaksna analiza doseze njegovo mesto v gramatiki.
4.2 Schmeiser-Barnardov analizator vrste LR
Kot odgovor na znane tezšave LL analize z levo rekurzijo sta Schmeiser in Barnard leta 1995 predstavila sintaksni analizator, ki temelji na LALR analizi, a kljub temu izracšuna levo sled izpeljave [3], njun pristop pa deluje tudi za LR analizo.
Schemiser-Barnardov LR analizator na vsakem koraku skupaj z LR stanjem, ki ustreza veljavnemu prefi-ksu yX, na sklad potisne še levo sled izpeljave podniza, ki se v vhodni besedi razvije iz simbola X:
•	ko LR analizator v stanju [7] opravi pomik simbola a g T, na sklad potisne [7a]e;
•	ko LR analizator v stanju [7] opravi prevedbo po produkciji [A —> X1X2... Xn], s sklada umakne skladovni niz [X1]ni [X2]n2 ... [Xn]nn in na sklad potisne
[yA][a-
■>XiX2...Xn] ni n2 ... n„
Primer 5: Vzemimo gramatiko G5 s produkcijami [S —> AB], [A a], [A —> Aa], [B —> b] in [B —> bB]. Sintaksna analiza niza aabb g L(G5) s Schmeiser-Barnardovim LR(1) analizatorjem je prikazana v tabeli 1.	□ LR analiza deluje po strategiji od-spodaj-navzgor, zato je zadnja prevedba, ki jo opravi LR analizator,
n
uv
u

a ,a
Sklad Vhod Akcija
$ [ej	aabb $	pomik a e	
$ [aj£	abb $	prevedba [A	—> aj
$ [Aj [A-^aj	abb $	pomik a	
$ [Aj [a—^aj [Aaje	bb $	prevedba [A	—> Aaj
$ [Aj [A-^Aaj[A-^aj	bb $	pomik b	
$ [Aj [A-^Aaj[A-^aj [Abje	b$	pomik b	
$ [Aj [A-^Aa][A-^aj [Abje [Abbje	$	prevedba [B	-- bj
$ [Aj [a-^Aaj[A-^aj [Abje [AbBj[B_^bj	$	prevedba [B	bBj
$ [Aj[A—^Aaj[A—^aj [ABj[B—>bBj[B—>bj	$	prevedba [S	ABj
$ [Sj[S—^ABj[A—^Aaj[A—>aj[B—>bBj[B —>bj	$	izpis [S —>	ABj[A Aaj[A —> aj[B bBj[B bj
Tabela 1: Sintaksna analiza vhodnega niza aabb po gramatiki G5 s Schmeiser-Barnardovim LR(1) analizatorjem.
vedno po produkciji, ki razvija simbol v korenu drevesa izpeljav. Prva produkcija leve sledi izpeljave celotnega vhodnega niza je zato znana šele povsem na koncu analize, iz cesar sledi, da Schmeiser-Barnardov analizator sploh ne izpisuje produkcij leve sledi med analizo in zato ni sposoben izvajati semanticšnih pravil med samo analizo.
Kljub temu, da je tak analizator primeren za vse LR gramatike in je neobčutljiv za levo rekurzijo, o optimalnosti seveda sploh ni mogocše govoriti.
4.3 Leva LR sintaksna analiza
Ker Schmeiser-Barnardov analizator ne more izpisati produkcij leve sledi med potekom analize, je bila leta 2005 definirana leva LR analiza [4].
Pot v nedeterministicnem LR(k) stroju, po kateri ta sprejme veljavni prefiks 7 in se konca z opisom oblike [A — a • xj pri z G FIRSTk(,0x), se imenuje (7, z)-pot. Pri znanem prefiksu u, ki se razvije iz veljavnega prefixa 7, in vsebini vhodnega okna z, vsaka (7, z)-pot dolocša neko izpeljavo
S uJ pri z G FIRSTk(J).
Vse leve sledi nu, ki jih pri znanem prefiksu u dolocajo (7, z)-poti, tvorijo mnozico nuz, najdaljši skupni prefiks teh sledi pa je ravno nu,z [4], [9].
Levi LR(k) analizator uporablja avtomat prefiksov levih sledi [4], s katerim ugotovi, ali za prefiks u in vsebino vhodnega okna z obstaja (7, z)-pot, ki doloca nu,z (nu,z je lahko namrec prekratka leva sled, ki zato ustreza neki poti za 7' \z 7). Ce taka (7, z)-pot obstaja, izracuna
•	veljavni sufiks JR in
•	prefiks leve sledi nu,z.
Tega izpiše, a obenem pazi, da ze v prejšnjih korakih izpisanega dela prefiksa leve sledi nu,z ne izpiše še enkrat. Ce taka pot ne obstaja, potem uporabi Schmeiser-Barnardov pristop zacšasnega hranjenja delov leve sledi na skladu.
Primer 6: Leva LR(1) analiza niza aabb G G5 je prikazana v tabeli 2. Na zacšetku analize je analizator
Sklad Vhod izhod
$ [ej	aabb $	[S -	ABj
$ [aj£	abb $		
$ [Aj [A-^aj	abb $		
$ [Aj [a—^aj [Aaje	bb $	[A -	— Aaj[A —> aj
$ [Aj	bb $		
$ [Aj [Abj	b$	[B -	- bBj
$ [Aj [Abj [Abbj	$	[B -	- bj
$ [Aj [Abj [AbBj	$		
$ [Aj [ABj	$		
$[Sj	$		
Tabela 2: Sintaksna analiza vhodnega niza aabb po gramatiki G 5 z levim LR(1) sintaksnim analizatorjem (akcije so enake kot v tabeli 1).
v stanju [ej, ki vsebuje veljavne LR(1) opise
[S' — •S, $], [S — •AB, $], [A — •a, bj, [A — •Aa, bj, [A — •a, aj, [A — •Aa, aj.
Vsi ti opisi so aktivni za simbol a v vhodnem oknu, zato lahko analizator napove zgolj razvoj simbola S, ne pa tudi razvoja simbola A, saj ne ve, po kateri poti in s tem po kateri produckiji se ta razvije.. Po pomiku prvega a-ja preide v stanje [aj z opisoma
[A — a^, aj in [A — a^, bj.
Cš e bi bil v vhodnem oknu simbol b, bi obstajala enolicšna pot nazaj do opisa [S' — •S, $j g [ej. Za simbol a v vhodnem oknu obstajata vsaj dve razlicni poti (ena preko opisa [A — •Aa, aj G [ej, druga pa ne) in zato vsaj dva razlicšna prefiksa leve sledi vhodnega niza aabb.
Ko levi LR(k) analizator potisne prvi a na sklad, izhod vsebuje zgolj [S —> ABj, ceprav bi (po analogiji s primerom 4) moral vsebovati
na,a = [S -- ABj[A -- Aaj.
Leva LR analiza torej ni optimalna.	□
4.4 Sintaksna analiza vrste ALL(*)
Sintaksna analiza vrste ALL(*) se od predhodno obravnavanih metod loci po tem, da ne uporablja vhodnega okna vnaprej določene dolZine. A ker v osnovi opravi sintaksno analizo vhodnega niza po strategiji od-zgoraj-navzdol, predvsem pa zato, ker na njej temelji trenutno izredno popularno orodje ANTLR v4.* [14], si seveda brez dvoma zasluzi vsaj kratko obravnavo.
Osnovno razlago sintaksne analize vrste ALL(*) naj si bralec ogleda v delu [14], njeno konkretno implementacijo v orodju ANTLR pa v delu [6]. Na tem mestu bomo z dvema primeroma predstavili le za obravnavo izpisa leve sledi pomembni lastnosti ALL(*) analize.
Primer 7: Vzemimo levo rekurzivno gramatiko G7 s produkcijami [S —> A], [A —> aBbC], [B —> Bb], [B b], [C Cc] and [C c]. Za vhodno besedo abbbbccc G L(G7) sintaksna analiza vrste ALL(*) izpise sled izpeljave
[S -	->A][A -	— aBbC]
[B -	- b][B -	Bb][B
[C -	- c][C -	Cc][C -
kar seveda ni leva sled, ustreza pa rezultatu levokotne sintaksne analize vrste XLC(1) ali LAXLC(1) [15], [9].
Primer 8: Vzemimo spet gramatiko G4 iz primera 4. Orodje ANTLR v4.* zgradi sintaksni analizator za to gramatiko, gramatika G4 pa ni primerna za ALL(*) analizo. Pri pretvorbi se namrec produkcija p2 = [A —> Aa] spremeni v produkcijo
P2 = [A —> P2,0 Ap2,l ap2,2],
ANTLR v4.* pa ne more izdelati analizatorja zaradi vstavljene produkcije [p2,0 —> e]. Oziroma, v sintak-snem analizatorju vrste ALL(*) za gramatiko G4 ni mogoce vstaviti semanticnega pravila takoj na zacetek desne strani produkcije p2.	□
S primeroma seveda nocemo napadati orodja ANTLR v4.*. Vendar je dejstvo, da je vrstni red izracuna semanticnih pravil manj pregleden kot pri LL ali LR analizi. Pri zapletenejših gramatikah, kjer se prepletata leva in desna rekurzija, je to lahko za pisca prevajalnika precej neprijetno.
5 Sklep
V tem clanku je predstavljen kriterij za optimalni izpis leve sledi izpeljave vhodnega niza. Ta upošteva zahteve, ki nastanejo pri izracunu semanticnih pravil v okviru sintaksno usmerjenega prevajanja.
Po pricakovanjih sintaksna analiza vrste LL izpolni ta kriterij (z njo vred pa tudi SLL analiza kot poenostavljena razlicica LL analize). Preostale obravnavane vrste sintaksne analize, ki so preimerne za analizo na podlagi širšega razreda gramatik, se optimalnosti le bolj ali manj priblizajo. Schmeiser-Barnardov analizator se optimalnosti niti ne priblizša. Leva LR analiza se
izkaže precej bolje. Levo sled izračuna s prepletanjem postopka sintaksne analize in izračun semantičnih pravil, zatakne pa se pri levo rekurzivnih produkcijah, ko se do izhoda iz leve rekurzije izpis produkcij in s tem izračun semantičnih pravil ustavi.
Algoritem ALL(*), ki ga uporablja trenutno najpopularnejše orodje za izdelavo sintaksnih analizatorjev, ravno tako ne doseze zahtev kriterija. Glavni problem je prečej preprost: ALL(*) analizator v primeru levo rekurzivnih produkčij ne izračuna leve sledi izpeljave (sičer pa razmeroma sproti izpisuje produkčije). Dolzina vhodnega okna, ki ni vnaprej fiksno določena, ni problematična.
Na konču ostaja vprašanje, ali se da levo LR(k) analizo spremeniti ali dopolniti do te mere, da bi dosegla optimalnost.
Literatura
[1]	A. V. Aho, M. S. Lam, R. Sethi, J. D. Ullman, Compilers: Principles, Techniques, & Tools, Addison-Wesley, 2006.
[2]	Z. Fiilop, H. Vogler, Syntax-Directed Semantics: Formal Models Based on Tree Transducers, Springer-Verlag, 1998.
[3]	J. P. Sčhmeiser, D. T. Barnard, "Produčing a top-down parse order with bottom-up parsing", Information Processing Letters, vol. 54, no. 6, pp. 323-326, 1995.
[4]	B. Slivnik, "Produčing the left parse during bottom-up parsing", Information Processing Letters, vol. 96, no. 6, pp. 220-224, 2005.
[5]	E. Sčott and A. Johnstone, "GLL Parsing", Electronic Notes in Theoretical Computer Science, Springer-Verlag, vol. 253, no. 7, pp. 177-189, 2010.
[6]	T. Parr, K. Fisčher, "LL(*): The Foundation of the ANTLR Parser Generator", ACM SIGPLAN Notices, vol. 46, no. 6, 425-436, 2011.
[7]	T. Parr, S. Harwell, K. Fisčher, "Adaptive LL(*) parsing: The power of dynamič analysis", Proc. of the 2014 ACM SIGPLAN Int. Conf. on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA'14), pp. 579-598, 2014.
[8]	B. Slivnik, "LLLR Parsing: a Čombination of LL and LR parsing", Proceedings of the 5th Symposium on Languages, Applications and Technologies (SLATE'16), 2016.
[9]	B. Slivnik, "On different LL and LR parsers used in LLLR parsing", Computer Languages, Systems & Structures, vol. 50, no. Č, pp. 108-126, 2017.
[10]	S. Sippu and E. Soisalon-Soininen, Parsing Theory, Volume I: Languages and Parsing, EATČS Monographs on Theoretičal Computer Sčienče, vol. 15, Springer-Verlag, 1988.
[11]	S. Sippu and E. Soisalon-Soininen, Parsing Theory, Volume II: LR(k) and LL(k) Parsing, EATČS Monographs on Theoretičal Čomputer Sčienče, vol. 20, Springer-Verlag, 1990.
[12]	J. Janousek, B. Meličhar, "The output-store formal translator direčted by LR parsing", Lecture Notes in Computer Science, Springer-Verlag, vol. 1338, pp. 432-439, 1997.
[13]	P. M. Lewis II, R. E. Stearns, Syntax direčted trasndučtion, Proc. of the 7th Annual Symp. on Switching and Automata Theory (SWAT'66), pp. 31-36, 1966.
[14]	T. Parr, The Definitive ANTLR 4 Reference, 2. izdaja, Pragmatič Bookshelf, 2013.
[15]	N. R. Horpsool, Rečursive Asčent-Desčent Parsing, Journal of Computer Languages, vol. 18, no. 1, pp. 1-16, 1993.
Boštjan Slivnik je docent za področje racunalništva in informatike na Univerzi v Ljubljani, kjer je leta 2003 doktoriral. Njegovo osnovno raziskovalno podrocšje so prevajalniki s poudarkom na sintaksni analizi, poleg tega pa se ukvarja tudi s porazdeljenimi sistemi in algoritmi. Od leta 1996 je clan zdruzenja ACM.