1 UVOD
Sintaksni analizatorji na podlagi kontekstno neodvisnih
gramatik se večinoma, še zlasti pa pri prevajanju pro-
gramskih jezikov, uporabljajo kot osnova za implemen-
tacijo 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 semantična pravila za izračun
vrednosti atributov. Med sintaksno usmerjenim prevaja-
njem izračunane 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 celo nujno
za njen pravilni potek.
Trenutek izračuna semantičnega pravila je določen z
mestom pravila v produkciji in s samim algoritmom
sintaksne analize. Zato morajo biti semantična pravila
vstavljena na točno določena mesta: če se izračun se-
mantičnega pravila sproži prekmalu, sintaksni analizator
morda sploh še ni prebral vseh za izračun potrebnih
vhodnih simbolov, če pa se sproži prepozno, ne more
podpreti morebitnega reševanja iz napak in/ali povratno
vplivati na sintaksno analizo.
V zadnjem času se je 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 (implicitno zgraje-
nega) 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 formal-
nih jezikov in sintaksne analize, notacija pa je vzeta iz
del Sippuja in Soisalon-Soininena [10], [11]. Od bralca
50 SLIVNIK
se pričakuje poznavanje LL in LR sintaksne analize.
Množica A∗ vsebuje vse nize končne dolžine, ki
so sestavljeni iz elementov množice A. Prazen niz
označimo z ε. Zapisi |w|, wR in wn označujejo dolžino
niza w, obratni niz niza w in n-kratno ponovitev niza,
k:w pomeni prefiks niza w dolžine k (ali kar w če je
|w| ≤ k). Zapis u @ w (oz. u v w) pove, da je niz u
pravi podniz (oz. podniz ali enak) niza w.
Naj končni množici N in T , za kateri velja N∩T = ∅,
vsebujeta vmesne in končne simbole, zaporedoma, in naj
končna množica P ⊂ N×(N ∪T )∗ vsebuje produkcije,
ki jih pišemo v obliki [A −→ α] pri 〈A,α〉 ∈ P . Tedaj
je G = 〈N,T, P, S〉 kontekstno neodvisna gramatika z
začetnim simbolom S ∈ N .
Skrajno leva izpeljava po produkciji [A −→ α]
gramatike G je definirana kot relacija
(=⇒pG,lm) = {〈xAδ, xαδ〉 ; x ∈ T
∗ ∧ δ ∈ (V ∪ T )∗}.
Izpeljava po levi sledi π ∈ P ∗ je definirana kot
(=⇒εG,lm) = idV ∗
(=⇒πpG,lm) = (=⇒
π
G,lm) ◦ (=⇒
p
G,lm)
Če sled izpeljave ni pomembna, v znaku za relacijo
izpeljave po levi sledi uporabimo ∗ namesto imena sledi.
Ekvivalentno definiramo tudi skrajno desno izpeljavo po
produkciji in po desni sledi izpeljave. Jezik kontekstno
neodvisne gramatike G je definiran kot L(G) = {w ∈
T ∗ ; ∃π ∈ P ∗:S =⇒πG,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〉 gra-
matiko Ḡ = 〈N̄ , T, P̄ , S〉 z množico vmesnih simbolov
N̄ = N ∪ {pi ; p = [A −→ α] ∈ P ∧ 0 ≤ i ≤ |α|}
in množico produkcij
P̄ = {[A −→ p0X1p1X2p2 . . . pn−1Xnpn] ;
p = [A −→ X1X2 . . . Xn] ∈ P} ∪
{[pi −→ ε] ; pi ∈ N̄ \N}
Produkcije [pi −→ ε] nastopajo v gramatiki Ḡ na
mestih, kjer lahko nastopajo semantična pravila v gra-
matiki G: v trenutku, ko se med sintaksno usmerjenim
prevajanjem na podlagi gramatike G sproži semantično
pravilo na mestu pi, sintaksni analizator za Ḡ izpiše
produkcijo [pi −→ ε] na izhod. (Ta pristop je v jedru
zelo podoben kontekstno neodvisnim prevodnim grama-
tikam [12], le da kljub preprostejšemu zapisu na tem
mestu povsem zadošča.)
Primer 1: Dana naj bo gramatika G1 s produkcijami
p1 = [S −→ aABb], p2 = [A −→ a] in p3 = [B −→ b].
Pripadajoča gramatika Ḡ1 vsebuje produkcije
p̄1 = [S −→ p1,0 a p1,1Ap1,2B p1,3 b p1,4],
p̄2 = [A −→ p2,0 a p2,1],
p̄3 = [B −→ p3,0 b p3,1] in
p̄i,j = [pi,j −→ ε]
za vse simbole pi,j , ki nastopajo v p̄1, p̄2 in p̄3.
Izhod LL(1) analizatorja za gramatiko Ḡ1 tik pred
pomikom drugega a-ja na sklad vsebuje levo sled
π̄1 = p̄1 p̄1,0 p̄1,1 p̄2 p̄2,0,
v kateri produkcije p̄1,0, p̄1,1, in p̄2,0 povedo, katera se-
mantična pravila in v kakšnem vrstem redu bi se izvedla
med sintaksno usmerjenim prevajanjem, ki bi temeljilo
na gramatiki G1 in sintaksni analizi vrste LL(1). �
Za gramatike brez nekoristnih simbolov lahko takoj
zapišemo naslednje tri ugotovitve:
Trditev 1: L(Ḡ) = L(G). (Dokaz očiten.) �
Trditev 2: ∀k ≥ 0:G ∈ LL(k) =⇒ Ḡ ∈ LL(k).
Dokaz: Noben simbol pi ∈ N̄ \N ne more povzročiti
LL(k) nasprotja, saj zanj obstaja ena sama produkcija.
Predpostavimo, da v Ḡ obstajata produkciji p̄1 in p̄2,
ki obe razvijata isti simbol A ∈ N̄∩N in sta napovedani
na isto vsebino vhodnega okna x. Tedaj se na isti x
prožita tudi izvirni produkciji p1 in p2, kar je v nasprotju
s predpostavko G ∈ LL(k). �
Trditev 3: ∀k ≥ 0:G ∈ LL(k) =⇒ Ḡ ∈ LR(k).
Dokaz: Po trditvi 2 velja Ḡ ∈ LL(k), torej velja tudi
Ḡ ∈ LR(k) ([11], izrek 8.57). �
Kot je omenjeno že 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 G1 iz pri-
mera 1. Hipotetični sintaksni analizator bi lahko takoj
na začetku analize izpisal levo sled p1p2p3, potem pa
svojo napoved preveril tako, kot svoje napovedi preverja
na primer LL(1) analizator. Enak sintaksni analizator
za Ḡ1 bi napovedal levo sled
p̄1 p̄1,0 p̄1,1 p̄2 p̄2,0 p̄2,1 p̄1,2 p̄3 p̄3,0 p̄3,1 p̄1,3 p̄1,4.
A takoj na začetku sintaksno usmerjenega prevajanja,
torej pred branjem prvega a-ja, se lahko izvede le se-
mantično pravilo na mestu produckije p̄1,0 — že pravilo
na mestu p̄1,1 zahteva prvi a (če ga ne, naj ga snovalec
pridruži pravilu p̄1,0). Napoved preostanka je s stališča
sintaksno usmerjenega prevajanja brez smisla. �
Da zagotovimo opis smiselnega prefiksa leve sledi
pri že prebranem prefiksu vhodne besede, definiramo
relacijo skrajno leve izpeljave prefiksa u po produkciji
p = [A −→ α] kot
(=⇒pG,u:lm) = {〈xAδ, xαδ〉 ∈ (=⇒
p
G,lm) ; x v u}
in jo po običajni poti posplošimo še na izpeljave po
levi sledi π. Če je jasno iz konteksta, oznako gramatike
izpustimo.
O OPTIMALNOSTI IZRAČUNA SEMANTIČNIH PRAVIL PO STRATEGIJI OD-ZGORAJ-NAVZDOL 51
Primer 3: Vrnimo se k primeru 2. Tik pred branjem
prvega simbola je prebrani prefiks vhodne besede enak ε.
Najdaljša izpeljava za prefiks ε po gramatiki G1 je
S =⇒p1ε:lm aABb, po gramatiki Ḡ1 pa
S =⇒p̄1ε:lmp1,0 a p1,1Ap1,2B p1,3 b p1,4
=⇒p̄1,0ε:lma p1,1Ap1,2B p1,3 b p1,4,
kar ustreza izvedbi semantičnega pravila na mestu pro-
dukcije p̄1,0.
Podobno velja za veljavni prefiks a. Tik pred po-
mikom drugega a-ja je prebrani prefiks zgolj a, zato
izpeljava po relaciji (=⇒∗a:lm) ustreza ravno levi sledi π̄1
iz primera 1:
S =⇒π̄1a:lm aa p2,1 p1,2B p1,3 b p1,4.
To pomeni, da se bodo izvedla semantična pravila na
mestu produkcij p̄1,0, p̄1,1 in p̄2,0, za kaj več pa mora
sintaksni analizator prebrati naslednji a z vhoda. �
Predpostavimo, da je sintaksni analizator že prebral
prefiks u, niz z dolžine k pa je v vhodnem oknu. Leva
sled izpeljave poljubne vhodne besede, ki se začne s
prefiksom uz, se lahko začne s katerokoli levo sledjo iz
množice
Πu,z =
{
πu ; S =⇒πuu:lm uδ ∧ z ∈ FIRSTk(δ)}.
To pomeni, da lahko ob prebranem prefiksu u in vsebini
vhodnega okna z izhod sintaksnega analizatorja vsebuje
kvečjemu najdaljši skupni prefiks
πu,z = max {π ∈ P ∗ ; ∀πu ∈ Πu,z:πu v π}
vseh levih sledi iz množice Πu,z . Če bi vseboval daljšo
levo sled od πu,z , bi to lahko pri nekaterih sufiksih v,
pri z v v, vodilo do napak.
Zato pravimo, da sintaksni analizator z vhodnim
oknom dolžine k optimalno izpiše levo sled izpeljave
po gramatiki G natanko tedaj, ko njegov izhod za vsak
prefiks u poljubne vhodne besede w = uv ∈ L(G)
vsebuje prefiks πu,z pri z = k:v.
Definicija optimalnosti izpisa leve sledi izpeljave se-
veda ni vezana zgolj na LL gramatike in sintaksno
analizo vrste LL.
Primer 4: Vzemimo gramatiko G4 6∈ LL s produk-
cijami [S −→ Ab], [A −→ Aa] in [A −→ a]. Za vsak
i ≥ 0 obstaja izpeljava
S =⇒[S−→Ab]a:lm Ab =⇒
[A−→Aa]i
a:lm Aa
ib =⇒[A−→a]a:lm a
i+1b,
kar pomeni, da velja
Πan,a = {[S −→ Ab][A −→ Aa]i[A −→ a] ; i ≥ n}
in
πan,a = [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 πan,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 pripadajočo gramatiko Ḡ, kar pomeni, da lahko
na podlagi te definicije ocenimo ustreznost posameznega
sintaksnega analizatorja za izračun semantičnih pravil.
4 OCENA RAZLIČNIH METOD
IZRAČUNA LEVE SLEDI
4.1 Sintaksna analiza vrste LL
LL analiza je standardni postopek za izračun 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 =⇒πulm uAδ =⇒
[A−→α]
lm uαδ =⇒
πv
lm uv = w,
vsebuje izhod sintaksnega analizatorja vrste LL(k) v
trenutku, ko je prebran prefiks u in je niz k:v v vhodnem
oknu, levo sled πu ([11], lemi 8.32 in 8.33). Povedano
drugače, vsakič, ko je simbol A na vrhu sklada LL anali-
zatorja, ta napove in izpiše produkcijo [A −→ α]; izhod
zato vsebuje levo sled πu[A −→ α].
Ker w ∈ T ∗, obstaja taka izpeljava gornje oblike, da
velja bodisi α = aα′ pri a ∈ T bodisi αδ = ε. Tedaj
velja πu,z = πu[A −→ α] pri z = k:v.
LL analizator torej vedno optimalno izpiše levo sled.
To je seveda pričakovano, saj je dobro znano, da se pri
LL analizi vsako semantično pravilo izvede v trenutku,
ko sintaksna analiza doseže njegovo mesto v gramatiki.
4.2 Schmeiser-Barnardov analizator vrste LR
Kot odgovor na znane težave LL analize z levo
rekurzijo sta Schmeiser in Barnard leta 1995 predstavila
sintaksni analizator, ki temelji na LALR analizi, a kljub
temu izračuna levo sled izpeljave [3], njun pristop pa
deluje tudi za LR analizo.
Schemiser-Barnardov LR analizator na vsakem ko-
raku skupaj z LR stanjem, ki ustreza veljavnemu prefi-
ksu γX , na sklad potisne še levo sled izpeljave podniza,
ki se v vhodni besedi razvije iz simbola X:
• ko LR analizator v stanju [γ] opravi pomik simbola
a ∈ T , na sklad potisne [γa]ε;
• ko LR analizator v stanju [γ] opravi prevedbo po
produkciji [A −→ X1X2 . . . Xn], s sklada umakne
skladovni niz [X1]π1 [X2]π2 . . . [Xn]πn in na sklad
potisne
[γA][A−→X1X2...Xn]π1 π2 ... πn .
Primer 5: Vzemimo gramatiko G5 s produkcijami
[S −→ AB], [A −→ a], [A −→ Aa], [B −→ b] in
[B −→ bB]. Sintaksna analiza niza aabb ∈ L(G5) s
Schmeiser-Barnardovim LR(1) analizatorjem je prika-
zana v tabeli 1. �
LR analiza deluje po strategiji od-spodaj-navzgor,
zato je zadnja prevedba, ki jo opravi LR analizator,
52 SLIVNIK
SKLAD VHOD AKCIJA
$ [ε] aabb $ pomik a ε
$ [a]ε abb $ prevedba [A −→ a]
$ [A][A−→a] abb $ pomik a
$ [A][A−→a] [Aa]ε bb $ prevedba [A −→ Aa]
$ [A][A−→Aa][A−→a] bb $ pomik b
$ [A][A−→Aa][A−→a] [Ab]ε b $ pomik b
$ [A][A−→Aa][A−→a] [Ab]ε [Abb]ε $ prevedba [B −→ b]
$ [A][A−→Aa][A−→a] [Ab]ε [AbB][B−→b] $ prevedba [B −→ bB]
$ [A][A−→Aa][A−→a] [AB][B−→bB][B−→b] $ prevedba [S −→ AB]
$ [S][S−→AB][A−→Aa][A−→a][B−→bB][B−→b] $ izpis [S −→ AB][A −→ Aa][A −→ a][B −→ bB][B −→ b]
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 ana-
lize, iz česar sledi, da Schmeiser-Barnardov analizator
sploh ne izpisuje produkcij leve sledi med analizo in
zato ni sposoben izvajati semantič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 mogoč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 nedeterminističnem LR(k) stroju, po kateri ta
sprejme veljavni prefiks γ in se konča z opisom oblike
[A→ α •β, x] pri z ∈ FIRSTk(βx), se imenuje 〈γ, z〉-
pot. Pri znanem prefiksu u, ki se razvije iz veljavnega
prefixa γ, in vsebini vhodnega okna z, vsaka 〈γ, z〉-pot
določa neko izpeljavo
S =⇒πulm uδ pri z ∈ FIRSTk(δ).
Vse leve sledi πu, ki jih pri znanem prefiksu u določajo
〈γ, z〉-poti, tvorijo množico Πu,z , najdaljši skupni pre-
fiks teh sledi pa je ravno πu,z [4], [9].
Levi LR(k) analizator uporablja avtomat prefiksov
levih sledi [4], s katerim ugotovi, ali za prefiks u in vse-
bino vhodnega okna z obstaja 〈γ, z〉-pot, ki določa πu,z
(πu,z je lahko namreč prekratka leva sled, ki zato ustreza
neki poti za γ′ @ γ). Če taka 〈γ, z〉-pot obstaja, izračuna
• veljavni sufiks δR in
• prefiks leve sledi πu,z .
Tega izpiše, a obenem pazi, da že v prejšnjih korakih
izpisanega dela prefiksa leve sledi πu,z ne izpiše še
enkrat. Če taka pot ne obstaja, potem uporabi Schmeiser-
Barnardov pristop začasnega hranjenja delov leve sledi
na skladu.
Primer 6: Leva LR(1) analiza niza aabb ∈ G5 je
prikazana v tabeli 2. Na začetku analize je analizator
SKLAD VHOD IZHOD
$ [ε] aabb $ [S −→ AB]
$ [a]ε abb $
$ [A][A−→a] abb $
$ [A][A−→a] [Aa]ε bb $ [A −→ Aa][A −→ a]
$ [A] bb $
$ [A] [Ab] b $ [B −→ bB]
$ [A] [Ab] [Abb] $ [B −→ b]
$ [A] [Ab] [AbB] $
$ [A] [AB] $
$ [S] $
Tabela 2: Sintaksna analiza vhodnega niza aabb po grama-
tiki G5 z levim LR(1) sintaksnim analizatorjem (akcije so
enake kot v tabeli 1).
v stanju [ε], ki vsebuje veljavne LR(1) opise
[S′ → •S, $], [S → •AB, $],
[A→ •a, b], [A→ •Aa, b],
[A→ •a, a], [A→ •Aa, a].
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 [a] z opisoma
[A→ a•, a] in [A→ a•, b].
Če bi bil v vhodnem oknu simbol b, bi obstajala enolična
pot nazaj do opisa [S′ → •S, $] ∈ [ε]. Za simbol a v
vhodnem oknu obstajata vsaj dve različni poti (ena preko
opisa [A→ •Aa, a] ∈ [ε], druga pa ne) in zato vsaj dva
različna prefiksa leve sledi vhodnega niza aabb.
Ko levi LR(k) analizator potisne prvi a na sklad,
izhod vsebuje zgolj [S −→ AB], čeprav bi (po analogiji
s primerom 4) moral vsebovati
πa,a = [S −→ AB][A −→ Aa].
Leva LR analiza torej ni optimalna. �
O OPTIMALNOSTI IZRAČUNA SEMANTIČNIH PRAVIL PO STRATEGIJI OD-ZGORAJ-NAVZDOL 53
4.4 Sintaksna analiza vrste ALL(∗)
Sintaksna analiza vrste ALL(∗) se od predhodno
obravnavanih metod loči po tem, da ne uporablja vho-
dnega okna vnaprej določene dolžine. 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 zasluži vsaj kratko obravnavo.
Osnovno razlago sintaksne analize vrste ALL(∗) naj
si bralec ogleda v delu [14], njeno konkretno implemen-
tacijo 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 be-
sedo abbbbccc ∈ L(G7) sintaksna analiza vrste ALL(∗)
izpiše sled izpeljave
[S −→ A][A −→ aBbC]
[B −→ b][B −→ Bb][B −→ Bb]
[C −→ c][C −→ Cc][C −→ Cc],
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 Ḡ4 pa ni primerna za ALL(∗) ana-
lizo. Pri pretvorbi se namreč produkcija p2 = [A −→
Aa] spremeni v produkcijo
p̄2 = [A −→ p2,0Ap2,1 a p2,2],
ANTLR v4.* pa ne more izdelati analizatorja zaradi
vstavljene produkcije [p2,0 −→ ε]. Oziroma, v sintak-
snem analizatorju vrste ALL(∗) za gramatiko G4 ni
mogoče vstaviti semantičnega pravila takoj na začetek
desne strani produkcije p2. �
S primeroma seveda nočemo napadati orodja AN-
TLR v4.*. Vendar je dejstvo, da je vrstni red izračuna
semantičnih 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 članku je predstavljen kriterij za optimalni izpis
leve sledi izpeljave vhodnega niza. Ta upošteva zahteve,
ki nastanejo pri izračunu semantičnih pravil v okviru
sintaksno usmerjenega prevajanja.
Po pričakovanjih sintaksna analiza vrste LL izpolni
ta kriterij (z njo vred pa tudi SLL analiza kot poeno-
stavljena različica LL analize). Preostale obravnavane
vrste sintaksne analize, ki so preimerne za analizo na
podlagi širšega razreda gramatik, se optimalnosti le
bolj ali manj približajo. Schmeiser-Barnardov analizator
se optimalnosti niti ne približ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 najpo-
pularnejše orodje za izdelavo sintaksnih analizatorjev,
ravno tako ne doseže zahtev kriterija. Glavni problem
je precej preprost: ALL(∗) analizator v primeru levo
rekurzivnih produkcij ne izračuna leve sledi izpeljave
(sicer pa razmeroma sproti izpisuje produkcije). Dolžina
vhodnega okna, ki ni vnaprej fiksno določena, ni pro-
blematična.
Na koncu ostaja vprašanje, ali se da levo LR(k)
analizo spremeniti ali dopolniti do te mere, da bi dosegla
optimalnost.