| treba putovati, treba otici tamo gdje ceš biti netko tamo gdje nitko ništa ne zna govoriti neki drugi jezik slušati neke druge glasove kušati neko drugo voce živjeti u drugim legendama |
treba putovati, treba otici izgubiti se na kraju svijeta i sam se vratiti tražiti druge prijatelje lutati nekim drugim ulicama spavati u drugim krevetima u rukama nepoznatima |
treba putovati, treba otici
na putove zemaljske i staze morske promijeniti sat i dan udisati druge mirise opijati se drugim vinima otkriti neke druge ljubavi |
treba putovati, treba otici reci zbogom samome sebi onome što se bilo i vratiti se možda kao iscrpljeni novi bogataš da se umre ili uskrsne tu otkud se otišlo, otišlo, otišlo |
| treba putovati // faut voyager (georges moustaki / zdravko dovedan) |
|||
U ovom je završnom poglavlju opisan jedan jednoprolazni postupak sintaksne analize primjenljiv na svim beskontekstnim i kontekstnim jezicima, te posebno pogodan za ustrojbu na racunalima. Postupak sintaksne analize pociva na definiciji jezika za koji se treba ustrojiti. Temelj definicije jezika sa svojstvima bit ce generator, a ne gramatika.
U prvom dijelu poglavlja definiran je generator jezika sa svojstvima. Potom slijedi opis postupka sintaksne analize jezika sa svojstvima i, na kraju, dani su rezultati usporedbe s ranije opisanim postupcima sintaksne analize beskontekstnih jezika.
Generator u kojem je kontrola konacnog stanja u potpunosti zadana funkcijom prijelaza generira regularne jezike. Drugim rijecima, jezik je regularan ako sadrži recenice:
co=ai. . . an cogI+
za koje vrijedi:
qi=8(q0,ai) q2==8(qi,a2) ••• qk=S(qj,an)
odnosno
qk =8(8(. . .,5 (q0,ai) ,a2) ,.. .,an)
gdje su qi, i=l, ..., k, stanja iz Q, q0 jest pocetno i qk jedno od završnih stanja, qkeF.
Primjer 7.1
Generator zadan dijagramom prijelaza:
gdje je q0=l, F={2}, a skup stanja, rjecnik i funkcija prijelaza vide se iz dijagrama, generira regularni jezik:
L = {(ma)n: m>0, n>0}
Proširenjem znacenja kontrole konacnog stanja generatora regularnih jezika dolazimo do definicije jezika sa svojstvima:
Definicija 7.1
Jezik sa svojstvima jest jezik ciji je generator zadan kao uredena osmorka:
J = (Q,I,V,8,q0,F,a,M)
gdje su:
| Q | konacan skup stanja (kontrole završnog stanja) |
| I | alfabet |
| V | rjecnik, VcX+ |
| 8 | funkcija prijelaza, definirana kao 8: Qxv-»P (Q) gdje je P (Q) particija od Q |
| q0 | pocetno stanje, q0eQ |
| F | skup završnih stanja, FeQ |
| a | skup akcija pridruženih svakom paru (qi, Sj), qieQ, SjgV, za koji je definirana funkcija prijelaza |
| M | pomocna memorija |
Dakle, kontrola završnog stanja generatora jezika sa svojstvima podijeljena je na dva dijela: funkciju prijelaza i skup akcija. Funkcijom prijelaza 8 (primijetiti da je definirana nad rjecnikom) zadaju se sve moguce promjene stanja. Akcija je, opcenito, postupak koji, ovisno o tekucem stanju qi i informacijama dobivenih od pomocne memorije, reducira broj mogucih prijelaza iz stanja qi, zadanih funkcijom 8, u trenutacno ostvarive prijelaze. I ne samo to, akcija može promijeniti vrijednosti funkcije prijelaza. Ako je prijelaz iz stanja qi u stanje qj prijelazom Sk uvijek ostvariv, smatrat cemo da je takvom prijelazu pridružena prazna akcija. Generator regularnih jezika primjer je u kojem su svi prijelazi uvijek ostvarivi. Otuda generator regularnih jezika nema potrebe za pomocnom memorijom.
U ustrojbi generatora jezika sa svojstvima kontrolu konacnog stanja i dalje cemo prikazivati dijagramom (tablicom) prijelaza, ali cemo svakom prijelazu dodati kod njemu pridružene akcije sa znacenjem:
0 (ili izostavljeno) - prazna akcija
1,2,... - neprazna akcija
Kaže se da regularne gramatike generiraju regularne jezike, beskontekstne gramatike beskontekstne jezike, itd. Medutim, to je oprecno s tvrdnjom da je svaka regularna gramatika istodobno beskontekstna, svaka beskontekstna gramatika da je istodobno kontekstna i, konacno, da je svaka kontekstna gramatika istodobno i gramatika bez ogranicenja, jer iz toga slijedi da je svaki regularni jezik istodobno beskontekstan, itd.
Iz definicije jezika sa svojstvima slijedi da ce takvi jezici u pravilu imati neka kontekstna svojstva, pa se postavlja pitanje: Može li beskontekstna gramatika generirati jezik sa svojstvima? Isto pitanje vrijedi i za regularne gramatike.
Odgovor je potvrdan! To ce biti u onim slucajevima kad beskontekstna gramatika u svojim produkcijama sadrži ekplicitno napisane "prave" rekurzije, odnosno, ako se za gramatiku bilo kojeg tipa može napisati niz izvodenja:
X +=> aXf3
a,/3e (jMj<7) *
Tada pomoćna memorija prepoznavača takvog jezika ima strukturu stoga.
Primjer 7.2
Beskontekstna gramatika gt s produkcijama:
E -> E+E | E*E | (E) | a
generira jezik jednostavnih aritmetickih izraza koji moraju zadovoljavati kontekstno svojstvo: broj otvorenih zagrada jednak je broju zatvorenih zagrada. Isto vrijedi i za ekvivalentnu linearnu (tipa 3) gramatiku g2:
E -» aB |(C
B -> *E | +E | S
C -> E)
No, generator jezika L(Qi) , odnosno L (g2), imat ce tablicu prijelaza;
()+•a@1122.....21......__ l;;1
gdje @ oznacuje kraj generiranja, i tablicu akcija:
()+.*a@11000002020003
odnosno, ako tablicu prijelaza i akcija spojimo u jednu u kojoj ce akcije biti prikazane kao eksponenti (prazna je akcija, 0, izostavljena):
()+•a@1l122,2,2,111J
Ako je Tp tablica prijelaza, Ta tablica akcija, R izlazni (generirani) niz, B brojac prijelaza sa " (", akcije su:
1: B 2: B 3: R
- B+r) '; Tp[2,2]=2
= copy (B, 2, 255); IFB=M THEN .Tp[2,2]=0
R +B
Generator napisan kao program u Turbo Pascalu :
PROGRAM Generator artimetickih izraza;
USES Crt;
CONST Mq = 2; Ms = 6;
Tp : ARRAY [l..Mq, l..Ms] OF byte = ( { ( ) + * a 6 } { 1 } ( 1, 0, 0, 0, 2, 0 ), { 2 } ( 0, 0, 1, 1, 0, 1 ) );
Ta : ARRAY [l..Mq, l..Ms] OF byte = ( { ( ) + * a @ } { 1 } ( 1, 0, 0, 0, 0, 0 ) , {2}(0, 2, 0, 0, 0, 3 ) ) ;
VAR
s
: STRING =
0+*a@' ;
B,
R : STRING;
q, k
: byte;
d
: STRING;
Kraj
. boolean;
i
: byte;
PROCEDURE a_l; BEGIN B := B + ')'; Tp [2, 2] := 2 END;
PROCEDURE a_2; BEGIN
B := copy (Bf 2, 255); q := Tp[qf k];
IF B='' THEN Tp[2, 2] := 0
END;
PROCEDURE a 3; BEGIN R := R +B; Kraj := True END;
BEGIN
ClrScr; Randomize;
B := ''; q := 1; R := ,!; Tp[2, 2] := 0; Kraj :== False; REPEAT d := f•; FOR i := 1 TO Ms DO
IF Tp[qf i] <> 0 THEN
d := d +chr (ordl^1) +i) ; k := ord (d[random (length (d)) +1]) -ord('O'); CASE Ta[q, k] OF
1: BEGIN R := R +s[k]; a_l; q := Tp[q, k] END; 2: BEGIN R := R +s[k]; a_2 END;
3: a_3; ELSE BEGIN
R := R +s[k]; q := Tp[qf k] END END UNTIL Kraj; WriteLN (Gen, R); Readln END.
Evo nekoliko primjera generiranih izraza:
( (a*a*a+a*(a)))
(a)
a
(a*(a+a))
(a*a*(a*a+((((a))))))
a*a
(a+a*((a*a)))
(a*(a*(a+a)))
(((a*(((a)))))))
(a+a)
(((((a))))) (a+a)*(a+a)
7.2 PREPOZNAVAC JEZIKA SA SVOJSTVIMA
Kod generatora jezika sa svojstvima akcijom je za svako stanje dijagrama (tablice) prijelaza bio odreden skup ostvarivih prijelaza, što je u svakom trenutku bilo uvjetovano informacijama dobivenim iz pomocne memorije.
U slucaju prepoznavaca jezika sa svojstvima postavlja se pitanje: "Postoji li za simbol Sj€V ostvariv prijelaz iz tekuceg stanja qi u neko stanje qk?". Prvi dio odgovora na ovo pitanje dat ce nam funkcija (tablica) prijelaza. Ako je gk=8 (qif Sj) definirano, prijelaz je moguc, a akcija pridružena paru (qif Sj) odredit ce je li ostvariv.
Opcenito se struktura prepoznavaca jezika sa svojstvima može prikazati kao na sljedecem crtežu:
SI. 7.1 - Model prepoznavaca jezika sa svojstvima.
Zamislit cemo da pomocnu memoriju cine, primitivne i strukturirane varijable, svih tipova, kao što je to, na primjer, u Turbo Pascalu. Inicijalno ce te varijable sadržavati odredene vrijednosti.
Citac je jednostavni pretvoritelj (program leksicke analize) koji prihvaca niz ulaznih znakova, kojima je na kraju dodan znak "@", i prevodi ih u niz simbola. Najcešce ce rjecnik biti jednak alfabetu, pa ce skup simbola biti jednak skupu znakova alfabeta. Svakom simbolu pridružen je jedinstveni cjelobrojni kod, od 1 do k, ako rjecnik sadrži k simbola, te k+1 za znak "@".
Ako je C kôd ucitanog simbola, S tekuce stanje kontrole konacnog stanja i Tp tablica prijelaza, moguci prijelaz Ss zadan je s:
Ss := Tp [S, C]
a akcija kodom na mjestu Ta [ S, C], gdje je Ta tablica akcija.
Tada se kontrola završnog stanja prepoznavatelja jezika sa svojstvima (postupak sintaksne analize) može prikazati sljedecim dijelom programa:
REPEAT
Ucitaj_Sim; Ss := Tp [S, C];IF (C=0) OR (Ss=0) THEN BEGIN
WriteLN ('* Sintaksna pogreška'); Pogreška := TRUE
END ELSE
CASE Ta [S, C] OF
0 : { Prazna akcija } S := Ss;
1 : { Akcija broj 1 };
2 : { Akcija broj 2 };
{ ... }
{N : (* Akcija broj N *) }
END
UNTIL Kraj OR Pogreška;
Najprije ce u posebnoj proceduri biti inicijalizirane varijable programa, tablica prijelaza i tablica akcija. Procedura Ucitaj_Sim ucitat ce tekuci simbol i vratiti njegov kôd, C. Ako je kôd razlicit od 0 i ako je definirano naredno stanje, izvršit ce se odgovarajuca akcija. Akcija može biti prazna, tada se bezuvjetno prelazi u naredno stanje. Neprazna se akcija izvodi u posebnoj proceduri.
Postupak se sintaksne analize nastavlja sve do dosezanja kraja ulaznog niza i njegova prihvacanja ili se prekida ako je ucitan simbol koji nije u rjecniku ili je pronadena sintaksna pogreška.
Primjer 7.3
U dodatku je knjige dan primjer prepoznavaca meta-jezika BNF ciju smo gramatiku definirali na kraju poglavlja posvecenog gramatikama. Ovdje dajemo primjer prepoznavaca jezika jednostavnih artimetickih izraza iz primjera 7.2.
PROGRAM Prepoznavac_aritmetickih__izraza;
USES Crt;
CONST Mq = 2; Ms = 6;
Tp : ARRAY [l..Mq, l..Ms] OF byte = ( { ( ) + * a @ }
{ 1 } ( 1, 0, 0, 0, 2, 0 ),
{ 2 } ( 0, 2, 1, 1, 0, 1 ) );
Ta : ARRAY [l..Mq, l..Ms] OF byte = (
{ ( ) + * a @ }
{ 1 ) ( 1, 0, 0, 0, 0, 0 ),
{ 2 } ( 0, 2, 0, 0, 0, 3 ) );
CONST V : STRING = '()+*a@';
VAR B, Niz : STRING; S, C, i : byte;
Kraj, Pogreska : boolean;
PROCEDURE Inicijalizacija; BEGIN
ClrScr; Randomize; B := ''; S := 1; Tp[2, 2] := 0; Kraj := False; Pogreška := False; i := 0 END;
PROCEDURE Citac; BEGIN
WriteLN ('Unesite ulazni niz:'); ReadLN(Niz); Niz := Niz+'@' END;
PROCEDURE a_l; BEGIN B := B +')'; Tp [2,2} := 2 END;
PROCEDURE a_2; BEGIN B := copy (B, 2, 255); S := Tp[S, C]; IF B='' THEN Tp[2, 2] := 0 END;
PROCEDURE a_3; BEGIN Pogreska := B <> ''; Kraj := True END;
BEGIN
Inicijalizacija; Citac; REPEAT
i := i +1;C := pos (Niz[i], V);
IF (C=0) OR (Tp[S,C]=0) THEN Pogreška := True
ELSE CASE Ta[S, C] OF
0: S := Tp[S, C]; 1: BEGIN a_l; S := Tp[S, C] END;
2: a_2; 3: a_3
END
UNTIL Kraj OR Pogreška;
IF Pogreška THEN BEGIN WriteLN ( ^G, ' ' :i-l,chr(24)); Write ('POGREŠKA, niz nije u jeziku!')
END
ELSE
WriteLN (^M, 'NIZ JE U JEZIKU!'); Readln
END.
U ovom je primjeru rjecnik jednak alfabetu, pa se ulazni niz odmah ucita do kraja i doda mu se simbol "@". Kodovi simbola rjecnika odredeni su inicijalizacijom varijable V, tj. kôd im je pozicija u torn nizu.
Izvodenje dijagrama prijelaza iz produkcija BNF-a
Vidimo da je program sintaksne analize jezika sa svojstvima prilicno jednostavan. Najveci je problem ispravno zadati tablicu prijelaza i akcija, te napisati procedure akcija. Za neke jednostavnije, "školske" primjere beskontekstnih jezika, kao što je bio jezik jednostavnih aritmetickih izraza, to možda i nije teško. Ali, nažalost, u praksi se ne susrecemo s trivijalnim jezicima, pa je izvodenje dijagrama prijelaza prilicno kompleksan problem. Medutim, posebno je interesantno pitanje: Kako iz dane beskontekstne gramatike G izvesti dijagrame prijelaza - generator jezika L(G) ? Jamacno, ne možemo ponuditi konacno rješenje, ali smo mu se pokušali približiti.
Kao ni u slucaju izvodenja gramatike zadanog jezika, ne postoje pravila koja bi nam pomogla da izvedemo odgovarajuce dijagrame prijelaza jezika za koji želimo riješiti problem sintaksne analize upravljan dijagramom prijelaza i akcija. Medutim, izvodenje dijagrama prijelaza može biti znatno olakšano ako nam je za dani jezik poznata bar jedna od ekvivalentnih gramatika. Polazeci od nje poslije niza transformacija može se doci do konacnog dijagrama.
Znamo da se jezik L generiran gramatikom G moze opcenito napisati kao:
L(G)={ ?: ? T*, S+=>? }
a to je skup recenica ? iz T* koje se mogu dobiti izvodenjem iz pocetnog simbola (recenicne forme) S. Svaku recenicnu formu izvedenu iz pocetnog simbola, tako da se uvijek zamjenjivao prvi neterminal slijeva, možemo napisati kao
S +=> xAa x S, AN,a (T N) *
Promatrajuci sva moguca izvodenja recenicnih formi, može se doci do pocetnog dijagrama prijelaza, a daljnjim postupkom njegove transformacije u ekvivalentni konacni dijagram prijelaza. Prije nego što definiramo pravila izvodenja i reduciranja dijagrama prijelaza, proširimo znacenje dijagrama (funkcije) prijelaza generatora jezika sa svojstvima u:
d : Qx(TN) - > P(Q)
tj. proširili smo prijelaze simbolima iz skupa neterminala.
Neka je G=(N,T,P,S) beskontekstna gramatika. Pravila izvodenja dijagrama prijelaza, ovisno o tipu produkcija gramatike G, jesu sljedeca:
i1) Produkcija oblika:
A ->a1a2 . . . ana(TN) *
prevodi e u dijagram prijelaza:
i2) Produkcija oblika:
A -> a1| a2 | . . . |an a(TN)*
prevodi se u dijagram prijelaza:
gdje svaki a ima dijagrame prijelaza prema pravilima i1 do i8.
i3) Produkcija oblika:
A ->a{ß}? a,? (TN)*, ß(TN)+
prevodi se u dijagram prijelaza:
i4) Rekurzija zdesna:
A -> aA | ß a(TN)+, ß(TN)*
Iz konacnog niza izvodenja:
A => aA => aaA =>...=> anA => anß i izravnog izvodenja:
A => ß
što se, prema definiciji praznog niza e, može dalje pisati:
ß => eß = a°ß pa se rekurzija zdesna može napisati kao:
A -> {a}ß
a to je poseban slucaj primjene pravila (i3), pa je, konacno, dijagram prijelaza rekurzije zdesna:
i5) Rekurzija slijeva:
A -> Aa | ß a(TN)+, ß(TN)*
Promatranjem konacnog niza izvodenja, kao i u slucaju rekurzije zdesna, na kraju bi se dobilo:
A ->ß{a}
što je, takoder, poseban slucaj primjene pravila (i3), pa je dijagram prijelaza rekurzije slijeva:
i6) Obostrana rekurzija:
A -> AaA | ß a(TN)+, ß(TN) *
Iz promatranja nekoliko nizova izvodenja:
A => ß A => AaA => ßaA => ßaß
A *=> ßaßaß = ß(aß)2 A *=> ß(aß)3
zakljucujemo da se umjesto produkcije
A -> AaA | ß može napisati:
A -> ß{aß}
pa je odgovarajuci dijagram prijelaza:
i7) Rekurzija:
A -> aAß | ? a, ß(TN)+, ?(TN) *
Kao i u prethodna tri slucaja, promatranjem svih konacnih nizova izvodenja, na kraju bi se dobilo:
A -> an?ßn
pa je dijagram prijelaza prikazan s:
gdje su 1 i 2 kodovi akcija sa znacenjem
1 - brojanje prijelaza sa a
2 - broj prijelaza sa ß; mora biti jednak broju prijelaza sa a
i8) e-produkcije:
A -> a | e a,ß(TN)+
imaju dijagram prijelaza:
Krajnji je cilj dobiti dijagrame prijelaza koji nece sadržavati neterminale kao prijelaze. To znaci da je potrebno eliminirati sve neterminale iz dijagrama supstituirajuci ih njihovim dijagramima. Tako što je dopušteno, jer su dijagrami prijelaza izvedeni iz produkcija ekvivalentni produkcijama gramatike, pa je supstitucija neterminala u njima ekvivalentna supstituciji neterminala u odgovarajucoj recenicnoj formi.
Neka je G=(N, T, P, S) beskontekstna gramatika. Pravila izvodenja konacnog dijagrama prijelaza iz produkcija gramatike G, jesu sljedeca:
p1) Za svaku produkciju iz P izvede se ekvivalentni dijagram prijelaza prema pravilima (i1) do (i7). U njima se oznace samo pocetna i završna stanja.
p2) Pocevši s dijagramom prijelaza pocetnog simbola S, supstituirati neterminale njihovim dijagramima prijelaza sve dok se ne dobije dijagram prijelaza koji ce sadržavati samo simbole iz T.
p3) Reducirati dobiveni dijagram prijelaza, ako je moguce, potom oznaciti stanja (od 1 nadalje).
Pravila supstituiranja su sljedeca:
z1) Dijagram prijelaza:
x, ?T, AN
Ako je dijagram prijelaza za A dobiven primjenom pravila (i1) do (i6), poslije supstitucije na njegovom mjestu bit ce odgovarajuci dijagram prijelaza, a ako je A dobiven primjenom pravila (i7), poslije supstitucije A dobit ce se dijagram:
z2) Poslije supstitucije neterminala A, u dijagramu oblika:
rezultirajuci dijagram prijelaza, ovisno o dijagramu prijelaza za A, može biti:
a) A -> a1a2. . .an
b) A -> a 1 | a2 | . . . | an
f)A -> a I e
Do tih dijagrama dolazi se promatrajuci ekvivalentne recenične forme. Na primjer, u slucaju rekurzije zdesna, smjenjujuci neterminal A u
a { A } y
s {a}b, dobije se:
x {{ a } b } y
pa primjenjujuci pravilo (i3) dvaput, dobije se dani dijagram prijelaza.
Primjer 7.4
Za gramatiku jednostavnih izraza iz primjera 7.2, s produkcijama:
E -> E+E | E*E | (E) | a
odgovarajuci su dijagrami prijelaza: E+E
pa je rezultirajuci dijagram prijelaza:
Ako se poslije supstitucije neterminala B u dijagramu prijelaza neterminala A novi dijagram sadrži prijelaz oznacen s A (što znaci da je osnovna beskontekstna gramatika rekurzivna, ali je rekurzija implicitna), treba dijagram prevesti u ekvivalentnu recenicnu formu, identificirati tip recenicne forme i, primjenjujuci odgovarajuce pravilo (i4) do (i6), izvesti ekvivalentni dijagram prijelaza.
Primjer 7.5
Gramatika s produkcijama
A -> B | c
B -> aA
ima implicitnu rekurziju. Odgovarajuci su dijagrami prijelaza:
Poslije supstitucije neterminala B u dijagramu za A, imamo:
što je ekvivalentno produkciji
A -> aA | c
pa je konacno (rekurzija zdesna):
Reduciranje dijagrama prijelaza
Primjenom pravila za izvodenje dijagrama prijelaza, te eliminiranjem neterminala, cesto ce se dobiveni dijagrami ili rezultirajuci dijagram moci pojednostavniti i prevesti u ekvivalentan dijagram prijelaza. Na primjer, ako postoji prijelaz s dva jednaka simbola iz jednakog stanja (nedeterminizam) u isto naredno stanje. Pravila reduciranja su sljedeca:
rl)
7.3 USPOREDBA POSTUPAKA SINTAKSNE ANALIZE
Na kraju, usporedimo postupak sintaksne analize jezika sa svojsvima s višeprolaznim povratnim silaznim i ulaznim postupkom, te predikatnom sintaksnom analizom. Analizirat ce se recenice jezika jednostavnih aritmetickih izraza definiranog gramatikom G s produkcijama:
G: E -> E+E | E*E | (E) | a
Ova je gramatika istodobno ulaz uzlazne (bottom-up) SA. Za primjenu silazne (top-down) i 1-predikatne SA potrebno je transformirati gramatiku G u gramatiku G1, koja nece sadržati rekurzije slijeva, i ekvivalentnu gramatiku G2 koja ce biti tipa LL(1):G1: E -> T+E | T
T -> F*T | F
F -> (E) | a
G2: E -> TA
A -> TA | e
T -> FB
B -> *FB | e
F -> (E) | a
Konacno, za postupak SA upravljan tablicama prijelaza i akcija potrebno je definirati te tablice, što je bilo ucinjeno u primjeru 7.3 i 7.4.
Kompletni programi - realizacija navedenih postupaka - napisani su u Turbo Pascalu i dani su u dodatku. U sljedecoj tablici dan je broj koraka koji je bio potreban za svaki od navedenih postupaka u sintaksnoj analizi nekoliko recenica jezika L(G).
Ulazni niz_________top-down bottom-up 1-predikatna tablice
a 32 3 7 2
a+a 47 7 13 4
a*a 56 7 11 4
a*a+a 53 11 17 6
a* (a+a) 330 14 24 8
(a+a)*(a+a) 528 21 37 12
(a+(a+(a+a) ) ) 6,326 24 46 14
Ocigledno je postupak SA upravljan tablicama prijelaza i akcija najefikasniji. Možda zacuduju rezultati postupka bottom-up. S obzirom na to da se radi o nedeterministickom postupku, ne bi se ocekivalo da ce biti efikasniji od 1-predikatne SA. Medutim, poslije detaljnije analize može se zakljuciti da je uzrok tome ulazna gramatika koja je omogucavala uvijek jednoznacnu redukciju pri izgradnji stabla sintaksne analize pa je u ovom slucaju opcenito nedeterministicki postupak radio deterministicki. Pripadao bi klasi LR( 1) SA, a poznato je da su takvi postupci efikasniji od LL (1) postupaka.
Neefikasnost nedeterministickih postupaka SA posebno dolazi do izražaja u analizi recenice koja sadrži sintaksnu pogrešku. Opet smo iste postupke usporedili u analizi nekoliko nizova koji ne mogu biti prihvaceni kao recenice jezika L(G). Evo rezultata:
Ulazni niz_________top-down bottom-up 1-predikatna tablice
a+ 67 10 8 3
a+b 67 14 8 3
((a+a) 1,397 36 24 7
a+a+a+ 143 86 20 7
(()) 629 10 9 3
Opet je prednost na strani postupka upravljanog tablicama prijelaza i akcija. Sada dolazi do izražaja nedeterminizam postupka "bottom-up".
Prednost deterministickih postupaka nije samo u bržem otkrivanju sintaksne pogreške, vec i u mogucnosti njezinog lociranja. Nedeterministicki postupci mogu otkriti sintaksnu pogrešku tek poslije iscrpljenja svih alternativa, bez preciznog lociranja pogreške.