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

Zhrnutie prednášky

Prednáška nadväzuje na bezkontextové gramatiky a motivuje ich použitie pri popise syntaxe programovacích jazykov a štruktúrovaných dát. Vysvetľuje parsovací problém, teda otázku, či má daný reťazec v danej gramatike deriváciu, a zdôrazňuje, že pre regulárne aj bezkontextové gramatiky je riešiteľný v polynomiálnom čase. Na jednoduchej gramatike ukazuje, že praktické parsovacie algoritmy z pravidiel extrahujú informáciu o tom, akým terminálom môže začínať reťazec odvodený z daného neterminálu. Takto možno niektoré reťazce odmietnuť ešte pred hľadaním derivácie. Tento princíp je úvodom k formálnej definícii množín FIRST a FOLLOW, ktoré sa využijú pri návrhu parserov.

• - Bezkontextové gramatiky popisujú syntax programovacích jazykov a štruktúrované dáta.
• - Parsovací problém: má reťazec v danej gramatike deriváciu z počiatočného neterminálu?
• - Pre regulárne a bezkontextové gramatiky je parsovanie polynomiálne, teda praktické.
• - Parsovacie algoritmy z pravidiel gramatiky extrahujú pomocnú informáciu, ktorá zjednodušuje hľadanie derivácie.
• - Množina FIRST určuje, akými terminálmi môže začínať reťazec odvodený z neterminálu.
• - Podľa FIRST možno reťazec odmietnuť, ak jeho prvý symbol nezodpovedá žiadnej možnosti (napr. reťazec začínajúci b pri gramatike, kde všetko začína a).
• - Množiny FIRST a FOLLOW sú príprava na neskoršie algoritmy syntaktickej analýzy v kompilátoroch.

Zhrnutie pripravené s pomocou AI z prepisu videa.