2022 AFJ Cvičenie č. 8 - Lexikálna analýza, FLEX

Zhrnutie prednášky

Cvičenie vysvetľuje princíp fungovania lexikálneho analyzátora na jednoduchom príklade s dvoma lexémami: identifikátorom (malé písmená a číslice začínajúce písmenom) a kľúčovým slovom end. Ku každej lexéme sa zostrojí konečný automat, ich zjednotením (epsilon prechodmi z nového počiatočného stavu) vznikne nedeterministický automat, ktorý sa determinizuje. Podľa akceptačného stavu, v ktorom výpočet skončí, sa rozpozná príslušná lexéma. Problémom je, že reťazec end spĺňa aj regulárny výraz pre identifikátor, čo je situácia bežná aj v reálnych jazykoch (napr. while v jazyku C). Riešením je buď komplikovaný regulárny výraz vylučujúci kľúčové slová, alebo praktickejšie priradenie priorít lexémam, kde end má vyššiu prioritu než identifikátor. Na začiatku sú oznámené podmienky testu: 20 bodov, 20 otázok so 4 odpoveďami.

• - Test: 20 bodov, 20 otázok, 4 odpovede s jednou správnou, zahŕňa aj lexikálnu analýzu.
• - Každá lexéma je popísaná regulárnym výrazom a jej deterministickým konečným automatom.
• - Automaty sa spoja zjednotením (nový počiatočný stav s epsilon prechodmi) a výsledný nedeterministický automat sa determinizuje.
• - Lexéma sa rozpozná podľa akceptačného stavu, v ktorom výpočet skončí.
• - Reťazec end spĺňa aj regulárny výraz pre identifikátor, takže vzniká nejednoznačnosť (podobne while v jazyku C).
• - Vylúčiť kľúčové slová priamo v regexe pre identifikátor je komplikované, najmä pri veľkej množine kľúčových slov.
• - V praxi sa nejednoznačnosť rieši prioritami lexém: kľúčové slovo end má vyššiu prioritu než identifikátor.

Zhrnutie pripravené s pomocou AI z prepisu videa.