Automaty a gramatiky (obsah)

Překladače jsou základním vybavením každého počítače, jakožto nástroje pro překlad z jednoho (programovacího) jazyka do druhého. Bez jejich existence by programování bylo prakticky nerealizovatelné, protože by programátoři museli psát ve strojovém kódu, což je v dnešní době již zcela nepředstavitelné. Programovací jazyky Z důvodu snadnější realizace programů a algoritmů vznikla celá řada programovacích jazyků, které jsou buď vázány na konkrétn...

Při syntaktické analýze shora-dolů bezkontextové gramatiky občas (skoro vždy) nemáme to štěstí a pro danou levou stranu pravidla existuje více pravých stran, čili jsme v situaci, kterou nejsme schopni deterministicky rozhodnout. Tento nedeterminismus jsme ale často schopni odstranit pomocí nápovědy, kterou je pro nás následující, dosud nezpracovaný, terminál. Pomocí něj jsme schopni ve většině případů rozhodnout, které pravidlo se má použít, tak...

Za předpokladu, že máme sestavenou (LL1) gramatiku a chceme pro daný vstup generovat i výstup, tak můžeme obohatit pravé strany gramatiky výstupními symboly. Tyto symboly mohou triviálně znamenat „vypiš symbol na výstup“ nebo volání nějaké metody. Tento postup je ovšem pro překlad složitějších jazyku příliš slabý, protože nám pro překlad nezajistí všechny potřebné informace. Pokud chceme výraz a = 5 + 3 jazyka C jako int a = 5 + 3, tak překladač ...

V některých případech, kdy gramatika není LL1, jsme schopni tuto gramatiku zmodifikovat takovým způsobem, aby LL1 byla. Eliminace levé rekurze Pokud obsahuje gramatika pravidlo ve tvaru A => Ab, pak se vždy jedná o gramatiku, která není LL1. Tuto vadu na kráse lze však poměrně jenoduše vyřešit. Mějme tedy pravidlo A => Ab1 | Ab2 | Ab3 | c1 | c2 Tato pravidla transformujme na A => c1A' | c2A' A' => b1A' | b2A' | b3A' | ε Pok...