Úvod do kompilácie a interpretácie. Rekurzívna syntaktická analýza zhora nadol.

1+2*3

2^2^3

from enum import Enum, auto

# Definícia typov tokenov rozpoznávaných lexerom
class TokenType(Enum):
    NUMBER = auto()    # Číselná hodnota (prirodzené čí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)

# Trieda reprezentujúca token - kombinácia typu a atribútu (hodnoty)
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"Token({self.type}, {self.attribute})"
        return f"Token({self.type})"

# Lexikálny analyzátor - rozpoznáva a extrahuje tokeny zo vstupného reťazca
class Lexer:
    def __init__(self, input_text):
        self.input_text = input_text                       # Vstupný analýzovaný vstupný text
        self.pos = 0                                  # Aktuálne analyzovaná pozícia vo vstupnom texte
        self.current_char = self.input_text[0] if input_text else None # Aktuálny znak alebo None ak je vstupný text prázdny
    
    def advance(self):
        """Posunie pozíciu na ďalší znak a aktualizuje current_char.
        Ak sa dostane za koniec textu, nastaví current_char na None."""
        self.pos += 1
        if self.pos < len(self.input_text):
            self.current_char = self.input_text[self.pos]
        else:
            self.current_char = None  # Dosiahli sme koniec textu
    
    def skip_whitespace(self):
        """Preskočí všetky medzery a nové riadky vo vstupe."""
        while self.current_char is not None and self.current_char.isspace():
            self.advance()
    
    def number(self):
        """Vracia token typu NUMBER s číselnou hodnotou."""
        # TODO: Implementujte rozpoznávanie čísla pomocou Hornerovej schémy


    
    def get_next_token(self):
        """Hlavná metóda lexikálneho analyzátora.
        Analyzuje text a vracia ďalší token v poradí."""
        while self.current_char is not None:
            # Ignorovanie medzier a formátovanie
            if self.current_char.isspace():
                self.skip_whitespace()
                continue
            
            # Rozpoznávanie čísla 
            if self.current_char.isdigit():
                return self.number()
            
            # Rozpoznávanie operátorov a zátvoriek - jeden znak = jeden token
            if self.current_char == '+':
                self.advance()
                return Token(TokenType.PLUS)
            
            if self.current_char == '-':
                self.advance()
                return Token(TokenType.MINUS)
            
            if self.current_char == '*':
                self.advance()
                return Token(TokenType.MULTIPLY)
            
            if self.current_char == '^':
                self.advance()
                return Token(TokenType.POWER)
            
            if self.current_char == '(':
                self.advance()
                return Token(TokenType.LPAREN)
            
            if self.current_char == ')':
                self.advance()
                return Token(TokenType.RPAREN)
            
            # Ak narazíme na neznámy znak, vyhodíme chybu
            raise ValueError(f"Nerozpoznaný znak: '{self.current_char}'")
        
        # Keď prejdeme celý text, vrátime token konca vstupu
        return Token(TokenType.EOF)

from Lexer import TokenType

# Syntaktický analyzátor - implementuje rekurzívny zostup podľa gramatiky
class Parser:
    def __init__(self, lexer):
        self.lexer = lexer                        # Lexikálny analyzátor, ktorý dodáva tokeny
        self.current_token = self.lexer.get_next_token()  # Načítame prvý token
    
    def consume(self, expected_token_type):
        """
        Kontrolná metóda - kontroluje, či aktuálny token je očakávaného typu.
        Ak áno, posunie sa na ďalší token. Ak nie, vyhodí chybu.
        
        Táto metóda implementuje prediktívnu analýzu - očakávame konkrétny token
        na základe gramatických pravidiel.
        """
        if self.current_token.type == expected_token_type:
            self.current_token = self.lexer.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}")
    
    def E(self):
        """
        Implementuje gramatické pravidlo:
        E ::= T {("+" | "-") T}
        
        Spracuje sčítanie a odčítanie s ľavou asociativitou.
        Najnižšia priorita operácií v gramatike.
         
        """
        # Najprv vyhodnotíme prvé T
        result = self.T()
        
        # Potom spracujeme všetky ďalšie operácie sčítania a odčítania
        while self.current_token.type in (TokenType.PLUS, TokenType.MINUS):
            token = self.current_token
            
            if token.type == TokenType.PLUS:
                self.consume(TokenType.PLUS)  # Overíme a posunieme sa za '+'
                result += self.T()     # Vyhodnotíme hodnotu T a pripočítame ju do výsledku
                
            elif token.type == TokenType.MINUS:
                self.consume(TokenType.MINUS)  # Overíme a posunieme sa za '-'
                result -= self.T()   # Vyhodnotíme hodnotu T a odčítame ju od výsledku
                
        
        return result
    
    def T(self):
        """
        TODO: Implementujte gramatické pravidlo:
        T ::= F {"*" F}
        """

    
    def F(self):
        """
        TODO: Implementujte gramatické pravidlo:
        F ::= P ["^" F]
        """

    
    def P(self):
        """
        Implementuje gramatické pravidlo:
        P ::= cislo | "(" E ")"
        
        Spracuje základné prvky výrazu - buď číslo alebo výraz v zátvorke.
        Najvyššia priorita v gramatike.
        """
        token = self.current_token
        
        if token.type == TokenType.NUMBER:
            # Jednoducho vrátime hodnotu čísla
            self.consume(TokenType.NUMBER)  # Overíme a posunieme sa za číslo
            return token.attribute
            
        elif token.type == TokenType.LPAREN:
            # Vyhodnotíme výraz v zátvorkách
            self.consume(TokenType.LPAREN)  # Overíme a posunieme sa za '('
            result = self.E()        # Rekurzívne vyhodnotíme výraz medzi zátvorkami
            self.consume(TokenType.RPAREN)  # Overíme a posunieme sa za ')'
            return result
            
        else:
            # Ak nie je ani číslo ani zátvorka, ide o chybu
            raise SyntaxError(f"Syntaktická chyba: Neočakávaný token {token}")
    
    def parse(self):
        """
        Začne syntaktickú analýzu a vráti výsledok výrazu.
        Vstupný bod pre parser.
        """
        return self.E()  # Začíname volaním funkcie zopdovedajúcej zažiatočnému symbolu gramatiky

# Hlavná trieda interpretera, ktorá spája lexer a parser
class Calculator:
    def evaluate(self, expression):
        """
        Vyhodnotí aritmetický výraz a vráti výsledok.
        
        Args:
            expression (str): Reťazec obsahujúci aritmetický výraz
            
        Returns:
            int: Výsledok výrazu, alebo chybovú správu
        """
        try:
            lexer = Lexer(expression)   # Vytvoríme lexikálny analyzátor pre daný výraz
            parser = Parser(lexer)      # Vytvoríme syntaktický analyzátor
            result = parser.parse()     # Vyhodnotíme výraz podľa gramatiky
            return result
        except Exception as e:
            return f"Chyba: {str(e)}"   # Vrátenie chyby

def test_calculator():
    calc = Calculator()
    
    # Základné operácie
    print("2 + 3 =", calc.evaluate("2 + 3"))                 # Očakávaný výsledok: 5
    print("5 - 3 =", calc.evaluate("5 - 3"))                 # Očakávaný výsledok: 2
    print("2 * 3 =", calc.evaluate("2 * 3"))                 # Očakávaný výsledok: 6
    print("2 ^ 3 =", calc.evaluate("2 ^ 3"))                 # Očakávaný výsledok: 8
    
    # Priorita operátorov
    print("2 + 3 * 4 =", calc.evaluate("2 + 3 * 4"))         # Očakávaný výsledok: 14 (nie 20)
    print("(2 + 3) * 4 =", calc.evaluate("(2 + 3) * 4"))     # Očakávaný výsledok: 20
    print("2 * 3 ^ 2 =", calc.evaluate("2 * 3 ^ 2"))         # Očakávaný výsledok: 18 (nie 36)
    
    # Asociativita
    print("5 - 3 - 1 =", calc.evaluate("5 - 3 - 1"))         # Očakávaný výsledok: 1 (ľavá asociativita)
    print("2 ^ 2 ^ 3 =", calc.evaluate("2 ^ 2 ^ 3"))         # Očakávaný výsledok: 256 (pravá asociativita)
    
    # Komplexný výraz
    print("2 * (3 + 4) ^ 2 - 5 =", calc.evaluate("2 * (3 + 4) ^ 2 - 5"))  # Očakávaný výsledok: 93


if __name__ == "__main__":
    test_calculator()