2026 AFJ P11 Syntaktická analýza zdola-nahor, LR(0)-analyzátor

Zhrnutie prednášky

Prednáška predstavuje syntaktickú analýzu zdola nahor (bottom-up) ako druhý základný prístup k budovaniu derivačného stromu, na rozdiel od LL(1) analýzy zhora nadol preberanej predtým. Vysvetľuje, že derivačný strom sa konštruuje od listov smerom ku koreňu, pravidlá gramatiky sa aplikujú opačne — pravá strana pravidla sa nahrádza ľavou (redukcia), a výsledkom je pravé odvodenie slova. Na jednoduchej gramatike programovacieho jazyka s begin/end blokmi príkazov sa demonštruje priebeh analýzy vstupného reťazca pomocou dvoch základných operácií — presunu vstupného symbolu do stromu ako listu a redukcie rozpoznanej pravej strany pravidla na príslušný neterminál. Zdôrazňuje sa, že tento proces je vo svojej podstate nedeterministický, keďže analyzátor sa musí rozhodovať medzi presunom a redukciou, vrátane špeciálneho prípadu redukcie prázdneho reťazca. Naznačuje sa, že determinizácia tohto procesu (analogicky k rozkladovej tabuľke pri LL analýze) bude témou nasledujúceho výkladu.

• - Bottom-up analýza konštruuje derivačný strom od listov ku koreňu, opačne než LL(1) prístup zhora nadol.
• - Pravidlá gramatiky sa aplikujú ako redukcie — pravá strana pravidla sa nahrádza ľavou stranou (neterminálom).
• - Výsledkom bottom-up analýzy je pravé odvodenie slova, kým LL(1) hľadá ľavé odvodenie.
• - Základné operácie analyzátora sú presun (shift) vstupného symbolu do stromu ako listu a redukcia rozpoznanej pravej strany pravidla.
• - Demonštrácia procesu na gramatike jednoduchého jazyka s pravidlami program→begin príkazy end a príkazy→príkaz;príkazy|ε.
• - Proces je nedeterministický — v každom kroku treba rozhodnúť medzi presunom a možnou redukciou.
• - Redukcia prázdneho reťazca (pravidlo príkazy→ε) sa môže uplatniť kdekoľvek vo vstupe, čo zvyšuje neurčitosť procesu.
• - Naznačená je potreba neskoršej determinizácie procesu podobne ako pri LL(1) rozkladovej tabuľke.

Zhrnutie pripravené s pomocou AI z prepisu videa.