2026 AFJ C12 - SLR(1)-parser

Zhrnutie prednášky

Cvičenie sa venuje konštrukcii SLR(1) analyzátora pre gramatiku generujúcu jazyk reťazcov nad abecedou {a,b} s rovnakým počtom výskytov oboch symbolov. Najprv sa overí, že gramatika je redukovaná, teda všetky pravidlá sú užitočné. Následne sa postupne konštruuje LR(0) konečný automat pomocou operácie LR(0) uzáveru a prechodov medzi stavmi na základe terminálov a neterminálov nasledujúcich za bodkou v položkách. Ukazuje sa, že hoci táto gramatika nie je vhodná pre LR(0) analyzátor kvôli konfliktom typu posun/redukcia, pre SLR(1) analýzu je použiteľná. Postupne sa vytvárajú stavy S0 až S10 a viac, pričom sa demonštruje princíp rozširovania položiek a prechodov medzi stavmi automatu.

• - Cieľom cvičenia je zostrojiť SLR(1) analyzátor pre gramatiku generujúcu reťazce s rovnakým počtom a a b
• - Najprv sa overuje, či je gramatika redukovaná (všetky pravidlá sú užitočné)
• - Gramatika nie je vhodná pre LR(0) analyzátor kvôli konfliktu posun/redukcia, ale je SLR(1)
• - Konštruuje sa LR(0) konečný automat pomocou LR(0) uzáveru položiek
• - Uzáver pridáva položky pre neterminály stojace za bodkou, prázdne pravidlá sa zapisujú len s bodkou na konci
• - Postupne sa vytvárajú stavy S0 až S10+ prechodmi na terminály a neterminály
• - Demonštruje sa praktický postup budovania tabuľky action a goto pre SLR(1) parser

Zhrnutie pripravené s pomocou AI z prepisu videa.