2022 AFJ Cvičenie č. 9 - Syntaktická analýza top-down, LL(1)-analyzátor

Zhrnutie prednášky

Cvičenie vysvetľuje, ako sa syntaktická analýza metódou zhora nadol (top-down) modeluje nedeterministickým zásobníkovým automatom. Analyzátor hľadá ľavú deriváciu vstupného reťazca a postupne buduje derivačný strom od koreňa k listom. V zásobníku je na začiatku počiatočný neterminál a automat používa dve základné operácie: ak je na vrchu neterminál, vykoná expanziu, čiže ho nahradí pravou stranou vhodného pravidla (symboly sa ukladajú odzadu), a ak je na vrchu terminál, vykoná porovnanie so vstupom, pri zhode symbol prečíta a odstráni zo zásobníka. Postup je ukázaný na príklade so vstupom begin p ; p ; end a pravidlami pre neterminály program, príkazy a príkaz, pričom sa paralelne zapisuje stav zásobníka, derivačný strom a ľavá derivácia.

• - Top-down analyzátor hľadá ľavú deriváciu a konštruuje derivačný strom od koreňa k listom.
• - Model analyzátora je nedeterministický zásobníkový automat, ktorého zásobníkovými symbolmi sú terminály a neterminály gramatiky.
• - Na začiatku je v zásobníku počiatočný neterminál gramatiky (v príklade program).
• - Expanzia: neterminál na vrchu zásobníka sa nahradí pravou stranou pravidla, symboly sa vkladajú od konca.
• - Porovnanie: terminál na vrchu zásobníka sa porovná s prvým neprečítaným symbolom vstupu; pri zhode sa symbol prečíta a odstráni.
• - Každá expanzia zodpovedá vytvoreniu potomkov vrcholu v derivačnom strome a ďalšiemu kroku ľavej derivácie.

Zhrnutie pripravené s pomocou AI z prepisu videa.