2022 AFJ Cvičenie č. 5 - Jednoznačnosť gramatiky, redukovaná gramatika.

Zhrnutie prednášky

Cvičenie nadväzuje na derivačné stromy v bezkontextových gramatikách a ukazuje, že strom nesie prídavnú informáciu o štruktúre reťazca, napríklad o priorite operátorov. Na jednoduchej gramatike pre vetvenie (if-then, if-then-else a jednoduchý príkaz p) je demonštrované, že reťazec if id then if id then p else p má dva rôzne derivačné stromy, podľa toho, ktoré pravidlo sa použije ako prvé. Prekladač vychádza práve z derivačného stromu, preto by ten istý kód dostal dve odlišné interpretácie: pri nepravdivej podmienke by sa v jednom prípade nevykonalo nič a v druhom by sa vykonal príkaz p. Z toho vyplýva pojem nejednoznačnej gramatiky, v ktorej má aspoň jeden reťazec viac derivačných stromov, na rozdiel od jednoznačnej gramatiky. Problém sa zhrnie ako otázka, ku ktorému if patrí else (tzv. dangling else), čo je ukázané aj na príklade v jazyku C.

• - Derivačný strom okrem derivácie vyjadruje aj štruktúru reťazca, napríklad prioritu operátorov.
• - Gramatika vetvenia s pravidlami if-then, if-then-else a príkaz p vytvára pre jeden reťazec dva rôzne derivačné stromy.
• - Prekladač generuje cieľový kód podľa derivačného stromu, takže dva stromy znamenajú dve rôzne interpretácie toho istého kódu.
• - Jednoznačná bezkontextová gramatika má pre každý odvoditeľný reťazec práve jeden derivačný strom.
• - Nejednoznačná gramatika má aspoň jeden reťazec s viacerými derivačnými stromami, čo je pri programovacích jazykoch vážny problém.
• - Klasický príklad nejednoznačnosti je tzv. dangling else: nie je jasné, ku ktorému if sa else viaže.

Zhrnutie pripravené s pomocou AI z prepisu videa.