Syntaktická analýza v zásobníkových automatoch

Čo je syntaktická analýza a postup syntaktickej analýzy pre zásobníkové automaty (formálne jazyky).

Syntaktická analýza bezkontextovej gramatiky

Syntaktická analýza je algoritmus, ktorý má:

• vstup: bezkontextovú gramatiku a slovo $w$;
• výstup: poradie pravidiel alebo chyba (ak je na vstupe slovo ktoré nepatrí do jazyka; konkrétne napríklad zlá syntax programovacieho jazyka ktorú analyzujeme a podobne)

Analýza nám umožňuje vytvoriť prehľad o tom, ako sme postupovali pri vyhodnotení určitého slova (čo bolo na vstupe, v zásobníku a na výstupe), pretože klasický zápis krokov odvodenia nám neumožňuje vytvoriť obraz o tom, aké pravidlá bezkontextovej gramatiky sme použili a v akom poradí. Je to dôležité vtedy, ak chceme napríklad vylepšiť nejaký algoritmus alebo ho optimalizovať.

Syntaktická analýza zhora nadol

Napr. majme bezkontextovú gramatiku: $V\to 1|2|...|9|\text{+VV}|\text{*VV}$

Pri syntaktickej analýze tvoríme tabuľku. V tomto spôsobe je v prvom riadku tabuľky na začiatku v zásobníku vždy začiatočný neterminálny symbol. Teda:

Vstup	Zásobník	Výstup
* + 3 4 5	V

« Zásobníkové automaty