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ů (symbolů), 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>\\/`

Lexikální gramatika

Specifikace programovacího jazyka často obsahuje sadu pravidel, lexikální gramatiku, která definuje lexikální syntaxi. Lexikální syntaxe je obvykle regulární jazyk s pravidly skládajícími se z regulárních výrazů; ty definují sadu množinu možných posloupností symbolů, které jsou použity k vytvoření individuálních tokenů nebo lexémů. Lexer rozpoznává řetězce a pro každý nalezený druh řetězce lexikální analyzátor provádí akci, nejčastěji vytváří token.

Důležité a zároveň běžné lexikální skupiny jsou bílé znaky, které oddělují dva tokeny (if x namísto ifx), a komentáře. Ty jsou rovněž definovány v gramatice a jsou zpracovávány lexerem, ale většinou jsou vyřazeny (neprodukují žádné tokeny) a jsou považovány za nepodstatné. Existují však dvě výjimky. Za prvé v jazycích, ve kterých jsou bloky kódu odděleny pomocí odsazení, je počáteční bílý znak podstatný, poněvadž definuje strukturu bloku a je obecně řešen na úrovni lexeru. Za druhé v určitých využitích lexeru mimo překladač musejí být komentáře zachovány. V šedesátých letech dvacátého století, především v jazyku ALGOL, byly bílé mezery a komentáře eliminovány při fázi rekonstrukce řádků (počáteční fáze přední části překladače), ale tato dříve oddělená fáze je nyní prováděna samotným lexerem.

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ů:

ve vstupním textu je přidán znak navíc
ve vstupním textu je znak vynechán
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:

opakovat pokus o nalezení větve v původním stavu
pokusit se nalézt nějakým způsobem stav, kam měl automat přejít a kam pokračovat
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

Lexikální analýza v České terminologické databázi knihovnictví a informační vědy (TDKIV)
http://quex.org – Quex: Nástroj pro generování lexikálních analyzátorů (anglicky)