Aula 10: Exemplo de Implementação de Parser LL

Data de Publicação

25/03/2026

Data de Modificação

08/03/2026

Objetivos

  • Hands-on: Implementando um parser na prática.
  • Estratégias de tratamento de erro (Panic Mode).

Motivação e foco da aula

Esta é a aula em que a teoria de parsing LL se materializa em código real. Do ponto de vista de Engenharia:

  • Você aprende a mapear uma gramática em uma API concreta (funções, estruturas de dados, tipos de token).
  • Começa a lidar com problemas de borda importantes: mensagens de erro, recuperação após erro, manutenção do parser.
  • Cria uma base de código que será usada e evoluída nas próximas etapas (integração com análise semântica, geração de AST, etc.).

Conteúdo

A teoria se solidifica na prática. Vamos analisar a implementação de um parser do tipo Descida Recursiva (Recursive Descent), que é o tipo mais intuitivo de escrever à mão.

flowchart LR
  Gram[Gramática] --> Funções[Uma função por não terminal]
  Funções --> Match[match token]
  Funções --> Chamada[Chamada recursiva]
  Match --> Chamada

Mapeamento Gramática \(\to\) Código

Cada Não-Terminal vira uma função (método). O corpo da função segue o lado direito da produção.

Gramática:

T -> F T'
T' -> * F T' | epsilon
F -> ( E ) | id

Código Java:

void parseT() {
    parseF();
    parseT_prime();
}

void parseT_prime() {
    if (currentToken.type == MULT) { // Regra: * F T'
        match(MULT);
        parseF();
        parseT_prime();
    }
    // else: Regra epsilon (não faz nada, apenas retorna)
}

Tratamento de Erro (Panic Mode)

Um compilador não deve travar no primeiro erro de sintaxe. Queremos reportar o erro e continuar encontrando outros. - Estratégia Pânico: Ao encontrar um token inesperado: 1. Emita mensagem de erro. 2. Entre num loop while consumindo (jogando fora) tokens até encontrar um símbolo de Sincronização seguro (ex: ; ou end ou )). 3. A pilha de chamadas desenrola e o parser tenta retomar a análise a partir dali.

Conexões com o projeto Mini-Pascal

  • O parser de descida recursiva da Etapa 3 deve seguir o padrão mostrado aqui:
    • Um scanner responsável por entregar tokens.
    • Funções de parsing que implementam não-terminais da gramática.
    • Estratégias de tratamento de erro para não "explodir" na primeira inconsistência.
  • Ao implementar o parser de Mini-Pascal, pense sempre na legibilidade e manutenibilidade do código: um parser limpo é crucial quando você começar a incorporar análise semântica.

Perguntas de reflexão

  • Quais são as vantagens e desvantagens de implementar um parser manual em comparação com usar uma ferramenta geradora?
  • Como você projetaria a interface entre o scanner e o parser para que seja fácil de testar e substituir (por exemplo, ao trocar um scanner manual por Flex/ANTLR)?

Resumo

  • Parser de descida recursiva: cada não terminal vira uma função; o corpo segue as produções; decisões com base no token atual (FIRST/FOLLOW).
  • Panic mode: ao detectar erro, consumir tokens até um símbolo de sincronização e tentar retomar; reportar mensagem com localização.
  • Interface clara entre scanner e parser (next token, tipo, valor) facilita testes e troca de implementação (manual vs gerado).

Referências

  • Aho et al. (2006). Compilers: Principles, Techniques, and Tools. Cap. 4.
  • Cooper & Torczon (2011). Engineering a Compiler.

Materiais da aula

Última atualização: 08/03/2026

De volta ao topo