2022 AFJ Prednáška č. 5 - Derivačné stromy

Zhrnutie prednášky

Prednáška rekapituluje, že jazyky sa členia podľa gramatík, ktoré ich generujú (regulárne, bezkontextové, kontextové a rekurzívne vyčísliteľné), a pripomína Chomského hierarchiu. Regulárne jazyky a konečné automaty majú obmedzenú výrazovú silu, preto sa v programovacích jazykoch hodia len na lexikálne elementy ako kľúčové slová, identifikátory či konštanty. Syntax konštrukcií, napríklad vetvenia alebo dobre uzátvorkovaných výrazov, vyžaduje silnejšie bezkontextové gramatiky, ktoré sa používajú aj na popis štruktúry dát, napríklad XML cez DTD. Ako príklad slúži jednoduchá gramatika pre dobre uzátvorkované výrazy a gramatika s neterminálmi E, T, F pre aritmetické výrazy, na ktorej sa krok za krokom ukazuje ľavé odvodenie reťazca, čo je úvod k derivačným stromom.

• - Jazyk je množina reťazcov a pomenúva sa podľa typu gramatiky, ktorá ho generuje.
• - Regulárne jazyky sú popísateľné konečnými automatmi, no ich výrazová sila je obmedzená.
• - Regulárne gramatiky v programovacích jazykoch popisujú lexikálne elementy: kľúčové slová, identifikátory, konštanty, operátory.
• - Dobre uzátvorkovaný výraz nemožno popísať regulárnou gramatikou, preto sú potrebné bezkontextové gramatiky.
• - Podľa Chomského hierarchie sú regulárne jazyky podmnožinou bezkontextových.
• - Bezkontextové gramatiky popisujú syntax programovacích jazykov a štruktúru dát, napríklad XML cez DTD.
• - Gramatika s neterminálmi E, T, F a terminálmi (, ), +, *, id popisuje aritmetické výrazy a slúži na ukážku postupného odvodzovania vetných foriem.

Zhrnutie pripravené s pomocou AI z prepisu videa.