Definice OO	Rozkladová tabulka OOO	Príklad O	Vztah OOO	pro různá k	Implementace silných LL gramatik ooooooooooooo
					
		Syntaktická	anal>	'za	
Silné LL(k) gramatiky
Šárka Vavrečková
Ústav informatiky, FPF SU Opava sarka.vavreckovaQfpf.slu.cz
Poslední aktualizace: 2. listopadu 2023
Syntaktická analýza Úl, FPF SU Opava
Definice •O	Rozkladová tabulka ooo	Príklad O	Vztah pro různá k OOO	Implementace silných LL gramatik ooooooooooooo
				
Definice (Silná LL(k) gramatika)
Nechť G je bezkontextová gramatika. G je silná LL(k) gramatika, jestliže pro jakákoliv dvě pravidla se stejnou levou stranou
• A^ a,
• /3, kde a ^ f3, platí
FIRSTk(a o FOLLOWk(A)) n FIRSTk(f3 o FOLLOWk(A)) = 0
Gramatiku, která je LL(k), ale není silná LL(k), nazýváme slabá LL(k) gramatika.
Syntaktická analýza
-0 0,0
Ul, FPF SU Opava
Definice O*	Rozkladová tabulka ooo	Príklad O	Vztah pro různá k OOO	Implementace silných LL gramatik ooooooooooooo
				
Vlastnosti
• pro rozhodování mezi pravidly stačí nejvýše k symbolů ze vstupu,
• nemusíme kontrolovat zásobník (stačí se řídit podle jediného, vyjmutého symbolu)
• mezi pravidly se dá deterministicky rozhodovat podle příslušné množiny signatur délky nejvýše k - pro pravidlo A —> a:
FIRSTk{a • FOLLOWk(A))
Syntaktická analýza
-0 0,0
Ul, FPF SU Opava
Definice O*	Rozkladová tabulka ooo	Príklad O	Vztah pro různá k OOO	Implementace silných LL gramatik ooooooooooooo
				
Vlastnosti
• pro rozhodování mezi pravidly stačí nejvýše k symbolů ze vstupu,
• nemusíme kontrolovat zásobník (stačí se řídit podle jediného, vyjmutého symbolu)
• mezi pravidly se dá deterministicky rozhodovat podle příslušné množiny signatur délky nejvýše k - pro pravidlo A —> a:
FIRSTk{a • FOLLOWk(A))
Syntaktická analýza
-0 0,0
Ul, FPF SU Opava
Definice O*	Rozkladová tabulka ooo	Príklad O	Vztah pro různá k OOO	Implementace silných LL gramatik ooooooooooooo
				
Vlastnosti
• pro rozhodování mezi pravidly stačí nejvýše k symbolů ze vstupu,
• nemusíme kontrolovat zásobník (stačí se řídit podle jediného, vyjmutého symbolu)
• mezi pravidly se dá deterministicky rozhodovat podle příslušné množiny signatur délky nejvýše k - pro pravidlo A —> a:
FIRSTk{a • FOLLOWk(A))
Syntaktická analýza
-0 0,0
Ul, FPF SU Opava
Definice OO	Rozkladová tabulka •OO	Príklad O	Vztah pro různá k ooo	Implementace silných LL gramatik ooooooooooooo
				
Schéma rozkladové tabulky
N
T
	u			$
A	■ • ■ e(i)			
		T		
				
	pop		pop	
#				acc
A —>> a je i-té pravidlo gramatiky
u E FIRSTS (a • FOLLOW/e (A))
Vstup
c
O
(o
N
Akce:
expect pop accept error
4 U k   <       ►   < -š ►   < -Š ►
-0 0,0
Syntaktická analýza
Úl, FPF SU Opava
Definice OO	Rozkladová tabulka o«o	Príklad O	Vztah pro různá k ooo	Implementace silných LL gramatik ooooooooooooo
				
	/c-tice symbolů ze vstupu	$
neterminály ze zásobníku	expand(číslo pravidla)	
Podtabulka, sloupce označeny terminály a $:		
terminály ze zásobníku	pop pop pop pop pop	
#		accept
Syntaktická analýza
Úl, FPF SU Opava
Definice OO	Rozkladová tabulka oo»	Príklad O	Vztah pro různá k ooo	Implementace silných LL gramatik ooooooooooooo
				
Postup
• ověříme, zda se jedná o silnou LL(k) gramatiku pro co nejmenší k, 9 pro všechna pravidla A —> a sestrojíme množiny
• pro každé pravidlo A
FIRSTk(a - FOLLOWk(A))
a (číslo i):
x e FIRSTk(a • FOLLOWk(A))
A
expand(i)
• doplníme pop, accept
Syntaktická analýza
-0 0,0
Ul, FPF SU Opava
Definice OO	Rozkladová tabulka ooo	Príklad •	Vztah pro různá k OOO	Implementace silných LL gramatik ooooooooooooo
				
G= ({S,A}, {a, 6}, P, S), množina P:
S A
abA Saa
e b
©,© FOLLOW2(S) = {$, aa} ©,©   FOLLOW2(A) = {$, aa}
	ab	aa	b$	ba	$
					
A					
					
Syntaktická analýza
-0 0,0
Ul, FPF SU Opava
Definice OO	Rozkladová tabulka ooo	Príklad •	Vztah pro různá k OOO	Implementace silných LL gramatik ooooooooooooo
				
G= ({S,A}, {a, 6}, P, S), množina P:
S A
abA Saa
e b
©,© FOLLOW2(S) = {$, aa} ©,©   FOLLOW2(A) = {$, aa}
	ab	aa	b$	ba	$
					
A					
					
Syntaktická analýza
-0 0,0
Ul, FPF SU Opava
Definice OO	Rozkladová tabulka ooo	Príklad •	Vztah pro různá k OOO	Implementace silných LL gramatik ooooooooooooo
				
G= ({S,A}, {a, 6}, P, S), množina P:
S^abA\e ©,®   FOLLOW2(S) = {$, aa}
A ->> Saa | b ®,®   FOLLOW2(A) = {$, aa}
F2(abA- FL2(S)) = {ab} F2(e-FL2(S)) = {$,aa} F2(Saa • FL2(A)) = {ab, aa} F2(b-FL2(A)) = {b$,ba}
	ab	aa	b$	ba	$
					
A					
					acc
-0 0,0
Syntaktická analýza
Úl, FPF SU Opava
Definice OO	Rozkladová tabulka ooo	Príklad •	Vztah pro různá k OOO	Implementace silných LL gramatik ooooooooooooo
				
G= ({S,A}, {a, 6}, P, S), množina P:
S^abA\e ©,©   FOLLOW2(S) = {$, aa}
A ->> Saa | b ®,®   FOLLCW2(A) = {$, aa}
F2(abA- FL2(S)) = {ab} F2(e-FL2(S)) = {$,aa} F2(Saa • FL2(A)) = {ab, aa} F2(b-FL2(A)) = {b$,ba}
	ab	aa	6$	ba	$
S	e(l)	e(2)			e(2)
A	e(3)	e(3)	e(4)	e(4)	
#					acc
-0 0,0
Syntaktická analýza
Úl, FPF SU Opava
Definice OO	Rozkladová tabulka OOO	Príklad •	Vztah pro různá k OOO	Implementace silných LL gramatik ooooooooooooo
				
G= {a, 6}, P, S), množina P:
S^abA\e ©,©   FOLLOW2(S) = {$, aa}
©,©   FOLLOW2(A) = {$, aa}
A —>• 5aa 6
	ab	aa	6$	ba	$
	e(l)	e(2)			e(2)
	e(3)	e(3)	e(4)	e(4)	
#					acc
Postup výpočtu slova afraa:
(afraa$,       e) h (afraa$, abA#, 1) hh (6aa$, 1) h (aa$, A#, 1) h (aa$, 5aa#, 1, 3) h
(aa$, aa#, 1,3, 2) h (a$, a#, 1,3, 2) h ($, #, 1,3, 2)
J
Syntaktická analýza
Úl, FPF SU Opava
Definice OO	Rozkladová tabulka ooo	Príklad •	Vztah pro různá k OOO	Implementace silných LL gramatik ooooooooooooo
				
G= ({S,A}, {a,b}, P, S), množina P:
S —>> abA I e A —>• Saa I 6
0,© FOLLOW2(S) = {$, aa} ©,©   FOLLCW2(A) = {$, aa}
	ab	aa	6$	ba	$
	e(l)	e(2)			e(2)
A	e(3)	e(3)	e(4)	e(4)	
#					acc
Postup výpočtu slova afra:
(afra$, S#, e) h (afra$, a6A#, 1) h (6a$,        1) h (a$, A#, 1) h error
Syntaktická analýza
-0 0,0
Ul, FPF SU Opava
Definice OO	Rozkladová tabulka ooo	Príklad O	Vztah pro různá k •OO	Implementace silných LL gramatik ooooooooooooo
				
Vztah mezi silnými LL(k) pro různá k
s
A B
C
fbACa I BaAC | e ©,©,© FL(S) = {$,a}
dA | mAp | e ©,©,© FL(A) = {u,p,$,a}
cBaS | f d ©,® FL(B) = {a}
uc\pC\e ©,@,@ FL(C) = {a, $}
FIRST(/6ACa • FOLLOW(5')) n FIRST(SaAC • FOLLOW(5')) = {/} / 0
(není LL(l))
Syntaktická analýza
Ul, FPF SU Opava
Definice OO	Rozkladová tabulka ooo	Príklad O	Vztah pro různá k omo	Implementace silných LL gramatik ooooooooooooo
				
Vztah mezi silnými LL(k) pro různá k
s
A B
C
fbACa I BaAC dA | mAp | e cBaS | f d uc | pC | e
e
0,©,® ©,©,© ©-© ®,@,@
FOLLOW2(5') FOLLOW2(A) FOLLOW2(B) FOLLOW2(C)
{$, ad, am, au, ap, as, af, ac, aB} —
{$, ad, am, au, ap, a$, aa, a/, ac}
{«c, pit, pp, pa, pA, $, ad, am, au, ap, as, af, ac,
{uc, pu, pp, pa, pA, $, ad, am, au, ap, a$, aa, a/,
{ad, am, ait, ap, a5, af, ac, aB} —
{ad, am, au, ap, a$, aa, af, ac}
{as, $, ad, am, au, ap, as, af, ac, aB} —
{a$, aa, $, ad, am, ait, ap, af, ac}
FL(S) FL(A) FL(B) FL(C)
aB} = ac}
{$,4
{u,p, $, a}
w {0,$}
Syntaktická analýza
Úl, FPF SU Opava
10
Definice OO	Rozkladová tabulka ooo	Príklad O	Vztah pro různá k omo	Implementace silných LL gramatik ooooooooooooo
				
Vztah mezi silnými LL(k) pro různá k
s
A B
C
fbACa I BaAC dA | mAp | e cBaS | f d uc | pC | e
e
0,©,® ©,©,©
®.® ©-©-©
FL(S) FL(A) FL(B) FL(C)
{$,a} {u,p, $, a}
w
{a,$}
FOLLOW2(5') FOLLOW2(A) FOLLOW2(S) FOLLOW2(C)
FS2(5', fbACa) FS2(S,BaAC)
{$, ad, am, au, ap, as, af, ac, aB} —
{$, ad, am, au, ap, a%, aa, af, ac}
{uc, pu, pp, pa, pA, $, ad, am, au, ap, as, af, ac, aB}
{uc, pu, pp, pa, pA, $, ad, am, au, ap, a%, aa, af, ac}
{ad, am, au, ap, as, af, ac, aB} —
{ad, am, au, ap, a%, aa, af, ac}
{as, $, ad, am, au, ap, as, af, ac, aB} —
{a%, aa, $, ad, am, au, ap, af, ac}
{fb}
{cc, cf, fd}
FS2(5', e) = {$, ad, am, au, ap, a$, aa, af, ac}
Syntaktická analýza
Úl, FPF SU Opava
Definice OO	Rozkladová tabulka ooo	Príklad O	Vztah pro různá k omo	Implementace silných LL gramatik ooooooooooooo
				
Vztah mezi silnými LL(k) pro různá k
s
A B
C
fbACa I BaAC dA | mAp | e cBaS | f d uc | pC | e
s
®,®,® ®,®,® ®>® ®.©.@
FL(S) FL(A) FL(B) FL(C)
{$,a} {u,p, $, a}
w {0,$}
{$, ad, am, au, ap, as, af, ac, aB} — {$, ad, am, au, ap, a$, aa, af, ac} {uc, pu, pp, pa, pA, $, ad, am, au, ap, as, af, ac, aB} {uc, pu, pp, pa, pA, $, ad, am, au, ap, a%, aa, af, ac} {ad, am, au, ap, as, af, ac, aB} — {ad, am, au, ap, a%, aa, af, ac} {as, $, ad, am, au, ap, as, af, ac, aB} — — {a%, aa, $, ad, am, au, ap, af, ac}
FS2(A, dA) — {dd, dm, du, dp, d%, da}
FS2(A,mAp) — {md,mm,mp}
FS2 (A, s) — {uc, pu, pp, pa, p$, $, ad, am, au, ap, a$, aa, af, ac}
FOLLOW2(5') FOLLOW2(A) FOLLOW2(S) FOLLOW2(C)
Syntaktická analýza
Úl, FPF SU Opava
Definice OO	Rozkladová tabulka ooo	Príklad O	Vztah pro různá k omo	Implementace silných LL gramatik ooooooooooooo
				
Vztah mezi silnými LL(k) pro různá k
S      fbACa | BaAC
A —> dA | rnAp \ e B       cBaS | f d
C —>• uc | pC | e
FOLLOW2(5')
e
©.© ®.®,@
FL(S) FL(A) FL(B) FL{C)
{$,0}
{u,p, $, a}
w
{a,$}
FOLLOW2(A) FOLLOW2(S) FOLLOW2(C)
FS2(S, cBaS) --FS2(BJd) = {fd}
{$, ad, am, au, ap, as, aj, ac, aB} — {$, ad, am, au, ap, a$, aa, aj, ac}
{uc, pu, pp, pa, pA, $, ad, am, au, ap, as, aj, ac, aB} — {uc, pu, pp, pa, pA, $, ad, am, au, ap, a%, aa, aj, ac} {ad, am, au, ap, as, aj, ac, aB} — {ad, am, au, ap, a$, aa, aj, ac} {as, $, ad, am, au, ap, as, aj, ac, aB} — {a%, aa, $, ad, am, au, ap, aj, ac}
{cc, dj}
Syntaktická analýza
Úl, FPF SU Opava
Definice OO	Rozkladová tabulka ooo	Príklad O	Vztah pro různá k omo	Implementace silných LL gramatik ooooooooooooo
				
Vztah mezi silnými LL(k) pro různá k
s
A B
C
fbACa I BaAC dA | mAp | e cBaS | f d uc | pC | e
e
®,®,®
®.® ®.©.@
FL(S) FL(A) FL{B) FL(C)
{$,a} {u,p, $, a}
w {0,$}
{$, ad, am, au, ap, as, af, ac, aB} — {$, ad, am, au, ap, a%, aa, af, ac} {uc, pu, pp, pa, pA, $, ad, am, au, ap, as, af, ac, aB} {uc, pu, pp, pa, pA, $, ad, am, au, ap, a%, aa, af, ac} {ad, am, au, ap, as, af, ac, aB} — {ad, am, au, ap, a%, aa, af, ac} {as, $, ad, am, au, ap, as, af, ac, aB} —
FOLLOW2(5')
FOLLOW2(A)
FOLLOW2(S) =
FOLLOW2(C) =
= {a%, aa, $, ad, am, au, ap, af, ac}
FS2(C, uc) — {uc}
FS2 (C,pC) — {pu,pp,pa,p%}
FS2(C, e) — {a%, aa, $, ad, am, au, ap, af, ac}
Syntaktická analýza
Úl, FPF SU Opava
Definice Rozkladová tabulka Přiklad Vztah pro různá k Implementace silných LL gramatik
OO OOO o oo» ooooooooooooo
Silná LL(2)
	fb	cc	cf	fd	$	ad	am	au	ap	a$	aa	af	ac
s	el	e2	e2	e2	e3	e3	e3	e3	e3	e3	e3	e3	e3
A					e6	e6	e6	e6	e6	e6	e6	e6	e6
B		e7	e7	e8									
C					ell	ell	ell	ell	ell	ell	ell	ell	ell
	dd	dm	du	dp		da	md	mm	mp	WC	pu	pp	pa	p$
S														
A	e4	e4	e4	e4	e4	e4	e5	e5	e5	e6	e6	e6	e6	e6
B														
C										e9	elO	elO	elO	elO
LL(1) tabulka
	a	6	c		/	m		u	$
	e3		e2		el, e2				e3
	e6			e4		e5	e6	e6	e6
B			e7		e8				
C	ell						elO	e9	ell
Syntaktická analýza
Ul, FPF SU Opava
Definice
OO
Rozkladová tabulka
ooo
Príklad
O
Vztah pro různá k
OOO
Implementace silných LL gramatik
•oooooooooooo
Implementace přepisem rozkladové tabulky
Popis metody
Potřebujeme
• rozkladovou tabulku a zásobník na ukládání symbolů,
• k proměnných pro symboly ze vstupu (např. pole),
• funkci lex(), která nám vrátí další symbol, který extrahovala ze vstupního souboru:
• dosud načtené vstupní symboly posune o jeden doleva (sym[i — 1] := sym[i]), nově načtený symbol uloží na konec pole (k-tý prvek),
• jestliže je na konci souboru, zařadí $ a dále provádí pouze posun,
• při prvním volání se načítá všech k vstupních symbolů,
• proměnnou pro výstup.
Syntaktická analýza
-0 0,0
Ul, FPF SU Opava
Definice
OO
Rozkladová tabulka
ooo
Príklad
O
Vztah pro různá k
OOO
Implementace silných LL gramatik
o»ooooooooooo
Implementace přepisem rozkladové tabulky
Postup
Rozdíl oproti analýze pro k = 1
Postup je stejný jako u LL(1) gramatik, jen
• složitější funkce lex(), musí provádět posuny symbolů,
• složitější funkce Akce() - při rozhodování mezi sloupci musí brát v úvahu /c-tice místo jediného symbolu.
Syntaktická analýza
-0 0,0
Ul, FPF SU Opava
Definice Rozkladová tabulka
oo ooo
Príklad
O
Vztah pro různá k
OOO
Implementace silných LL gramatik
00*0000000000
Implementace přepisem rozkladové tabulky
Proměnné a inicializace
const int KSYM 2;    // resp. podle hodnoty k TSymbol symboly[KSYM]; int s_prvni, s_posledni; TTypSymbolu   vrchol_zas;
void Init() {
s_prvni = 0; s_posledni = 0;
Lex(); // načte symbol na index s_posledni
if (s.posledni != S.ENDOFFILE) { s_posledni++;
Lex(); // načte druhý symbol na index s_posledni
// předchozí čtyři řádky celkem (k-1)-krát, příp. cyklus for
y
y
Syntaktická analýza
Úl, FPF SU Opava
Definice Rozkladová tabulka
oo ooo
Príklad
O
Vztah pro různá k
OOO
Implementace silných LL gramatik
000*000000000
Implementace přepisem rozkladové tabulky
Metoda přepisu rozkladové tabulky
void pop() {
if (symboly[s_prvni] == vrchol_zas) {
if (symboly[s_posledni]   != S_ENDOFFILE) { s_prvni++;
if (s_prvni >= k) s_prvni = 0; s_posledni++;
if (s_posledni >= k) s_posledni = 0; Lex();
}
else {
s_prvni++;
if (s_prvni >= k)
s_prvni = 0;
};
else error(...);
}
Syntaktická analýza
Úl, FPF SU Opava
Definice
OO
Rozkladová tabulka
ooo
Príklad
O
Vztah pro různá k
OOO
Implementace silných LL gramatik
oooo»oooooooo
Implementace přepisem rozkladové tabulky
Expanze podle pravidla
int expand(int cislo_prav) { switch (cislo_prav) {
case   1: // S abA
Pridej_do_zasobniku(S_NA); Pridej_do_zasobniku(S_b); Pridej_do_zasobniku(S_a); break;
case   2: // S £
break;
case   3: // A ->• Saa
Přidej _do_zasobniku(S_a); Přidej _do_zasobniku(S_a); Přidej _do_zasobniku(S_NS); break;
... // pro každé pravidlo gramatiky
};
vystup(cislo_prav); // zápis čísla použitého pravidla na výstup
Syntaktická analýza
Úl, FPF SU Opava
Definice
OO
Rozkladová tabulka
ooo
Príklad
O
Vztah pro různá k
OOO
Implementace silných LL gramatik
00000*0000000
Implementace přepisem rozkladové tabulky
Metoda přepisu rozkladové tabulky
void Akce() {
vrchol_zas = Vyjmi_ze_zasobniku(); switch (vrchol_zas) {
		uv	xy	
				
A		e(n)	e(m)	
				
case S_MA: switch (symboly[s_prvni].typ) {
case u: if (symboly[s_prvni+l].typ == v) expand(n);
else ...; break;    // další řetězec začínající symbolem u nebo chyba case x: if (symboly[s_prvni+l].typ == y) expand(m);
else ...; break;    // další řetězec začínající symbolem x nebo chyba ... // další buňka v řádku A default: error(...);
}
...    // další řádky tabulky
case S_HASH: if (symboly[s_prvni] .typ == S_EMDDFFILE) acceptO;
else error(...); break; case S_ID: case S_MUM: case S_PLUS: pop(); break; default: error(...);
Syntaktická analýza
Úl, FPF SU Opava
Definice
OO
Rozkladová tabulka
ooo
Príklad
O
Vztah pro různá k
OOO
Implementace silných LL gramatik
000000*000000
Implementace přepisem rozkladové tabulky
Podle příkladu:
S abA A —>• Saa
e b
©,© FOLLOW2(S) = {$,aa} ®,0 FOLLOW2(A) = {$,aa}
	ab	aa	b$	ba	S
s	e(l)	e(2)			e(2)
A	e(3)	e(3)	e(4)	e(4)	
#					acc
void Akce() {
vrchol_zas = Vyjmi_ze_zasobniku(); switch (vrchol_zas) ■{
case S_MS: switch (symboly[s_prvni].typ) {
case S_a: switch (symboly[s_prvni+l].typ) { case S_b: expand(1); break; case S_a: expand(2); break;
default: chyba ("Očekáván ......11) ;
} break;
case S_EMDDFFILE: expand(2); break;
default: chyba ("Očekáván......11) ;
}
case S_MA: ...
case S_a: case S_b: pop(); break;
case S_HASH: if (symboly[s_prvni].typ == S_EMDOFFILE) accept else error(
);
•<□►   4 S" ►   4 -E *■   4 S ►
-0 0,0
Syntaktická analýza
Ul, FPF SU Opava
Definice	Rozkladová tabulka	Príklad	Vztah pro různá k	Implementace silných LL gramatik
OO	OOO	O	OOO	ooooooo»ooooo
Implementace rekurzivnin	i sestupem			
Popis metody
Potřebujeme
• silnou LL(k) gramatiku (nemusíme dělat rozkladovou tabulku),
• pro každé pravidlo A —> a vytvoříme „množinu signatur"
F S (A, a) = FIRSTk (a • FOLLOWk(A))
• k proměnných, ve kterých jsou uloženy symboly načtené ze vstupu (příp. řetězec o délce
k),
• funkci lex() upravenou stejně jako u předchozí metody,
• proměnnou pro výstup (soubor, dynamická struktura apod.).
Syntaktická analýza
-0 0,0
Ul, FPF SU Opava
Definice	Rozkladová tabulka	Príklad	Vztah pro různá k	Implementace silných LL gramatik
OO	ooo	O	OOO	oooooooo»oooo
Implementace rekurzivnín	n sestupem			
Postup
Rozdíl oproti analýze pro k = 1
Postup je stejný jako u LL(1) gramatik, jen
• složitější funkce lex(), musí provádět posuny symbolů,
• složitější funkce pro jednotlivé neterminály - při rozhodování používáme množiny FS, jejichž prvky jsou /c-tice místo jednotlivých symbolů.
Syntaktická analýza
-0 0,0
Ul, FPF SU Opava
Definice
OO
Rozkladová tabulka
ooo
Príklad
O
Vztah pro různá k
OOO
Implementace silných LL gramatik
000000000*000
Implementace rekurzivním sestupem
Metoda rekurzivního sestupu
void pop(TTypSymbolu term) {
if (symboly[s_prvni].typ == term) {
if (symboly[s_posledni]   != S_ENDOFFILE) { s_prvni++;
if (s_prvni >= k) s_prvni = 0; s_posledni++;
if (s_posledni >= k) s_posledni = 0; Lex();
}
else {
s_prvni++;
if (s_prvni >=
}
k)
s_prvni = 0;
else error(...);
}
Syntaktická analýza
Úl, FPF SU Opava
Definice	Rozkladová tabulka	Príklad	Vztah pro různá k	Implementace silných LL gramatik
OO	ooo	O	OOO	OOOOOOOOOO0OO
Implementace rekurzivnín	n sestupem			
Metoda rekurzivního sestupu
		uv	xy	
				
A		e(n)	e(m)	
				
void A() {
switch (symboly[s_prvni].typ) {
case u: if (symboly[s_prvni+l].typ == v) { // zpracováni pravidla číslo n y else ...       // další řetězec začínající symbolem u nebo chyba case x: if (symboly[s_prvni+l].typ == y) { // zpracováni pravidla číslo m y end else ...       // další řetězec začínající symbolem x nebo chyba ...       // další buňka v řádku A default: error(...);
Syntaktická analýza
•<□►   •<ě5I^   ■<■!►   < -1 ►
Úl, FPF SU Opava
Definice	Rozkladová tabulka	Príklad	Vztah pro různá k	Implementace silných LL gramatik
OO	ooo	O	OOO	ooooooooooo»o
Implementace rekurzivnín	n sestupem			
Podle příkladu:
S -> ab A		©.©	FOLLOW2(S)	— {$,aa}		ab	aa	6$	6a	$
	£				S	e(l)	e(2)			e(2)
A —)• Saa	b	©.©	FOLLOW2(A)	— {$,aa}	A	e(3)	e(3)	e(4)	e(4)	
					_.#					acc
void SO {
switch (symboly[s_prvni].typ) {
case S_a: switch (symboly[s_prvni+l].typ) { case S_b:
pop(S_a); pop(S_b); A(); break; case S_a: break; default: error(...);
}
case S_EMDDFFILE: break; default: error(...);
}
}
Syntaktická analýza
Úl, FPF SU Opava
Definice	Rozkladová tabulka	Príklad	Vztah pro různá k	Implementace silných LL gramatik
OO	ooo	O	OOO	oooooooooooo*
Implementace rekurzivnín	n sestupem			
Podle příkladu:
S abA A —)• Saa
£ b
®,® FOLLOW2(S) = {$, aa} ©,©   FOLLOW2(A) = {$, aa}
	ab	aa	6$	ba	$
S	e(l)	e(2)			e(2)
A	e(3)	e(3)	e(4)	e(4)	
#					acc
J
void A() {
switch (symboly[s_prvni].typ) {
case S_a: if (symboly[s_prvni+l] .typ == S_b | | symboly[s_prvni+l] .typ == S_a) ■{ SO;
pop(S_a); pop(S_a); break; default: error(...);
case S_b: if (symboly[s_prvni+l] .typ == S_EMDDFFILE I |  symboly[s_prvni+l] .typ == S_a) ■{ pop(S_b); break;
}
default: error(...); } error(...);
}
}
•<□►  •<t5i^  ■<■!► <
= ►
Syntaktická analýza
Úl, FPF SU Opava