Obsah

Jazyk - množina slov složená pomocí konečné abecedy
Gramatika - seznam pravidel, která popisuje daný jazyk. Obsahuje terminály (konstanty), neterminály (proměnné) a počáteční neterminál S. Příklad: S → Ak, A → l. Vygeneruje jazyk: {nic, lk}
Bezkontextová gramatika - taková gramatika kde na levé straně jsou pouze neterminály
Regulární gramatika - bezkontextová gramatika, kde na pravé straně je maximálně jeden neterminál a jeden terminál.
DKA - Deterministický konečný automat - pro danou sekvenci znamků rozhodne jestli přijímá nebo nepřijímá. Obsahuje stavy, abecedu, přijímací stavy a tabulku přechodů - co se má stát pro každou kombinaci stavu a znaku na vstupu. Deterministický znamená že pro každý vstup a stav existuje jenom jeden přechod.
Derivační strom - gramatika přepsaná do stromu tak, že kořen je S, vnitřní uzly jsou neterminály a listy terminály.

Lexikální analyzátor

Lexikální analyzátor je první součástí překladače. Na vstupu dostává text a generuje lexikální symboly, které jsou terminálními symboly pro syntaktickou analýzu. Ignoruje části textu jako whitespace, komentáře atd. Lexikální symboly jsou popsány regulárními výrazy nebo regulární gramatikou. Analyzátor je obvykle implementován pomocí DKA. Jednotlivé symboly mohou mít také atributy - např. hodnotu proměnné.

Příklad:

Vstup: int i = 15;
Výstup: <integer> <ident i> <assignment> <number 15> <semicolon />

Syntaktický analyzátor shora dolů

LL(1) gramatiky

LL1 gramatika je postavena tak, aby se v žádném okamžiku nedostala do situace, ve které by mohlo jít zpracování vstupu více cestami (tj. zpracování je deterministické). Zásobníkový automat gramatiky je vždy schopen rozhodnout na základě svého stavu a prvního nezpracovaného znaku, do kterého dalšího stavu má přejít.

Průběh analýzy shora

Syntaktický analyzátor bere výstup s lexikálního analyzátoru a kontroluje jeho správnost podle LL(1) gramatiky. Realizuje se zásobníkovým automatem. Na začátku je na zásobníku počáteční neterminál. V každém kroku automat rozvine neterminály podle gramatiky. Když už to nejde dál rozvinout - je tam terminál - automat se podívá na vstup a porovná vstup s terminálem. Pokud se liší, vyhodí chybu. Pokud jsou stejné, posune vstup na další znak a odebere terminál ze zásobníku. Když je zásobník prázdný, slovo bylo přijato.

FIRST a FOLLOW

K rozvinutí neterminálů je potřeba rozkladová tabulka. Ta se z LL(1) gramatiky spočítá pomocí funkcí FIRST a FOLLOW.

FIRST(A) je množina terminálů, které mohou být na prvním místě když na levé straně je A
FOLLOW(A) má cenu počítat jenom když FIRST(A) obsahuje prázdný znak. Podíváme se na pravé strany pravidel a zjistíme jaké terminály mohou být hned za A.

Rozkladová tabulka

Rozkladová tabulka se používá pro rozvinutí neterminálů v syntaktické analýze. Je to tabulka neterminálů na terminály. Nedřív jí vyplníme podle FIRST. Pokud FIRST obsahuje prázdný znak, vyplníme také FOLLOW.

Syntaktický strom

Abstraktní syntaktický strom je výstupem překladače u interpretovaných jazyků. Je to strom, jehož vnitřní uzly jsou operátory a uzly operandy. Je abstraktní v tom smyslu, že neobsahuje všechny detaily původního kódu (jako to obsahuje derivační strom). Používá se pro zjednodušování a optimalizaci běhu kódu - např. když je operand disjunkce(OR) a levá větev vyjde true, můžeme přeskočit vyhodnocování pravé větve.