O que você vai aprender
Explicar o parsing recursivo-descendente e o método de um procedimento por não-terminal.
Diagnosticar e eliminar recursão à esquerda.
Aplicar fatoração à esquerda.
Reconhecer essas transformações como pré-requisitos de LL(1).
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.
O que veremos nesta aula
- 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.
Onde estamos: as seis aulas até aqui
Antes de entrar na descida recursiva, vale parar um minuto e olhar para trás. As seis aulas até aqui não são seis assuntos soltos: são seis elos de uma corrente que termina exatamente no que esta aula faz — pegar uma fila de tokens e devolver a árvore sintática.
Cada aula entregou uma peça que a seguinte usa como matéria-prima. Lendo a tabela da esquerda para a direita você vê o objetivo; lendo a última coluna você vê por que a aula precisou existir.
| Aula | Objetivo | O que ela entrega para a seguinte | O que faltaria sem ela |
|---|---|---|---|
| 1 Introdução à compilação | Entender o que é um compilador, como ele difere de um interpretador e o panorama das fases. | O modelo de fases — e, com ele, um erro que tem dono: cada fase reclama só do que é dela. | A única mensagem possível seria “erro no programa”, sem dizer o que nem onde. |
| 2 Linguagens, gramáticas e estrutura do compilador | Compreender os níveis de abstração, a organização front-end/back-end e a hierarquia de Chomsky. | A régua que diz de que máquina cada parte precisa: token é tipo 3 (autômato finito), aninhamento é tipo 2 (pilha). | Tentaríamos analisar sintaxe com expressão regular — e ela aceita programa desbalanceado. |
| 3 Análise léxica I | Aprender a transformar caracteres em tokens, dominando a tríade lexema/token/padrão e as expressões regulares. | O token: total deixa de ser cinco caracteres e vira um símbolo só, id. | O analisador sintático receberia caracteres — e a gramática dele não fala em caracteres. |
| 4 Análise léxica II | Entender como expressões regulares viram código executável (ER → AFN → AFD → código). | O scanner que roda — e com ele o maior casamento, que faz >= ser um token e não dois. | A expressão regular ficaria escrita e correta, mas sem máquina que a execute direito. |
| 5 Gramáticas livres de contexto | Dominar GLCs, derivações, árvores sintáticas, ambiguidade e as notações BNF/EBNF. | A gramática que dá uma árvore só — com a precedência morando na forma da árvore. | A mesma cadeia teria duas árvores e dois valores: a tradução deixaria de estar definida. |
| 6 Análise sintática descendente | Aprender o parsing recursivo-descendente e como preparar a gramática (eliminar recursão à esquerda, fatorar). | O parser: um procedimento por não-terminal, que reconstrói a árvore da raiz às folhas. | A gramática ficaria correta no papel e o parser giraria para sempre na primeira produção. |
A bancada abaixo põe isso à prova: a mesma entrada atravessa as seis aulas, e você pode desligar qualquer uma delas para ver onde a corrente arrebenta.
Análise descendente (top-down)
"Descendente" porque parte do topo da árvore e desce, prevendo a estrutura antes de ver todos os tokens.
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.
Reconhecendo "id + id"
Acompanhe as chamadas para a entrada id + id, com a gramática E → T E', E' → + T E' | ε:
| Chamada | Token atual | Ação |
|---|---|---|
| E → T E' | id | chama T |
| T → id | id | consome id |
| E' → + T E' | + | consome +, chama T |
| T → id | id | consome id |
| E' → ε | fim | retorna |
Passo a passo: a pilha de chamadas
Abaixo, a mesma descida ao vivo: escolha uma cadeia e acompanhe a pilha de chamadas, a fita e a árvore crescendo da raiz — inclusive nas cadeias inválidas, para ver onde o erro nasce.
Gerar × reconhecer: a aula 5 e a aula 6 lado a lado
Na aula 5 você gerava: partia de E e escolhia as produções sabendo aonde queria chegar. O parser faz o caminho inverso: recebe a cadeia pronta, vinda do léxico, e precisa descobrir se existe uma derivação que a produza — e qual. Ele não pode escolher olhando a resposta: a cada passo, enxerga só o token sob a cabeça.
| Aula 5 · gerar | Aula 6 · reconhecer | |
|---|---|---|
| Ponto de partida | o símbolo inicial E | a cadeia de tokens, inteira na fita |
| Quem escolhe a produção | quem deriva, conhecendo o alvo inteiro | o token sob a cabeça (o FIRST de cada alternativa) |
| Um terminal na árvore | nasce escrito, quando a produção é aplicada | nasce previsto e só vale depois de conferido na fita |
| Erro de sintaxe | não existe: quem gera nunca escreve uma cadeia errada | nasce num consome() que não bate, ou num procedimento sem alternativa para o token |
| A gramática | E → E + T | T serve | precisa ser reescrita: E → T E', E' → + T E' | ε |
A reescrita não muda a linguagem: as mesmas cadeias continuam aceitas. Muda só a forma das produções, para que cada procedimento avance na entrada antes de chamar a si mesmo — é o assunto das próximas seções. Quando você vê E(), T() e E1() no pseudocódigo lá em cima, não é uma gramática nova saída do nada: é a gramática de expressões da aula 5, saneada para a descida.
A bancada abaixo põe as duas lado a lado sobre a mesma cadeia. Repare em três coisas: a forma sentencial é a mesma nas duas colunas em todo passo — do lado da aula 6 ela é lida da pilha de chamadas, não de uma derivação; o mesmo terminal nasce escrito à esquerda e previsto à direita, e só fica verde quando a cabeça passa por ele; e, trocando para a gramática original da aula 5, veja em que linha as colunas se separam — e por quê.
Recursão à esquerda
Por que ela quebra o parser
A solução é reescrever a gramática, transformando a recursão à esquerda em recursão à direita:
| Com recursão à esquerda | Reescrita (à direita) |
|---|---|
| E → E + T | T | E → T E' E' → + T E' | ε |
A porta giratória infinita
Na bancada abaixo, veja a porta girar de verdade: E() chamando E() com a cabeça parada até a pilha estourar — e a reescrita passando na mesma cadeia. Na segunda aba, o detector encontra também a recursão indireta, a que é mais difícil de enxergar, e a elimina com o algoritmo do livro.
Descendente × ascendente
| Descendente (top-down) | Ascendente (bottom-up) | |
|---|---|---|
| Constrói a árvore | Da raiz às folhas | Das folhas à raiz |
| Decisão | Qual produção aplicar | Quando reduzir |
| Recursão à esquerda | Proíbe | Aceita |
| Exemplo | LL(1), recursivo-descendente | LR(1), LALR |
Preparando a gramática
Antes de escrever um parser descendente, a gramática passa por duas transformações de saneamento:
O mesmo analisador, escrito à mão
A tabela preditiva pode virar código direto — uma função por não-terminal. É o método da descida recursiva:
Compare com o simulador: a pilha explícita da tabela vira, aqui, a pilha de chamadas da própria linguagem. São o mesmo algoritmo com implementações diferentes.
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:
| Antes | Depois |
|---|---|
| S → if E then S | if E then S else S | S → 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'.
Na bancada abaixo, o prefixo comum é diagnosticado sobre a gramática que estiver na tela, a fatoração é aplicada com um clique e a mesma cadeia roda no parser antes e depois: antes ela falha, depois passa — sem que a linguagem tenha mudado.
A pilha do analisador preditivo, passo a passo
Aqui você acompanha o analisador trabalhando: de um lado a pilha, do outro a entrada restante, e a cada passo a produção aplicada ou o token casado.
Comece com id + id * id e avance passo a passo. Depois experimente as cadeias inválidas: id + (falta operando) e id id (falta operador). Observe onde exatamente a análise trava — a mensagem de erro de um compilador nasce desse ponto.
Verifique você mesmo: precisa fatorar?
A produção A → a b | a c precisa de fatoração à esquerda?
Parsers escritos à mão
Muitos compiladores reais (incluindo versões de GCC e Clang) usam parsers recursivo-descendentes escritos à mão.
Armadilhas do parser descendente
Ordem das transformações
Ponha isso à prova na bancada abaixo: oito gramáticas para diagnosticar e uma oficina em que você aplica as duas transformações na ordem que quiser, com o diagnóstico refeito a cada passo.
Reflita: descendente x ascendente
Se o parser descendente proíbe recursão à esquerda, por que ela é tão comum nas gramáticas?
Termos-chave da aula
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).
Resumo visual
Atividade em grupo · Refatorando gramáticas
Em trios, deixem uma gramática pronta para parsing descendente.
Roteiro
- Dada A → A α | β, eliminem a recursão à esquerda.
- Dada B → x y | x z, façam a fatoração à esquerda.
- Escrevam o procedimento recursivo-descendente para a gramática resultante.
- Testem o procedimento com uma entrada de exemplo.
Mini-quiz · Aula 6
20 questões sobre esta aula. Escolha e veja a explicação na hora.
📌 Resumo — leve isto para a prova
- Parser descendente constrói a árvore da raiz às folhas; recursivo-descendente usa uma função por não-terminal.
- Gerar (aula 5) e reconhecer (aula 6) chegam à mesma árvore, na mesma ordem: o parser escolhe cada produção pelo token sob a cabeça, e a pilha de chamadas faz o papel da forma sentencial.
- Recursão à esquerda (direta ou indireta) causa laço infinito e precisa ser eliminada.
- Fatoração à esquerda resolve prefixos comuns, adiando a decisão.
- Elimine a recursão à esquerda antes de fatorar.
- Ambas são pré-requisitos para LL(1).