KAPITOLA 3

´ ´ SYNTAKTICKA ANALYZA

44

Definice 3.6 (Syntakticka analyza metodou zdola nahoru) Syntakticka analyza me´ ´ ´ ´ todou zdola nahoru je proces nalezenı praveho rozkladu dane vety. ´ ´ ´ˇ Podobne jako u metody shora dolu, i zde se musıme rozhodovat mezi pravidly, ˇ ˚ ´ ktera chceme pouz´t. Tentokrat vsak nejde o pravidla se stejnou levou stranou ´ ˇı ´ˇ (pro stejny neterminal), ale rozhodujeme se mezi pravidly, ktera majı podobnou ´ ´ ´ ´ ˇ ˇı pravou stranu a jsou proto pouzitelna pro tentyz podretenec vetne formy. Res´me ˇ ´ ´ˇ ˇˇ ˇ´ to podobne jako u predchozı metody: ˇ ˇ ´ 1. Analyza s navratem – vybereme ve vetne forme jeden podretezec (jako prvnı ´ ´ ˇ´ ˇ ˇˇ ´ vybırame ten, ktery zac´na nejvıc vlevo, je co nejdels´ a je shodny s pravou ´´ ´ ˇı ´ ´ ˇı ´ stranou nektereho pravidla), prepıseme neterminalem na prave strane praviˇ ´ ˇ ´ˇ ´ ´ ˇ dla a pokracujeme v konstrukci derivacnıho stromu. Kdyz zjistıme, ze tento ˇ ˇ´ ˇ ´ ˇ krok nevede k uspechu, vyzkous´me jiny podretezec, . . . Tato metoda je jako ´ˇ ˇı ´ ˇˇ v predchozım pr´pade take casove narocna, proto nenı moc pouz´vana. ˇ ´ ˇı ˇ ´ˇ ˇ ´ ˇ´ ´ ˇı ´ 2. Deterministicka analyza – vyuz´vame dals´ informace zıskane pri prekladu, ´ ´ ˇı ´ ˇı ´ ´ˇˇ napr´klad obsah neprectene casti vstupnı pasky nebo obsah zasobnıku. ˇı ˇ ˇ ´ ˇ´ ´´ ´ ´

3.3
3.3.1

Pomocne mnoziny pro syntaktickou analyzu ´ ˇ ´
Mnoziny F IRST a F OLLOW ˇ

Pro analyzu vlastnostı gramatiky jazyka a take pro konstrukci automatu budeme ´ ´ ´ pouz´vat mnoziny F IRST a F OLLOW . Jsou to mnoziny terminalnıch symbolu ˇı ˇ ˇ ´´ ˚ definovane takto: ´ Definice 3.7 (F IRST , F OLLOW ) Oznacme α libovolnou vetnou formu generovanou ˇ ˇ gramatikou G. Potom F IRST (α) je mnozina terminalnıch symbolu, jimiz zac´najı retezce ˇ ´´ ˚ ˇ ˇı ´ ˇ ˇ ∗ derivovane z α. Pokud existuje derivace α ⇒ ε, pak ε ∈ F IRST (α). ´ Necht’ A je libovolny neterminal gramatiky G. Potom F OLLOW (A) je mnozina vsech ´ ´ ˇ ˇ terminalnıch symbolu a gramatiky G, ktere se mohou vyskytovat bezprostredne vpravo od ´´ ˚ ´ ˇ ˇ ∗ A v nejake vetne forme, tedy existuje derivace S ⇒ βAaγ . Pokud je v nektere derivaci ˇ ´ˇ´ ˇ ˇ ´ symbol A poslednım symbolem vetne formy, do mnoziny F OLLOW (A) radıme take symbol ´ ˇ´ ˇ ˇ´ ´ ukoncenı vstupnıho retezce $. ˇ´ ´ ˇˇ Do mnoziny F IRST („prvnı“) radıme vsechny terminaly, kterymi muze zac´ˇ ´ˇ´ ˇ ´ ´ ˚ˇ ˇı nat nektery retezec derivovany z testovane vetne formy, do mnoziny F OLLOW ˇ ´ˇ ˇ ´ ´ˇ´ ˇ