Lexikálna analýza Flashcards
Aká je primárna úloha lexikálnej analýzy?
Čítanie znakov zo vstupu a ich preklad na postupnost’ tokenov, ktorú d’alej využije syntaktická analýza
Aké sú ďalšie úlohy lexikálnej analýzy?
- 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
Čo je token?
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.
Čo je pattern?
Pravidlo popisujúce množinu ret’azcov pre daný token
Čo je lexéma?
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.
Ako sa vie lexikálny analyzátor zotaviť z chyby? (ak postupnost’ čítaných znakov zo vstupu nezodpovedá žiadnemu patternu)
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
Ako funguje vstup pre LA?
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
Opíš dvojbufferovú schému
Opíš algoritmus 2bufferovej schémy
Opíš algoritmus 2bufferovej schémy s použitím zarážok
Ako spolupracuje LA a SA?
Opíš regulárne výrazy, ich formu
Aké sú nejaké “zločiny” LA?
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
Opíš atribúty tokenov
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, …)
Ako funguje tabuľka symbolov pri rozpoznaní tokenu?
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
Ako vieme implementovať tabuľku symbolov?
Aké sú kroky pri vytváraní lex. analyzátora?
Najskôr definuj množinu tokenov
Vytvor patterny pre jednotlivé tokeny
Implementuj rozpoznávanie patternov
Aké poznáme metódy tvorby lexikárneho analyzátora?
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
Čo sú konečné automaty?
Čo sú prechodové diagramy?
Opíš implementáciu prechodových diagramov
Ako vieme zostrojiť NKA pre L1|L2?
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é
Aké poznáme 2 prístupy k Thomsonovej metóde?
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|)
Opíš algoritmus Aho-Corasick
