2026 AFJ P12 SLR(1)-parser

Zhrnutie prednášky

Prednáška predstavuje syntaktický analyzátor typu SLR1 ako rozšírenie jednoduchšieho LR0 analyzátora, ktoré dokáže riešiť konflikty typu presun-redukcia a redukcia-redukcia vznikajúce v LR0 tabuľke action. Na konkrétnom príklade gramatiky sa ukazuje, že pri rozhodovaní o redukcii treba brať do úvahy aktuálny vstupný symbol a porovnávať ho s množinou FOLLOW neterminálu, na ktorý sa redukuje. Vysvetľuje sa teoretický princíp, podľa ktorého musí zreťazenie obsahu zásobníka a zvyšku vstupu tvoriť platnú pravú vetnú formu, čo je kľúčové kritérium na overenie správnosti redukcie. Na základe tejto úvahy sa formuluje všeobecné pravidlo: redukcia podľa pravidla B→ρ má zmysel iba vtedy, ak aktuálny vstupný symbol patrí do množiny FOLLOW(B). Toto pravidlo umožňuje odstrániť konflikty v LR0 automate a vytvoriť deterministickú tabuľku action pre SLR1 analyzátor.

• - SLR1 analyzátor rozširuje LR0 o využitie aktuálneho vstupného symbolu pri rozhodovaní o akcii.
• - LR0 konflikty (presun-redukcia, redukcia-redukcia) vznikajú, keď automat nezohľadňuje vstupný symbol.
• - Redukcia je platná len ak zreťazenie zásobníka a zvyšku vstupu tvorí platnú pravú vetnú formu.
• - Kľúčové kritérium: redukcia podľa pravidla B→ρ má zmysel iba ak vstupný symbol patrí do FOLLOW(B).
• - Na príklade gramatiky sa demonštruje, ako FOLLOW množiny neterminálov S a A rozhodujú o platnosti redukcií v stavoch S2 a S4.
• - Ak FOLLOW neterminálu obsahuje len prázdny reťazec, redukcia je platná iba pri úplne prečítanom vstupe.
• - Pomocou FOLLOW množín sa dá odstrániť konflikt v LR0 tabuľke a vytvoriť deterministickú SLR1 tabuľku action.

Zhrnutie pripravené s pomocou AI z prepisu videa.