2026 AFJ C11 LR(0)-parser

Zhrnutie prednášky

Cvičenie sa venuje konštrukcii LR0 analyzátora pre danú bezkontextovú gramatiku jazyka a^n b^n a^m b^m, pričom najprv sa overuje, že gramatika je redukovaná. Následne sa postupne buduje LR0 konečný automat, kde počiatočný stav S0 obsahuje položku pre rozšírené pravidlo S'→•S a pomocou operácie LR0 uzáveru (closure) sa doň dopĺňajú ďalšie položky pre neterminály A a B. Vysvetľuje sa princíp posúvania guličky v LR0 položkách pri prechodoch medzi stavmi na základe rozpoznávaných terminálnych a neterminálnych symbolov. Postupne sa odvodzujú stavy S1 a S2 na základe prechodov z S0 na symboly S a A, pričom sa demonštruje, ako sa v novom stave znovu aplikuje uzáver pre neterminál B.

• - Overenie, že gramatika je redukovaná pred konštrukciou LR0 automatu.
• - Zavedenie rozšíreného počiatočného pravidla S'→S pre počiatočný stav S0.
• - Vysvetlenie LR0 položky a významu guličky označujúcej rozpoznanú časť pravej strany pravidla.
• - Popis operácie LR0 uzáveru (closure) – pridávanie položiek pre neterminál za guličkou.
• - Konštrukcia prechodov medzi stavmi automatu na základe terminálnych a neterminálnych symbolov.
• - Odvodenie stavov S0, S1 a S2 vrátane opakovaného uzáveru pre neterminál B v stave S2.
• - Demonštrácia, že prechody a uzávery určujú štruktúru celého LR0 konečného automatu.

Zhrnutie pripravené s pomocou AI z prepisu videa.