Konštrukcia jazykových procesorov – Lexikálna analýza.

Krok 1

Programy určené na spracovanie počítačových jazykov vo všeobecnosti označujeme ako jazykové procesory a podľa ich účelu ich delíme do dvoch skupín:

• interpretátory a
• kompilátory.

Interpretátor je počítačový program, ktorý interpretuje iný program zapísaný v konkrétnom programovacom jazyku. Interpretátory môžu program interpretovať:

• riadok po riadku (z angl. line-by-line), alebo
• preložia program do tzv. medzikódu a tento medzikód potom vykonávajú.

Ak je v programe syntaktická chyba, prvý druh interpretátora vykoná program po túto syntaktickú chybu a ohlási chybu na príslušnom riadku, druhý druh interpretátora program nezačne vôbec vykonávať a ohlási chybu počas prekladu do medzikódu.

Kompilátory sú vo všeobecnosti zodpovedné za preklad programu zo zdrojového jazyka do cieľového jazyka. Na základe druhu cieľového jazyka potom rozlišujeme rôzne typy kompilátorov:

• štandardné kompilátory – realizujú preklad z vyššieho programovacieho jazyka do strojovo orientovaného jazyka,
• dekompilátory – realizujú preklad z nižšieho programovacieho jazyka do vyššieho programovacieho jazyka,
• transpiléry (transkompilátory) – realizujú preklad medzi vyššími programovacími jazykmi,
• a ďalšie.

Nasledujúci obrázok schematicky znázorňuje a porovnáva základné fázy spracovania zdrojového programu v procese kompilácie a interpretácie. Keďže iniciálne analytické fázy, medzi ktoré patrí lexikálna, syntaktická a sémantická analýza, predstavujú univerzálne kroky pri spracovaní programového kódu, sú prítomné aj v interpretačných modeloch. Rozdiel medzi kompiláciou a interpretáciou sa prejavuje predovšetkým v záverečnej fáze: kým kompilátor na základe vykonanej analýzy generuje cieľový kód (napr. strojový alebo medzikód), interpretátor program vykonáva priamo riadok po riadku alebo prostredníctvom interpretácie medzikódu.

Po všeobecnom predstavení procesov kompilácie a interpretácie sa v nasledujúcich častiach podrobnejšie zameriame na dve základné analytické fázy.

Krok 2

Prvou fázou spracovania zdrojového kódu je lexikálna analýza alebo tokenizácia, ktorej úlohou je čítať program zo vstupu, zapísaný v zdrojovom jazyku, po jednotlivých znakoch a rozdeliť ho na jednotlivé lexémy (logicky oddelené lexikálne jednotky).

Lexikálny analyzátor (angl. scanner) nahradí každú lexému kódom nazývaným token, ktorý je k danej lexéme ekvivalentný a z pohľadu syntaktickej analýzy predstavuje terminálny symbol.

Token ako vnútorný kódovaný tvar lexémy pozostáva z nasledujúcich súčastí:

• typ tokenu – kategória lexém s rovnakou vnútornou štruktúrou (napr. NUM_CONST pre numerickú konštantu) a
• atribút – doplnková informácia, ktorá obvykle predstavuje konkrétnu hodnotu lexémy (napr. číslo 4 pre token NUM_CONST). Tento údaj je nepovinný, keďže nie všetky lexémy disponujú hodnotou, napr. token reprezentujúci lexému + žiaden atribút nepotrebuje.

Pojmy lexéma a token priblížime na nasledujúcom príklade príkazu z jazyka Python, a to x = y + 5.

Výstupom lexikálnej analýzy je prúd tokenov (z angl. stream).

Konštrukcia lexikálneho analyzátora jazyka preto bude pozostávať z troch krokov:

1. Pre každý typ tokenu, teda skupinu lexém s rovnakou vnútornou štruktúrou, zostrojíme regulárny výraz popisujúci túto štruktúru. Z daného regulárneho výrazu následne vytvoríme DKA, ktorý podrobíme minimalizácii.
2. Z množiny DKA z predchádzajúceho kroku vytvoríme jeden NKA, ktorý bude rozpoznávať všetky lexémy daného jazyka. Postupujeme tak, že k DKA z predchádzajúceho kroku pridáme nový spoločný počiatočný stav a $\varepsilon$-prechody z tohto stavu do pôvodných počiatočných stavov každého DKA.
3. Výsledný NKA determinizujeme. Tento krok je nevyhnutný na zabezpečenie efektivity lexikálnej analýzy – dosiahnutie lineárnej výpočtovej zložitosti rozpoznávania lexém (v závislosti od ich dĺžky), ktorú zaručujú práve DKA.

Akceptovanie konkrétnej lexémy je realizované prechodom do takého (zloženého) stavu výsledného DKA, ktorý obsahuje akceptačný stav príslušného DKA vytvoreného v prvom kroku. V prípade ak daný stav obsahuje obsahuje viacero akceptačných stavov rôznych typov lexém, predpokladá sa pevne stanovená priorita určujúca, ktorý typ má prednosť pri kolízii.

Keďže lexikálny analyzátor, na rozdiel od štandardného konečnostavového automatu, nemá explicitnú informáciu o tom, kde začína a kde konči každá lexéma, rieši tento problém tak, že číta vstup postupne až do momentu, kým sa "nezasekne". Tým sa rozumie situácia, keď už neexistuje žiadny prechod, ktorým by mohol prejsť do ďalšieho stavu, potenciálne aj toho istého.

Ak sa lexikálny analyzátor v takomto okamihu nachádza v akceptačnom stave, vyhlási doteraz prečítaný reťazec za lexému a vráti jej zodpovedajúci token. Ak sa však nachádza v neakceptačnom stave, hľadá najbližší predchádzajúci akceptačný stav, vráti token zodpovedajúci lexéme rozpoznanej v tomto stave a ďalšiu lexému sa pokúsi rozpoznať od konca predchádzajúcej. Tento príncíp sa nazýva zásada najdlhšej zhody (z angl. longest match rule).

Krok 3

Riešenie

Postupovať budeme podľa vyššie prezentovaného princípu. Prvým krokom bude konštrukcia regulárnych výrazov pre jednotlivé typy tokenov:

• pre token typu VAR ide o triviálny regulárny výraz zhodný s týmto kľučovým slovom, teda

${}$
var,

• pre token typu ID zodpovedajúci skupine lexém predstavujúcich identifikátory to je

${}$
(a-z){a-z$\mid$A-Z$\mid$0-9}.

Následne môžeme na základe týchto regulárnych výrazov pristúpiť ku konštrukcii im zodpovedajúcich DKA (pozri Obr. 2). Na ich zostavenie nie je potrebné použiť žiadnu formálnu konštrukčnú metódu, keďže ide o triviálne regulárne výrazy. Z konštrukcie automatov je zároveň zrejmé, že ide o minimálne automaty, ktoré už nemožno ďalej minimalizovať.

Druhým krokom je konštrukcia jedného NKA z jednotlivých DKA zavedením nového spoločného počiatočného stavu, ktorý označíme $q_0$, a $\varepsilon$-prechodov z tohto stavu do pôvodných počiatočných stavov jednotlivých DKA.

Posledným krokom je determinizácia tohto NKA, výsledokm ktorej je DKA (pozri Obr. 4) schopný rozoznávať jednotlivé lexémy v lineárnom čase. Stavy výsledného DKA predstavujú nasledujúce zložené stavy: $$\underbrace{\{q_0,q_0',q_0''\}}_{A},\underbrace{\{q_1,\textcolor{green}{q_{\mathit{id}}}\}}_{B},\underbrace{\{q_2,\textcolor{green}{q_{\mathit{id}}}\}}_{C},\underbrace{\{\textcolor{red}{q_{\mathit{id}}},\textcolor{red}{q_{\mathit{var}}}\}}_{D},\underbrace{\{\textcolor{green}{q_{\mathit{id}}}\}}_{E}$$

Keďže zložené stavy $B$, $C$ a $E$ obsahujú len jediný akceptačný stav $q_{id}$, ide o stavy, v ktorých sú rozpoznávané identifikátory. Zložený stav $D$ obsahuje akceptačné stavy $q_{id}$ a $q_{var}$, čím vzniká konflikt medzi rozpoznaním identifikátora a kľúčového slova var. Tento konflikt je riešený na báze priority, čo znamená, že v tomto prípade má prednosť rozpoznanie špecifickejšej lexémy, teda kľúčového slova var.

Riešenie

Riešenie budeme opäť budovať postupne, pričom sa zameriame na formálny opis jednotlivých typov lexém a ich následnú automatovú reprezentáciu.

Najskôr je potrebné určiť regulárne výrazy zodpovedajúce jednotlivým tokenom. Operátor rozsahu RANGE je pevne daný symbolickou dvojicou bodiek, a preto je jeho regulárny výraz triviálny. V prípade celočíselných konštánt typu CONST_INT rozlišujeme buď samotnú nulu, alebo prirodzené číslo nezačínajúce nulou, čím sa eliminuje výskyt bezvýznamných núl zľava. Reálna konštanta CONST_REAL je tvorená celočíselnou časťou spĺňajúcou rovnaké obmedzenia ako CONST_INT, za ktorou nasleduje bodka a desatinná časť pozostávajúca z jednej alebo viacerých číslic.

Na základe týchto regulárnych výrazov zostrojíme DKA rozpoznávajúce jednotlivé triedy lexém (pozri Obr. 5). Vzhľadom na jednoduchú štruktúru výrazov ide o automaty s minimálnym počtom stavov, ktoré už nie je možné ďalej zjednodušiť.

Poznámka

Prítomnosť dvoch akceptačných stavov $q_\mathit{zro}$ a $q_\mathit{nat}$ v druhom DKA vyplýva zo štruktúry regulárneho výrazu 0$\mid$(1-9){0-9}, ktorý rozlišuje lexému 0 a lexémy prirodzených čísel bez bezvýznamných núl zľava. Hoci oba prípady predstavujú token typu CONST_INT, ich samostatné akceptačné stavy zjednodušujú zachytenie uvedeného lexikálneho obmedzenia.

V ďalšom kroku tieto automaty zlúčime do jedného NKA. To dosiahneme zavedením nového spoločného počiatočného stavu $q_0$, z ktorého vedú $\varepsilon$-prechody do počiatočných stavov všetkých pôvodných DKA. Takto vzniknutý NKA modeluje správanie lexikálneho analyzátora, ktorý je schopný paralelne sledovať všetky možné typy tokenov.

Keďže praktická implementácia lexikálneho analyzátora vyžaduje deterministický automat, pristúpime k determinizácii skonštruovaného NKA. Výsledkom je DKA, ktorého (zložené) stavy predstavujú množiny elementárnych stavov pôvodného NKA. Konkrétne ide o nasledujúce zložené stavy: $$\underbrace{\{q_0,q_0',q_0'',q_0'''\}}_{A},\underbrace{\{q_1'\}}_{B},\underbrace{\{\textcolor{green}{q_{\mathit{rng}}}\}}_{C},\underbrace{\{\textcolor{green}{q_{\mathit{zro}}}, q_1\}}_{D},\underbrace{\{\textcolor{green}{q_{\mathit{nat}}}, q_2\}}_{E}, \underbrace{\{q_3\}}_{F}, \underbrace{\{\textcolor{green}{q_{\mathit{rel}}}\}}_{G}$$

Akceptačné stavy výsledného DKA určujú typ rozpoznaného tokenu. V stave $C$ dochádza k rozpoznaniu operátora rozsahu. V stavoch $D$ a $E$ dochádza k rozpoznaniu celočíselnej konštanty a stav $G$ je jediným akceptačným stavom pre reálne konštanty. Takto skonštruovaný DKA umožňuje jednoznačné a efektívne rozpoznávanie všetkých požadovaných typov lexém v lineárnom čase vzhľadom na dĺžku vstupného reťazca.

Krok 4