Č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 ;
- 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:
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 |