Aula 09: Análise Sintática Descendente (LL)

Data de Publicação

25/03/2026

Data de Modificação

08/03/2026

Objetivos

  • Entender algoritmos de parsing Top-Down.
  • Construir tabelas de parsing LL(1).

Motivação prática

Parsers descendentes (LL) são especialmente interessantes para Engenharia de Computação porque:

  • São relativamente simples de implementar e depurar manualmente (funções recursivas que espelham a gramática).
  • Permitem construir rapidamente protótipos de linguagens e DSLs.
  • São uma porta de entrada natural para entender parsers gerados por ferramentas como ANTLR (que geram essencialmente parsers Top-Down).

Visão geral: Top-Down

flowchart TB
  S[Símbolo inicial] --> Expand[Expandir produção]
  Expand --> Tokens[Consumir tokens]
  Tokens --> Mais{Mais não terminais?}
  Mais -->|Sim| Expand
  Mais -->|Não| Fim[Árvore construída]

A análise Top-Down constrói a árvore da raiz para as folhas: começa em \(S\), escolhe uma produção \(A \to \alpha\), expande \(A\) por \(\alpha\), e continua expandindo não terminais da esquerda para a direita até obter a sequência de tokens da entrada. O parser “adivinha” qual produção usar com base no token atual (lookahead).

Conteúdo

Parsers Preditivos (LL)

Parsers que não precisam de backtracking. Eles olham o token atual (Lookahead \(k=1\)) e decidem deterministicamente o caminho. - Left-to-right scan (Lê da esquerda pra direita). - Leftmost derivation (Gera a derivação mais à esquerda).

Conjuntos FIRST e FOLLOW

Para construir a tabela de decisão do parser, calculamos dois conjuntos auxiliares para cada não-terminal:

  1. FIRST(\(\alpha\)): O conjunto de terminais que podem começar a string derivada de \(\alpha\).
    • Se eu tenho a regra A -> c B, então c está no FIRST(A).
  2. FOLLOW(A): O conjunto de terminais que podem aparecer imediatamente após o não-terminal A na derivação.
    • É necessário para regras que podem sumir (\(\epsilon\)). Se A -> \epsilon, o parser só aplica essa regra se o token atual estiver no FOLLOW(A).

A Tabela de Parsing \(M\)

Uma matriz \(M[A, a]\) onde \(A\) é o não-terminal e \(a\) é o token atual. - Se \(a \in FIRST(\alpha)\), então \(M[A, a] = A \to \alpha\). - Se \(\alpha\) pode ser nulo e \(a \in FOLLOW(A)\), então \(M[A, a] = A \to \epsilon\). - Se uma célula tiver mais de uma regra, a gramática não é LL(1) (tem conflitos).

Algoritmo do parser LL(1)

Enquanto a pilha (ou a pilha de chamadas, na descida recursiva) não estiver vazia e a entrada não tiver sido toda consumida:

  • Se o topo for terminal: deve coincidir com o token atual; consumir ambos e avançar.
  • Se o topo for não terminal \(A\): consultar \(M[A, a]\) onde \(a\) é o token atual; se \(M[A,a] = A \to X_1 X_2 \ldots X_k\), desempilhar \(A\) e empilhar \(X_k, \ldots, X_1\) (ordem inversa para que \(X_1\) seja processado primeiro). Se \(M[A,a]\) for vazio, erro de sintaxe.

Na descida recursiva, não há pilha explícita: cada não terminal corresponde a uma função; a “pilha” é a pilha de chamadas. A função para \(A\) lê o token atual, consulta FIRST/FOLLOW (ou uma tabela equivalente) para decidir qual produção usar, e chama as funções dos não terminais no lado direito na ordem.

Conexões com o projeto Mini-Pascal

  • Na Etapa 3 do projeto, você implementará um parser de descida recursiva para Mini-Pascal, seguindo a ideia de que cada não-terminal da gramática vira uma função.
  • O cálculo de FIRST e FOLLOW para a gramática de Mini-Pascal é a base para garantir que seu parser seja determinístico (LL(1) em subconjuntos relevantes da linguagem).

Perguntas de reflexão

  • Quais características da gramática de Mini-Pascal facilitam ou dificultam a construção de um parser LL(1)?
  • Em que momento pode ser mais vantajoso abandonar um parser manual LL e adotar uma ferramenta que gera parsers automaticamente?

Resumo

  • Parser LL(1): leitura da esquerda para a direita, derivação mais à esquerda, lookahead de 1 token.
  • FIRST e FOLLOW permitem construir a tabela de parsing \(M\); se toda célula tiver no máximo uma produção, a gramática é LL(1).
  • Descida recursiva: cada não terminal vira uma função; a decisão é tomada com base no token atual e em FIRST/FOLLOW.

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