tree-walking-interpreter.py

import re
from enum import Enum, auto
from dataclasses import dataclass
from typing import List, Any, Optional

# ============== PARTE 1: ANÁLISE LÉXICA ==============

class TokenType(Enum):
    # Literais
    NUMBER = auto()
    
    # Operadores
    PLUS = auto()
    MINUS = auto()
    MULT = auto()
    DIV = auto()
    
    # Pontuação
    LPAREN = auto()
    RPAREN = auto()
    
    # Palavras-chave
    PRINT = auto()
    
    # Especiais
    EOF = auto()

@dataclass
class Token:
    type: TokenType
    value: Any
    position: int

class Lexer:
    def __init__(self, source: str):
        self.source = source
        self.position = 0
        self.tokens = []
    
    def current_char(self) -> Optional[str]:
        if self.position >= len(self.source):
            return None
        return self.source[self.position]
    
    def advance(self) -> None:
        self.position += 1
    
    def skip_whitespace(self) -> None:
        while self.current_char() and self.current_char().isspace():
            self.advance()
    
    def read_number(self) -> int:
        start = self.position
        while self.current_char() and self.current_char().isdigit():
            self.advance()
        return int(self.source[start:self.position])
    
    def read_identifier(self) -> str:
        start = self.position
        while self.current_char() and self.current_char().isalnum():
            self.advance()
        return self.source[start:self.position]
    
    def tokenize(self) -> List[Token]:
        while self.position < len(self.source):
            self.skip_whitespace()
            
            if self.current_char() is None:
                break
            
            # Números
            if self.current_char().isdigit():
                number = self.read_number()
                self.tokens.append(Token(TokenType.NUMBER, number, self.position))
            
            # Identificadores e palavras-chave
            elif self.current_char().isalpha():
                identifier = self.read_identifier()
                if identifier == "print":
                    self.tokens.append(Token(TokenType.PRINT, identifier, self.position))
                else:
                    raise SyntaxError(f"Identificador desconhecido: {identifier}")
            
            # Operadores e pontuação
            elif self.current_char() == '+':
                self.tokens.append(Token(TokenType.PLUS, '+', self.position))
                self.advance()
            elif self.current_char() == '-':
                self.tokens.append(Token(TokenType.MINUS, '-', self.position))
                self.advance()
            elif self.current_char() == '*':
                self.tokens.append(Token(TokenType.MULT, '*', self.position))
                self.advance()
            elif self.current_char() == '/':
                self.tokens.append(Token(TokenType.DIV, '/', self.position))
                self.advance()
            elif self.current_char() == '(':
                self.tokens.append(Token(TokenType.LPAREN, '(', self.position))
                self.advance()
            elif self.current_char() == ')':
                self.tokens.append(Token(TokenType.RPAREN, ')', self.position))
                self.advance()
            else:
                raise SyntaxError(f"Caractere inválido: {self.current_char()}")
        
        self.tokens.append(Token(TokenType.EOF, None, self.position))
        return self.tokens

# ============== PARTE 2: ÁRVORE SINTÁTICA ABSTRATA (AST) ==============

class ASTNode:
    """Classe base para todos os nós da AST"""
    pass

@dataclass
class NumberNode(ASTNode):
    """Nó para números literais"""
    value: int

@dataclass
class BinaryOpNode(ASTNode):
    """Nó para operações binárias (+, -, *, /)"""
    left: ASTNode
    operator: Token
    right: ASTNode

@dataclass
class PrintNode(ASTNode):
    """Nó para a função print"""
    expression: ASTNode

# ============== PARTE 3: ANÁLISE SINTÁTICA (PARSER) ==============

class Parser:
    def __init__(self, tokens: List[Token]):
        self.tokens = tokens
        self.position = 0
    
    def current_token(self) -> Token:
        if self.position < len(self.tokens):
            return self.tokens[self.position]
        return self.tokens[-1]  # EOF
    
    def advance(self) -> None:
        if self.position < len(self.tokens) - 1:
            self.position += 1
    
    def expect(self, token_type: TokenType) -> Token:
        """Verifica se o token atual é do tipo esperado e avança"""
        token = self.current_token()
        if token.type != token_type:
            raise SyntaxError(f"Esperado {token_type}, encontrado {token.type}")
        self.advance()
        return token
    
    def parse(self) -> ASTNode:
        """Ponto de entrada do parser"""
        return self.parse_statement()
    
    def parse_statement(self) -> ASTNode:
        """Parse de declarações (por enquanto, apenas print)"""
        if self.current_token().type == TokenType.PRINT:
            return self.parse_print()
        else:
            return self.parse_expression()
    
    def parse_print(self) -> PrintNode:
        """Parse da função print"""
        self.expect(TokenType.PRINT)
        self.expect(TokenType.LPAREN)
        expr = self.parse_expression()
        self.expect(TokenType.RPAREN)
        return PrintNode(expr)
    
    def parse_expression(self) -> ASTNode:
        """Parse de expressões (com precedência de operadores)"""
        return self.parse_addition()
    
    def parse_addition(self) -> ASTNode:
        """Parse de adição e subtração (menor precedência)"""
        left = self.parse_multiplication()
        
        while self.current_token().type in (TokenType.PLUS, TokenType.MINUS):
            operator = self.current_token()
            self.advance()
            right = self.parse_multiplication()
            left = BinaryOpNode(left, operator, right)
        
        return left
    
    def parse_multiplication(self) -> ASTNode:
        """Parse de multiplicação e divisão (maior precedência)"""
        left = self.parse_primary()
        
        while self.current_token().type in (TokenType.MULT, TokenType.DIV):
            operator = self.current_token()
            self.advance()
            right = self.parse_primary()
            left = BinaryOpNode(left, operator, right)
        
        return left
    
    def parse_primary(self) -> ASTNode:
        """Parse de elementos primários (números e expressões entre parênteses)"""
        token = self.current_token()
        
        # Número
        if token.type == TokenType.NUMBER:
            self.advance()
            return NumberNode(token.value)
        
        # Expressão entre parênteses
        elif token.type == TokenType.LPAREN:
            self.advance()
            expr = self.parse_expression()
            self.expect(TokenType.RPAREN)
            return expr
        
        else:
            raise SyntaxError(f"Token inesperado: {token.type}")

# ============== PARTE 4: INTERPRETADOR (TREE-WALKING) ==============

class Interpreter:
    """Tree-Walking Interpreter que percorre e executa a AST"""
    
    def visit(self, node: ASTNode) -> Any:
        """Método principal que despacha para o método apropriado baseado no tipo do nó"""
        method_name = f'visit_{node.__class__.__name__}'
        method = getattr(self, method_name, self.generic_visit)
        return method(node)
    
    def generic_visit(self, node: ASTNode) -> None:
        raise Exception(f'Nenhum método visit_{node.__class__.__name__} definido')
    
    def visit_NumberNode(self, node: NumberNode) -> int:
        """Visita um nó de número - simplesmente retorna seu valor"""
        print(f"  Visitando NumberNode: {node.value}")
        return node.value
    
    def visit_BinaryOpNode(self, node: BinaryOpNode) -> int:
        """Visita um nó de operação binária - avalia os operandos e aplica a operação"""
        print(f"  Visitando BinaryOpNode: {node.operator.value}")
        
        # Avalia o lado esquerdo
        left_value = self.visit(node.left)
        print(f"    Lado esquerdo = {left_value}")
        
        # Avalia o lado direito
        right_value = self.visit(node.right)
        print(f"    Lado direito = {right_value}")
        
        # Aplica a operação
        if node.operator.type == TokenType.PLUS:
            result = left_value + right_value
            print(f"    Resultado: {left_value} + {right_value} = {result}")
            return result
        elif node.operator.type == TokenType.MINUS:
            result = left_value - right_value
            print(f"    Resultado: {left_value} - {right_value} = {result}")
            return result
        elif node.operator.type == TokenType.MULT:
            result = left_value * right_value
            print(f"    Resultado: {left_value} * {right_value} = {result}")
            return result
        elif node.operator.type == TokenType.DIV:
            if right_value == 0:
                raise RuntimeError("Divisão por zero!")
            result = left_value // right_value  # Divisão inteira
            print(f"    Resultado: {left_value} // {right_value} = {result}")
            return result
        else:
            raise RuntimeError(f"Operador desconhecido: {node.operator.type}")
    
    def visit_PrintNode(self, node: PrintNode) -> None:
        """Visita um nó print - avalia a expressão e imprime o resultado"""
        print(f"  Visitando PrintNode")
        value = self.visit(node.expression)
        print(f"\n>>> SAÍDA DO PROGRAMA: {value}\n")
        return None

# ============== PARTE 5: FUNÇÃO PRINCIPAL ==============

def interpret(source: str) -> None:
    """Função principal que coordena todo o processo de interpretação"""
    print("=" * 50)
    print(f"CÓDIGO FONTE: {source}")
    print("=" * 50)
    
    # 1. Análise Léxica
    print("\n1. ANÁLISE LÉXICA (Tokenização)")
    print("-" * 30)
    lexer = Lexer(source)
    tokens = lexer.tokenize()
    print("Tokens gerados:")
    for token in tokens[:-1]:  # Não mostra EOF
        print(f"  {token.type.name:10} -> {token.value}")
    
    # 2. Análise Sintática
    print("\n2. ANÁLISE SINTÁTICA (Construção da AST)")
    print("-" * 30)
    parser = Parser(tokens)
    ast = parser.parse()
    
    def print_ast(node: ASTNode, indent: int = 0) -> None:
        """Função auxiliar para imprimir a AST"""
        spaces = "  " * indent
        if isinstance(node, NumberNode):
            print(f"{spaces}NumberNode({node.value})")
        elif isinstance(node, BinaryOpNode):
            print(f"{spaces}BinaryOpNode({node.operator.value})")
            print_ast(node.left, indent + 1)
            print_ast(node.right, indent + 1)
        elif isinstance(node, PrintNode):
            print(f"{spaces}PrintNode")
            print_ast(node.expression, indent + 1)
    
    print("Árvore Sintática Abstrata (AST):")
    print_ast(ast)
    
    # 3. Interpretação
    print("\n3. INTERPRETAÇÃO (Tree-Walking)")
    print("-" * 30)
    print("Caminhando pela árvore e executando:")
    interpreter = Interpreter()
    interpreter.visit(ast)
    
    print("=" * 50)

# ============== TESTES ==============

if __name__ == "__main__":
    # Exemplo principal
    print("\n### EXEMPLO 1: print(2 + 3 * 4)")
    interpret("print(2 + 3 * 4)")
    
    # Outros exemplos
    print("\n### EXEMPLO 2: print((2 + 3) * 4)")
    interpret("print((2 + 3) * 4)")
    
    print("\n### EXEMPLO 3: print(10 - 2 * 3)")
    interpret("print(10 - 2 * 3)")
    
    print("\n### EXEMPLO 4: print(100 / 5 + 3)")
    interpret("print(100 / 5 + 3)")