2022 AFJ Prednáška č. 9 doplnok

Zhrnutie prednášky

Prednáška nadväzuje na tému syntaktickej analýzy zhora nadol a LL1 analyzátora, pričom najprv zhrnie princíp fungovania zásobníkového automatu s operáciami expanzia a porovnanie riadenými rozkladovou tabuľkou. Následne sa venuje kľúčovému obmedzeniu tejto metódy – nie každú bezkontextovú gramatiku možno spracovať deterministicky, keďže v rozkladovej tabuľke môžu vzniknúť konflikty, ak je v niektorej bunke viac než jedno pravidlo. Na príklade gramatiky generujúcej reťazce s rovnakým počtom symbolov A a B sa demonštruje, ako nejednoznačnosť gramatiky spôsobuje takéto konflikty a znemožňuje jej klasifikáciu ako LL1 gramatiky. Ako riešenie sa uvádza možnosť nahradiť problematickú gramatiku ekvivalentnou LL1 gramatikou, generujúcou ten istý jazyk, hoci to má nevýhodu v prípadoch, keď tvar pôvodných pravidiel je dôležitý pre neskoršie spracovanie derivačného stromu, napríklad v sémantickej analýze pri kompilácii. Na záver sa zavádza príklad gramatiky opisujúcej podmienený príkaz (if-then-else) ako ilustráciu praktického problému s konfliktmi.

• - LL1 analyzátor funguje ako zásobníkový automat s operáciami expanzia a porovnanie riadenými rozkladovou tabuľkou
• - Nie každá bezkontextová gramatika sa dá spracovať LL1 analyzátorom deterministicky
• - Konflikt v rozkladovej tabuľke vzniká, ak bunka obsahuje viac než jedno pravidlo pre danú kombináciu neterminálu a terminálu
• - Gramatika, v ktorej rozkladovej tabuľke sú konflikty, sa nazýva ne-LL1 gramatika
• - Každá nejednoznačná gramatika je automaticky ne-LL1 gramatikou
• - Riešením konfliktu môže byť nahradenie gramatiky ekvivalentnou LL1 gramatikou generujúcou rovnaký jazyk
• - Úprava gramatiky má nevýhodu, ak je tvar pravidiel dôležitý pre neskoršie spracovanie derivačného stromu (napr. sémantická analýza)
• - Zavedený príklad gramatiky pre podmienený príkaz if-then-else ako ilustrácia praktického problému

Zhrnutie pripravené s pomocou AI z prepisu videa.