flowchart TD
A[📚 Autômatos de Pilha<br/>Semana 10] --> B[⬇️ Parser Descendente + AST<br/>Semana 11]
B --> C[⬆️ Parser Ascendente<br/>Semana 12]
B --> D[🧠 Análise Semântica<br/>Semana 13]
B --> E[🛠️ Projeto Integrador<br/>Parser Funcional]
E --> F[📝 Funções de Parsing]
E --> G[🌳 Construção de AST]
E --> H[⚠️ Recuperação de Erros]
Implementação de Parser com Construção de AST: Transformando Teoria em Código Funcional
⬇️
Hoje você finalmente implementará seu próprio parser recursivo descendente, construindo árvores sintáticas abstratas que capturam a estrutura essencial dos programas. Esta é a semana onde toda a teoria que você estudou se materializa em código funcional que analisa linguagens de programação!
Imagine que você tem um texto em uma linguagem de programação, como x = 5 + 3 * 2. Seu analisador léxico já transformou isso em tokens: [IDENTIFICADOR:x, IGUAL, NUMERO:5, MAIS, NUMERO:3, VEZES, NUMERO:2]. Agora você precisa entender a estrutura desse código! Qual operação acontece primeiro? Como representar essa hierarquia? É aqui que os parsers entram em ação, e hoje você aprenderá a construir um parser recursivo descendente que não apenas reconhece se o código está sintaticamente correto, mas também constrói uma representação estruturada dele chamada Árvore Sintática Abstrata (AST). Esta AST será a base para todas as análises posteriores do seu compilador!
🎯 Por Que Implementar Parsing É Tão Importante?
Quando você estudou gramáticas livres de contexto e autômatos de pilha nas semanas anteriores, você descobriu os fundamentos teóricos que descrevem a sintaxe de linguagens. Mas teoria sozinha não basta! Você precisa transformar essa teoria em código executável que realmente processa programas. O parsing é o processo de verificar se uma sequência de tokens segue as regras da gramática e, simultaneamente, construir uma representação estruturada do programa.
A importância do parsing vai muito além de simplesmente validar sintaxe. Um bom parser faz várias coisas simultaneamente: ele verifica correção sintática, constrói representações úteis para análises posteriores, detecta e reporta erros de forma compreensível, e se recupera de erros para continuar processando o resto do arquivo. Sem um parser robusto, seu compilador seria inútil, parando na primeira vírgula faltante ou parêntese desbalanceado.
💡 Intuição Central do Parsing Descendente
O parsing recursivo descendente é uma técnica elegante onde cada não-terminal da gramática se torna uma função no seu código. Estas funções se chamam recursivamente de forma que a estrutura do código espelha perfeitamente a estrutura da gramática. É uma correspondência direta e natural entre especificação formal e implementação concreta!
O aspecto “descendente” significa que começamos do símbolo inicial da gramática e tentamos “descer” na árvore de derivação até alcançar os tokens da entrada. É como se perguntássemos “dado que estou tentando reconhecer um não-terminal X, qual produção devo usar?” e fazêssemos essa escolha olhando para o próximo token disponível.
A beleza do parsing recursivo descendente está na sua simplicidade conceitual e elegância de implementação. Diferente de parsers baseados em tabelas que exigem pré-computação complexa, parsers descendentes podem ser escritos diretamente, quase como tradução linha por linha da gramática. Cada produção A \rightarrow \alpha da gramática sugere naturalmente um pedaço de código na função que reconhece A.
As vantagens práticas dessa abordagem são numerosas. Parsers descendentes produzem mensagens de erro excelentes porque sempre sabem exatamente qual estrutura estão tentando reconhecer. Eles são fáceis de debugar porque o código segue a estrutura da gramática de forma óbvia. São simples de modificar quando a linguagem evolui. E são suficientemente eficientes para uso prático em compiladores de produção.
As limitações também existem e são importantes de compreender. Parsers descendentes requerem gramáticas que satisfaçam certas propriedades, especialmente não podem ter recursão à esquerda direta e precisam permitir previsão determinística de qual produção usar olhando apenas para o próximo token. Estas limitações não são problemas insuperáveis; vocês aprenderão técnicas para transformar gramáticas problemáticas em formas adequadas.
📋 Conceitos Fundamentais: Tokens, Gramáticas e Árvores
Antes de mergulharmos na implementação, precisamos estabelecer claramente os conceitos fundamentais que fundamentam todo o processo de parsing. Estes conceitos já foram introduzidos em semanas anteriores, mas agora os revisitaremos sob a perspectiva de implementação prática.
Tokens: A Entrada Para o Parser
Tokens são os blocos atômicos que o parser recebe do analisador léxico. Cada token possui tipicamente duas informações: seu tipo (identificador, número, palavra-chave, operador, etc.) e seu valor (o texto exato que foi reconhecido). Por exemplo, o código if (x > 5) seria tokenizado como:
- Token(tipo=PALAVRA_CHAVE, valor=“if”)
- Token(tipo=PAREN_ESQ, valor=“(”)
- Token(tipo=IDENTIFICADOR, valor=“x”)
- Token(tipo=MAIOR, valor=“>”)
- Token(tipo=NUMERO, valor=“5”)
- Token(tipo=PAREN_DIR, valor=“)”)
O parser opera sobre esta sequência de tokens, sem se preocupar com espaços em branco, comentários, ou outros detalhes lexicais que já foram abstraídos pelo analisador léxico. Esta separação de responsabilidades entre léxico e sintático torna o design do compilador modular e limpo.
⚡ Interface Entre Léxico e Sintático
O parser consome tokens através de uma interface simples mas poderosa. Tipicamente, há duas operações principais:
- peek(): olha o próximo token sem consumi-lo (operação de “preview”)
- advance(): consome o token atual e avança para o próximo
Esta interface permite que o parser tome decisões olhando para frente sem se comprometer, essencial para parsing descendente preditivo.
Gramáticas: A Especificação Formal
A gramática define quais sequências de tokens são sintaticamente válidas na linguagem. Por exemplo, uma gramática simples para expressões aritméticas poderia ser:
Expressao → Termo ( ('+' | '-') Termo )*
Termo → Fator ( ('*' | '/') Fator )*
Fator → NUMERO | IDENTIFICADOR | '(' Expressao ')'Esta gramática captura a precedência de operadores: multiplicação e divisão ligam mais forte que adição e subtração. Note que a estrutura recursiva da gramática (Fator pode conter Expressao entre parênteses) permite aninhamento arbitrário.
A transformação dessa gramática em código é surpreendentemente direta no parsing recursivo descendente. Cada não-terminal vira uma função. Cada alternativa (separada por |) vira um bloco condicional. Cada sequência de símbolos vira chamadas sequenciais de funções ou verificações de tokens.
Árvores Sintáticas Abstratas: A Representação Estruturada
A Árvore Sintática Abstrata (Abstract Syntax Tree, ou AST) é a estrutura de dados que o parser constrói enquanto analisa o código. Diferente de árvores de derivação que mostram cada passo da aplicação das regras gramaticais, ASTs capturam apenas a informação semântica essencial, omitindo detalhes sintáticos irrelevantes como parênteses e palavras-chave que apenas servem para desambiguação.
Para a expressão 5 + 3 * 2, a AST seria:
graph TD
A["Binária: +"] --> B["Literal: 5"]
A --> C["Binária: *"]
C --> D["Literal: 3"]
C --> E["Literal: 2"]
style A fill:#e3f2fd
style C fill:#fff3e0
Observe que a estrutura da árvore captura automaticamente a precedência: a multiplicação está mais profunda na árvore, significando que é computada primeiro. Não há tokens de parênteses ou símbolos de operadores explícitos; a estrutura da árvore é que comunica as relações.
Os nós da AST tipicamente contêm informações necessárias para análises posteriores. Um nó representando uma declaração de variável pode ter campos para o nome da variável, seu tipo (se especificado), e sua expressão de inicialização. Um nó de chamada de função tem o nome da função e lista de argumentos. Esta representação estruturada facilita enormemente as fases subsequentes do compilador.
🏗️ Arquitetura do Parser: Estrutura e Componentes
Antes de implementar as funções de parsing específicas, precisamos estabelecer a arquitetura geral do parser. Uma estrutura bem projetada torna o código limpo, manutenível, e fácil de estender quando a gramática evolui.
Estrutura Básica da Classe Parser
Um parser recursivo descendente é tipicamente implementado como uma classe que mantém estado sobre o processo de parsing. Vamos ver a estrutura básica em pseudocódigo que você pode adaptar para Dart, C++, ou C:
classe Parser:
tokens: Lista<Token>
posicao_atual: Inteiro = 0
funcao construtor(tokens):
esta.tokens = tokens
esta.posicao_atual = 0
funcao peek() -> Token:
retorna tokens[posicao_atual]
funcao advance() -> Token:
token_atual = peek()
posicao_atual = posicao_atual + 1
retorna token_atual
funcao fim_da_entrada() -> Booleano:
retorna posicao_atual >= tamanho(tokens)
funcao verificar(tipo_esperado) -> Booleano:
se fim_da_entrada():
retorna falso
retorna peek().tipo == tipo_esperado
funcao consumir(tipo_esperado) -> Token:
se nao verificar(tipo_esperado):
erro("Esperado " + tipo_esperado + " mas encontrado " + peek().tipo)
retorna advance()Esta estrutura básica fornece as operações fundamentais que todas as funções de parsing usarão. A função peek() permite olhar o token atual sem consumi-lo. A função advance() move para o próximo token. A função verificar() testa se o token atual é de um tipo esperado. E consumir() é uma combinação que verifica e avança, lançando erro se o token não for do tipo esperado.
🔍 Padrão de Consumo Seguro
A função consumir() é extremamente útil porque combina verificação com avanço. Quando você sabe que um token específico deve aparecer (como um ponto-e-vírgula no final de uma declaração), usar consumir(PONTO_VIRGULA) garante que o token está lá ou produz erro claro se não estiver. Este padrão torna o código de parsing mais robusto e conciso.
Organização das Funções de Parsing
Cada não-terminal da gramática corresponde a uma função no parser. A organização dessas funções deve espelhar a hierarquia da gramática. Para a gramática de expressões que vimos anteriormente, teríamos:
funcao parsear_expressao() -> NodoAST:
// Implementação para Expressao → Termo ( ('+' | '-') Termo )*
...
funcao parsear_termo() -> NodoAST:
// Implementação para Termo → Fator ( ('*' | '/') Fator )*
...
funcao parsear_fator() -> NodoAST:
// Implementação para Fator → NUMERO | IDENTIFICADOR | '(' Expressao ')'
...A função para o símbolo inicial (tipicamente algo como parsear_programa()) será chamada primeiro e iniciará todo o processo. Esta função chamará outras funções de parsing conforme necessário, que por sua vez chamarão outras funções, criando uma cascata de chamadas recursivas que espelha a estrutura da gramática.
Design dos Nós da AST
Os nós da AST precisam de design cuidadoso porque eles são a principal saída do parser e a principal entrada para todas as fases subsequentes. Uma abordagem orientada a objetos funciona bem, com uma classe base abstrata e subclasses específicas para diferentes tipos de construções:
classe abstrata NodoAST:
posicao: Posicao // Localização no código fonte para mensagens de erro
classe NodoExpressao herda NodoAST:
// Classe base para todos os tipos de expressões
classe ExpressaoBinaria herda NodoExpressao:
operador: String
esquerda: NodoExpressao
direita: NodoExpressao
classe ExpressaoLiteral herda NodoExpressao:
valor: Objeto
classe ExpressaoIdentificador herda NodoExpressao:
nome: String
classe NodoDeclaracao herda NodoAST:
// Classe base para declarações (statements)
classe DeclaracaoVariavel herda NodoDeclaracao:
nome: String
tipo: String (opcional)
inicializador: NodoExpressao (opcional)Esta hierarquia de classes permite que código que percorre a AST (como o analisador semântico) trate uniformemente todos os nós enquanto ainda tem acesso a informações específicas de cada tipo de nó quando necessário.
🎨 Design Pattern: Visitor
Um padrão de design extremamente útil para trabalhar com ASTs é o padrão Visitor. Ele permite adicionar novas operações sobre a AST sem modificar as classes dos nós. Cada fase do compilador (análise semântica, geração de código, otimização) pode ser implementada como um visitor diferente que percorre a árvore realizando suas operações específicas.
Implementar o padrão Visitor requer adicionar um método aceitar(visitor) em cada classe de nó da AST, e criar uma interface Visitor com um método visitar para cada tipo de nó. Esta pequena complexidade inicial paga dividendos enormes em flexibilidade e organização do código.
🔄 Implementando Parsing Recursivo Descendente
Agora que estabelecemos a arquitetura, vamos implementar parsers recursivos descendentes de verdade. Começaremos com exemplos simples e progressivamente aumentaremos a complexidade, mostrando como lidar com vários desafios que surgem na prática.
Exemplo Básico: Expressões Aritméticas
Vamos implementar um parser completo para nossa gramática de expressões aritméticas. Este exemplo mostrará os princípios fundamentais que você aplicará em gramáticas mais complexas.
A gramática revisitada:
Implementação de parsear_expressao():
funcao parsear_expressao() -> NodoExpressao:
// Parseia o primeiro termo
esquerda = parsear_termo()
// Enquanto houver operadores + ou -
enquanto verificar(MAIS) ou verificar(MENOS):
operador = advance().valor // Consome o operador
direita = parsear_termo()
// Constrói nó binário e o torna a nova esquerda
esquerda = ExpressaoBinaria(operador, esquerda, direita)
retorna esquerdaEsta implementação segue diretamente a gramática. A notação ( ... )* na gramática vira um loop enquanto no código. Cada termo adicional se torna operando direito de um novo nó binário, e o resultado vira o operando esquerdo da próxima iteração, criando associatividade à esquerda naturalmente.
Implementação de parsear_termo():
A implementação de parsear_termo() é estruturalmente idêntica a parsear_expressao(), mas opera em um nível diferente da hierarquia:
O fato de parsear_termo() chamar parsear_fator() enquanto parsear_expressao() chama parsear_termo() cria automaticamente a precedência correta de operadores. Multiplicações e divisões são parseadas mais “profundamente” na árvore.
Implementação de parsear_fator():
funcao parsear_fator() -> NodoExpressao:
// Caso 1: Número literal
se verificar(NUMERO):
token = advance()
retorna ExpressaoLiteral(converter_para_numero(token.valor))
// Caso 2: Identificador (variável)
se verificar(IDENTIFICADOR):
token = advance()
retorna ExpressaoIdentificador(token.valor)
// Caso 3: Expressão entre parênteses
se verificar(PAREN_ESQ):
consumir(PAREN_ESQ)
expressao = parsear_expressao() // Recursão!
consumir(PAREN_DIR)
retorna expressao
// Nenhum caso correspondeu: erro de sintaxe
erro("Esperado expressão, mas encontrado " + peek().tipo)Esta função mostra como alternativas na gramática (separadas por |) se tornam condicionais no código. A chamada recursiva a parsear_expressao() no caso de parênteses permite aninhamento arbitrário de expressões.
✅ Teste Mental Valioso
Trace mentalmente como este parser processaria 3 + 4 * 2. Comece em parsear_expressao(). Ela chama parsear_termo(), que chama parsear_fator(), que retorna ExpressaoLiteral(3). Então vê o +, parseia outro termo (que será 4 * 2 analisado como uma multiplicação), e constrói ExpressaoBinaria('+', Literal(3), Binaria('*', Literal(4), Literal(2))). Perfeito!
Lidando com Associatividade
A implementação acima naturalmente produz associatividade à esquerda para todos os operadores porque construímos a árvore iterativamente de cima para baixo. Para 1 + 2 + 3, obtemos ((1 + 2) + 3), que é representado como:
graph TD
A["Binária: +"] --> B["Binária: +"]
A --> C["Literal: 3"]
B --> D["Literal: 1"]
B --> E["Literal: 2"]
style A fill:#e3f2fd
style B fill:#fff3e0
Se precisássemos de associatividade à direita (útil para exponenciação, por exemplo), teríamos que usar recursão em vez de iteração:
Esta versão constrói 2 ^ 3 ^ 4 como 2 ^ (3 ^ 4), que é o comportamento matematicamente correto para exponenciação.
Tratando Operadores Unários
Operadores unários como negação -x ou ! lógico requerem tratamento especial. Eles têm precedência mais alta que operadores binários e são naturalmente recursivos à direita (podemos ter --x ou !!valor):
Esta função se insere na hierarquia de precedência entre termos/fatores e os valores primitivos, garantindo que operadores unários ligam mais forte que operadores binários mas mais fraco que chamadas de função ou acesso a membros.
🌳 Construindo Árvores Sintáticas Abstratas Eficazes
A construção de ASTs é uma arte que equilibra completude de informação com simplicidade de representação. Uma AST bem projetada facilita tremendamente todas as fases subsequentes do compilador, enquanto uma AST mal projetada complica tudo que vem depois.
Princípios de Design de AST
O primeiro princípio fundamental é capturar semântica, não sintaxe. A AST deve representar o significado do código, não sua forma textual. Por exemplo, os códigos x = 5, x=5, e x = 5 devem todos produzir ASTs idênticas, porque semanticamente são a mesma coisa. Espaços em branco são irrelevantes.
Da mesma forma, parênteses não devem aparecer na AST. Para (5 + 3) * 2 e 5 + 3 * 2, as ASTs devem ser diferentes (refletindo a diferença na ordem de avaliação), mas essa diferença deve ser expressa através da estrutura da árvore, não através de nós representando parênteses. A estrutura comunica precedência de forma inerente.
O segundo princípio é manter informação de localização. Cada nó da AST deve saber onde no código fonte ele corresponde (arquivo, linha, coluna). Esta informação é fundamental para mensagens de erro de alta qualidade em fases posteriores. Quando o analisador semântico detecta uso de variável não declarada, ele precisa reportar exatamente onde no código o erro ocorreu.
O terceiro princípio é usar tipagem forte. Diferentes tipos de construções devem ser representados por diferentes tipos de nós. Não use uma única classe genérica Nodo com um campo tipo string. Use subclasses específicas como ExpressaoChamadaFuncao, DeclaracaoFuncao, ComandoIf, etc. Isto permite que o compilador detecte muitos erros em tempo de compilação e torna o código mais claro.
Exemplo: AST Para Declarações
Vamos ver como projetar nós AST para declarações de variáveis. Uma declaração de variável pode ter várias formas: int x;, int x = 5;, var x = 5; (com inferência de tipo). Nossa AST deve acomodar todas essas variações:
classe DeclaracaoVariavel herda NodoDeclaracao:
nome: String
tipo_explicito: String (opcional/nulo)
inicializador: NodoExpressao (opcional/nulo)
posicao: Posicao
funcao construtor(nome, tipo_explicito, inicializador, posicao):
esta.nome = nome
esta.tipo_explicito = tipo_explicito
esta.inicializador = inicializador
esta.posicao = posicaoCom esta estrutura, podemos representar todas as variações. Para int x;, teríamos DeclaracaoVariavel("x", "int", nulo, pos). Para var x = 5;, teríamos DeclaracaoVariavel("x", nulo, Literal(5), pos). Os campos opcionais permitem flexibilidade sem complicar a representação.
A função de parsing correspondente:
funcao parsear_declaracao_variavel() -> DeclaracaoVariavel:
posicao_inicio = peek().posicao
// Parseia tipo (ou 'var' para inferência)
tipo_explicito = nulo
se verificar(VAR):
consumir(VAR)
senao:
tipo_explicito = consumir(TIPO).valor
// Parseia nome da variável
nome = consumir(IDENTIFICADOR).valor
// Parseia inicializador se presente
inicializador = nulo
se verificar(IGUAL):
consumir(IGUAL)
inicializador = parsear_expressao()
consumir(PONTO_VIRGULA)
retorna DeclaracaoVariavel(nome, tipo_explicito, inicializador, posicao_inicio)Esta implementação segue a gramática naturalmente, usando campos opcionais para capturar as diferentes possibilidades sintáticas em uma única estrutura de dados unificada.
Exemplo: AST Para Estruturas de Controle
Comandos if-else ilustram bem como estruturas de controle são representadas. A AST precisa capturar a condição, o bloco então, e o bloco senão opcional:
A implementação do parser para if-else:
funcao parsear_comando_if() -> ComandoIf:
posicao_inicio = consumir(IF).posicao
consumir(PAREN_ESQ)
condicao = parsear_expressao()
consumir(PAREN_DIR)
bloco_entao = parsear_bloco()
bloco_senao = nulo
se verificar(ELSE):
consumir(ELSE)
bloco_senao = parsear_bloco()
retorna ComandoIf(condicao, bloco_entao, bloco_senao, posicao_inicio)
funcao parsear_bloco() -> Lista<NodoDeclaracao>:
comandos = []
consumir(CHAVE_ESQ)
enquanto nao verificar(CHAVE_DIR) e nao fim_da_entrada():
comandos.adicionar(parsear_declaracao())
consumir(CHAVE_DIR)
retorna comandosNote como parsear_bloco() chama parsear_declaracao() em loop para processar múltiplos comandos dentro das chaves. Esta função parsear_declaracao() seria um dispatcher que decide qual tipo específico de declaração parsear com base no próximo token.
🎯 Hierarquia de Chamadas de Parsing
Em um parser completo, há tipicamente uma hierarquia clara de funções:
parsear_programa()→ ponto de entrada, parseia múltiplas declarações de nível superiorparsear_declaracao()→ dispatcher que decide qual tipo de declaração parsearparsear_funcao(),parsear_variavel(),parsear_classe()→ parsers específicosparsear_bloco()→ parseia sequências de comandos entre chavesparsear_comando()→ dispatcher para diferentes tipos de comandosparsear_if(),parsear_while(),parsear_return()→ comandos específicosparsear_expressao()→ ponto de entrada para expressões- Hierarquia de precedência de operadores (termo, fator, etc.)
Esta organização torna o código modular e fácil de manter.
Otimizando a Representação da AST
Em linguagens com muitas construções sintáticas, a AST pode ter dezenas de tipos de nós diferentes. Para gerenciar essa complexidade, considere usar hierarquias de classes cuidadosamente projetadas. Por exemplo:
NodoAST
├─ NodoExpressao
│ ├─ ExpressaoBinaria
│ ├─ ExpressaoUnaria
│ ├─ ExpressaoLiteral
│ ├─ ExpressaoIdentificador
│ ├─ ExpressaoChamadaFuncao
│ └─ ExpressaoIndice (acesso a arrays)
└─ NodoComando
├─ ComandoExpressao (expressão como comando)
├─ ComandoIf
├─ ComandoWhile
├─ ComandoReturn
└─ ComandoDeclaracao
├─ DeclaracaoVariavel
├─ DeclaracaoFuncao
└─ DeclaracaoClasseEsta hierarquia permite que código que percorre a AST trate categorias amplas de nós (todas as expressões, todos os comandos) uniformemente quando apropriado, mas ainda acesse informações específicas quando necessário.
Padrões de percorrimento da AST são fundamentais. Você frequentemente precisará “visitar” cada nó da árvore para realizar alguma análise. O padrão Visitor mencionado anteriormente é perfeito para isso:
interface Visitor:
funcao visitar_expressao_binaria(nodo: ExpressaoBinaria)
funcao visitar_expressao_literal(nodo: ExpressaoLiteral)
funcao visitar_comando_if(nodo: ComandoIf)
// ... um método para cada tipo de nó
classe NodoAST:
funcao abstrata aceitar(visitor: Visitor)
classe ExpressaoBinaria:
funcao aceitar(visitor: Visitor):
visitor.visitar_expressao_binaria(esta)Com este padrão, adicionar uma nova análise sobre a AST (como otimização ou geração de código) é apenas questão de criar uma nova classe Visitor sem modificar as classes de nós.
⚠️ Recuperação de Erros: Tornando o Parser Robusto
Um parser que para no primeiro erro é frustrante de usar. Imagine estar escrevendo código e receber apenas uma mensagem de erro por vez! Você corrigi um erro, recompila, e descobre o próximo erro. Este ciclo lento desperdiça tempo e prejudica produtividade. Parsers profissionais implementam recuperação de erros para detectar e reportar múltiplos erros em uma única passada.
Estratégia de Modo de Pânico
A estratégia mais comum e eficaz é o modo de pânico com sincronização. Quando o parser encontra um erro (token inesperado), ele entra em “modo de pânico”, descartando tokens até encontrar um token de sincronização onde pode recuperar e continuar o parsing.
Os tokens de sincronização são escolhidos estrategicamente. Tipicamente incluem:
- Delimitadores de declarações (ponto-e-vírgula)
- Palavras-chave que iniciam novas declarações (
if,while,function,class) - Fechamento de blocos (chave direita
})
Implementação básica:
funcao sincronizar():
enquanto nao fim_da_entrada():
// Se encontramos ponto-e-vírgula, consumimos e retornamos
se peek().tipo == PONTO_VIRGULA:
advance()
retorna
// Se o próximo token inicia uma nova declaração, retornamos sem consumi-lo
se peek().tipo em [IF, WHILE, FOR, FUNCTION, CLASS, VAR]:
retorna
// Continua descartando tokens
advance()
funcao parsear_declaracao() -> NodoDeclaracao:
tentar:
// Tenta parsear normalmente
se verificar(VAR):
retorna parsear_declaracao_variavel()
se verificar(FUNCTION):
retorna parsear_declaracao_funcao()
// ... outros tipos de declaração
// Se chegou aqui, token inesperado
erro("Declaração esperada")
capturar ErroSintatico como e:
reportar_erro(e)
sincronizar()
retorna nulo // Retorna nó de erro ou nuloEsta abordagem garante que após detectar um erro, o parser se recupera e continua processando o resto do arquivo. Embora o código após o erro possa ter análises incorretas devido à perda de contexto, erros adicionais genuínos ainda serão detectados e reportados.
⚡ Qualidade das Mensagens de Erro
A qualidade das mensagens de erro é tão importante quanto a capacidade de recuperação. Uma mensagem como “erro de sintaxe” é inútil. Uma boa mensagem especifica:
- Onde o erro ocorreu (arquivo, linha, coluna)
- O que foi encontrado (token inesperado)
- O que era esperado (contexto específico)
- Como possivelmente corrigir (sugestão quando apropriado)
Exemplo: “Erro em programa.lang:15:8: Esperado ‘(’ após ‘if’, mas encontrado identificador ‘x’. Você esqueceu de colocar a condição entre parênteses?”
Estratégia de Inserção de Tokens
Outra estratégia é a inserção de tokens faltantes. Se o parser espera um token específico (como ponto-e-vírgula ou parêntese de fechamento), ele pode fingir que o token está lá, reportar o erro, e continuar:
funcao consumir_com_recuperacao(tipo_esperado) -> Token:
se verificar(tipo_esperado):
retorna advance()
// Token não está lá: reporta erro mas continua
token_atual = peek()
reportar_erro("Esperado " + tipo_esperado + " mas encontrado " + token_atual.tipo)
// Cria token "fantasma" para permitir que parsing continue
retorna Token(tipo_esperado, "", token_atual.posicao)Esta estratégia funciona especialmente bem para tokens obrigatórios em posições previsíveis. Se falta um ponto-e-vírgula no final de uma declaração, podemos inserir um implicitamente e continuar parseando a próxima declaração normalmente.
Evitando Erros em Cascata
Um desafio com recuperação de erros é erros em cascata: um erro inicial causa interpretação incorreta do código subsequente, gerando múltiplos erros espúrios. Por exemplo, se o parser perde um ponto-e-vírgula, pode interpretar a próxima linha incorretamente, gerando erros falsos.
Para minimizar erros em cascata:
Limite a quantidade de erros reportados por declaração - depois de alguns erros, pare de reportar até sincronizar completamente
Use heurísticas de provável intenção - se o parser pode inferir o que o programador provavelmente quis dizer, faça essa inferência
Marque claramente erros com baixa confiança - alguns erros reportados após recuperação podem ser espúrios; indique isso ao usuário
Teste extensivamente com código com erros - a melhor forma de melhorar recuperação de erros é testar o parser com código intencionalmente incorreto e ajustar a estratégia baseado nos resultados
Exemplo Completo: Parser Robusto
Vamos ver um exemplo mais completo que integra recuperação de erros:
classe Parser:
// ... campos e métodos básicos omitidos ...
teve_erro: Booleano = falso
modo_panico: Booleano = falso
funcao parsear_programa() -> NodoPrograma:
declaracoes = []
enquanto nao fim_da_entrada():
declaracao = parsear_declaracao()
se declaracao != nulo:
declaracoes.adicionar(declaracao)
retorna NodoPrograma(declaracoes)
funcao parsear_declaracao() -> NodoDeclaracao:
tentar:
modo_panico = falso
se verificar(VAR):
retorna parsear_declaracao_variavel()
se verificar(FUNCTION):
retorna parsear_declaracao_funcao()
se verificar(IF):
retorna parsear_comando_if()
// ... outros tipos
// Token inesperado no início de declaração
jogar ErroSintatico("Declaração esperada no início, mas encontrado " + peek().tipo)
capturar ErroSintatico como e:
reportar_erro(e)
sincronizar()
retorna nulo
funcao reportar_erro(erro: ErroSintatico):
se modo_panico:
retorna // Não reporta erros adicionais enquanto em pânico
teve_erro = verdadeiro
modo_panico = verdadeiro
imprimir("Erro [linha " + erro.posicao.linha + "]: " + erro.mensagem)
funcao sincronizar():
advance() // Pula o token problemático
enquanto nao fim_da_entrada():
// Encontrou ponto-e-vírgula: está seguro continuar
se tipo_anterior() == PONTO_VIRGULA:
retorna
// Próximo token inicia nova declaração: pode continuar
se peek().tipo em [CLASS, FUNCTION, VAR, FOR, IF, WHILE, RETURN]:
retorna
advance()Este parser completo mostra como todas as peças se encaixam. O flag modo_panico evita reportar múltiplos erros enquanto se recuperando. A função sincronizar() busca pontos seguros para retomar parsing. E parsear_declaracao() captura erros e se recupera automaticamente.
🎨 Casos Especiais e Desafios Comuns
Mesmo com a estrutura sólida que estabelecemos, parsing real de linguagens reais apresenta vários desafios específicos que merecem atenção. Vamos explorar os mais comuns e como resolvê-los.
Lidando com Precedência e Associatividade Complexas
Linguagens modernas têm muitos níveis de precedência de operadores. Por exemplo, JavaScript tem mais de 15 níveis! Implementar isso requer cuidado para não criar código massivamente repetitivo.
Uma técnica é usar uma tabela de precedência e uma única função genérica de parsing de expressões binárias:
tabela_precedencia = {
ATRIBUICAO: 1,
OU_LOGICO: 2,
E_LOGICO: 3,
IGUALDADE: 4, // ==, !=
COMPARACAO: 5, // <, >, <=, >=
ADICAO: 6, // +, -
MULTIPLICACAO: 7, // *, /, %
EXPONENCIAL: 8 // **
}
funcao parsear_expressao_binaria(precedencia_minima) -> NodoExpressao:
esquerda = parsear_unario()
enquanto verdadeiro:
operador = peek()
se operador.tipo nao em tabela_precedencia:
quebrar
precedencia = tabela_precedencia[operador.tipo]
se precedencia < precedencia_minima:
quebrar
advance() // Consome operador
// Para associatividade à esquerda, usamos precedencia + 1
// Para à direita, usaríamos apenas precedencia
direita = parsear_expressao_binaria(precedencia + 1)
esquerda = ExpressaoBinaria(operador.valor, esquerda, direita)
retorna esquerdaEsta implementação baseada em precedência numérica evita criar uma função separada para cada nível de precedência, tornando o código mais conciso e fácil de manter quando novos operadores são adicionados.
Resolvendo Ambiguidades Sintáticas
Algumas construções sintáticas são inerentemente ambíguas. O clássico exemplo é o “problema do else pendurado”:
O else pertence ao primeiro ou segundo if? A maioria das linguagens resolve isso fazendo o else pertencer ao if mais próximo, mas isso deve ser implementado explicitamente no parser.
Solução: estruturar o parsing para evitar a ambiguidade:
funcao parsear_comando_if() -> ComandoIf:
consumir(IF)
consumir(PAREN_ESQ)
condicao = parsear_expressao()
consumir(PAREN_DIR)
// Força uso de blocos com chaves em vez de comandos soltos
bloco_entao = parsear_bloco_ou_comando()
bloco_senao = nulo
se verificar(ELSE):
consumir(ELSE)
bloco_senao = parsear_bloco_ou_comando()
retorna ComandoIf(condicao, bloco_entao, bloco_senao)
funcao parsear_bloco_ou_comando() -> Lista<NodoComando>:
// Se há chave, é um bloco
se verificar(CHAVE_ESQ):
retorna parsear_bloco()
// Senão, parseia um único comando
// Mas NÃO permite if sem bloco no contexto de else
// para evitar ambiguidade
comando = parsear_comando()
retorna [comando]Alternativamente, muitas linguagens modernas simplesmente exigem chaves para blocos de if e else, eliminando a ambiguidade completamente. Esta é uma decisão de design de linguagem que torna o parsing mais simples.
Tratando Comentários e Documentação
Comentários já foram removidos pelo analisador léxico, mas comentários de documentação (como JavaDoc ou doc comments) podem precisar ser preservados e anexados aos nós AST apropriados:
O analisador léxico pode marcar comentários de documentação especialmente, e o parser os anexa ao próximo nó relevante. Isso permite que ferramentas de documentação extraiam informação diretamente da AST.
Suportando Sintaxe Extensível
Algumas linguagens modernas permitem que programadores definam novos operadores ou sintaxe customizada. Implementar isso em um parser requer arquitetura extensível:
classe Parser:
operadores_customizados: Dicionario<String, InformacaoOperador>
funcao registrar_operador(simbolo, precedencia, associatividade):
operadores_customizados[simbolo] = InformacaoOperador(precedencia, associatividade)
funcao parsear_expressao_binaria(...):
// Consulta tanto operadores built-in quanto customizados
...Esta extensibilidade é complexa mas extremamente poderosa, permitindo que a linguagem evolua sem modificar o compilador.
🔬 Otimizações e Considerações de Performance
Embora parsers recursivos descendentes sejam geralmente eficientes, há várias técnicas de otimização que podem melhorar significativamente a performance, especialmente para arquivos grandes.
Memorização de Resultados de Parsing
Em gramáticas ambíguas ou com muito backtracking (mais comuns em parsers mais sofisticados como PEG), memorização pode evitar re-parsear as mesmas posições repetidamente:
classe Parser:
cache_parsing: Dicionario<Tupla<String, Inteiro>, ResultadoCache>
funcao parsear_expressao_memoizada() -> NodoExpressao:
chave = ("expressao", posicao_atual)
se chave em cache_parsing:
resultado = cache_parsing[chave]
posicao_atual = resultado.posicao_final
retorna resultado.nodo
posicao_inicial = posicao_atual
nodo = parsear_expressao()
cache_parsing[chave] = ResultadoCache(nodo, posicao_atual)
retorna nodoEsta técnica é mais útil em parsers PEG (Parsing Expression Grammars) que fazem backtracking extensivo, mas pode ajudar em qualquer parser que re-analisa as mesmas regiões do código múltiplas vezes.
Parsing Incremental
Para editores que precisam re-parsear código conforme o usuário digita, parsing incremental evita re-parsear todo o arquivo em cada mudança:
classe ParserIncremental:
ast_anterior: NodoPrograma
tokens_anteriores: Lista<Token>
funcao parsear_incremental(tokens_novos, regiao_modificada) -> NodoPrograma:
// Identifica quais funções/classes foram afetadas pela mudança
nodes_afetados = identificar_nodes_afetados(regiao_modificada)
// Re-parseia apenas as partes afetadas
para nodo em nodes_afetados:
tokens_regiao = extrair_tokens_regiao(tokens_novos, nodo.regiao)
nodo_novo = parsear_nodo_isolado(tokens_regiao, tipo_de(nodo))
substituir_em_ast(ast_anterior, nodo, nodo_novo)
retorna ast_anteriorParsing incremental é complexo mas essencial para performance em editores modernos. Ele permite que mudanças locais sejam processadas em tempo proporcional ao tamanho da mudança, não ao tamanho total do arquivo.
Paralelização do Parsing
Para arquivos muito grandes ou projetos com múltiplos arquivos, parsing pode ser paralelizado:
Como cada arquivo é independente na fase de parsing (dependências são resolvidas apenas na análise semântica), parsing de múltiplos arquivos pode ser trivialmente paralelizado, aproveitando múltiplos núcleos de CPU.
🧪 Testando Seu Parser Completamente
Testes abrangentes são absolutamente essenciais para parsers confiáveis. Bugs em parsers podem causar comportamento extremamente confuso e difícil de depurar, então investir em testes é fundamental.
Estratégia de Testes em Camadas
Nível 1: Testes Unitários de Funções Individuais
Teste cada função de parsing isoladamente com entradas mínimas:
teste "parsear_expressao_binaria_simples":
tokens = [Token(NUMERO, "5"), Token(MAIS, "+"), Token(NUMERO, "3")]
parser = Parser(tokens)
ast = parser.parsear_expressao()
afirmar ast é ExpressaoBinaria
afirmar ast.operador == "+"
afirmar ast.esquerda.valor == 5
afirmar ast.direita.valor == 3
teste "parsear_expressao_com_precedencia":
tokens = tokenizar("3 + 4 * 2")
parser = Parser(tokens)
ast = parser.parsear_expressao()
// Árvore deve ser: +(3, *(4, 2))
afirmar ast.operador == "+"
afirmar ast.direita.operador == "*"Nível 2: Testes de Integração de Construções Completas
Teste construções mais complexas que envolvem múltiplas funções:
teste "parsear_funcao_completa":
codigo = """
function soma(a, b) {
return a + b;
}
"""
tokens = tokenizar(codigo)
parser = Parser(tokens)
ast = parser.parsear_programa()
afirmar tamanho(ast.declaracoes) == 1
funcao = ast.declaracoes[0]
afirmar funcao.nome == "soma"
afirmar tamanho(funcao.parametros) == 2
afirmar tamanho(funcao.corpo) == 1Nível 3: Testes de Programas Completos
Teste programas completos e realistas:
teste "parsear_programa_fibonacci":
codigo = ler_arquivo("testes/programas/fibonacci.lang")
tokens = tokenizar(codigo)
parser = Parser(tokens)
ast = parser.parsear_programa()
// Verifica estrutura geral sem ser excessivamente específico
afirmar ast != nulo
afirmar tamanho(ast.declaracoes) > 0
afirmar nao parser.teve_erroTestes de Casos de Erro
Tão importante quanto testar código correto é testar código com erros:
teste "detectar_ponto_virgula_faltando":
codigo = "var x = 5" // Falta ponto-e-vírgula
tokens = tokenizar(codigo)
parser = Parser(tokens)
ast = parser.parsear_programa()
afirmar parser.teve_erro
afirmar "ponto-e-vírgula" em parser.mensagens_erro[0].toLowerCase()
teste "recuperar_apos_erro":
codigo = """
var x = 5 // Falta ;
var y = 10; // Esta deve ser parseada corretamente
"""
tokens = tokenizar(codigo)
parser = Parser(tokens)
ast = parser.parsear_programa()
afirmar parser.teve_erro // Primeiro erro detectado
afirmar tamanho(ast.declaracoes) == 2 // Mas ambas declarações foram processadasTestes de Regressão
Sempre que você corrigir um bug, adicione um teste que o reproduz:
teste "regressao_bug_123_precedencia_unario":
// Bug #123: -5 * 2 estava sendo parseado como -(5 * 2) em vez de (-5) * 2
codigo = "-5 * 2"
tokens = tokenizar(codigo)
parser = Parser(tokens)
ast = parser.parsear_expressao()
// Deve ser *(-(5), 2), não -(*(5, 2))
afirmar ast.operador == "*"
afirmar ast.esquerda é ExpressaoUnaria
afirmar ast.esquerda.operador == "-"Estes testes garantem que bugs corrigidos não reapareçam em refatorações futuras.
Testes de Fuzzing
Fuzzing gera entradas aleatórias para encontrar casos extremos:
teste "fuzzing_expressoes_aleatorias":
para i de 1 ate 1000:
// Gera expressão aritmética aleatória válida
expressao = gerar_expressao_aleatoria()
tokens = tokenizar(expressao)
parser = Parser(tokens)
tentar:
ast = parser.parsear_expressao()
// Se parsing sucedeu, deve ter produzido AST válida
afirmar ast != nulo
validar_ast(ast)
capturar qualquer_erro:
falhar("Parser crashou em: " + expressao)Fuzzing frequentemente revela bugs sutis que testes manuais perdem.
🌟 Reflexões Finais: Da Teoria à Prática
Esta semana você deu um dos passos mais importantes da disciplina: transformou teoria abstrata de gramáticas e autômatos em código concreto funcional. O parser que você implementou no Projeto Integrador não é um exercício acadêmico abstrato; é um componente real de um compilador funcional que processa linguagens de programação.
A jornada de entender gramáticas formalmente na Semana 3, através de autômatos de pilha na Semana 10, até implementar parsers recursivos descendentes hoje, ilustra perfeitamente como teoria e prática se reforçam mutuamente. A teoria forneceu o framework conceitual que guia o design, enquanto a prática revelou desafios específicos que teoria sozinha não antecipa, como recuperação de erros robusta e qualidade de mensagens de erro.
🎓 Lições Fundamentais Desta Semana
Implementar um parser recursivo descendente desenvolveu múltiplas competências essenciais:
Capacidade de traduzir especificações formais em código: Você aprendeu a ler gramáticas e transformá-las sistematicamente em funções recursivas. Esta habilidade transcende parsing; é aplicável sempre que você precisa implementar algoritmos descritos formalmente.
Compreensão profunda de recursão: Parsers descendentes são inerentemente recursivos. Trabalhar com eles desenvolve intuição poderosa sobre como a recursão pode resolver problemas complexos elegantemente.
Habilidade de design de estruturas de dados: Projetar ASTs eficazes requer pensar cuidadosamente sobre quais informações preservar, como organizá-las hierarquicamente, e como torná-las fáceis de processar posteriormente. Esta é uma habilidade de design de software fundamental.
Experiência com tratamento robusto de erros: Implementar recuperação de erros e mensagens de erro de alta qualidade ensinou que código robusto vai muito além de processar entradas corretas. Antecipar e lidar graciosamente com erros é marca de software profissional.
As capacidades que você desenvolveu vão muito além de parsing especificamente. Você praticou pensamento estruturado ao decompor problemas complexos (reconhecer linguagens completas) em subproblemas gerenciáveis (reconhecer construções individuais). Você experimentou design modular ao criar componentes que funcionam independentemente mas cooperam para resolver o problema maior. Você aplicou abstração ao criar hierarquias de classes AST que ocultam detalhes irrelevantes enquanto expõem interfaces úteis.
A conexão com as próximas semanas é direta e emocionante. A AST que você construiu hoje será a entrada para a análise semântica da Semana 13, onde você verificará correção além da sintaxe. Será transformada em código executável na Semana 14. E informará o Language Server Protocol na Semana 15, fornecendo feedback em tempo real em editores modernos. A AST é literalmente o coração do compilador, conectando todas as fases subsequentes.
As habilidades práticas que você adquiriu são diretamente aplicáveis em contextos profissionais. Parsers são usados não apenas em compiladores, mas em processamento de formatos de dados (JSON, XML, YAML), análise de linguagens de consulta (SQL, RegEx), interpretação de linguagens de domínio específico, e inúmeras outras aplicações. Compreender parsing profundamente torna você mais eficaz sempre que precisar processar texto estruturado.
A apreciação por ferramentas modernas também cresceu. Embora você tenha implementado um parser manualmente para compreender os fundamentos, agora você entende exatamente o que ferramentas como ANTLR, Bison, ou Yacc fazem nos bastidores. Esta compreensão permite que você use essas ferramentas mais eficazmente, sabendo suas limitações e capacidades.
A próxima semana explorará parsers ascendentes (LR), uma abordagem diferente mas igualmente poderosa. Você verá como construir tabelas de parsing automaticamente, como resolver conflitos sistemicamente, e como parsers ascendentes podem aceitar classes maiores de gramáticas que parsers descendentes. Esta exposição a múltiplas técnicas aprofundará sua compreensão dos trade-offs fundamentais no design de parsers.
O projeto continua evoluindo conforme você adiciona cada novo componente. O compilador que parecia impossível de construir no início do semestre está se materializando peça por peça. Cada semana adiciona uma camada de funcionalidade, e você pode ver concretamente como tudo se conecta. Este é o poder da aprendizagem baseada em projeto: conceitos abstratos se tornam tangíveis através de construção incremental.
A jornada de parsing recursivo descendente que você completou hoje é uma das mais gratificantes da ciência da computação. Você pegou símbolos sem significado (tokens) e construiu estruturas ricas em semântica (ASTs) através de código elegante que espelha perfeitamente especificações matemáticas. Esta síntese de teoria e prática, de abstração e concretude, é a essência da ciência da computação.
Continue experimentando, testando extensivamente, e refinando seu parser. A qualidade do seu parser determinará a qualidade de todo o resto do compilador. Invista tempo em mensagens de erro excelentes, recuperação robusta, e testes abrangentes. Seu futuro eu (e os usuários da sua linguagem!) agradecerão.
Prepare-se para a Semana 12, onde você explorará a abordagem ascendente de parsing, vendo o problema sob perspectiva completamente diferente mas complementar. A comparação entre descendente e ascendente revelará insights profundos sobre a natureza do reconhecimento de linguagens. Você está construindo não apenas um compilador, mas compreensão profunda de como linguagens funcionam! 🚀✨
💻 Implementação Prática Completa: Passo a Passo
Agora vamos consolidar tudo que aprendemos em uma implementação completa e funcional de um parser recursivo descendente. Esta seção fornece código detalhado e comentado que você pode usar como referência direta para o Projeto Integrador.
Estrutura Completa do Parser em Dart
Vamos implementar um parser completo para uma linguagem simples mas expressiva em Dart (a linguagem didática que usamos no projeto). Esta implementação será literal e clara, priorizando compreensão sobre otimização:
// arquivo: parser.dart
import 'token.dart';
import 'ast.dart';
class Parser {
final List<Token> tokens;
int posicaoAtual = 0;
bool teveErro = false;
bool modoPanico = false;
List<String> mensagensErro = [];
Parser(this.tokens);
// ========== Métodos Utilitários ==========
/// Retorna o token atual sem consumi-lo
Token peek() {
if (fimDaEntrada()) {
return tokens.last; // Token EOF
}
return tokens[posicaoAtual];
}
/// Retorna o token anterior (útil para mensagens de erro)
Token anterior() {
return tokens[posicaoAtual - 1];
}
/// Avança para o próximo token e retorna o atual
Token advance() {
if (!fimDaEntrada()) {
posicaoAtual++;
}
return anterior();
}
/// Verifica se chegamos ao fim da entrada
bool fimDaEntrada() {
return peek().tipo == TipoToken.EOF;
}
/// Verifica se o token atual é do tipo especificado
bool verificar(TipoToken tipo) {
if (fimDaEntrada()) return false;
return peek().tipo == tipo;
}
/// Consome um token do tipo esperado ou lança erro
Token consumir(TipoToken tipo, String mensagemErro) {
if (verificar(tipo)) return advance();
throw erroParser(peek(), mensagemErro);
}
/// Cria um erro de parsing
ErroParser erroParser(Token token, String mensagem) {
reportarErro(token, mensagem);
return ErroParser(mensagem);
}
/// Reporta um erro ao usuário
void reportarErro(Token token, String mensagem) {
if (modoPanico) return; // Não reporta erros em cascata
teveErro = true;
modoPanico = true;
String localizacao = "Linha ${token.linha}, coluna ${token.coluna}";
String mensagemCompleta = "Erro [$localizacao]: $mensagem";
if (token.tipo == TipoToken.EOF) {
mensagemCompleta += " (no fim do arquivo)";
} else {
mensagemCompleta += " (próximo a '${token.lexema}')";
}
mensagensErro.add(mensagemCompleta);
print(mensagemCompleta);
}
/// Sincroniza o parser após um erro
void sincronizar() {
advance();
while (!fimDaEntrada()) {
// Se encontramos ponto-e-vírgula, consumimos e saímos
if (anterior().tipo == TipoToken.PONTO_VIRGULA) {
return;
}
// Se o próximo token inicia uma nova declaração, paramos
switch (peek().tipo) {
case TipoToken.FUNCTION:
case TipoToken.VAR:
case TipoToken.IF:
case TipoToken.WHILE:
case TipoToken.FOR:
case TipoToken.RETURN:
case TipoToken.CLASS:
return;
default:
break;
}
advance();
}
}
// ========== Ponto de Entrada ==========
/// Parseia o programa completo
NodoPrograma parsearPrograma() {
List<NodoDeclaracao> declaracoes = [];
while (!fimDaEntrada()) {
try {
declaracoes.add(parsearDeclaracao());
} catch (e) {
sincronizar();
}
}
return NodoPrograma(declaracoes);
}
// ========== Declarações ==========
/// Parseia uma declaração (dispatcher)
NodoDeclaracao parsearDeclaracao() {
try {
modoPanico = false;
if (verificar(TipoToken.FUNCTION)) {
return parsearDeclaracaoFuncao();
}
if (verificar(TipoToken.VAR)) {
return parsearDeclaracaoVariavel();
}
if (verificar(TipoToken.CLASS)) {
return parsearDeclaracaoClasse();
}
// Se não é uma declaração, deve ser um comando
return parsearComando();
} catch (e) {
sincronizar();
return NodoErro(); // Nó especial para indicar erro
}
}
/// Parseia declaração de função
NodoDeclaracaoFuncao parsearDeclaracaoFuncao() {
Token palavraChave = consumir(TipoToken.FUNCTION,
"Esperado palavra-chave 'function'");
Token nome = consumir(TipoToken.IDENTIFICADOR,
"Esperado nome da função");
consumir(TipoToken.PAREN_ESQ,
"Esperado '(' após nome da função");
// Parseia parâmetros
List<Parametro> parametros = [];
if (!verificar(TipoToken.PAREN_DIR)) {
do {
if (parametros.length >= 255) {
erroParser(peek(), "Não pode ter mais de 255 parâmetros");
}
Token nomeParam = consumir(TipoToken.IDENTIFICADOR,
"Esperado nome do parâmetro");
// Tipo opcional
String? tipoParam;
if (verificar(TipoToken.DOIS_PONTOS)) {
advance();
Token tokenTipo = consumir(TipoToken.IDENTIFICADOR,
"Esperado tipo do parâmetro");
tipoParam = tokenTipo.lexema;
}
parametros.add(Parametro(nomeParam.lexema, tipoParam));
} while (verificar(TipoToken.VIRGULA) && advance() != null);
}
consumir(TipoToken.PAREN_DIR, "Esperado ')' após parâmetros");
// Tipo de retorno opcional
String? tipoRetorno;
if (verificar(TipoToken.DOIS_PONTOS)) {
advance();
Token tokenTipo = consumir(TipoToken.IDENTIFICADOR,
"Esperado tipo de retorno");
tipoRetorno = tokenTipo.lexema;
}
consumir(TipoToken.CHAVE_ESQ, "Esperado '{' antes do corpo da função");
List<NodoComando> corpo = parsearBloco();
return NodoDeclaracaoFuncao(
nome.lexema,
parametros,
tipoRetorno,
corpo,
palavraChave.linha
);
}
/// Parseia declaração de variável
NodoDeclaracaoVariavel parsearDeclaracaoVariavel() {
Token palavraChave = consumir(TipoToken.VAR, "Esperado 'var'");
Token nome = consumir(TipoToken.IDENTIFICADOR,
"Esperado nome da variável");
// Tipo opcional
String? tipoExplicito;
if (verificar(TipoToken.DOIS_PONTOS)) {
advance();
Token tokenTipo = consumir(TipoToken.IDENTIFICADOR,
"Esperado tipo da variável");
tipoExplicito = tokenTipo.lexema;
}
// Inicializador opcional
NodoExpressao? inicializador;
if (verificar(TipoToken.IGUAL)) {
advance();
inicializador = parsearExpressao();
}
consumir(TipoToken.PONTO_VIRGULA,
"Esperado ';' após declaração de variável");
return NodoDeclaracaoVariavel(
nome.lexema,
tipoExplicito,
inicializador,
palavraChave.linha
);
}
/// Parseia declaração de classe (simplificada)
NodoDeclaracaoClasse parsearDeclaracaoClasse() {
Token palavraChave = consumir(TipoToken.CLASS, "Esperado 'class'");
Token nome = consumir(TipoToken.IDENTIFICADOR, "Esperado nome da classe");
consumir(TipoToken.CHAVE_ESQ, "Esperado '{' antes do corpo da classe");
List<NodoDeclaracaoFuncao> metodos = [];
List<NodoDeclaracaoVariavel> campos = [];
while (!verificar(TipoToken.CHAVE_DIR) && !fimDaEntrada()) {
if (verificar(TipoToken.FUNCTION)) {
metodos.add(parsearDeclaracaoFuncao());
} else if (verificar(TipoToken.VAR)) {
campos.add(parsearDeclaracaoVariavel());
} else {
throw erroParser(peek(),
"Esperado declaração de método ou campo na classe");
}
}
consumir(TipoToken.CHAVE_DIR, "Esperado '}' após corpo da classe");
return NodoDeclaracaoClasse(
nome.lexema,
campos,
metodos,
palavraChave.linha
);
}
// ========== Comandos ==========
/// Parseia um comando (dispatcher)
NodoComando parsearComando() {
if (verificar(TipoToken.IF)) return parsearComandoIf();
if (verificar(TipoToken.WHILE)) return parsearComandoWhile();
if (verificar(TipoToken.FOR)) return parsearComandoFor();
if (verificar(TipoToken.RETURN)) return parsearComandoReturn();
if (verificar(TipoToken.CHAVE_ESQ)) return parsearComandoBloco();
// Se não é nenhum comando especial, é comando de expressão
return parsearComandoExpressao();
}
/// Parseia comando if
NodoComandoIf parsearComandoIf() {
Token palavraChave = consumir(TipoToken.IF, "Esperado 'if'");
consumir(TipoToken.PAREN_ESQ, "Esperado '(' após 'if'");
NodoExpressao condicao = parsearExpressao();
consumir(TipoToken.PAREN_DIR, "Esperado ')' após condição do if");
NodoComando blocoEntao = parsearComando();
NodoComando? blocoSenao;
if (verificar(TipoToken.ELSE)) {
advance();
blocoSenao = parsearComando();
}
return NodoComandoIf(condicao, blocoEntao, blocoSenao, palavraChave.linha);
}
/// Parseia comando while
NodoComandoWhile parsearComandoWhile() {
Token palavraChave = consumir(TipoToken.WHILE, "Esperado 'while'");
consumir(TipoToken.PAREN_ESQ, "Esperado '(' após 'while'");
NodoExpressao condicao = parsearExpressao();
consumir(TipoToken.PAREN_DIR, "Esperado ')' após condição do while");
NodoComando corpo = parsearComando();
return NodoComandoWhile(condicao, corpo, palavraChave.linha);
}
/// Parseia comando for
NodoComandoFor parsearComandoFor() {
Token palavraChave = consumir(TipoToken.FOR, "Esperado 'for'");
consumir(TipoToken.PAREN_ESQ, "Esperado '(' após 'for'");
// Inicializador (pode ser declaração de variável ou expressão)
NodoComando? inicializador;
if (verificar(TipoToken.PONTO_VIRGULA)) {
advance();
} else if (verificar(TipoToken.VAR)) {
inicializador = parsearDeclaracaoVariavel();
} else {
inicializador = parsearComandoExpressao();
}
// Condição
NodoExpressao? condicao;
if (!verificar(TipoToken.PONTO_VIRGULA)) {
condicao = parsearExpressao();
}
consumir(TipoToken.PONTO_VIRGULA, "Esperado ';' após condição do for");
// Incremento
NodoExpressao? incremento;
if (!verificar(TipoToken.PAREN_DIR)) {
incremento = parsearExpressao();
}
consumir(TipoToken.PAREN_DIR, "Esperado ')' após cláusulas do for");
NodoComando corpo = parsearComando();
return NodoComandoFor(
inicializador,
condicao,
incremento,
corpo,
palavraChave.linha
);
}
/// Parseia comando return
NodoComandoReturn parsearComandoReturn() {
Token palavraChave = consumir(TipoToken.RETURN, "Esperado 'return'");
NodoExpressao? valor;
if (!verificar(TipoToken.PONTO_VIRGULA)) {
valor = parsearExpressao();
}
consumir(TipoToken.PONTO_VIRGULA, "Esperado ';' após return");
return NodoComandoReturn(valor, palavraChave.linha);
}
/// Parseia bloco de comandos
NodoComandoBloco parsearComandoBloco() {
Token chaveEsq = consumir(TipoToken.CHAVE_ESQ, "Esperado '{'");
List<NodoComando> comandos = parsearBloco();
return NodoComandoBloco(comandos, chaveEsq.linha);
}
/// Parseia sequência de comandos até '}'
List<NodoComando> parsearBloco() {
List<NodoComando> comandos = [];
while (!verificar(TipoToken.CHAVE_DIR) && !fimDaEntrada()) {
comandos.add(parsearDeclaracao());
}
consumir(TipoToken.CHAVE_DIR, "Esperado '}' após bloco");
return comandos;
}
/// Parseia comando de expressão
NodoComandoExpressao parsearComandoExpressao() {
int linha = peek().linha;
NodoExpressao expressao = parsearExpressao();
consumir(TipoToken.PONTO_VIRGULA, "Esperado ';' após expressão");
return NodoComandoExpressao(expressao, linha);
}
// ========== Expressões ==========
/// Parseia expressão (ponto de entrada)
NodoExpressao parsearExpressao() {
return parsearAtribuicao();
}
/// Parseia atribuição
NodoExpressao parsearAtribuicao() {
NodoExpressao expressao = parsearOuLogico();
if (verificar(TipoToken.IGUAL)) {
Token operador = advance();
NodoExpressao valor = parsearAtribuicao();
if (expressao is NodoExpressaoVariavel) {
return NodoExpressaoAtribuicao(
expressao.nome,
valor,
operador.linha
);
}
throw erroParser(operador, "Alvo de atribuição inválido");
}
return expressao;
}
/// Parseia operador lógico OR
NodoExpressao parsearOuLogico() {
NodoExpressao esquerda = parsearELogico();
while (verificar(TipoToken.OU)) {
Token operador = advance();
NodoExpressao direita = parsearELogico();
esquerda = NodoExpressaoBinaria(
operador.lexema,
esquerda,
direita,
operador.linha
);
}
return esquerda;
}
/// Parseia operador lógico AND
NodoExpressao parsearELogico() {
NodoExpressao esquerda = parsearIgualdade();
while (verificar(TipoToken.E)) {
Token operador = advance();
NodoExpressao direita = parsearIgualdade();
esquerda = NodoExpressaoBinaria(
operador.lexema,
esquerda,
direita,
operador.linha
);
}
return esquerda;
}
/// Parseia operadores de igualdade
NodoExpressao parsearIgualdade() {
NodoExpressao esquerda = parsearComparacao();
while (verificar(TipoToken.IGUAL_IGUAL) ||
verificar(TipoToken.DIFERENTE)) {
Token operador = advance();
NodoExpressao direita = parsearComparacao();
esquerda = NodoExpressaoBinaria(
operador.lexema,
esquerda,
direita,
operador.linha
);
}
return esquerda;
}
/// Parseia operadores de comparação
NodoExpressao parsearComparacao() {
NodoExpressao esquerda = parsearAdicao();
while (verificar(TipoToken.MAIOR) ||
verificar(TipoToken.MAIOR_IGUAL) ||
verificar(TipoToken.MENOR) ||
verificar(TipoToken.MENOR_IGUAL)) {
Token operador = advance();
NodoExpressao direita = parsearAdicao();
esquerda = NodoExpressaoBinaria(
operador.lexema,
esquerda,
direita,
operador.linha
);
}
return esquerda;
}
/// Parseia adição e subtração
NodoExpressao parsearAdicao() {
NodoExpressao esquerda = parsearMultiplicacao();
while (verificar(TipoToken.MAIS) || verificar(TipoToken.MENOS)) {
Token operador = advance();
NodoExpressao direita = parsearMultiplicacao();
esquerda = NodoExpressaoBinaria(
operador.lexema,
esquerda,
direita,
operador.linha
);
}
return esquerda;
}
/// Parseia multiplicação, divisão e módulo
NodoExpressao parsearMultiplicacao() {
NodoExpressao esquerda = parsearUnario();
while (verificar(TipoToken.VEZES) ||
verificar(TipoToken.DIVIDE) ||
verificar(TipoToken.MODULO)) {
Token operador = advance();
NodoExpressao direita = parsearUnario();
esquerda = NodoExpressaoBinaria(
operador.lexema,
esquerda,
direita,
operador.linha
);
}
return esquerda;
}
/// Parseia operadores unários
NodoExpressao parsearUnario() {
if (verificar(TipoToken.NAO) || verificar(TipoToken.MENOS)) {
Token operador = advance();
NodoExpressao direita = parsearUnario();
return NodoExpressaoUnaria(
operador.lexema,
direita,
operador.linha
);
}
return parsearChamada();
}
/// Parseia chamadas de função e acesso a membros
NodoExpressao parsearChamada() {
NodoExpressao expressao = parsearPrimario();
while (true) {
if (verificar(TipoToken.PAREN_ESQ)) {
expressao = finalizarChamada(expressao);
} else if (verificar(TipoToken.PONTO)) {
advance();
Token nome = consumir(TipoToken.IDENTIFICADOR,
"Esperado nome de propriedade após '.'");
expressao = NodoExpressaoAcesso(
expressao,
nome.lexema,
nome.linha
);
} else {
break;
}
}
return expressao;
}
/// Finaliza parsing de chamada de função
NodoExpressao finalizarChamada(NodoExpressao funcao) {
Token parenEsq = consumir(TipoToken.PAREN_ESQ, "Esperado '('");
List<NodoExpressao> argumentos = [];
if (!verificar(TipoToken.PAREN_DIR)) {
do {
if (argumentos.length >= 255) {
erroParser(peek(), "Não pode ter mais de 255 argumentos");
}
argumentos.add(parsearExpressao());
} while (verificar(TipoToken.VIRGULA) && advance() != null);
}
consumir(TipoToken.PAREN_DIR, "Esperado ')' após argumentos");
return NodoExpressaoChamada(funcao, argumentos, parenEsq.linha);
}
/// Parseia expressões primárias (literais, variáveis, agrupamento)
NodoExpressao parsearPrimario() {
// Literais booleanos
if (verificar(TipoToken.TRUE)) {
Token token = advance();
return NodoExpressaoLiteral(true, token.linha);
}
if (verificar(TipoToken.FALSE)) {
Token token = advance();
return NodoExpressaoLiteral(false, token.linha);
}
// Literal null
if (verificar(TipoToken.NULL)) {
Token token = advance();
return NodoExpressaoLiteral(null, token.linha);
}
// Literais numéricos
if (verificar(TipoToken.NUMERO)) {
Token token = advance();
return NodoExpressaoLiteral(
double.parse(token.lexema),
token.linha
);
}
// Literais de string
if (verificar(TipoToken.STRING)) {
Token token = advance();
// Remove as aspas
String valor = token.lexema.substring(1, token.lexema.length - 1);
return NodoExpressaoLiteral(valor, token.linha);
}
// Identificadores (variáveis)
if (verificar(TipoToken.IDENTIFICADOR)) {
Token token = advance();
return NodoExpressaoVariavel(token.lexema, token.linha);
}
// Expressão entre parênteses
if (verificar(TipoToken.PAREN_ESQ)) {
Token parenEsq = advance();
NodoExpressao expressao = parsearExpressao();
consumir(TipoToken.PAREN_DIR, "Esperado ')' após expressão");
return NodoExpressaoAgrupamento(expressao, parenEsq.linha);
}
throw erroParser(peek(), "Esperado expressão");
}
}
// Exceção para erros de parsing
class ErroParser implements Exception {
final String mensagem;
ErroParser(this.mensagem);
@override
String toString() => mensagem;
}Esta implementação completa demonstra todos os conceitos que discutimos: hierarquia de precedência, recuperação de erros, construção de AST, e mensagens de erro informativas. O código é didático e literal, facilitando compreensão dos algoritmos.
Estrutura das Classes AST
Agora vamos definir as classes que representam os nós da AST. Esta hierarquia é fundamental para todas as fases posteriores do compilador:
// arquivo: ast.dart
/// Classe base para todos os nós da AST
abstract class NodoAST {
final int linha; // Localização no código fonte
NodoAST(this.linha);
/// Padrão Visitor para percorrer a AST
T aceitar<T>(VisitorAST<T> visitor);
}
// ========== Programa e Declarações ==========
class NodoPrograma extends NodoAST {
final List<NodoDeclaracao> declaracoes;
NodoPrograma(this.declaracoes) : super(0);
@override
T aceitar<T>(VisitorAST<T> visitor) => visitor.visitarPrograma(this);
}
abstract class NodoDeclaracao extends NodoAST {
NodoDeclaracao(int linha) : super(linha);
}
class NodoDeclaracaoFuncao extends NodoDeclaracao {
final String nome;
final List<Parametro> parametros;
final String? tipoRetorno;
final List<NodoComando> corpo;
NodoDeclaracaoFuncao(
this.nome,
this.parametros,
this.tipoRetorno,
this.corpo,
int linha
) : super(linha);
@override
T aceitar<T>(VisitorAST<T> visitor) =>
visitor.visitarDeclaracaoFuncao(this);
}
class Parametro {
final String nome;
final String? tipo;
Parametro(this.nome, this.tipo);
}
class NodoDeclaracaoVariavel extends NodoDeclaracao {
final String nome;
final String? tipoExplicito;
final NodoExpressao? inicializador;
NodoDeclaracaoVariavel(
this.nome,
this.tipoExplicito,
this.inicializador,
int linha
) : super(linha);
@override
T aceitar<T>(VisitorAST<T> visitor) =>
visitor.visitarDeclaracaoVariavel(this);
}
class NodoDeclaracaoClasse extends NodoDeclaracao {
final String nome;
final List<NodoDeclaracaoVariavel> campos;
final List<NodoDeclaracaoFuncao> metodos;
NodoDeclaracaoClasse(
this.nome,
this.campos,
this.metodos,
int linha
) : super(linha);
@override
T aceitar<T>(VisitorAST<T> visitor) =>
visitor.visitarDeclaracaoClasse(this);
}
// ========== Comandos ==========
abstract class NodoComando extends NodoDeclaracao {
NodoComando(int linha) : super(linha);
}
class NodoComandoExpressao extends NodoComando {
final NodoExpressao expressao;
NodoComandoExpressao(this.expressao, int linha) : super(linha);
@override
T aceitar<T>(VisitorAST<T> visitor) =>
visitor.visitarComandoExpressao(this);
}
class NodoComandoIf extends NodoComando {
final NodoExpressao condicao;
final NodoComando blocoEntao;
final NodoComando? blocoSenao;
NodoComandoIf(
this.condicao,
this.blocoEntao,
this.blocoSenao,
int linha
) : super(linha);
@override
T aceitar<T>(VisitorAST<T> visitor) =>
visitor.visitarComandoIf(this);
}
class NodoComandoWhile extends NodoComando {
final NodoExpressao condicao;
final NodoComando corpo;
NodoComandoWhile(this.condicao, this.corpo, int linha) : super(linha);
@override
T aceitar<T>(VisitorAST<T> visitor) =>
visitor.visitarComandoWhile(this);
}
class NodoComandoFor extends NodoComando {
final NodoComando? inicializador;
final NodoExpressao? condicao;
final NodoExpressao? incremento;
final NodoComando corpo;
NodoComandoFor(
this.inicializador,
this.condicao,
this.incremento,
this.corpo,
int linha
) : super(linha);
@override
T aceitar<T>(VisitorAST<T> visitor) =>
visitor.visitarComandoFor(this);
}
class NodoComandoReturn extends NodoComando {
final NodoExpressao? valor;
NodoComandoReturn(this.valor, int linha) : super(linha);
@override
T aceitar<T>(VisitorAST<T> visitor) =>
visitor.visitarComandoReturn(this);
}
class NodoComandoBloco extends NodoComando {
final List<NodoComando> comandos;
NodoComandoBloco(this.comandos, int linha) : super(linha);
@override
T aceitar<T>(VisitorAST<T> visitor) =>
visitor.visitarComandoBloco(this);
}
// ========== Expressões ==========
abstract class NodoExpressao extends NodoAST {
NodoExpressao(int linha) : super(linha);
}
class NodoExpressaoLiteral extends NodoExpressao {
final Object? valor;
NodoExpressaoLiteral(this.valor, int linha) : super(linha);
@override
T aceitar<T>(VisitorAST<T> visitor) =>
visitor.visitarExpressaoLiteral(this);
}
class NodoExpressaoVariavel extends NodoExpressao {
final String nome;
NodoExpressaoVariavel(this.nome, int linha) : super(linha);
@override
T aceitar<T>(VisitorAST<T> visitor) =>
visitor.visitarExpressaoVariavel(this);
}
class NodoExpressaoBinaria extends NodoExpressao {
final String operador;
final NodoExpressao esquerda;
final NodoExpressao direita;
NodoExpressaoBinaria(
this.operador,
this.esquerda,
this.direita,
int linha
) : super(linha);
@override
T aceitar<T>(VisitorAST<T> visitor) =>
visitor.visitarExpressaoBinaria(this);
}
class NodoExpressaoUnaria extends NodoExpressao {
final String operador;
final NodoExpressao operando;
NodoExpressaoUnaria(this.operador, this.operando, int linha) : super(linha);
@override
T aceitar<T>(VisitorAST<T> visitor) =>
visitor.visitarExpressaoUnaria(this);
}
class NodoExpressaoAtribuicao extends NodoExpressao {
final String nome;
final NodoExpressao valor;
NodoExpressaoAtribuicao(this.nome, this.valor, int linha) : super(linha);
@override
T aceitar<T>(VisitorAST<T> visitor) =>
visitor.visitarExpressaoAtribuicao(this);
}
class NodoExpressaoChamada extends NodoExpressao {
final NodoExpressao funcao;
final List<NodoExpressao> argumentos;
NodoExpressaoChamada(this.funcao, this.argumentos, int linha) : super(linha);
@override
T aceitar<T>(VisitorAST<T> visitor) =>
visitor.visitarExpressaoChamada(this);
}
class NodoExpressaoAcesso extends NodoExpressao {
final NodoExpressao objeto;
final String propriedade;
NodoExpressaoAcesso(this.objeto, this.propriedade, int linha) : super(linha);
@override
T aceitar<T>(VisitorAST<T> visitor) =>
visitor.visitarExpressaoAcesso(this);
}
class NodoExpressaoAgrupamento extends NodoExpressao {
final NodoExpressao expressao;
NodoExpressaoAgrupamento(this.expressao, int linha) : super(linha);
@override
T aceitar<T>(VisitorAST<T> visitor) =>
visitor.visitarExpressaoAgrupamento(this);
}
// Nó especial para indicar erro de parsing
class NodoErro extends NodoDeclaracao {
NodoErro() : super(0);
@override
T aceitar<T>(VisitorAST<T> visitor) => visitor.visitarErro(this);
}
// ========== Interface Visitor ==========
abstract class VisitorAST<T> {
T visitarPrograma(NodoPrograma nodo);
T visitarDeclaracaoFuncao(NodoDeclaracaoFuncao nodo);
T visitarDeclaracaoVariavel(NodoDeclaracaoVariavel nodo);
T visitarDeclaracaoClasse(NodoDeclaracaoClasse nodo);
T visitarComandoExpressao(NodoComandoExpressao nodo);
T visitarComandoIf(NodoComandoIf nodo);
T visitarComandoWhile(NodoComandoWhile nodo);
T visitarComandoFor(NodoComandoFor nodo);
T visitarComandoReturn(NodoComandoReturn nodo);
T visitarComandoBloco(NodoComandoBloco nodo);
T visitarExpressaoLiteral(NodoExpressaoLiteral nodo);
T visitarExpressaoVariavel(NodoExpressaoVariavel nodo);
T visitarExpressaoBinaria(NodoExpressaoBinaria nodo);
T visitarExpressaoUnaria(NodoExpressaoUnaria nodo);
T visitarExpressaoAtribuicao(NodoExpressaoAtribuicao nodo);
T visitarExpressaoChamada(NodoExpressaoChamada nodo);
T visitarExpressaoAcesso(NodoExpressaoAcesso nodo);
T visitarExpressaoAgrupamento(NodoExpressaoAgrupamento nodo);
T visitarErro(NodoErro nodo);
}Esta hierarquia completa de classes AST fornece uma base sólida para todas as operações sobre o código parseado. O padrão Visitor facilita adicionar novas operações sem modificar as classes de nós.
🎨 Visualizador de AST: Ferramenta de Depuração
Uma ferramenta extremamente útil durante desenvolvimento é um visualizador de AST que renderiza a árvore graficamente. Vamos implementar um visitante que gera representação textual estruturada da AST:
// arquivo: visualizador_ast.dart
import 'ast.dart';
class VisualizadorAST implements VisitorAST<String> {
int _indentacao = 0;
String _indent() => ' ' * _indentacao;
String visualizar(NodoAST nodo) {
return nodo.aceitar(this);
}
@override
String visitarPrograma(NodoPrograma nodo) {
final buffer = StringBuffer();
buffer.writeln('Programa:');
_indentacao++;
for (var declaracao in nodo.declaracoes) {
buffer.writeln('${_indent()}${declaracao.aceitar(this)}');
}
_indentacao--;
return buffer.toString();
}
@override
String visitarDeclaracaoFuncao(NodoDeclaracaoFuncao nodo) {
final buffer = StringBuffer();
buffer.write('Função ${nodo.nome}(');
for (int i = 0; i < nodo.parametros.length; i++) {
if (i > 0) buffer.write(', ');
final param = nodo.parametros[i];
buffer.write(param.nome);
if (param.tipo != null) buffer.write(': ${param.tipo}');
}
buffer.write(')');
if (nodo.tipoRetorno != null) buffer.write(': ${nodo.tipoRetorno}');
buffer.writeln();
_indentacao++;
for (var comando in nodo.corpo) {
buffer.writeln('${_indent()}${comando.aceitar(this)}');
}
_indentacao--;
return buffer.toString();
}
@override
String visitarDeclaracaoVariavel(NodoDeclaracaoVariavel nodo) {
final buffer = StringBuffer();
buffer.write('Var ${nodo.nome}');
if (nodo.tipoExplicito != null) buffer.write(': ${nodo.tipoExplicito}');
if (nodo.inicializador != null) {
buffer.write(' = ${nodo.inicializador!.aceitar(this)}');
}
return buffer.toString();
}
@override
String visitarDeclaracaoClasse(NodoDeclaracaoClasse nodo) {
final buffer = StringBuffer();
buffer.writeln('Classe ${nodo.nome}:');
_indentacao++;
if (nodo.campos.isNotEmpty) {
buffer.writeln('${_indent()}Campos:');
_indentacao++;
for (var campo in nodo.campos) {
buffer.writeln('${_indent()}${campo.aceitar(this)}');
}
_indentacao--;
}
if (nodo.metodos.isNotEmpty) {
buffer.writeln('${_indent()}Métodos:');
_indentacao++;
for (var metodo in nodo.metodos) {
buffer.writeln('${_indent()}${metodo.aceitar(this)}');
}
_indentacao--;
}
_indentacao--;
return buffer.toString();
}
@override
String visitarComandoExpressao(NodoComandoExpressao nodo) {
return 'Comando: ${nodo.expressao.aceitar(this)}';
}
@override
String visitarComandoIf(NodoComandoIf nodo) {
final buffer = StringBuffer();
buffer.writeln('If ${nodo.condicao.aceitar(this)}:');
_indentacao++;
buffer.writeln('${_indent()}Então: ${nodo.blocoEntao.aceitar(this)}');
if (nodo.blocoSenao != null) {
buffer.writeln('${_indent()}Senão: ${nodo.blocoSenao!.aceitar(this)}');
}
_indentacao--;
return buffer.toString();
}
@override
String visitarComandoWhile(NodoComandoWhile nodo) {
final buffer = StringBuffer();
buffer.writeln('While ${nodo.condicao.aceitar(this)}:');
_indentacao++;
buffer.writeln('${_indent()}${nodo.corpo.aceitar(this)}');
_indentacao--;
return buffer.toString();
}
@override
String visitarComandoFor(NodoComandoFor nodo) {
final buffer = StringBuffer();
buffer.write('For(');
if (nodo.inicializador != null) {
buffer.write(nodo.inicializador!.aceitar(this));
}
buffer.write('; ');
if (nodo.condicao != null) {
buffer.write(nodo.condicao!.aceitar(this));
}
buffer.write('; ');
if (nodo.incremento != null) {
buffer.write(nodo.incremento!.aceitar(this));
}
buffer.writeln('):');
_indentacao++;
buffer.writeln('${_indent()}${nodo.corpo.aceitar(this)}');
_indentacao--;
return buffer.toString();
}
@override
String visitarComandoReturn(NodoComandoReturn nodo) {
if (nodo.valor != null) {
return 'Return ${nodo.valor!.aceitar(this)}';
}
return 'Return';
}
@override
String visitarComandoBloco(NodoComandoBloco nodo) {
final buffer = StringBuffer();
buffer.writeln('Bloco:');
_indentacao++;
for (var comando in nodo.comandos) {
buffer.writeln('${_indent()}${comando.aceitar(this)}');
}
_indentacao--;
return buffer.toString();
}
@override
String visitarExpressaoLiteral(NodoExpressaoLiteral nodo) {
if (nodo.valor is String) {
return '"${nodo.valor}"';
}
return '${nodo.valor}';
}
@override
String visitarExpressaoVariavel(NodoExpressaoVariavel nodo) {
return nodo.nome;
}
@override
String visitarExpressaoBinaria(NodoExpressaoBinaria nodo) {
return '(${nodo.esquerda.aceitar(this)} ${nodo.operador} ${nodo.direita.aceitar(this)})';
}
@override
String visitarExpressaoUnaria(NodoExpressaoUnaria nodo) {
return '(${nodo.operador}${nodo.operando.aceitar(this)})';
}
@override
String visitarExpressaoAtribuicao(NodoExpressaoAtribuicao nodo) {
return '${nodo.nome} = ${nodo.valor.aceitar(this)}';
}
@override
String visitarExpressaoChamada(NodoExpressaoChamada nodo) {
final buffer = StringBuffer();
buffer.write(nodo.funcao.aceitar(this));
buffer.write('(');
for (int i = 0; i < nodo.argumentos.length; i++) {
if (i > 0) buffer.write(', ');
buffer.write(nodo.argumentos[i].aceitar(this));
}
buffer.write(')');
return buffer.toString();
}
@override
String visitarExpressaoAcesso(NodoExpressaoAcesso nodo) {
return '${nodo.objeto.aceitar(this)}.${nodo.propriedade}';
}
@override
String visitarExpressaoAgrupamento(NodoExpressaoAgrupamento nodo) {
return nodo.expressao.aceitar(this);
}
@override
String visitarErro(NodoErro nodo) {
return '[ERRO DE PARSING]';
}
}
// Exemplo de uso:
void main() {
String codigo = '''
function fibonacci(n: int): int {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
var resultado = fibonacci(10);
''';
// Assumindo que temos lexer funcionando
var tokens = Lexer(codigo).tokenizar();
var parser = Parser(tokens);
var ast = parser.parsearPrograma();
if (!parser.teveErro) {
var visualizador = VisualizadorAST();
print(visualizador.visualizar(ast));
} else {
print('Erros encontrados durante parsing:');
for (var erro in parser.mensagensErro) {
print(erro);
}
}
}Esta ferramenta de visualização torna muito mais fácil depurar problemas no parser, permitindo ver exatamente como a AST está sendo construída.
🧪 Suite de Testes Abrangente
Finalmente, vamos criar uma suite de testes completa que valida todas as funcionalidades do parser:
// arquivo: test_parser.dart
import 'package:test/test.dart';
import 'parser.dart';
import 'lexer.dart';
import 'ast.dart';
void main() {
group('Testes de Expressões', () {
test('Expressão literal numérica', () {
var parser = criarParser('42;');
var ast = parser.parsearPrograma();
expect(parser.teveErro, false);
expect(ast.declaracoes, hasLength(1));
var comando = ast.declaracoes[0] as NodoComandoExpressao;
var literal = comando.expressao as NodoExpressaoLiteral;
expect(literal.valor, 42.0);
});
test('Expressão binária simples', () {
var parser = criarParser('5 + 3;');
var ast = parser.parsearPrograma();
expect(parser.teveErro, false);
var comando = ast.declaracoes[0] as NodoComandoExpressao;
var binaria = comando.expressao as NodoExpressaoBinaria;
expect(binaria.operador, '+');
expect((binaria.esquerda as NodoExpressaoLiteral).valor, 5.0);
expect((binaria.direita as NodoExpressaoLiteral).valor, 3.0);
});
test('Precedência de operadores', () {
var parser = criarParser('2 + 3 * 4;');
var ast = parser.parsearPrograma();
expect(parser.teveErro, false);
var comando = ast.declaracoes[0] as NodoComandoExpressao;
var adicao = comando.expressao as NodoExpressaoBinaria;
// Deve ser: +(2, *(3, 4))
expect(adicao.operador, '+');
expect((adicao.esquerda as NodoExpressaoLiteral).valor, 2.0);
var multiplicacao = adicao.direita as NodoExpressaoBinaria;
expect(multiplicacao.operador, '*');
expect((multiplicacao.esquerda as NodoExpressaoLiteral).valor, 3.0);
expect((multiplicacao.direita as NodoExpressaoLiteral).valor, 4.0);
});
test('Expressão entre parênteses', () {
var parser = criarParser('(2 + 3) * 4;');
var ast = parser.parsearPrograma();
expect(parser.teveErro, false);
var comando = ast.declaracoes[0] as NodoComandoExpressao;
var multiplicacao = comando.expressao as NodoExpressaoBinaria;
// Deve ser: *(+(2, 3), 4)
expect(multiplicacao.operador, '*');
var adicao = multiplicacao.esquerda as NodoExpressaoBinaria;
expect(adicao.operador, '+');
expect((adicao.esquerda as NodoExpressaoLiteral).valor, 2.0);
expect((adicao.direita as NodoExpressaoLiteral).valor, 3.0);
expect((multiplicacao.direita as NodoExpressaoLiteral).valor, 4.0);
});
test('Operadores unários', () {
var parser = criarParser('-5 * 2;');
var ast = parser.parsearPrograma();
expect(parser.teveErro, false);
var comando = ast.declaracoes[0] as NodoComandoExpressao;
var multiplicacao = comando.expressao as NodoExpressaoBinaria;
// Deve ser: *(-(5), 2)
expect(multiplicacao.operador, '*');
var negacao = multiplicacao.esquerda as NodoExpressaoUnaria;
expect(negacao.operador, '-');
expect((negacao.operando as NodoExpressaoLiteral).valor, 5.0);
});
});
group('Testes de Declarações', () {
test('Declaração de variável simples', () {
var parser = criarParser('var x = 5;');
var ast = parser.parsearPrograma();
expect(parser.teveErro, false);
expect(ast.declaracoes, hasLength(1));
var declaracao = ast.declaracoes[0] as NodoDeclaracaoVariavel;
expect(declaracao.nome, 'x');
expect(declaracao.tipoExplicito, null);
expect((declaracao.inicializador as NodoExpressaoLiteral).valor, 5.0);
});
test('Declaração de variável com tipo', () {
var parser = criarParser('var x: int = 5;');
var ast = parser.parsearPrograma();
expect(parser.teveErro, false);
var declaracao = ast.declaracoes[0] as NodoDeclaracaoVariavel;
expect(declaracao.nome, 'x');
expect(declaracao.tipoExplicito, 'int');
});
test('Declaração de função simples', () {
var parser = criarParser('''
function soma(a: int, b: int): int {
return a + b;
}
''');
var ast = parser.parsearPrograma();
expect(parser.teveErro, false);
expect(ast.declaracoes, hasLength(1));
var funcao = ast.declaracoes[0] as NodoDeclaracaoFuncao;
expect(funcao.nome, 'soma');
expect(funcao.parametros, hasLength(2));
expect(funcao.parametros[0].nome, 'a');
expect(funcao.parametros[0].tipo, 'int');
expect(funcao.tipoRetorno, 'int');
expect(funcao.corpo, hasLength(1));
});
});
group('Testes de Comandos', () {
test('Comando if simples', () {
var parser = criarParser('''
if (x > 5) {
y = 10;
}
''');
var ast = parser.parsearPrograma();
expect(parser.teveErro, false);
var comandoIf = ast.declaracoes[0] as NodoComandoIf;
expect(comandoIf.condicao, isA<NodoExpressaoBinaria>());
expect(comandoIf.blocoEntao, isA<NodoComandoBloco>());
expect(comandoIf.blocoSenao, null);
});
test('Comando if-else', () {
var parser = criarParser('''
if (x > 5) {
y = 10;
} else {
y = 20;
}
''');
var ast = parser.parsearPrograma();
expect(parser.teveErro, false);
var comandoIf = ast.declaracoes[0] as NodoComandoIf;
expect(comandoIf.blocoSenao, isNotNull);
});
test('Comando while', () {
var parser = criarParser('''
while (x < 10) {
x = x + 1;
}
''');
var ast = parser.parsearPrograma();
expect(parser.teveErro, false);
var comandoWhile = ast.declaracoes[0] as NodoComandoWhile;
expect(comandoWhile.condicao, isA<NodoExpressaoBinaria>());
expect(comandoWhile.corpo, isA<NodoComandoBloco>());
});
test('Comando for', () {
var parser = criarParser('''
for (var i = 0; i < 10; i = i + 1) {
soma = soma + i;
}
''');
var ast = parser.parsearPrograma();
expect(parser.teveErro, false);
var comandoFor = ast.declaracoes[0] as NodoComandoFor;
expect(comandoFor.inicializador, isA<NodoDeclaracaoVariavel>());
expect(comandoFor.condicao, isA<NodoExpressaoBinaria>());
expect(comandoFor.incremento, isA<NodoExpressaoAtribuicao>());
});
});
group('Testes de Recuperação de Erros', () {
test('Erro de ponto-e-vírgula faltando', () {
var parser = criarParser('''
var x = 5
var y = 10;
''');
var ast = parser.parsearPrograma();
expect(parser.teveErro, true);
expect(parser.mensagensErro, hasLength(1));
expect(parser.mensagensErro[0], contains('ponto-e-vírgula'));
// Deve ter parseado ambas declarações mesmo com erro
expect(ast.declaracoes, hasLength(2));
});
test('Erro de parêntese não fechado', () {
var parser = criarParser('var x = (5 + 3;');
var ast = parser.parsearPrograma();
expect(parser.teveErro, true);
expect(parser.mensagensErro[0], contains(')'));
});
test('Múltiplos erros detectados', () {
var parser = criarParser('''
var x = 5
var y = 10
var z = 15;
''');
var ast = parser.parsearPrograma();
expect(parser.teveErro, true);
expect(parser.mensagensErro.length, greaterThanOrEqual(2));
});
});
group('Testes de Casos Complexos', () {
test('Função recursiva', () {
var parser = criarParser('''
function fatorial(n: int): int {
if (n <= 1) {
return 1;
}
return n * fatorial(n - 1);
}
''');
var ast = parser.parsearPrograma();
expect(parser.teveErro, false);
var funcao = ast.declaracoes[0] as NodoDeclaracaoFuncao;
expect(funcao.nome, 'fatorial');
// Verifica que há uma chamada recursiva no corpo
var bloco = funcao.corpo[1] as NodoComandoReturn;
var multiplicacao = bloco.valor as NodoExpressaoBinaria;
var chamada = multiplicacao.direita as NodoExpressaoChamada;
var funcaoChamada = chamada.funcao as NodoExpressaoVariavel;
expect(funcaoChamada.nome, 'fatorial');
});
test('Classe com métodos', () {
var parser = criarParser('''
class Ponto {
var x: int;
var y: int;
function distancia(): int {
return x * x + y * y;
}
}
''');
var ast = parser.parsearPrograma();
expect(parser.teveErro, false);
var classe = ast.declaracoes[0] as NodoDeclaracaoClasse;
expect(classe.nome, 'Ponto');
expect(classe.campos, hasLength(2));
expect(classe.metodos, hasLength(1));
});
test('Expressões complexas aninhadas', () {
var parser = criarParser('''
var resultado = ((a + b) * (c - d)) / (e + (f * g));
''');
var ast = parser.parsearPrograma();
expect(parser.teveErro, false);
var declaracao = ast.declaracoes[0] as NodoDeclaracaoVariavel;
expect(declaracao.inicializador, isA<NodoExpressaoBinaria>());
});
});
}
// Função auxiliar para criar parser a partir de código
Parser criarParser(String codigo) {
var lexer = Lexer(codigo);
var tokens = lexer.tokenizar();
return Parser(tokens);
}Esta suite de testes cobre desde casos simples até cenários complexos, incluindo testes de recuperação de erros. Executar estes testes regularmente durante desenvolvimento garante que mudanças no parser não quebram funcionalidade existente.