2022 AFJ Prednáška č. 7 - Zásobníkové automaty

Zhrnutie prednášky

Prednáška uvádza zásobníkové automaty ako výpočtový model zodpovedajúci bezkontextovým jazykom, podobne ako konečné automaty zodpovedajú regulárnym jazykom. Úvod rekapituluje množiny first a follow, ktoré popisujú tvar vetných foriem a využijú sa v algoritmoch na zisťovanie, či reťazec má deriváciu v bezkontextovej gramatike, teda či je program syntakticky korektný. Zásobníkový automat tvorí konečná riadiaca jednotka, vstupná páska čítaná zľava doprava bez návratu a teoreticky nekonečný zásobník typu LIFO s operáciami push a pop. Pri každom kroku automat berie do úvahy aktuálny stav, vstupný symbol a symbol na vrchu zásobníka, tento symbol vyberie, prejde do nového stavu a na zásobník môže vložiť celý reťazec symbolov.

• - Bezkontextové jazyky sú akceptovateľné zásobníkovými automatmi, tak ako regulárne jazyky konečnými automatmi.
• - Zásobníkový automat je konečný automat rozšírený o zásobník s princípom LIFO.
• - Zásobník je teoreticky nekonečný a podporuje operácie push a pop.
• - Prechod závisí od aktuálneho stavu, vstupného symbolu a symbolu na vrchu zásobníka.
• - Pri prechode sa vyberie vrchný symbol zásobníka a vloží sa naň reťazec symbolov.
• - Množiny first a follow popisujú tvar vetných foriem a slúžia v algoritmoch na overenie derivácie reťazca.
• - Praktická motivácia: overenie syntaktickej správnosti programu a tvorba derivačného stromu pre kompiláciu.

Zhrnutie pripravené s pomocou AI z prepisu videa.