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. Jej úlohou je spracovať program zapísaný v zdrojovom jazyku ako postupnosť znakov a rozdeliť ho na logicky oddelené lexikálne jednotky, nazývané lexémy.

Lexikálny analyzátor (angl. scanner) priradzuje každej lexéme jej kódovanou reprezentáciu nazývanú token, ktorá je vhodná pre ďalšie spracovanie. Z pohľadu syntaktickej analýzy predstavuje token terminálny symbol. Ako vnútorná kódovaná reprezentácia lexémy sa token skladá z dvoch častí typu tokenu a atribútu.

Typ tokenu predstavuje kategóriu lexém s podobnou vnútornou štruktúrou a významom. Medzi základné typy tokenov patria:

• Identifikátory – predstavujú názvy premenných, funkcií alebo iných pomenovaných entít, napríklad: x, sum, counter1.
• Kľúčové slová – sú rezervované slová jazyka, ako napríklad: if, else, while, return a ďalšie.
• Separátory – slúžia na oddelenie alebo zoskupovanie častí programu, napríklad: ( ) { } ; ,
• Operátory – určujú operácie vykonávané nad operandmi, napríklad: +, -, *, /, ==, &&.
• Konštanty a literály – predstavujú pevné hodnoty zapísané priamo v programe, napríklad: 123, 3.14, "text", true.
• Špeciálne tokeny – používajú sa na signalizáciu špeciálnych stavov počas analýzy, napríklad dosiahnutie konca vstupu alebo výskyt neplatnej lexémy.

Atribút je doplnková informácia priradená tokenu, ktorá spravidla predstavuje konkrétnu hodnotu lexémy, napríklad číslo $4$ pre token typu NUM_CONST. Tento údaj je voliteľný, pretože nie všetky lexémy majú priradenú hodnotu. Napríklad token reprezentujúci lexému + atribút nepotrebuje.

Pojmy lexéma a token ilustrujeme na nasledujúcom príklade z programovacieho jazyka Python: 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

Prvým krokom pri implementácii lexikálneho analyzátora je návrh dátovej štruktúry pre token, ktorú realizujeme prostredníctvom nasledujúcej definície triedy Token:

# Trieda reprezentujúca token
class Token:
    def __init__(self, type: TokenType, value: str | None = None):
        self.type = type        # Typ tokenu (z enum TokenType)
        self.attribute = value  # Hodnota tokenu (relevantná hlavne pre identifikátory)

    def __repr__(self):
        # Reťazcová reprezentácia tokenu
        if self.attribute is not None:
            return f"<{self.type}, {self.attribute}>"
        return f"<{self.type}>"

Stavy a typy tokenov môžeme definovať pomocou enumeračných typov State a TokenType nasledovne:

# Definícia stavov
class State(Enum):
    A = auto()      # počiatočný stav
    B_ID = auto()  
    C_ID = auto()  
    D_VAR = auto() 
    E_ID = auto()  

# Definícia typov tokenov
class TokenType(Enum):
    VAR = auto()  # kľučové slovo var
    ID = auto()   # identifikátor
    EOF = auto()  # koniec vstupu
    ERR = auto()  # lexikálna chyba

Inicializácia lexikálneho analyzátora: Keďže táto implementácia stavia na báze iteratívnej implementácie DKA, konštruktor lexikálneho analyzátora preberá prechodovú tabuľku, akceptačné stavy a počiatočný stav. Okrem toho inicializuje ďalšie interné atribúty pre aktuálny stav automatu, vstupný reťazec, aktuálne spracovávanú pozíciu a symbol vo vstupnom reťazci.

# Lexikálny analyzátor - rozpoznáva a extrahuje tokeny zo vstupného reťazca
class Scanner:
    def __init__(self, transition_table : dict, accepting_states: dict, init_state: State):
        self.transition_table = transition_table
        self.accepting_states = accepting_states
        self.init_state = init_state
        self.current_state = None
        self.input_string = None
        self.pos = None
        self.current_char = None

Setter pre atribút vstupného reťazca:

    def set_input_string(self, string: str) -> None:
        self.input_string = string
        self.pos = 0
        self.current_char = self.input_string[0] if self.input_string and len(self.input_string)>0 else None

Pomocná metóda advance: Metóda posunie aktuálne spracovávanú pozíciu vo vstupnom reťazci a aktualizuje aktuálne spracovávaný znak. Ak sa pozícia dostane mimo rozsahu reťazca, aktuálne spracovávaný znak sa nastaví na hodnotu None.

    def advance(self) -> None:
        self.pos += 1
        if self.pos < len(self.input_string):
            self.current_char = self.input_string[self.pos]
        else:
            self.current_char = None

Ignorovanie bielych znakov: Lexikálny analyzátor ignoruje medzery, pretože z pohľadu lexikálnej analýzy slúžia nanajvýš ako separátory jednotlivých lexém.

    def skip_whitespaces(self) -> None:
        while self.current_char is not None and self.current_char.isspace():
            self.advance()

Hlavný algoritmus lexikálneho analyzátora: Táto metóda predstavuje rozhranie lexikálneho analyzátora, ktoré pri každom volaní spracuje časť vstupu a vráti nasledujúci token až pokiaľ nenarazí na koniec vstupu. Premenná last_accept uchováva posledný dosiahnutý akceptačný stav, čím umožňuje implementovať princíp najdlhšej zhody.

    def get_next_token(self) -> Token:
        self.skip_whitespaces()

        if self.current_char is None:
            return Token(TokenType.EOF)

        self.current_state = self.init_state
        token_start = self.pos
        token_end = self.pos
        last_accept = None

        while self.current_char is not None and (self.current_state, self.current_char) in self.transition_table:
            self.current_state = self.transition_table[(self.current_state, self.current_char)]

            if self.current_state in self.accepting_states:
                last_accept = self.current_state
                token_end = self.pos

            self.advance()

        if last_accept is None:
            error_token_end = self.pos
            # Zotavenie z lexikálnej chyby - prostredníctvom vynechania neočakávaného symbolu
            self.advance()
            return Token(TokenType.ERR, f"Lexikálna chyba! " f"Nerozpoznaná lexéma '{self.input_string[token_start:error_token_end+1]}' na pozícii {token_start + 1}")
        else:
            self.pos = token_end + 1

        token_type = self.accepting_states[last_accept]
        value = self.input_string[token_start:token_end+1] if token_type== TokenType.ID else None

        return Token(token_type, value)

Vyššie prezentovaný zdrojový kód predstavuje abstraktnú (všeobecnú) implemnetácia lexikálneho analyzátora. Inštanciovaním triedy Scanner poskytnutím prechodovej tabuľky, akceptačných stavov a počiatočného stavu z 1. príkladu 3. kroku získame konkrétnu implementáciu lexikálneho analyzátora pre jazyk identifikátorov a kľučového slova var.

if __name__ == "__main__":
    # Tabuľka prechodovej funkcie
    transition_table = {}
    
    # Funkcia pre naplnenie prechodovej tabuľky
    def add(state_from, chars, state_to):
        for c in chars:
            transition_table[(state_from, c)] = state_to
    
    LOWER = string.ascii_lowercase
    UPPER = string.ascii_uppercase
    DIGIT = string.digits

    add(State.A,"v",State.B_ID)
    add(State.A,LOWER.replace('v', ''),State.E_ID)

    add(State.B_ID,"a",State.C_ID)
    add(State.B_ID,LOWER.replace('a', '') + UPPER + DIGIT,State.E_ID)

    add(State.C_ID,"r",State.D_VAR)
    add(State.C_ID,LOWER.replace('r', '') + UPPER + DIGIT,State.E_ID)

    add(State.D_VAR,LOWER + UPPER + DIGIT,State.E_ID)

    add(State.E_ID,LOWER + UPPER + DIGIT,State.E_ID)

    # Slovník akceptačných stavov mapujúci stavy na v nich rozpoznávané typy tokenov
    accepting_states = {
        State.B_ID: TokenType.ID,
        State.C_ID: TokenType.ID,
        State.E_ID: TokenType.ID,
        State.D_VAR: TokenType.VAR
    }

    # Lexikálny analyzátor
    scanner = Scanner(transition_table=transition_table,
              accepting_states=accepting_states,
              init_state=State.A)

    input_string = input ("Zadaj vstupný reťazec> ")
    while input_string != "quit":
        scanner.set_input_string(input_string)
        token = scanner.get_next_token()
        print(token)
        while token.type != TokenType.EOF:
            token = scanner.get_next_token()
            print(token)
        input_string = input ("Zadaj vstupný reťazec> ")