Možnosti	Metoda přepisu rozkladové tabulky	Rekurzivní sestup
O	ooooooooooooooo	oooooooooooooooo
		
	Syntaktická analýza	
	Implementace LL(1) překladů	
	Šárka Vavrečková	
	Ústav informatiky, FPF SU Opava	
	sarka.vavreckovaQfpf.slu.cz	
	Poslední aktualizace: 27. října 2023	
		
Syntaktická analýza		Úl, FPF SU Opava
Možnosti
Metoda přepisu rozkladové tabulky
ooooooooooooooo
Rekurzivní sestup
oooooooooooooooo
Postup
Programujeme syntaktickou analýzu:
O Navrhneme vhodnou LL(1) gramatiku popisující strukturu jazyka.
Q Vytvoříme podle ní překladový automat (rozkladovou tabulku) nebo alespoň všechny potřebné množiny.
O Naprogramujeme:
Syntaktická analýza Úl, FPF SU Opava
Možnosti
Metoda přepisu rozkladové tabulky
ooooooooooooooo
Rekurzivní sestup
oooooooooooooooo
Postup
Programujeme syntaktickou analýzu:
O Navrhneme vhodnou LL(1) gramatiku popisující strukturu jazyka.
Q Vytvoříme podle ní překladový automat (rozkladovou tabulku) nebo alespoň všechny potřebné množiny.
O Naprogramujeme:
Syntaktická analýza Úl, FPF SU Opava
Možnosti
Metoda přepisu rozkladové tabulky
ooooooooooooooo
Rekurzivní sestup
oooooooooooooooo
Postup
Programujeme syntaktickou analýzu:
O Navrhneme vhodnou LL(1) gramatiku popisující strukturu jazyka.
O Vytvoříme podle ní překladový automat (rozkladovou tabulku) nebo alespoň všechny potřebné množiny.
O Naprogramujeme:
Syntaktická analýza Úl, FPF SU Opava
Možnosti •	Metoda přepisu rozkladové tabulky ooooooooooooooo	Rekurzivní sestup oooooooooooooooo
		
Postup
Programujeme syntaktickou analýzu:
O Navrhneme vhodnou LL(1) gramatiku popisující strukturu jazyka.
O Vytvoříme podle ní překladový automat (rozkladovou tabulku) nebo alespoň všechny potřebné množiny.
O Naprogramujeme:
• metodou přepisu rozkladové tabulky,
• metodou rekurzivního sestupu.
Syntaktická analýza
Úl, FPF SU Opava
Možnosti •	Metoda přepisu rozkladové tabulky ooooooooooooooo	Rekurzivní sestup oooooooooooooooo
		
Postup
Programujeme syntaktickou analýzu:
O Navrhneme vhodnou LL(1) gramatiku popisující strukturu jazyka.
O Vytvoříme podle ní překladový automat (rozkladovou tabulku) nebo alespoň všechny potřebné množiny.
O Naprogramujeme:
• metodou přepisu rozkladové tabulky,
• metodou rekurzivního sestupu.
Syntaktická analýza
Úl, FPF SU Opava
Možnosti
O
Metoda přepisu rozkladové tabulky •oooooooooooooo
Rekurzivní sestup
oooooooooooooooo
Myšlenka postupu
Přepis rozkladové tabulky
Potřebujeme
• rozkladovou tabulku,
• zásobník na ukládání symbolů,
• proměnnou, ve které je uložen právě zpracovávaný symbol,
• funkci lex(), která nám vrátí další symbol, který extrahovala ze vstupního souboru (uloží do proměnné z předchozího bodu),
• proměnnou pro výstup (soubor, dynamická struktura apod.).
Syntaktická analýza
Úl, FPF SU Opava
Možnosti
O_
Myšlenka postupu
Metoda přepisu rozkladové tabulky O0OOOOOOOOOOOOO
Rekurzivní sestup
oooooooooooooooo
Popis metody
Budeme potřebovat tyto funkce:
• expand(číslo_pravidla) uloží pravou stranu pravidla s daným číslem do zásobníku a na výstup přidá číslo pravidla,
• pop() ověří shodnost symbolu na vstupu se symbolem ze zásobníku a posune se na vstupu,
• acceptO při konci vstupu a konci zásobníku ukončí program,
• errorO ošetří chybu, která se vyskytla při překladu,
• AkceO je hlavní řídicí funkce, v cyklu volá předchozí, zajišťuje „pohyb v tabulce",
• InitQ, Done() je inicializační a úklidová funkce.
J
Syntaktická analýza
Úl, FPF SU Opava
Možnosti
O
Metoda přepisu rozkladové tabulky OO0OOOOOOOOOOOO
Rekurzivní sestup
oooooooooooooooo
Implementace
Příklad
S ->■ AB		©		
A^CD		©		
B -> +AB	-AB s	©.	©■	©
C -> (S) \ i	| n	®.	®.	©
D -> *CD |	/CD | e	®.		©
	i	n	+						$
	el	el					el		
									
									
									
									
Syntaktická analýza
Ul, FPF SU Opava
Možnosti			Metoda přepisu rozkladové tabulky	Rekurzivní sestup	
O			OO0OOOOOOOOOOOO	oooooooooooooooo	
Implementace					
Příklad					
S-tAB					
A^CD					
B -> +AB	-AB	e			
C -> (S) \ i	| n		©. ©.©		
D -> *CD |	/CD | e				
					
Rozkladová tabulka
	i	n		—	*	/	(	)	$
S	el	el					el		
A	e2	e2					e2		
B			e3	e4				e5	e5
C	eľ	e8					e6		
D			ell	ell	e9	elO		ell	ell
Syntaktická analýza
Ul, FPF SU Opava
Možnosti Metoda přepisu rozkladové tabulky Rekurzivní sestup
O OOO0OOOOOOOOOOO oooooooooooooooo
Implementace
Datové typy
enum TTypSymbolu { S.MOTHIMG, S.EMDOFFILE, S.LPAR, S.RPAR,
S_ID, S_MUM, S_IS, S.PLUS, S.MIMUS, S_MUL, S_DIV, // terminály
S_NS, S_MA, S_MB, S_MC, S_ND, S.HASH }; // neterminály
struct TSymbol { TTypSymbolu typ; string atrib;
TSymbol symbol; TVstup vstup; bool konec; TZasobnik zasobnik; TTypSymbolu vrchol_zas;
struct TVstup { char znak; int cisloRad; int pozice; int konec;
Syntaktická analýza
Úl, FPF SU Opava
Možnosti
O
Metoda přepisu rozkladové tabulky
oooo«oooooooooo
Rekurzivní sestup
oooooooooooooooo
Implementace
expanze pravidla
int expand(int cislo_prav) { switch (cislo_prav) {
case   1: // S ->■ AB
Pridej_do_zasobniku(S_NB); Pridej_do_zasobniku(S_NA); break;
case   2: // A ->• CD
Pridej_do_zasobniku(S_ND); Pridej_do_zasobniku(S_NC); break;
case   3: // B ->■ +AB
Pridej_do_zasobniku(S_NB); Pridej_do_zasobniku(S_NA); Přidej_do_zasobniku(S_PLUS); 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
Možnosti O	Metoda přepisu rozkladové tabulky OOOOO0OOOOOOOOO	Rekurzivní sestup oooooooooooooooo
Implementace		
Ošetření chyb
void error(string hláska) { // Chyba syntaxe;
// vypíše číslo řádku, pozici na řádku a řetězec s daným hlášením konec = true;
printf ("Chyba při syntaktické analýze na řádku °/,d, sloupci °/,d: °/,s", vstup.cisloRad, vstup.pozice, hláska);
}
Syntaktická analýza
Úl, FPF SU Opava
Možnosti Metoda přepisu rozkladové tabulky Rekurzivní sestup
O_000000*00000000_oooooooooooooooo
Implementace
Zpracování terminálů a akceptování
int pop() {
if (symbol.typ == vrchol_zas)
Lex(); // lexikální analyzátor načte další symbol
eise error("chybný symbol na vstupu -" +VypisTyp(symbol.typ));
}
void accept() { konec = true;
}
Syntaktická analýza
Úl, FPF SU Opava
Možnosti O	Metoda přepisu rozkladové tabulky OOOOOOO0OOOOOOO	Rekurzivní sestup oooooooooooooooo
Implementace		
Inicializace a ukončení
void Init() {
... // inicializace vstupu a výstupu
Vytvor_zasobnik();
Přidej_do_zasobniku(S_HASH); // symbol konce zásobníku Přidej_do_zasobniku(S_MS);     // startovací symbol gramatiky Lex(); // načte symbol ze vstupu do symbol
konec = falše;
}
void Done() {
Zlikviduj_zasobnik();
// uvolní paměť zabranou zásobníkem // uzavření vstupu a výstupu
Syntaktická analýza
Ul, FPF SU Opava
Možnosti Metoda přepisu rozkladové tabulky Rekurzivní sestup
O OOOOOOOO0OOOOOO oooooooooooooooo
Implementace
Simulace práce s tabulkou
Funkce Akce Pracuje takto:
• vyjme ze zásobníku jeden symbol, tím určí řádek tabulky a podle symbolu na vstupu určí sloupec tabulky,
• podle obsahu buňky zavolá funkci expand, pop, accept nebo error,
• je volána v cyklu tak dlouho, dokud není konec zpracovávaného programu.
Syntaktická analýza
Úl, FPF SU Opava
Možnosti Metoda přepisu rozkladové tabulky Rekurzivní sestup
o ooooooooo»ooooo oooooooooooooooo
Implementace
Simulace práce s tabulkou
switch (řádek) {
case první_řádek: switch (sloupec) {
case první_sloupec: obsah_buňky_[1,1]; break;
case druhý_sloupec: obsah_buňky_[1,2]; break;
• • •
default: error(...); } break;
case druhý_řádek: switch (sloupec) {
case první_sloupec: obsah_buňky_[2,1]; break; case druhý_sloupec: obsah_buňky_[2,2]; break;
• • •
default: error(...); } break;
• • •
case terminál: pop; break;
case dno.zásobníku: if (konec_vstupu) accept(); else error(...);
}
Syntaktická analýza Úl, FPF SU Opava
Možnosti
O
Metoda přepisu rozkladové tabulky 0000000000*0000
Rekurzivní sestup
oooooooooooooooo
Implementace
Simulace práce s tabulkou
void Akce() {
vrchol_zas = Vyjmi_ze_zasobniku(); switch (vrchol_zas) {
case S_NS: switch(symbol.typ) { case S_ID: case S_NUM:
case S_LPAR: expand(l); break;
default: error("chybný symbol na vstupu -" +symbol.typ); } break;
	i	n	+	—	*	/	(	)	$
S	el	el					el		
A	e2	e2					e2		
B			e3	e4				e5	e5
C	el	e8					e6		
D			ell	ell	e9	elO		ell	ell
case S_NA: switch(symbol.typ) { case S_ID: case S_NUM:
case S_LPAR: expand(2); break;
default: error("chybný symbol na vstupu -" +symbol.typ); } break;
Syntaktická analýza
Úl, FPF SU Opava
Možnosti
O
Metoda přepisu rozkladové tabulky OOOOOOOOOOO0OOO
Rekurzivní sestup
oooooooooooooooo
Implementace
Simulace práce s tabulkou
case S_NB: switch (symbol.typ) { case S_PLUS: expand(3); break; case S_MINUS: expand(4); break; case S_RPAR:
case S_ENDOFFILE: expand(5); break;
default: error("chybný symbol na vstupu -" +symbol.typ); } break;
case S_NC: switch (symbol.typ) { case S_ID: expand(7); break; case S_NUM: expand(8); break; case S_LPAR: expand(6); break;
default: error("chybný symbol na vstupu -" +symbol.typ); } break;
	i	n	+	—	*	/	(	)	$
S	el	el					el		
A	e2	e2					e2		
B			e3	e4				e5	e5
C	e7	e8					e6		
D			ell	ell	e9	elO		ell	ell
-<□►   4 S> ►   < -E ►   4 S ►
Syntaktická analýza
Úl, FPF SU Opava
Možnosti
O
Metoda přepisu rozkladové tabulky OOOOOOOOOOOO0OO
Rekurzivní sestup
oooooooooooooooo
Implementace
Simulace práce s tabulkou
	i	n	+	—	*	/	(	)	$
s	el	el					el		
A	e2	e2					e2		
B			e3	e4				e5	e5
C	el	e8					e6		
D			ell	ell	e9	elO		ell	ell
case S_ND: switch (symbol.typ) { case S_MUL: expand(9); break; case S_DIV: expand(lO); break;
case S_PLUS: case S.MINUS: case S_RPAR: case S.ENFOFFILE: expand(ll); break; default: error("chybný symbol na vstupu -" +symbol.typ); } break;
case S_ID: case S_NUM:  ... case S_RZAV: pop(); break;
case S_HASH: if (symbol.typ == S.ENDOFFILE) accept(); eise error("chybný symbol na vstupu -" +symbol.typ); break;
default: error("chybný symbol na vstupu -" +symbol.typ);
Syntaktická analýza
Úl, FPF SU Opava
Možnosti Metoda přepisu rozkladové tabulky Rekurzivní sestup
O_0000000000000*0_oooooooooooooooo
Implementace
Hlavní funkce syntaktické analýzy
void S_analyza() { InitO;
while (! konec)
Akce(); Done();
}
Syntaktická analýza
Úl, FPF SU Opava
Možnosti Metoda přepisu rozkladové tabulky Rekurzivní sestup
O oooooooooooooo* oooooooooooooooo
Vlastnosti
Vlastnosti metody
Výhody:
• nepoužíváme přímo rekurzi (netřeba řešit problém hloubky rekurze s prostorovou složitostí).
• u překladů zahrnujících např. matematické výrazy se hůře implementuje sémantika,
• potřebujeme zásobník.
Syntaktická analýza
Úl, FPF SU Opava
Možnosti
O
Metoda přepisu rozkladové tabulky oooooooooooooo*
Rekurzivní sestup
oooooooooooooooo
Vlastnosti
Vlastnosti metody
Výhody:
• nepoužíváme přímo rekurzi (netřeba řešit problém hloubky rekurze s prostorovou složitostí).
Nevýhody:
• u překladů zahrnujících např. matematické výrazy se hůře implementuje sémantika,
• potřebujeme zásobník.
Syntaktická analýza
Úl, FPF SU Opava
Možnosti
O
Metoda přepisu rozkladové tabulky
ooooooooooooooo
Rekurzivní sestup •OOOOOOOOOOOOOOO
Myšlenka postupu
Rekurzívní sestup
Potřebujeme
• LL(1) gramatiku (nemusíme dělat rozkladovou tabulku),
• množiny FIRST a FOLLOW, pro každé pravidlo A —> a vytvoříme „množinu signatur"
FS(A, a) = FIRST(a ■ FOLLOW (A))
• proměnnou, ve které je uložen právě zpracovávaný symbol,
• funkci lex(), která nám vrátí další symbol, který extrahovala ze vstupního souboru (uloží do proměnné z předchozího bodu),
• proměnnou pro výstup.
Syntaktická analýza
Úl, FPF SU Opava
Možnosti Metoda přepisu rozkladové tabulky Rekurzivní sestup
o ooooooooooooooo o»oooooooooooooo
Myšlenka postupu
Popis metody
Analýza probíhá takto:
O zavoláme funkci lex(), pak opět voláme pro každý symbol,
O postupujeme tak, jakobychom konstruovali derivační strom „ručně"
O rekurzívní volání probíhá zleva doprava a shora dolů, vstup je čten zleva doprava, O když skončí rekurze a vstup je přečtený ($), akceptujeme vstup.
Syntaktická analýza
Úl, FPF SU Opava
Možnosti                                                                 Metoda přepisu rozkladové tabulky O_ooooooooooooooo_
Myšlenka postupu
Popis metody
Analýza probíhá takto:
O zavoláme funkci lex(), pak opět voláme pro každý symbol, O postupujeme tak, jakobychom konstruovali derivační strom „ručně":
• když jsme v uzlu ohodnoceném neterminálem, vytvoříme poduzly podle zvoleného pravidla,
• tentýž postup rekurzívně na všechny potomky, kteří jsou ohodnoceni neterminály,
• u terminálních poduzlů pouze spustíme „kontrolní porovnání".
O rekurzívní volání probíhá zleva doprava a shora dolů, vstup je čten zleva doprava, O když skončí rekurze a vstup je přečtený ($), akceptujeme vstup.
■■ i
Rekurzivní sestup o»oooooooooooooo
Syntaktická analýza
Úl, FPF SU Opava
Možnosti                                                                 Metoda přepisu rozkladové tabulky O_ooooooooooooooo_
Myšlenka postupu
Popis metody
Analýza probíhá takto:
O zavoláme funkci lex(), pak opět voláme pro každý symbol, O postupujeme tak, jakobychom konstruovali derivační strom „ručně":
• když jsme v uzlu ohodnoceném neterminálem, vytvoříme poduzly podle zvoleného pravidla,
• tentýž postup rekurzívně na všechny potomky, kteří jsou ohodnoceni neterminály,
• u terminálních poduzlů pouze spustíme „kontrolní porovnání".
O rekurzívní volání probíhá zleva doprava a shora dolů, vstup je čten zleva doprava, O když skončí rekurze a vstup je přečtený ($), akceptujeme vstup.
Rekurzivní sestup o»oooooooooooooo
Syntaktická analýza
Úl, FPF SU Opava
Možnosti                                                                 Metoda přepisu rozkladové tabulky O_ooooooooooooooo_
Myšlenka postupu
Popis metody
Analýza probíhá takto:
O zavoláme funkci lex(), pak opět voláme pro každý symbol, O postupujeme tak, jakobychom konstruovali derivační strom „ručně":
• když jsme v uzlu ohodnoceném neterminálem, vytvoříme poduzly podle zvoleného pravidla,
• tentýž postup rekurzívně na všechny potomky, kteří jsou ohodnoceni neterminály,
• u terminálních poduzlů pouze spustíme „kontrolní porovnání".
O rekurzívní volání probíhá zleva doprava a shora dolů, vstup je čten zleva doprava, O když skončí rekurze a vstup je přečtený ($), akceptujeme vstup.
Rekurzivní sestup o»oooooooooooooo
Syntaktická analýza
Úl, FPF SU Opava
Možnosti                                                                 Metoda přepisu rozkladové tabulky O_ooooooooooooooo_
Myšlenka postupu
Popis metody
Analýza probíhá takto:
O zavoláme funkci lex(), pak opět voláme pro každý symbol, O postupujeme tak, jakobychom konstruovali derivační strom „ručně":
• když jsme v uzlu ohodnoceném neterminálem, vytvoříme poduzly podle zvoleného pravidla,
• tentýž postup rekurzívně na všechny potomky, kteří jsou ohodnoceni neterminály,
• u terminálních poduzlů pouze spustíme „kontrolní porovnání".
O rekurzívní volání probíhá zleva doprava a shora dolů, vstup je čten zleva doprava, O když skončí rekurze a vstup je přečtený ($), akceptujeme vstup.
Rekurzivní sestup o»oooooooooooooo
Syntaktická analýza
Úl, FPF SU Opava
Možnosti
O_
Myšlenka postupu
Metoda přepisu rozkladové tabulky
ooooooooooooooo
Rekurzivní sestup o»oooooooooooooo
Popis metody
Analýza probíhá takto:
O zavoláme funkci lex(), pak opět voláme pro každý symbol,
O postupujeme tak, jakobychom konstruovali derivační strom „ručně":
• když jsme v uzlu ohodnoceném neterminálem, vytvoříme poduzly podle zvoleného pravidla,
• tentýž postup rekurzívně na všechny potomky, kteří jsou ohodnoceni neterminály,
• u terminálních poduzlů pouze spustíme „kontrolní porovnání".
O rekurzívní volání probíhá zleva doprava a shora dolů, vstup je čten zleva doprava,
O když skončí rekurze a vstup je přečtený ($), akceptujeme vstup.
Syntaktická analýza
Úl, FPF SU Opava
Možnosti
O_
Myšlenka postupu
Metoda přepisu rozkladové tabulky
ooooooooooooooo
Rekurzivní sestup o»oooooooooooooo
Popis metody
Analýza probíhá takto:
O zavoláme funkci lex(), pak opět voláme pro každý symbol,
O postupujeme tak, jakobychom konstruovali derivační strom „ručně":
• když jsme v uzlu ohodnoceném neterminálem, vytvoříme poduzly podle zvoleného pravidla,
• tentýž postup rekurzívně na všechny potomky, kteří jsou ohodnoceni neterminály,
• u terminálních poduzlů pouze spustíme „kontrolní porovnání".
O rekurzívní volání probíhá zleva doprava a shora dolů, vstup je čten zleva doprava, O když skončí rekurze a vstup je přečtený ($), akceptujeme vstup.
Syntaktická analýza
Úl, FPF SU Opava
Možnosti
O
Metoda přepisu rozkladové tabulky
ooooooooooooooo
Rekurzivní sestup 00*0000000000000
Myšlenka postupu
Popis metody
Budeme potřebovat tyto funkce:
• InitO, Done(),
• pop() ověří shodnost symbolů a posune se na vstupu,
• S(), A(), B(), ... - pro každý neterminál, tyto funkce se budou navzájem rekurzívně volat,
• errorQ ošetří chybu, která se vyskytla při překladu.
Syntaktická analýza
Ul, FPF SU Opava
Možnosti
O
Metoda přepisu rozkladové tabulky
ooooooooooooooo
Rekurzivní sestup 000*000000000000
Implementace
Příklad
S ->■ AB		©		
A^CD		©		
B -> +AB	-AB s	©.	©■	©
C -> (S) \ i	| n	©-	®.	©
D -> *CD |	/CD | e	®.	©.	©
Syntaktická analýza
Úl, FPF SU Opava
Možnosti O	Metoda přepisu rozkladové tabulky ooooooooooooooo	Rekurzivní sestup OOOO0OOOOOOOOOOO
Implementace		
Datové typy
enum TTypSymbolu { S.NOTHING, S.EMDOFFILE, S.LPAR, S.RPAR, S_ID, S_MUM, S_IS, S.PLUS, S.MIMUS, S_MUL, S_DIV };
J
struct TSymbol { TTypSymbolu typ; string atrib;
struct TVstup { char znak; int cisloRad; int pozice; int konec;
TSymbol symbol; TVstup vstup; bool konec;
Syntaktická analýza
Úl, FPF SU Opava
Možnosti
O
Metoda přepisu rozkladové tabulky
ooooooooooooooo
Rekurzivní sestup ooooo»oooooooooo
Implementace
Hlavní funkce syntaktické analýzy
Úkol:
inicializovat výpočet,
zavolat funkci S(), dále je vše voláno rekurzí, ukončit výpočet.
void S_analyza() { InitO; SO; Done();
}
Syntaktická analýza
Úl, FPF SU Opava
Možnosti
O
Metoda přepisu rozkladové tabulky
ooooooooooooooo
Rekurzivní sestup ooooo»oooooooooo
Implementace
Hlavní funkce syntaktické analýzy
Úkol:
inicializovat výpočet,
zavolat funkci S(), dále je vše voláno rekurzí, ukončit výpočet.
void S_analyza() { InitO; SO; Done();
}
Syntaktická analýza
Úl, FPF SU Opava
Možnosti O	Metoda přepisu rozkladové tabulky ooooooooooooooo	Rekurzivní sestup 000000*000000000	
Implementace			
Inicializace a ukončení			
void Init() {			
• • • Lex(); konec = false; };	// inicializace vstupu a výstupu // načte symbol ze vstupu do sym		
void Done() {			
• • • }	// uzavření vstupu a výstupu		
	4 □ ►   4 S> ►		
Syntaktická analýza		Úl, FPF SU Opava	
Možnosti O	Metoda přepisu rozkladové tabulky ooooooooooooooo	Rekurzivní sestup 0000000*00000000
Implementace		
Ošetření chyb
// vypíše číslo řádku, pozici na řádku a řetězec s daným hlášením void error(string hláska) { konec = true;
printf ("Chyba při syntaktické analýze na řádku °/,d, sloupci °/,d: °/,s", vstup.cisloRad, vstup.pozice, hláska);
}
Syntaktická analýza
Úl, FPF SU Opava
Možnosti
O
Metoda přepisu rozkladové tabulky
ooooooooooooooo
Rekurzivní sestup oooooooo»ooooooo
Implementace
Zpracování terminálů
porovná zpracovávaný symbol (terminál z pravidla) se znakem na vstupu, načte další znak ze vstupu.
int pop(TTypSymbolu terminal) { if (symbol.typ == terminal)
Lex(); // lexikální analyzátor načte další symbol
else error("chybný symbol na vstupu -" +VypisTyp(symbol.typ));
}
Syntaktická analýza
Úl, FPF SU Opava
Možnosti O	Metoda přepisu rozkladové tabulky ooooooooooooooo	Rekurzivní sestup OOOOOOOOO0OOOOOO
Implementace		
Funkce neterminálů
Pro každou množinu pravidel se stejnou levou stranou
A ai
OL2
a
n
void A() {
if (vstupni_sym) in FS(A,aii)
... postupně jsou ošetřeny symboly z řetězce a\ else if (vstupni_sym) in FS(A,ai2)
. . . postupně jsou ošetřeny symboly z řetězce ct2 else ... ostatní pravidla else error(...);
}
Syntaktická analýza
Úl, FPF SU Opava
Možnosti O	Metoda přepisu rozkladové tabulky ooooooooooooooo	Rekurzivní sestup OOOOOOOOO0OOOOOO
Implementace		
Funkce neterminálů
Pro každou množinu pravidel se stejnou levou stranou
A ai
OL2
a
n
void A() {
if (vstupni_sym) in FS(A,aii)
... postupně jsou ošetřeny symboly z řetězce a\ else if (vstupni_sym) in FS(A,ai2)
. . . postupně jsou ošetřeny symboly z řetězce ct2 else ... ostatní pravidla else error(...);
}
Syntaktická analýza
Úl, FPF SU Opava
Možnosti
O
Metoda přepisu rozkladové tabulky
ooooooooooooooo
Rekurzivní sestup OOOOOOOOOO0OOOOO
Implementace
Funkce neterminálů
S-> AB
void S() {
if (symbol.typ == S_ID || symbol.typ == S_NUM || symbol.typ == S_LPAR) { A(); B();
} eise error("chybný symbol na vstupu -" +VypisTyp(symbol.typ));
}
Syntaktická analýza
Úl, FPF SU Opava
Možnosti
O
Metoda přepisu rozkladové tabulky
ooooooooooooooo
Rekurzivní sestup ooooooooooo»oooo
Implementace
Funkce neterminálů
A^CD
void A() {
if symbol.typ (symbol.typ == S_ID || symbol.typ == S_MUM || symbol.typ == S_LPAR) { C(); D();
} else error("chybný symbol na vstupu -" +VypisTyp(symbol.typ));
}
Syntaktická analýza
Úl, FPF SU Opava
Možnosti O	Metoda přepisu rozkladové tabulky ooooooooooooooo	Rekurzivní sestup 000000000000*000
Implementace		
Funkce neterminálů
B -> +AB   - AB
e
void B() {
switch (symbol.typ) { case S_PLUS:
pop(S_PLUS);
A();
BO;
break; case S.MIMUS:
pop(S_MIMUS);
AO;
B();
break;
case S_RPAR: case S.ENDOFFILE: ;
default: error("chybný symbol na vstupu -" +VypisTyp(symbol.typ));
}
il
J
Syntaktická analýza
Ul, FPF SU Opava
Možnosti O	Metoda přepisu rozkladové tabulky ooooooooooooooo	Rekurzivní sestup OOOOOOOOOOOOO0OO
Implementace		
Funkce neterminálů
C -> (S) I i
n
j
void CO {
switch (symbol.typ) { case S_LPAR: pop(S_LPAR); SO;
pop(S_RPAR); break;
case S_ID: pop(S_ID); break; case S_MUM: pop(S_MUM); break;
default: error("chybný symbol na vstupu -" +VypisTyp(symbol.typ));
Syntaktická analýza
Úl, FPF SU Opava
Možnosti O	Metoda přepisu rozkladové tabulky ooooooooooooooo	Rekurzivní sestup OOOOOOOOOOOOOO0O
Implementace		
Funkce neterminálů
D -> *CD I /CD | e
void D() {
switch (symbol.typ) { case S_MUL:
pop(S.MUL);
C();
DO;
break; case S_DIV:
pop(S.DIV);
CO;
DO;
break;
case S.PLUS: case S.MIMUS: case S_RPAR: case S.ENDOFFILE: ; default: error("chybný symbol na vstupu -" +VypisTyp(symbol.typ));
}
3
J
Syntaktická analýza
Ul, FPF SU Opava
Možnosti Metoda přepisu rozkladové tabulky Rekurzivní sestup
O OOOOOOOOOOOOOOO OOOOOOOOOOOOOOO*
Vlastnosti
Vlastnosti metody
Výhody:
• není nutné vytvářet rozkladovou tabulku, třebaže množiny signatur vytvořit musíme,
• nepotřebujeme vlastní zásobník, rekurze probíhá pouze přes vzájemné volání funkcí (procedur) s použitím systémového zásobníku,
• není problém s navázáním sémantické analýzy.
• hloubka rekurze může za určitých okolností působit problémy s prostorovou složitostí.
Syntaktická analýza
Úl, FPF SU Opava
Možnosti
O
Metoda přepisu rozkladové tabulky
ooooooooooooooo
Rekurzivní sestup OOOOOOOOOOOOOOO*
Vlastnosti
Vlastnosti metody
Výhody:
• není nutné vytvářet rozkladovou tabulku, třebaže množiny signatur vytvořit musíme,
• nepotřebujeme vlastní zásobník, rekurze probíhá pouze přes vzájemné volání funkcí (procedur) s použitím systémového zásobníku,
• není problém s navázáním sémantické analýzy.
Nevýhody: I
• hloubka rekurze může za určitých okolností působit problémy s prostorovou složitostí.
Syntaktická analýza
Úl, FPF SU Opava