Lexikální analýza

Lexikální analýza je činnost, kterou provádí tzv. lexikální analyzátor (scanner) - je součástí překladače. Lexikální analyzátor rozdělí vstupní posloupnost znaků na lexémy - lexikální jednotky (např. identifikátory, čísla, klíčová slova, operátory, …). Tyto lexémy jsou reprezentovány ve formě tokenů, ty jsou poskytnuty ke zpracování syntaktickému analyzátoru.

Úkolem lexikálního analyzátoru je také odstranění komentářů a bílých znaků ze zdrojového programu.

V praxi je lexikální analyzátor realizován pomocí konečného automatu.

Definice lexikální analýzy

Lexikální analyzátor je vstupní a nejjednodušší částí překladače. Čte ze vstupního souboru znaky reprezentující zdrojový program a z těchto znaků vytváří symboly programu, což je forma vhodná pro zpracování syntaktickou analýzou. Provádí tedy překlad posloupnosti znaků vstupního textu do posloupnosti symbolů na výstupu. Kromě této základní funkce lexikální analyzátor provádí obvykle i výpis (listing) zdrojového programu a vynechává zbytečné znaky z hlediska programu (mezery, poznámky apod.). Symboly na výstupu lexikální analýzy si můžeme představit jako dvojice (sym, atr), kde sym je jméno (identifikace) symbolu a atr představuje případný atribut (u symbolů bez atribut je atr prázdné).

Z hlediska implementace v jazyku Pascal je vstupem lexikálního analyzátoru textový soubor (file of char) a výstupem posloupnost symbolů (tokens), přičemž

type Token = record
       SYM: SYMBOL; {jméno rozpoznaného symbolu}
       ATR: STR;    {atribut symbolu}
end;

Typ SYMBOL je datový typ definovaný výčtem, který obsahuje jména všech symbolů rozpoznaných lexikální analýzou. Typ STR je abstraktní datový typ řetězce. Cílem návrhu lexikálního analyzátoru je vytvořit proceduru:

procedure TOKGET(var T: TOKEN);

Předávající při každém volání jeden symbol T rozpoznaný ve vstupním textu.

Pojmy lexikální analýzy

Pattern 

pravidla popisující množinu řetězců pro daný token. Většinou využívá regulární výrazy.

Token 

výstup lexikální analýzy a vstup syntaktické analýzy. V syntaktické analýze se nazývá terminál.

Lexém 

sekvence znaků ve zdrojovém kódu, která odpovídá nějakému patternu určitého tokenu.

Literál 

konstanta s určitou hodnotou.

Token	Lexém	Regulární výraz
while	while	while
relop	<, <=, =, <>, >, >=	\<|\<=|\<>|>|>=
uint	0, 123	[0-9]+
	/*komentář*/	\/\*—> cmt, <cmt>., <cmt>\*\/

Generátory lexikálních analyzátorů

Existuji automatické nástroje pro tvorbu lexikálních analyzátorů, např. Lex, Flex

Algoritmus lexikální analýzy

Jak bylo uvedeno dříve, lexikální analyzátor provádí překlad vstupního textu na posloupnost symbolů. Víme, že stavbu jednotlivých symbolů lze obvykle popsat regulární gramatikou. Lexikální analyzátor je pak tvořen deterministickým konečným automatem (též DKA). Opakovanou činností procesoru nad tímto DKA získáme hledanou posloupnost symbolů. Identifikace přijatého symbolu se bude provádět podle koncového stavu automatu, v němž pro daný symbol procesor skončil svou činnost.

Chyby vzniklé během lexikální analýzy

Během chodu DKA může dojít k chybě. Chyba vznikne, pokud pro znak pod čtecí hlavou DKA neexistuje žádná větev vedoucí ze stavu, ve kterém se procesor nad DKA nachází a zároveň tento stav není koncový.

Taková chyba vznikne jedním ze tří možných způsobů:

1. ve vstupním textu je přidán znak navíc
2. ve vstupním textu je znak vynechán
3. ve vstupním textu je zaměněn správný znak za chybný

Každý z těchto tří typů chyb by se měl ošetřit jiným způsobem:

1. opakovat pokus o nalezení větve v původním stavu
2. pokusit se nalézt nějakým způsobem stav, kam měl automat přejít a kam pokračovat
3. vynechat zaměněný znak a pokračovat dále podle bodu 2.

Nelze předem předpokládat, kterou z chyb na daném místě programátor udělá, proto se obvykle ošetřuje chyba vynecháním chybného znaku a na výstup lexikálního analyzátoru se odevzdá speciální symbol (NULSYM). Tím se zotavením po chybě odsune do fáze syntaktické analýzy. Existují i metody známé z teorie informace (Hammingova vzdálenost), které mohou sloužit k opravě některých lexikálních chyb.

Ukázka konečného automatu v C

Související články

• GNU bison, yacc – generátory syntaktického analyzátoru
• flex lexical analyser, lex – generátory lexikálního analyzátoru
• Překladač

Externí odkazy

• http://quex.org – Quex: Nástroj pro generování lexikálních analyzátorů (anglicky)