Lexikálna analýza

Question 1

Aká je primárna úloha lexikálnej analýzy?

Answer 1

Čítanie znakov zo vstupu a ich preklad na postupnost’ tokenov, ktorú d’alej využije syntaktická analýza

Question 2

Aké sú ďalšie úlohy lexikálnej analýzy?

Answer 2

• Uloženie informácie o tokenoch do tabul’ky symbolov
• Odstránenie komentárov a bieleho priestoru (medzery,
  tabulátory, znaky nového riadku)
• Zosúladit’ chybové hlásenia so zdrojovým programom

Question 3

Čo je token?

Answer 3

množina ret’azcov so spoločným významom
Výstup lexikálnej analýzy a vstup syntaktickej analýzy
napr. identifikátor, konštanta, operátor a pod.

Question 4

Čo je pattern?

Answer 4

Pravidlo popisujúce množinu ret’azcov pre daný token

Question 5

Čo je lexéma?

Answer 5

Postupnost’ znakov v zdrojovom programe, ktorá
zodpovedá patternu pre nejaký token

Lex. analyzátor rozpoznáva lexémy v zdrojovom programe a prekladá ich na príslušné tokeny.

Question 6

Ako sa vie lexikálny analyzátor zotaviť z chyby? (ak postupnost’ čítaných znakov zo vstupu nezodpovedá žiadnemu patternu)

Answer 6

1 Vymazanie znakov zo vstupu, kým sa nenájde ret’azec
zodpovedajúci niektorému patternu
2 Vloženie znakov navyše
3 Výmena nesprávneho znaku za správny
4 Výmena susedných znakov

Question 7

Ako funguje vstup pre LA?

Answer 7

Používa sa buffer
Treba čítať znak po znaku ale treba niekedy aj lookahead
1 Naraz je načítaný jeden blok znakov
2 Pozícia práve spracovávaného znaku je v bufferi označená
smerníkom
3 čítanie a spätné vrátenie znakov na vstup je riešené presunutím smerníka v bufferi

Question 8

Opíš dvojbufferovú schému

Answer 8

Question 9

Opíš algoritmus 2bufferovej schémy

Answer 9

Question 10

Opíš algoritmus 2bufferovej schémy s použitím zarážok

Answer 10

Question 11

Ako spolupracuje LA a SA?

Answer 11

Question 12

Opíš regulárne výrazy, ich formu

Answer 12

Question 13

Aké sú nejaké “zločiny” LA?

Answer 13

Odsadenie ako syntaktická konštrukcia (Python, Flex)
Povolené medzery v mene identifikátora, napr. Fortran
Kl’účové slová nie sú rezervované a môžu byt’ použité ako
identifikátory

Question 14

Opíš atribúty tokenov

Answer 14

Lex. analyzátor vracia v skutoňnosti dvojicu (token, atribút)
Atribút je upresnenie konkrétnej inštancie tokenu, pre synt. analýzu zväčša nemá význam ale využíva sa v d’al’ších fázach pri preklade (napr. smerník do tabuľky symbolov, hodnota, …)

Question 15

Ako funguje tabuľka symbolov pri rozpoznaní tokenu?

Answer 15

Pri rozpoznaní identifkátora sa najskôr skontroluje, či už je v tabul’ke symbolov
* Ak áno: vráti sa smerník na príslušný záznam
* Ak nie: pridá sa nový záznam

Question 16

Ako vieme implementovať tabuľku symbolov?

Answer 16

Question 17

Aké sú kroky pri vytváraní lex. analyzátora?

Answer 17

Najskôr definuj množinu tokenov
Vytvor patterny pre jednotlivé tokeny
Implementuj rozpoznávanie patternov

Question 18

Aké poznáme metódy tvorby lexikárneho analyzátora?

Answer 18

Prechodové diagramy
Thomsonova metóda (cez regulárne výrazy, jednoduché ale menej efektívne)
Naprogramovanie v programovacom jazyku (is_digit() a podobne využité)
Zahrnutie do syntaktickej analýzy

Question 19

Čo sú konečné automaty?

Answer 19

Question 20

Čo sú prechodové diagramy?

Answer 20

Question 21

Opíš implementáciu prechodových diagramov

Answer 21

Question 22

Ako vieme zostrojiť NKA pre L1|L2?

Answer 22

Máme 2 automaty, z prvého stavu kroky na epsilon do oboch, následne z ich akceptačných na epsilon do akceptačného. A podobne ostatné

Question 23

Aké poznáme 2 prístupy k Thomsonovej metóde?

Answer 23

r - reg. výraz, x - reťazec
1 Priama simulácia zostrojeného NKA
Priestor:O(|r|), čas:O(|r|×|x|)
2. Zostrojenie ekvivalentného DKA štandardnou konštrukciou, simulácia DKA
Priestor: O(2^|r|), čas: O(|x|)

Question 24

Opíš algoritmus Aho-Corasick

Answer 24