2022 AFJ Prednáška + Cvičenie č. 6 - Množina FOLLOW

Zhrnutie prednášky

Prednáška nadväzuje na množinu FIRST a zavádza množinu FOLLOW pre neterminály redukovanej bezkontextovej gramatiky (CFG). FOLLOW(A) tvoria terminály, ktoré môžu vo vetnej forme odvoditeľnej zo štartovacieho neterminálu S stáť bezprostredne za neterminálom A; ak A môže stáť na konci vetnej formy, patrí do nej aj epsilon. Keďže každá derivácia začína symbolom S, do FOLLOW počiatočného neterminálu vždy patrí epsilon. Na príklade gramatiky so symbolmi S, A, B, C sa množiny FOLLOW najprv hľadajú „skúsmo“ skúšaním rôznych odvodení a čítaním susedných symbolov. Množiny slúžia na analýzu vetných foriem a neskôr sa použijú v algoritmoch na zisťovanie, či reťazec má deriváciu.

• - FOLLOW(A) obsahuje terminály, ktoré môžu vo vetnej forme bezprostredne nasledovať neterminál A.
• - Vetná forma je každá postupnosť symbolov odvoditeľná zo štartovacieho neterminálu S.
• - Epsilon patrí do FOLLOW(A), ak A môže stáť na konci nejakej vetnej formy.
• - Do FOLLOW počiatočného neterminálu vždy patrí epsilon, pretože každá derivácia začína symbolom S.
• - Na rozdiel od FIRST sa FOLLOW definuje len pre jednotlivé neterminály, nie pre ľubovoľné reťazce.
• - V príklade vyšlo FOLLOW(S) = {$, ), ε}, FOLLOW(A) = {(}, FOLLOW(B) = FOLLOW(C) = {$, )}.
• - FIRST aj FOLLOW sa neskôr využijú pri algoritmoch overujúcich, či reťazec má deriváciu.

Zhrnutie pripravené s pomocou AI z prepisu videa.