Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Lexikální analýza

Definice (Lexikální analýza)

Lexikální analýza je část překladače, zodpovědná za rozpoznávání jednotlivých nedělitelných elementů zdrojového jazyka (např. klíčová slova, identifikátory, závorky atd.) a jejich převod na nějakou binární reprezentaci, vhodnou pro syntaktickou analýzu (např. uložení názvů identifikátorů do tabulek symbolů). V zásadě jde o rozpoznávání regulárních výrazů. Historicky šlo o provedení analýzy na celém zdrojáku a přeposlání do další fáze, dnes je většinou ovládaná ze syntaktické analýzy (opakované volání vrať další element). Slouží také ke zvětšení výhledu dalších fází (jedním elementem přestává být jeden znak, je jím jeden element vstupního jazyka).

Definice (Token, pattern)

Token je výstup lexikální analýzy - jeden nedělitelný element zdrojového jazyka. Je zároveň vstupem syntaktické analýzy (tam se nazývá terminál). Lexikální analýza uvažuje množinu řetězců, které produkují pro syntaktickou analýzu stejný token (např. díky ignore-caseovosti nebo jako důsledek sloučení všech řetězcových nebo číselných konstant pod stejný token, protože s nimi je dále nakládáno bez ohledu na hodnotu). Množina řetězců, produkujících daný token, se popisuje urč. pravidly - patternem, kde se obvykle užívá regulárních výrazů.

Definice (Lexém)

Lexém neboli lexikální element je sekvence znaků ve zdrojovém kódu, která (většinou) odpovídá nějakému patternu nějakého tokenu. Např. komentáře ale jako svůj výstup žádný token nemají.

Definice (Literál)

Literál je konstanta ve vstupním jazyce - má svoji hodnotu (atribut), ukládanou do tabulek symbolů.

Poznámka (Atributy tokenů)

Je-li jeden token rozpoznáván více patterny, nebo je-li to literál, má nějaké další atributy (většinou jenom jeden), které jeho význam upřesňují - např. token relační operátor má zpřesnění menší nebo rovno, token číselný literál má zpřesnění 12345.

Problémy lex. analýzy

Mezi některé problémy, které syntaktická analýza musí řešit, patří

- Počítání zarovnání - některé jazyky (Python) mají zarovnání na řádce jako svoji syntaktickou konstrukci
- Identifikátory s mezerami (rozlišit identifikátor od jiné konstrukce, i víceslovné)
- Klíčová slova jako identifikátory (někdy se mohou překrývat)
- Kontextově závislé tokeny - token závisí na jiných informacích (např. `a*b;` v C - jde o násobení, nebo deklaraci pointerové proměnné), tady je nutné tokeny slučovat pro oba významy ???

Pozadí lex. analýzy

Na pozadí lexikálního analyzátoru většinou pracuje nějaký konečný automat (protože rozpoznávání regulárních výrazů - hodnotou reg. výrazu je reg. jazyk - je práce pro konečné automaty). Po každém rozpoznaném tokenu je potřeba automat uvést zpět do výchozího stavu.

Lexikální chyby

Chyba v lexikální analýze nastane tehdy, když konečný automat nemůže pokračovat dál a není v koncovém stavu (např. pokud nalezne neplatný znak, nebo neukončený řetězec na konci řádky apod.). Většina lexikálních analyzátorů (pomineme Turbo Pascal ;-)) by měla být schopna nějakého rozumného zotavení z chyby - vypsat chybu a domyslet chybějící znak nebo neplatný znak ignorovat apod., tj. nezastavit se na první chybě. I logické zotavení může ale scanner úplně rozhodit a ten pak vyhazuje nesmyslné chyby. Je také spousta chyb, které lexikální analýza nepozná a projeví se až u syntaktické analýzy, např. `beign` místo `begin`, chápané jako identifikátor.

Poznámka (Bufferování vstupu)

Syntaktická analýza časově zabere cca 60-80% překladu, takže se pro její urychlení používá bufferování - nečte se po znacích, ale o něco napřed. Problémem pak jsou např. `#include` direktivy (jsou-li ve vstupním jazyce) - v okamžiku vložení jiného souboru je scanner v nějakém stavu apod.; scannery musí mít pak možnost přepínat mezi více vstupními soubory (manipulovat s několika buffery).