flowchart TB
subgraph DESC["Descendente"]
direction TB
R1["raiz: simbolo inicial"] --> M1["expande variaveis<br/>escolhendo producoes"]
M1 --> F1["fronteira: cadeia lida"]
end
subgraph ASC["Ascendente"]
direction BT
F2["folhas: cadeia lida"] --> M2["reduz trechos ao<br/>lado esquerdo da producao"]
M2 --> R2["raiz: simbolo inicial"]
end
DESC -.->|"mesma arvore,<br/>ordens opostas"| ASC
1 Módulo 10: Análise Sintática Descendente — Resumo
Esta é a versão de revisão. Recapitulo aqui, em ritmo de véspera, o módulo mais pesado do eixo sintático. Nada é demonstrado por inteiro — para isso existem a versão completa do material deste módulo e o livro. Use este texto para conferir se você percorre as cinco etapas do método sem consultar nada.
O módulo anterior terminou com uma máquina que dá sorte. O autômato de pilha das gramáticas livres de contexto é não determinístico, e não determinismo quer dizer que a máquina aceita quando alguma sequência de escolhas dá certo — sem dizer qual. Como objeto matemático, impecável; como especificação de programa, inútil. Este módulo é sobre eliminar a adivinhação.
1.1 O que a fase realmente entrega
Dizer que a análise sintática “verifica se o programa está correto” é modesto demais. O enunciado honesto tem três partes: dada G = (V, \Sigma, P, S) e uma cadeia w \in \Sigma^*, decidir se w \in L(G), exibir uma árvore quando sim, e localizar o ponto exato da falha quando não. O peso das três é desigual: decidir a pertinência é o que a teoria enfatiza e o que menos interessa a quem constrói compiladores; a árvore alimenta as fases seguintes; e o diagnóstico, que a teoria nem menciona, ocupa boa parte do código real.
Há ainda uma exigência que a teoria ignora: custo. O algoritmo geral mais conhecido custa proporcionalmente ao cubo do comprimento da entrada — para dez mil símbolos, ordem de 10^{12} operações. Compiladores usam métodos lineares, e a linearidade é comprada restringindo a classe de gramáticas aceitas. É essa troca que explica todo o trabalho de preparação a seguir.
A árvore tem raiz, o símbolo inicial, e fronteira, a cadeia de terminais — daí as duas famílias. A descendente parte da raiz e expande variáveis; a ascendente parte das folhas e reduz trechos. Aqui tratamos da primeira: ela reconhece menos gramáticas, e em troca o código fica tão parecido com a gramática que dá para ler um no outro. Expande-se sempre a variável mais à esquerda, e a razão não é de gosto: nessa derivação toda forma sentencial é x A \gamma com x já fixado, ou seja, o prefixo de terminais só cresce, e é isso que permite confrontar derivação e entrada enquanto se avança. A caracterização formal veio na segunda metade dos anos 1960, com Philip Lewis e Richard Stearns, detalhada por Daniel Rosenkrantz e Stearns em 1970.
Pare e pense. Que informação eu preciso ter, no instante de expandir uma variável, para acertar a produção de primeira? As duas seções seguintes são a formalização exata dessa resposta.
1.2 Preparar a gramática
A dificuldade do módulo não está no algoritmo de análise, simples ao ponto de decepcionar. Está antes dele: nem toda gramática serve. A gramática canônica das expressões, E \to E + T \mid T e T \to T * F \mid F, é não ambígua e exibe a precedência na forma das árvores — e é impossível de analisar por descida recursiva. Para expandir E o analisador chamaria o procedimento de E sem ter consumido símbolo nenhum: recursão sobre o mesmo problema, não sobre um menor. Recursão à direita é inofensiva, porque A \to \alpha A chama-se depois de consumir \alpha.
A eliminação sai de um raciocínio, não de uma fórmula: se toda derivação precisa sair da recursão por algum \beta_j, há um \beta obrigatório seguido de uma sequência arbitrária de \alpha, e isso pede variável nova:
A \to \beta_1 A' \mid \cdots \mid \beta_n A' \qquad A' \to \alpha_1 A' \mid \cdots \mid \alpha_m A' \mid \varepsilon
flowchart LR
G["gramatica de referencia<br/>legivel, publicada"] --> E["eliminar recursao<br/>a esquerda imediata"]
E --> D{"ha ciclo no grafo<br/>de primeiros simbolos?"}
D -->|"sim"| I["eliminar recursao<br/>indireta por ordenacao"]
D -->|"nao"| Fa
I --> Fa["fatorar a esquerda<br/>prefixo comum mais longo"]
Fa --> C["calcular anulaveis,<br/>primeiros e seguidores"]
C --> T["construir a tabela"]
Fa -.->|"preco cobrado"| P["legibilidade perdida<br/>associatividade invertida<br/>producoes vazias criadas"]
A recursão à esquerda indireta emerge da composição e não aparece procurando produções da forma A \to A\alpha. Detectá-la é barato: monte o grafo com aresta de A para B quando alguma produção de A começa por B ou por anuláveis seguidos de B, e procure ciclos. Detectar sem implementar a eliminação geral é defensável quando não há ciclo algum.
O segundo obstáculo é banal: duas produções da mesma variável que começam igual. A fatoração troca A \to \alpha\beta_1 \mid \alpha\beta_2 por A \to \alpha A', adiando a decisão até onde a informação aparece. Dois cuidados que a prova cobra: pegue o prefixo comum mais longo e fature depois de eliminar a recursão. Nenhuma das duas transformações é grátis: perde-se legibilidade, perde-se associatividade — a nova gramática agrupa à direita — e ganham-se produções vazias onde não havia nenhuma. Esse terceiro preço é o que a próxima seção tem de pagar.
O erro sistemático da eliminação. Esquecer a variável nova ao fim das produções não recursivas. O resultado compila, roda e reconhece expressões com um operador, falhando a partir do segundo — por isso todo teste precisa ter três operandos encadeados.
1.3 Primeiros, seguidores e o ponto fixo
Antes de tudo, a noção que quase todo erro daqui ignora: um símbolo é anulável quando deriva a cadeia vazia, uma sequência quando todos os seus símbolos o são, e nenhum terminal é anulável.
O conjunto \mathrm{PRIM}(X) reúne os terminais que podem iniciar alguma cadeia derivada de X, mais \varepsilon se X for anulável. Para A \to X_1 X_2 \cdots X_k, percorre-se o lado direito acrescentando os elementos não vazios de cada \mathrm{PRIM}(X_i) e avançando se e somente se o símbolo anterior for anulável. Sublinho a condição do avanço porque é o que separa o certo do errado, com sintomas opostos: quem percorre tudo sem checar anulabilidade obtém conjuntos grandes demais e inventa conflitos; quem para sempre no primeiro símbolo obtém conjuntos pequenos demais e deixa células vazias.
Quando uma alternativa é vazia, primeiros não bastam — se a variável pode sumir, o terminal que o analisador vê pertence ao que vem depois dela. O conjunto \mathrm{SEG}(A) reúne os terminais que podem aparecer imediatamente à direita de A em alguma forma sentencial, mais o marcador \$ quando A é o símbolo inicial. Duas regras o calculam: em A \to \alpha B \beta, os elementos não vazios de \mathrm{PRIM}(\beta) entram em \mathrm{SEG}(B); e quando B está no fim, ou o que sobra é anulável, \mathrm{SEG}(A) inteiro entra em \mathrm{SEG}(B).
| Variável | Anulável | Primeiros | Seguidores |
|---|---|---|---|
| E | não | (, \mathbf{id} | ), \$ |
| E' | sim | +, \varepsilon | ), \$ |
| T | não | (, \mathbf{id} | +, ), \$ |
| T' | sim | *, \varepsilon | +, ), \$ |
| F | não | (, \mathbf{id} | *, +, ), \$ |
flowchart TD
A["todos os conjuntos vazios"] --> B["marca de mudanca = falso"]
B --> C["percorre todas as producoes<br/>aplicando as regras"]
C --> D{"algum conjunto<br/>cresceu nesta passada?"}
D -->|"sim: marca ligada"| B
D -->|"nao"| E["menor ponto fixo alcancado"]
E --> F["anulaveis, primeiros<br/>e seguidores estaveis"]
As definições se referem a si mesmas, então o cálculo é por ponto fixo: começa tudo vazio, aplicam-se as regras a todas as produções e repete-se enquanto algo mudar — processo que termina porque os conjuntos só crescem e os terminais são finitos.
O esquecimento mais frequente, e o seu sintoma. Deixar o marcador de fim de entrada fora dos seguidores do símbolo inicial faz a produção vazia da variável mais externa não entrar na tabela, e o analisador rejeita o programa no último símbolo. Como todo teste com um trecho passa e só o arquivo completo falha, a culpa é atribuída a qualquer outra coisa antes.
1.4 A tabela e a condição LL(1)
A tabela sai de uma regra só, que vale memorizar em português: a produção A \to \alpha vai para a célula do terminal a quando a pode ser o primeiro símbolo do que \alpha produz, e para a célula de b quando \alpha pode não produzir nada e b pode vir logo depois de A. A primeira parte diz onde a produção começa; a segunda, onde ela desaparece. Célula vazia não é desperdício — é erro detectável com mensagem informativa, porque a linha inteira diz o que caberia ali.
flowchart TD
P["producao A -> alfa"] --> Q{"alfa pode comecar<br/>pelo terminal a?"}
Q -->|"sim"| R["a producao entra na celula<br/>da variavel A com o terminal a"]
P --> S{"alfa pode derivar<br/>a cadeia vazia?"}
S -->|"sim"| T["a producao entra na celula<br/>de cada seguidor de A"]
R --> U{"a celula ja tinha<br/>outra producao?"}
T --> U
U -->|"nao"| V["gramatica tratavel<br/>ate aqui"]
U -->|"sim"| W["conflito: a gramatica avisa<br/>que um simbolo nao basta"]
Uma gramática é LL(1) quando toda célula tem no máximo uma produção. Vale então o teorema que justifica o esforço: cadeia analisada em tempo O(|w|), e o primeiro erro reportado exatamente onde a cadeia deixa de ser prefixo de alguma sentença da linguagem — a propriedade do prefixo viável, que é o que faz a mensagem apontar o caractere esquecido.
Quando uma célula recebe duas produções, o instinto é culpar a ferramenta. A leitura correta é a inversa: a tabela está certa, e o que ela diz é que ali um símbolo de antecipação não basta — afirmação sobre a gramática, verificável. As causas são três: recursão à esquerda remanescente, falta de fatoração, ou, se nenhuma se aplica sobre gramática já preparada, ambiguidade real. O caso clássico é o condicional com parte alternativa opcional, em que a palavra que a introduz está nos primeiros de uma produção e nos seguidores da variável; resolve-se por convenção, associando ao condicional mais próximo e registrando a decisão por escrito. E há o limite duro: existem linguagens livres de contexto determinísticas sem gramática LL(k) para k algum.
1.5 As duas realizações e a árvore que sai
A primeira realização é tão direta que decepciona: uma função por variável, e o corpo de cada uma é a transcrição das produções. A segunda usa pilha explícita e um laço dirigido pela tabela, empilhando o lado direito em ordem inversa porque a pilha guarda o que ainda falta reconhecer, na ordem em que será reconhecido. A recursiva ganha em legibilidade e diagnóstico; a dirigida por tabela ganha em compacidade, e é por isso que os geradores produzem tabelas — gerar matriz é bem mais fácil que gerar código.
flowchart LR
subgraph REC["Descida recursiva"]
direction TB
A1["uma funcao por variavel"] --> A2["a pilha de chamadas<br/>e a pilha do automato"]
A2 --> A3["mensagem especifica<br/>dentro de cada funcao"]
end
subgraph TAB["Dirigido por tabela"]
direction TB
B1["um laco unico + pilha explicita"] --> B2["a tabela e o dado;<br/>o codigo nao muda"]
B2 --> B3["falha unica: celula vazia"]
end
REC -.->|"mesmas entradas aceitas"| TAB
Uma propriedade da versão recursiva merece destaque: a pilha de chamadas do programa é a pilha do autômato. O autômato do módulo anterior não sumiu — está materializado na execução, sem uma linha de código de pilha escrita.
A saída da fase é uma árvore, e não é a de derivação. A árvore sintática abstrata descarta delimitadores e separadores, cuja função já está na forma da árvore, palavras reservadas que só identificam a construção, e as variáveis auxiliares da preparação — deixá-las aparecer exporia uma decisão interna do analisador. Não existe árvore abstrata canônica: existe a que você projetou. Dois itens são obrigatórios em todo nó: a posição no texto-fonte, porque as fases seguintes vão reportar erros e a posição só existe naturalmente aqui, e o tipo do nó, numa forma sobre a qual se despache de modo barato.
E aqui pago a dívida da preparação. A eliminação da recursão à esquerda inverteu a associatividade, e a transcrição recursiva ingênua agrupa à direita. A correção é escrever a função como um laço com árvore acumulada, em que cada nova operação recebe como filho esquerdo tudo o que veio antes — o que a implementação de referência da Peneira faz nas condições compostas:
AstPtr AnalisadorSintatico::expressaoE() {
AstPtr esquerda = comparacao();
while (ehLexema("and")) {
const Position pos = atual_.posicao;
avancar();
AstPtr direita = comparacao();
AstPtr no = criarNo(TipoAst::E, pos);
no->filhos.push_back(std::move(esquerda));
no->filhos.push_back(std::move(direita));
esquerda = std::move(no);
}
return esquerda;
}flowchart TB
subgraph CON["Arvore de derivacao concreta"]
direction TB
C1["expressao"] --> C2["termo"]
C1 --> C3["auxiliar da soma"]
C3 --> C4["operador +"]
C3 --> C5["termo"]
C3 --> C6["auxiliar vazio"]
C2 --> C7["abre parenteses"]
C2 --> C8["identificador"]
C2 --> C9["fecha parenteses"]
end
subgraph ABS["Arvore sintatica abstrata"]
direction TB
D1["soma<br/>linha 3, coluna 12"] --> D2["identificador"]
D1 --> D3["identificador"]
end
CON -->|"saem delimitadores, palavras<br/>reservadas e auxiliares"| ABS
O defeito mais caro do módulo, porque não impede o programa de funcionar. Um analisador com associatividade errada aceita exatamente as mesmas entradas e passa em qualquer teste de aceitação e rejeição; a falha só aparece quando alguém avaliar a árvore, módulos adiante, e apenas para operadores não associativos. O teste que denuncia: três operandos, um operador não associativo, conferência do agrupamento.
1.6 Recuperação de erros
Um analisador que aborta no primeiro erro é fácil de escrever e desagradável de usar. E o critério de qualidade não é o que parece: mede-se pela correspondência entre mensagens e defeitos reais, não pelo número de mensagens. Um erro verdadeiro seguido de vinte inventados é pior do que reportar só o primeiro e parar. O teste honesto é um arquivo com número conhecido de defeitos em posições conhecidas.
stateDiagram-v2
[*] --> Analisando
Analisando --> Reportando: divergencia detectada
Reportando --> Recuperando: uma mensagem emitida
Recuperando --> Recuperando: descarta simbolo<br/>diagnosticos silenciados
Recuperando --> Analisando: simbolo de sincronizacao<br/>consumido com sucesso
Analisando --> [*]: entrada esgotada
note right of Recuperando
parada sem consumo exige
contador de progresso
end note
O modo pânico é a estratégia de melhor retorno: reporta-se e descartam-se símbolos até um ponto de retomada. Tudo depende dos símbolos de sincronização. Delimitadores de fim de construção são a escolha óbvia e insuficiente, porque o próximo ponto e vírgula pode estar dentro da construção seguinte, apagando trecho correto; as palavras que iniciam construção corrigem isso, desde que parem o descarte sem serem consumidas; e o conjunto de seguidores é a terceira fonte, ideia popularizada por Niklaus Wirth. Detalhe que o descuido apaga: o ponto e vírgula vai junto com o descarte, mas a chave de fechamento pertence ao bloco de fora e consumi-la gera erro derivado.
A segunda estratégia é corrigir localmente — inserir o terminal esperado ou remover o inesperado, reportando a correção, o que troca “erro de sintaxe” por “faltou um ponto e vírgula aqui”. Daí as duas salvaguardas obrigatórias: a garantia de progresso, um contador que força avanço quando a iteração não consumiu símbolo algum, e a supressão durante a recuperação, que silencia diagnósticos até um símbolo esperado ser consumido com sucesso. Sem a primeira, o compilador trava em silêncio — a falha mais difícil de atribuir.
1.7 O caso conduzido e o que o seu grupo entrega
Na Peneira, a preparação aplicou seis transformações: duas eliminações de recursão à esquerda, nas variáveis de expressão, e quatro fatorações. A gramática foi de vinte e duas para vinte e oito produções e ganhou cinco variáveis anuláveis onde não havia nenhuma. Sobre a preparada, a tabela tem quarenta e nove células e zero conflitos; sobre a original, trinta células e dezenove conflitos, cada um apontando uma das seis transformações. É a leitura do conflito como diagnóstico, em números.
A ordem das cinco etapas não é negociável: preparar a gramática, calcular os conjuntos, verificar a condição e ler os conflitos, implementar o analisador com a árvore, e fazê-lo recuperar-se de erros. Quem programa antes de preparar gasta uma sessão de tutoria depurando recursão infinita cuja causa estava na gramática desde o começo. A entrega do seu grupo é exatamente isso: gramática transformada com registro de cada transformação, conjuntos em tabela, analisador produzindo a árvore e recuperação demonstrada sobre programas malformados.
1.8 Síntese
Analisar sintaticamente é construir a árvore, não apenas dizer se a cadeia pertence à linguagem. A estratégia descendente corresponde à derivação mais à esquerda, e é a certa porque nela o prefixo de terminais só cresce. Para a decisão ser determinística a gramática precisa ser preparada, e as transformações cobram legibilidade, associatividade e produções vazias — este terceiro preço é o que torna obrigatório o tratamento das anuláveis, exatamente onde quase todo erro acontece. Volte à máquina que adivinha: ela não sumiu, foi domesticada. O que o autômato de pilha fazia por sorte virou consulta a uma tabela tirada da própria gramática, e a prova de que um símbolo de antecipação basta é a tabela sem conflito. Com isso o front-end está completo. Falta o salto para o significado, porque a árvore que você acabou de construir pode estar impecável e ainda assim usar um nome nunca declarado.