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

Krok 1

Syntaktická analýza alebo parsing je druhá fáza spracovania zdrojového kódu, 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 stromu odvodenia alebo 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.

Rekurzívny zostup interpretuje pravidlá gramatiky ako predpis pre štruktúru procedúr. Pri analyzátore s jedným symbolom dopredného pohľadu možno postupovať mechanicky, podľa nasledujúcich zásad zhrnutých taktiež v predchádzajúcej tabuľke:

• 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.
• Alternácii | 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.
• Kleeneho uzáveru resp. iterácii { } 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. Takto vytvorený strom poskytuje prehľadnú štruktúru, ktorá odhaľuje vnútornú reprezentáciu výrazu a zároveň slúži ako základ pre ďalšie fázy jeho prekladu, resp. interpretácie.

Celý proces postupnej transformácie vstupu od zdrojového textu, cez lexikálnu analýzu produkujúcu prúd tokenov, až po syntaktickú analýzu konštruujúcu strom odvodenia je schematicky znázornený na konkrétnom príklade vstupu na nasôedujúcom obrázku.

Krok 2

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.

Syntax 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}")

Krok 3

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.