Krok 1

Pri návrhu programovacích jazykov a vyhodnocovaní výrazov zohrávajú dôležitú úlohu dva základné koncepty, ktoré určujú spôsob, akým sa výrazy analyzujú a vyhodnocujú. Sú to

• priorita a
• asociativita operátorov.

Tieto vlastnosti možno vyjadriť už na úrovni syntaktického modelu jazyka (gramatiky),, čo vysvetlíme podrobnejšie v nasledujúcom kroku.

Špecifikácia priority operátorov

Priorita operátorov určuje, ktoré operácie majú prednosť pri vyhodnocovaní výrazov. Štandardne má napríklad operácia násobenia vyššiu prioritu ako operácia sčítania. Preto sa výraz 1+2*3 vyhodnotí na hodnotu $7$ a nie $9$. Pri syntaktickej špecifikácii priority operátorov v gramatike sa budeme riadiť nasledujúcimi pravidlami:

1. Pre každú úroveň priority operácii definujeme samostatný neterminálny symbol.
2. Pravidlá sa pre jednotlivé úrovne (neterminálne symboly) zreťazia tak, že smerom dovnútra (vnáranie k operandom) sa zvyšuje priorita.

Demonštrujme tento postup na nasledujúcom príklade gramatiky aritmetických výrazov.

Nech $G$ je gramatika $(\{$E, T, F$\},\{$+, *, (, )$\}$,$P$,E$)$, kde množina prepisovacích pravidiel v EBNF $P$ je daná nasledovne:

1. najvyššia úroveň priority: zátvorky (spracovávané v F),
2. stredná úroveň priority: násobenie (spracovávané v T),
3. najnižšia úroveň priority: sčítanie (spracovávané v E).

Porovnajme vplyv tvaru gramatiky na prioritu operátorov prostredníctvom zostrojenia stromov odvodenia pre ten istý syntaktický zápis aritmetického výrazu 1+2*3.

Špecifikácia asociativity operátorov

Asociativita operátorov zohráva dôležitú úlohu v prípadoch, keď sa v sekvencii vyskytne viacero operátorov s rovnakou prioritou. Určuje totiž, v akom poradí sa tieto operácie budú vyhodnocovať. Napríklad v aritmetických výrazoch:

• Ľavá asociativita: výraz 5−3−2 sa vyhodnotí ako (5−3)−2=0.
• Pravá asociativita: výraz 2^2^3 sa vyhodnotí ako 2^(2^3)=256. Doplníme, že ľavá asociativita by nebola pri umocňovaní užitočná – rovnaký výsledok sa dá dosiahnúť vďaka pravidlám pre mocniny pomocou súčinu exponentov (2^2)^3=2^(2*3).
• Neasociatívne operátory: operátory porovnania.

Pri implementácii syntaktického analyzátora pomocou rekurzívnych funkcií sa asociativita vyjadruje tvarom pravidiel gramatiky, a to nasledovne:

Porovnajme vplyv tvaru gramatiky na asociativitu operátorov prostredníctvom zostrojenia stromov odvodenia pre ten istý syntaktický zápis aritmetického výrazu 2^2^3.

Krok 2

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 základné fázy spracovania zdrojového programu v procese kompilá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, či už 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.

Lexikálna analýza (tokenizácia)

Prvou fázou kompilácie je lexikálna analýza, 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 koncový stav príslušného DKA vytvoreného v prvom kroku.

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 akceptujúcom 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 neakceptujúcom stave, hľadá najbližší predchádzajúci akceptujúci 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.

Syntaktická analýza (parsing)

Je to fáza, v rámci ktorej dochádza ku kontrole, či vstupná sekvencia tokenov zodpovedá gramatickým pravidlám jazyka. V jej priebehu sa vytvára vnútornú reprezentácia vstupného reťazca, často vo forme abstraktného syntaktického stromu (AST).

Pri tvorbe syntaktického analyzátora (angl. parser) je možné postupovať dvoma spôsobmi:

• zhora nadol (z angl. top-down),
• zdola nahor (z angl. bottom-up).

Rekurzívny zostup je najjednoduchší spôsob zostavenia syntaktického analyzátora zhora nadol, pretože začína od najvyššieho alebo najvzdialenejšieho gramatického pravidla a postupuje smerom nadol do vnorených podvýrazov, kým sa nedostane k listom odvodzovacieho stromu. To je v kontraste s analyzátormi zdola nahor, ktoré začínajú elementárnymi výrazmi a postupne ich skladajú do zložitejších syntaktických výrazov.

Analyzátor rekurzívneho zostupu je doslovný preklad pravidiel gramatiky priamo do imperatívneho kódu. Nasledujúca tabuľka prakticky prezentuje základné princípy implementácie takéhoto syntaktického analyzátora.

Vysvetlenie zásad z predchádzajúcej tabuľky:

• Hlavným princípom implementácie syntaktického analyzátora je vytvorenie procedúry s názvom neterminálneho symbolu na ľavej strane tohto pravidla pre každé pravidlo gramatiky.
• Neterminálnemu symbolu na pravej strane každého pravidla zodpovedá volanie procedúry.
• Terminálnemu symbolu zodpovedá volanie procedúry, ktorá prečíta zo vstupného reťazca ďalší terminálny symbol.
• Postupnosti symbolov na pravej strane každého pravidla zodpovedá postupnosť volaní procedúr uvedených v predchádzajúcich bodoch.
• Alternatíve | a výrazu voliteľnosti [ ] zodpovedá príkaz vetvenia (if alebo match-case, ktorý predstavuje switch-case konštrukciu v jazyku Python), vstup do príkazu vetvenia je bodom rozhodnutia.
• Tranzitívnemu uzáveru resp. opakovaniu { } zodpovedá príkaz cyklu (while). Vstup do príkazu cyklu je bodom rozhodnutia.
• Samotný proces analýzy sa spustí volaním procedúry zodpovedajúcej začiatočnému symbolu gramatiky.

Tok riadenia syntaktického analyzátora vyplývajúci z postupnosti volaní jednotlivých procedúr predstavuje odvodzovací strom analyzovaného (akceptovaného) výrazu.

Krok 3

V tomto kroku pristúpime ku konštrukcii gramatiky aritmetických výrazov, implementácii lexikálneho a syntaktického analyzátora a jeho záverečnej modifikácii na syntaxou riadený interpretátor.

Gramatika jazyka

Abeceda jazyka aritmetických výrazov, pozostáva z nasledujúcich terminálnych symbolov:

• terminálne symboly pre číselne konštanty (celé nezáporné čísla),
• ^ pre binárnu operáciu umocňovania s najvyššou úrovňou priority a štandardnou pravou asociativitou,
• * pre binárnu operáciu násobenia s nižšou úrovňou priority ako umocňovanie a ľavou asociativitou.
• + a - pre binárne operácie sčítania a odčítania s rovnakou najnižšou úrovňou priority a ľavou asociativititou,
• jazyk bude podporovať aj zátvorkované výrazy využitím terminálnych symbolov ( a ).

Výsledná gramatika: $G=(\{$E, T, F, X$\},\{$+, -, *, ^, (, )$\}, P$,E$)$ kde $P$ je nasledujúca množina prepisovacích pravidiel v EBNF:

Návrh a implementácia lexikálneho analyzátora

Nasledujúca séria obrázkov 7 až 9 ilustruje postupnú konštrukciu formálneho modelu lexikálneho analyzátora na báze DKA podľa vyššie prezentovaného postupu.

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, value=None):
        self.type = type        # Typ tokenu (z enum TokenType)
        self.attribute = value  # Hodnota tokenu (relevantná hlavne pre čísla)
    
    def __repr__(self):
        # Reťazcová reprezentácia tokenu
        if self.attribute is not None:
            return f"<{self.type}, {self.attribute}>"
        return f"<{self.type}>"

Typy tokenov môžeme definovať pomocou enumeračného typu TokenType nasledovne:

# Definícia typov tokenov
class TokenType(Enum):
    NUM_CONST = auto() # číselná konštanta (celé nezáporne číslo)
    PLUS = auto()      # operátor sčítania '+'
    MINUS = auto()     # operátor odčítania '-'
    MULTIPLY = auto()  # operátor násobenia '*'
    POWER = auto()     # operátor umocnenia '^'
    LPAREN = auto()    # ľavá zátvorka '('
    RPAREN = auto()    # pravá zátvorka ')'
    EOF = auto()       # koniec vstupu (End Of File)

Teraz sa podrobne pozrieme na implementáciu samotného lexikálneho analyzátora.

Inicializácia lexikálneho analyzátora: Vstupný reťazec sa uloží do internej premennej, pozícia aktuálne čítaného znaku vo vstupnom reťazci sa nastaví na hodnotu 0 a aktuálne čítaný znak na prvý znak vo vstupnom reťazci alebo na hodnotu None, v prípade ak je vstupný reťazec prázdny.

# Lexikálny analyzátor - rozpoznáva a extrahuje tokeny zo vstupného reťazca
class Scanner:
    def __init__(self, input_text):
        self.input_text = input_text
        self.pos = 0
        self.current_char = self.input_text[0] if input_text else None

Pomocná metóda advance: Metóda posunie aktuálnu pozíciu vo vstupnom reťazci a aktualizuje práve čítaný znak. Ak sa pozícia dostane mimo rozsahu reťazca, aktuálny znak sa nastaví na hodnotu None.

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

Ignorovanie bielych znakov: Lexikálny analyzátor ignoruje medzery, pretože pre analýzu aritmetických výrazov nie sú významné.

    def skip_whitespace(self):
        while self.current_char is not None and self.current_char.isspace():
            self.advance()

Hlavný algoritmus lexikálneho analyzátora: Táto metóda prechádza vstupný reťazec po znakoch a identifikuje jednotlivé lexémy:

    def get_next_token(self):
        while self.current_char is not None:
            # Ignorovanie medzier
            if self.current_char.isspace():
                self.skip_whitespace()
                continue
                
            # Rozpoznávanie jednotlivých lexém a priradenie im zodpovedajúcich tokenov
            match self.current_char:
                case '0':
                    self.advance()
                    return Token(TokenType.NUM_CONST, 0)
                # Rozpoznávanie numerálov
                case ch if ch.isdigit():
                    # Vracia token typu NUM_CONST s číselnou hodnotou.
                    # TODO: Implementujte rozpoznávanie čísla pomocou Hornerovej schémy
                case '+':
                    self.advance()
                    return Token(TokenType.PLUS)
                case '-':
                    self.advance()
                    return Token(TokenType.MINUS)
                case '*':
                    self.advance()
                    return Token(TokenType.MULTIPLY)
                case '^':
                    self.advance()
                    return Token(TokenType.POWER)
                case '(':
                    self.advance()
                    return Token(TokenType.LPAREN)
                case ')':
                    self.advance()
                    return Token(TokenType.RPAREN)
                case _:
                    # Ak narazí na neznámy znak, zahlási chybu
                    raise ValueError(f"Nerozpoznaný znak: '{self.current_char}'")

        # Keď prejde celý vstupný text, vráti token konca vstupného textu
        return Token(TokenType.EOF)

Návrh a implementácia syntaktického analyzátora

Po vytvorení lexikálneho analyzátora sa teraz zameriame na syntaktickú analýzu, ktorej cieľom je overiť, či sekvencia tokenov zodpovedá pravidlám gramatiky. Pristúpime preto k implementácii syntaktického analyzátora metódou rekurzívneho zostupu, ktorú opíšeme v nasledujúcich krokoch.

Inicializácia syntaktického analyzátora: Syntaktický analyzátor využíva lexikálny analyzátor ako sprostredkovateľa tokenov získavaných zo vstupného reťazca. Pri jeho inicializácii sa preto inštancia lexikálneho analyzátora uloží do internej premennej, aby mohla byť opakovane využívaná počas analýzy. Zároveň sa hneď na začiatku vykoná načítanie prvého tokenu zo vstupu.

# Syntaktický analyzátor
class Parser:
    def __init__(self, scanner):
        self.scanner = scaner
        self.current_token = self.scanner.get_next_token()

Pomocná metóda consume: Táto metóda slúži na kontrolu, či aktuálny token zodpovedá očakávanému typu podľa gramatických pravidiel. V prípade zhody zabezpečí posun na nasledujúci token. Ak typ tokenu nezodpovedá očakávaniu, ohlási syntaktickú chybu.

    def consume(self, expected_token_type):
        if self.current_token.type == expected_token_type:
            self.current_token = self.scanner.get_next_token()  # Prejdeme na ďalší token
        else:
            raise SyntaxError(f"Syntaktická chyba: očakávaný token {expected_token_type}, " 
                             f"získaný {self.current_token.type}")

Procedúra E: Táto procedúra je zodpovedná za spracovanie operácií sčítania a odčítania s najnižšou prioritou a ľavou asociativitou. Prvý operand sa spracuje volaním procedúry T, následne sa opakovane spracovávajú ďalšie podľa výskytu + alebo - vo vstupnom reťazci.

    def E(self):
        self.T()
        while self.current_token.type in (TokenType.PLUS, TokenType.MINUS):
            token = self.current_token
            
            if token.type == TokenType.PLUS:
                self.consume(TokenType.PLUS)
                self.T()
                
            elif token.type == TokenType.MINUS:
                self.consume(TokenType.MINUS) 
                self.T()

Štruktúra procedúr procedúry T je úplne analogická k štruktúre procedúry E. Istá variácia nastáva pri procedúre F, ktorá na rozdiel od E a T nepoužíva cyklus, ale podmienku a rekurzívne volanie. Táto zmena odráža pravú asociativitu operátora umocňovania, na rozdiel od ľavej asociativity operátorov sčítania odčítania a násobenia.

Procedúra X: Táto procedúra je zodpovedná za spracovanie základných stavebných prvkov aritmetických výrazov – číselných konštánt a taktiež vnorených výrazov v zátvorkách. Keďže ide o najnižšiu úroveň zostupu v gramatike, analyzátor v tomto bode očakáva výlučne numerál, alebo otváraciu zátvorku ako začiatok vnoreného výrazu.

Pri praktickej implementácii však nestačí pokryť len tieto dve možnosti. Je nevyhnutné počítať aj s prípadom, že sa na vstupe nachádza iný, neplatný symbol, teda taký, ktorý nezodpovedá žiadnemu inému prípadu tohto pravidla. Z tohto dôvodu implementácia obsahuje aj predvolenú vetvu (z angl. default), ktorá takúto situáciu identifikuje ako syntaktickú chybu.

def X(self):
    match self.current_token.type:
        case TokenType.NUM_CONST:
            self.consume(TokenType.NUM_CONST)
        case TokenType.LPAREN:
            self.consume(TokenType.LPAREN)
            self.E()
            self.consume(TokenType.RPAREN)            
        case _:
            raise SyntaxError(f"Syntaktická chyba: Neočakávaný token {self.current_token}")

Vstupný bod syntaktickej analýzy: Procedúra parse je hlavný spúšťač syntaktickej analýzy. Zavolá procedúru E a následne overí, či po spracovaní neostali ďalšie nespotrebované tokeny (čo by signalizovalo chybu). Je to bežný koncový krok v analyzátoroch.

    def parse(self):
        self.E()
        if self.current_token.type != TokenType.EOF:
            raise SyntaxError(f"Očakávaný koniec vstupu, nájdené: {self.current_token}")

Princíp syntaxou riadenej interpretácie výrazov

Syntaktická analýza môže byť rozšírená o priame vyhodnocovanie výrazu už počas jeho spracovania, čo predstavuje tzv. syntaxou riadená interpretácia. Na tento účel je však potrebné pristúpiť k miernej úprave implementácie syntaktického analyzátora prezentovanej v predchádzajúcom kroku: Namieto procedúr sú použité funkcie, ktorých návratová hodnota zodpovedá výsledku (hodnote) práve spracovávanej časti výrazu.