LRM Prof. Mantovani ← Aulas da disciplina
Semana 6 · Aula 6 de 14

Análise sintática descendente

Parsing recursivo-descendente: como percorrer a gramática, da raiz às folhas, para reconstruir a árvore sintática a partir dos tokens. Estudamos por que a recursão à esquerda quebra o método, como eliminá-la, e como a fatoração à esquerda prepara a gramática.

📚 Compiladores📝 mini-quiz ao final
Objetivos da aula

O que você vai aprender

1

Explicar o parsing recursivo-descendente e o método de um procedimento por não-terminal.

2

Diagnosticar e eliminar recursão à esquerda.

3

Aplicar fatoração à esquerda.

4

Reconhecer essas transformações como pré-requisitos de LL(1).

1 · Motivação

Reconstruir a árvore

A gramática gera cadeias. Mas o compilador recebe a cadeia (os tokens) e precisa do caminho inverso: reconstruir a árvore sintática. Esse é o trabalho do parser.

Há duas estratégias gerais: descendente (de cima para baixo) e ascendente (de baixo para cima). Esta aula foca na descendente, intuitiva e fácil de programar à mão.

🔑
Parsing = transformar uma sequência de tokens na árvore sintática que a gramática associa a ela.
2 · Mapa

O que veremos nesta aula

Top-down→Recursivo-descendente→Recursão à esquerda→Fatoração
  • A estratégia descendente.
  • Um procedimento por não-terminal.
  • Por que a recursão à esquerda quebra tudo e como removê-la.
  • A fatoração à esquerda.
3 · Definição

Análise descendente (top-down)

Parsing descendente. Constrói a árvore sintática da raiz (símbolo inicial) para as folhas (terminais), tentando casar a entrada com as produções, escolhendo qual produção aplicar a cada passo.

"Descendente" porque parte do topo da árvore e desce, prevendo a estrutura antes de ver todos os tokens.

4 · Aprofundamento

Um procedimento por não-terminal

No recursivo-descendente, cada não-terminal vira uma função. A função tenta reconhecer a parte da entrada que aquele não-terminal gera, chamando as funções dos outros não-terminais conforme a produção.

// um procedimento por nao-terminal função E(): T(); E1() função E1(): se token == '+': consome('+'); T(); E1() função T(): F(); T1() função F(): se token=='(' : consome('('); E(); consome(')') senão consome(id)
5 · Exemplo

Reconhecendo "id + id"

Acompanhe as chamadas para a entrada id + id, com a gramática E → T E', E' → + T E' | ε:

ChamadaToken atualAção
E → T E'idchama T
T → ididconsome id
E' → + T E'+consome +, chama T
T → ididconsome id
E' → εfimretorna
6 · Interativo

Passo a passo: a pilha de chamadas

Passo 1
Chama E(). Para reconhecer E, chama T() e depois E1().
Passo 2
Dentro de T(), chama F(). F vê o token id e o consome.
Passo 3
De volta em T(), chama T1(). O token seguinte não é '*', então T1 deriva ε e retorna.
Passo 4
De volta em E(), chama E1(). Não há '+', E1 deriva ε. A entrada foi reconhecida.
7 · Definição

Recursão à esquerda

Recursão à esquerda. Ocorre quando um não-terminal pode, em uma derivação, gerar a si mesmo como símbolo mais à esquerda (ex.: A → A α). Direta na produção, ou indireta via outros não-terminais.
8 · Aprofundamento

Por que ela quebra o parser

⚠️
A produção E → E + T faz a função E() chamar E() imediatamente, sem consumir nenhum token — um laço infinito. O parser descendente trava antes de ler qualquer coisa.

A solução é reescrever a gramática, transformando a recursão à esquerda em recursão à direita:

Com recursão à esquerdaReescrita (à direita)
E → E + T | TE → T E'
E' → + T E' | ε
9 · Analogia

A porta giratória infinita

🔧 Analogia
Recursão à esquerda é como uma porta giratória em que você empurra mas nunca avança: a função chama a si mesma sem "andar" na entrada, girando para sempre. A reescrita coloca um obstáculo que força você a dar um passo (consumir um token) antes de girar de novo.
10 · Comparação

Descendente × ascendente

Descendente (top-down)Ascendente (bottom-up)
Constrói a árvoreDa raiz às folhasDas folhas à raiz
DecisãoQual produção aplicarQuando reduzir
Recursão à esquerdaProíbeAceita
ExemploLL(1), recursivo-descendenteLR(1), LALR
11 · Fluxo

Preparando a gramática

Antes de escrever um parser descendente, a gramática passa por duas transformações de saneamento:

Gramática original→Eliminar recursão à esquerda→Fatorar à esquerda→Parser
12 · Aprofundamento

Fatoração à esquerda

Quando duas produções de um não-terminal começam igual, o parser não sabe, ao ver o prefixo comum, qual escolher. A fatoração à esquerda adia a decisão até depois do prefixo:

AntesDepois
S → if E then S | if E then S else SS → if E then S S'
S' → else S | ε

Agora há uma só produção começando com "if E then S", e a escolha do else fica isolada em S'.

13 · Verifique

Verifique você mesmo: precisa fatorar?

A produção A → a b | a c precisa de fatoração à esquerda?

Ao ver 'a', o parser não sabe se seguirá 'b' ou 'c'. Fatorando: A → a A', A' → b | c. A decisão se adia para depois do prefixo comum.
14 · Caso prático

Parsers escritos à mão

Muitos compiladores reais (incluindo versões de GCC e Clang) usam parsers recursivo-descendentes escritos à mão.

💡
A vantagem é o controle fino sobre mensagens de erro e recuperação. Como cada não-terminal é uma função, é fácil inserir lógica de diagnóstico específica em cada ponto da gramática.
15 · Erros comuns

Armadilhas do parser descendente

⚠️
Cuidado. Recursão à esquerda indireta (A → B..., B → A...) também causa laço infinito e é mais difícil de enxergar. E eliminar recursão à esquerda não dispensa fatorar: são problemas diferentes, e a gramática pode precisar das duas transformações.
16 · Boas práticas

Ordem das transformações

✅
Dica. Elimine a recursão à esquerda primeiro, depois fatore. A ordem importa: eliminar recursão pode introduzir novos prefixos comuns que precisarão de fatoração. Fazer na ordem inversa pode deixar recursão escondida.
17 · Revelar

Reflita: descendente x ascendente

Se o parser descendente proíbe recursão à esquerda, por que ela é tão comum nas gramáticas?
Porque a recursão à esquerda expressa naturalmente a associatividade à esquerda (a - b - c = (a - b) - c), que é a mais comum nos operadores. Parsers ascendentes (LR) aceitam recursão à esquerda diretamente, o que é uma de suas vantagens. No método descendente, pagamos o preço de reescrever a gramática para recursão à direita e depois reconstruir a associatividade correta nas ações semânticas.
18 · Flashcards

Termos-chave da aula

Top-downvirar
Estratégia que constrói a árvore da raiz para as folhas.
Recursivo-descendentevirar
Parser top-down com uma função por não-terminal.
Recursão à esquerdavirar
A → A α: causa laço infinito no parser descendente; deve ser eliminada.
Fatoração à esquerdavirar
Isola o prefixo comum de produções, adiando a decisão do parser.
19 · Conexões

Onde isto se encaixa no curso

Esta aula é o elo entre gramática e algoritmo:

  • Vem da aula 5: usa a gramática de expressões e a noção de árvore.
  • Prepara a aula 7: eliminar recursão e fatorar são pré-condições para LL(1) e a tabela preditiva.
  • Conecta com a aula 8: as funções do parser serão o lugar das ações semânticas (tradução dirigida pela sintaxe).
20 · Síntese

Resumo visual

🔑
Parser descendente constrói a árvore da raiz às folhas; o recursivo-descendente usa uma função por não-terminal. Recursão à esquerda causa laço infinito e precisa ser eliminada. Fatoração à esquerda resolve prefixos comuns. Ambas são pré-requisitos para LL(1).
Mão na massa · colaborativo

Atividade em grupo · Refatorando gramáticas

Em trios, deixem uma gramática pronta para parsing descendente.

⏱️ 25 min👥 trios🧩 exercício

Roteiro

  1. Dada A → A α | β, eliminem a recursão à esquerda.
  2. Dada B → x y | x z, façam a fatoração à esquerda.
  3. Escrevam o procedimento recursivo-descendente para a gramática resultante.
  4. Testem o procedimento com uma entrada de exemplo.
Refatoradorreescreve as produções
Codificadorescreve os procedimentos
Verificadortesta com uma entrada
📤 Entrega: Gramática refatorada + pseudocódigo dos procedimentos.
Teste seu conhecimento

Mini-quiz · Aula 6

20 questões sobre esta aula. Escolha e veja a explicação na hora.

0/20

📌 Resumo — leve isto para a prova