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
Bem-vindo ao módulo mais exigente do eixo sintático. Aqui o modelo abstrato do módulo anterior vira programa. Ao fim desta leitura você deve conseguir pegar uma gramática, dizer se ela serve ao método, consertá-la quando não servir e transcrevê-la em código que lê o texto uma única vez, sem voltar atrás.
1.1 O problema: a máquina que adivinha
O módulo anterior terminou com uma máquina que dá sorte. Não é força de expressão: o autômato de pilha correspondente às gramáticas livres de contexto é não determinístico, e não determinismo, na definição formal, significa que em cada configuração há várias transições possíveis e a máquina aceita a cadeia quando alguma sequência de escolhas dá certo. A definição não diz como escolher — afirma que existe caminho e passa a bola. Como objeto matemático é impecável; como especificação de programa é inútil, porque nenhum computador escolhe por sorte.
Este módulo é sobre eliminar a adivinhação. O alvo: transformar a gramática em um programa que, olhando um único símbolo da entrada por vez e sem jamais retroceder, decide qual produção aplicar — e monta, no caminho, a estrutura hierárquica do programa. Dali em diante o texto deixa de ser sequência de caracteres e passa a ser uma árvore.
E aviso onde está a dificuldade, porque quase todo mundo a procura no lugar errado. O algoritmo de análise em si é simples ao ponto de decepcionar; a dificuldade vem antes dele: nem toda gramática serve, e é preciso transformar uma que não serve em outra que serve sem alterar a linguagem descrita.
Este capítulo pressupõe três coisas dos anteriores, e vale nomeá-las para que você saiba a que voltar se alguma delas estiver frouxa.
Pressuponho a gramática livre de contexto como objeto formal — quádrupla, derivação, árvore de derivação, ambiguidade — e, em particular, a distinção entre derivação mais à esquerda e mais à direita, que aqui deixa de ser vocabulário e passa a ser o critério que organiza o método. Pressuponho o autômato de pilha como modelo abstrato correspondente, incluindo o traçado de configurações e o resultado que separa o determinístico do não determinístico. E pressuponho um analisador léxico funcionando, com interface sob demanda: o analisador sintático deste capítulo consome símbolos um a um, e é sobre essa interface que a antecipação de um símbolo se apoia.
O que não pressuponho é qualquer experiência com geradores automáticos de analisadores. Tudo o que este capítulo usa é construído aqui, à mão, e uma das razões para fazê-lo à mão é justamente entender o que esses geradores fazem por dentro — e o que os relatórios de conflito deles estão dizendo.
1.2 Construir a árvore, não apenas dizer “sim”
A formulação corrente — “verificar se o programa está sintaticamente correto” — é modesta demais. O enunciado honesto é: dada uma gramática livre de contexto G = (V, \Sigma, P, S) e uma cadeia w \in \Sigma^*, decidir se w \in L(G), exibir uma árvore de derivação quando a resposta for sim, e produzir um diagnóstico que localize o ponto exato da falha quando for não.
O peso das três partes é desigual. Decidir a pertinência é o que a teoria enfatiza e o que menos interessa a quem constrói compiladores; exibir a árvore é o que importa, porque é ela que alimenta as fases seguintes; e o diagnóstico, que a formulação teórica sequer menciona, ocupa boa parte do código real. Repare ainda que se pede uma árvore, não a melhor nem todas — o que só é aceitável porque supomos a gramática não ambígua.
Há também 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, a ordem de 10^{12} operações. Compiladores usam métodos lineares, e a linearidade é comprada restringindo a classe de gramáticas admissíveis.
A árvore tem raiz, o símbolo inicial, e fronteira, a cadeia de terminais — daí as duas famílias. A construção descendente parte da raiz e desce, expandindo variáveis; a ascendente parte das folhas e sobe, reduzindo trechos ao lado esquerdo das produções. Este módulo trata da primeira, o próximo da segunda. A ascendente reconhece uma classe estritamente maior de gramáticas, ao preço de um código que não se parece nada com a gramática; a descendente reconhece menos, e o seu analisador é tão parecido com a gramática que dá para ler um no outro.
Dentro da estratégia descendente sobra uma liberdade aparente: qual variável expandir? A resposta é sempre a mais à esquerda, e a razão não é de gosto. Numa derivação mais à esquerda, toda forma sentencial tem o formato x A \gamma, com x \in \Sigma^* já fixado — ou seja, o prefixo de terminais só cresce. É o que se precisa para confrontar a derivação com a entrada enquanto se avança: coincidindo, segue; divergindo, o erro tem posição conhecida. O nome consagrado da família registra o sentido da leitura, o tipo de derivação e o número de símbolos de antecipação; 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 escolher a produção certa de primeira? Responda antes de seguir: as duas próximas seções são a formalização dessa resposta.
1.3 Preparar a gramática
Uma gramática escrita para descrever bem uma linguagem tende a ser recursiva à esquerda nos operadores binários, e por um motivo excelente: é isso que dá associatividade à esquerda. A gramática canônica das expressões, E \to E + T \mid T, T \to T * F \mid F, F \to (E) \mid \mathbf{id}, é não ambígua e exibe a precedência da multiplicação na própria estrutura das árvores. É exemplar por todos os critérios — e é impossível de analisar por descida recursiva.
O argumento é curto. Para expandir E, o analisador escolheria E \to E + T e, para reconhecer o primeiro símbolo do lado direito, chamaria o procedimento de E, que sem ter consumido símbolo nenhum chamaria a si mesmo nas mesmas condições. Não é recursão sobre um problema menor: é recursão sobre o mesmo problema. E não é limitação da versão recursiva — a recursão à esquerda é fatal para qualquer realização do método, porque os terminais que podem iniciar E + T são exatamente os que podem iniciar T. Curiosamente, a recursão à direita é inofensiva: A \to \alpha A chama o procedimento de A depois de consumir \alpha, sobre entrada menor.
A transformação sai de um raciocínio, não de uma fórmula a decorar. Se as produções são A \to A\alpha_1 \mid \cdots \mid A\alpha_m \mid \beta_1 \mid \cdots \mid \beta_n, toda derivação precisa sair da recursão por algum \beta_j, que acaba no início, seguido dos \alpha_i — um \beta obrigatório seguido de uma sequência arbitrária de \alpha, o que pede uma 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
Aplicada às expressões, ela dá a gramática que uso no resto do módulo:
E \to T E' \qquad E' \to +\,T\,E' \mid \varepsilon \qquad T \to F T' \qquad T' \to *\,F\,T' \mid \varepsilon \qquad F \to (E) \mid \mathbf{id}
Um erro sistemático que vale antecipar. É fácil esquecer de acrescentar a variável nova ao fim das produções não recursivas. O resultado compila, roda e reconhece as expressões com um operador, falhando a partir do segundo — defeito que passa em metade dos testes que alguém escreveria espontaneamente. Por isso todo teste de expressão precisa ter no mínimo três operandos encadeados.
A recursão à esquerda indireta é mais difícil de ver porque emerge da composição. Em S \to A a \mid b com A \to S d \mid \varepsilon, temos A \Rightarrow Sd \Rightarrow Aad, e nenhum algoritmo que procure apenas produções da forma A \to A\alpha encontra o ciclo. Existe um algoritmo geral de eliminação, por ordenação das variáveis e substituição sucessiva, mas muitas gramáticas reais não têm recursão indireta nenhuma, e escrever o algoritmo geral para elas produz código morto. A alternativa disciplinada é a detecção, que é barata: monte o grafo cujos vértices são as variáveis, com aresta de A para B quando alguma produção de A começa por B ou por anuláveis seguidos de B; recursão indireta é um ciclo nesse grafo.
O segundo obstáculo não tem nada de patológico: 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' com A' \to \beta_1 \mid \beta_2, adiando a decisão até depois de \alpha, que é onde a informação distintiva aparece. Dois cuidados: procure o prefixo comum mais longo, sob pena de gerar uma cascata de auxiliares; e fature depois de eliminar a recursão, porque a eliminação pode dissolver prefixos que existiam antes.
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"]
Nenhuma das duas é grátis. Perde-se legibilidade: a gramática deixa de descrever a linguagem e passa a descrever o procedimento de análise, o que leva muitos projetos a manter duas, a de referência publicada e a preparada. Perde-se associatividade: a nova gramática agrupa à direita, e a - b - c vira a - (b - c) se você montar a árvore ingenuamente. E ganham-se produções vazias onde não havia nenhuma, porque toda variável auxiliar tem \varepsilon como saída. Guarde este terceiro item: a preparação cria o problema que a próxima seção tem de resolver.
1.4 Os dois conjuntos que orientam a decisão
Primeiro uma noção auxiliar cujo esquecimento causa a maior parte dos erros daqui. Um símbolo é anulável quando deriva a cadeia vazia; uma sequência é anulável quando todos os seus símbolos o são; nenhum terminal é anulável. Na gramática preparada das expressões, as anuláveis são exatamente E' e T'.
O conjunto \mathrm{PRIM}(X) reúne os terminais que podem iniciar alguma cadeia derivada de X, acrescido de \varepsilon quando X é anulável. É a informação que faltava ao analisador ingênuo: se só uma das produções de A pode começar pelo terminal que está na entrada, a escolha está feita. O cálculo tem três regras: um terminal é primeiro de si mesmo; uma produção vazia acrescenta \varepsilon; e, para A \to X_1 X_2 \cdots X_k, percorre-se o lado direito da esquerda para a direita acrescentando os elementos não vazios de cada \mathrm{PRIM}(X_i), avançando para o próximo símbolo se e somente se o anterior for anulável.
Sublinho a condição do avanço, porque é a linha que separa o cálculo certo do errado, e os dois erros têm sintomas opostos. Quem percorre o lado direito inteiro sem verificar anulabilidade obtém conjuntos grandes demais, e a tabela ganha conflitos inexistentes; quem para sempre no primeiro símbolo obtém conjuntos pequenos demais, e a tabela fica com células vazias. Os dois rejeitam programas válidos, mas o primeiro é bem mais difícil de diagnosticar, porque a rejeição acontece longe da causa.
Os primeiros bastam enquanto todas as alternativas produzem alguma coisa. Quando uma delas é vazia, o analisador precisa de outra informação: se a variável pode sumir, o terminal que ele 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 derivável do símbolo inicial, mais o marcador de fim de entrada \$ 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 vem depois é anulável, \mathrm{SEG}(A) inteiro entra em \mathrm{SEG}(B).
O esquecimento mais frequente do módulo, 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. Resultado: o analisador rejeita o programa exatamente no último símbolo. Como todo teste com um trecho passa e só o arquivo completo falha, o defeito costuma ser atribuído a qualquer outra coisa antes de ser encontrado.
| 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} | *, +, ), \$ |
Os dois conjuntos são definidos por regras que se referem a si mesmas, o que pede o cálculo por ponto fixo: inicializa-se tudo vazio, aplicam-se todas as regras a todas as produções e repete-se enquanto alguma coisa tiver mudado — processo que termina porque os conjuntos só crescem e os terminais são finitos.
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"]
1.5 A tabela e a condição LL(1)
Com os dois conjuntos, a tabela sai de uma regra só, e recomendo memorizar a leitura 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 vai 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.
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"]
| \mathbf{id} | + | * | ( | ) | \$ | |
|---|---|---|---|---|---|---|
| E | E \to TE' | E \to TE' | ||||
| E' | E' \to +TE' | E' \to \varepsilon | E' \to \varepsilon | |||
| T | T \to FT' | T \to FT' | ||||
| T' | T' \to \varepsilon | T' \to *FT' | T' \to \varepsilon | T' \to \varepsilon | ||
| F | F \to \mathbf{id} | F \to (E) |
As células vazias não são desperdício: cada uma é um erro detectável. Um analisador que chega em F com um + na entrada sabe, olhando a linha de F, que ali só cabem ( e \mathbf{id} — e pode dizer isso, em vez de apenas reclamar.
Uma gramática é LL(1) quando toda célula contém no máximo uma produção. Na formulação equivalente, por pares de produções da mesma variável, os primeiros das duas precisam ser disjuntos e, se uma delas for anulável, os primeiros da outra não podem tocar os seguidores da variável. E vale o teorema que justifica o esforço: se G é LL(1), toda cadeia w é analisada em tempo O(|w|) e o primeiro erro é reportado exatamente na posição em que a cadeia deixa de ser prefixo de alguma sentença da linguagem — propriedade do prefixo viável, que é o que faz a mensagem apontar o caractere que a pessoa esqueceu.
A mudança de atitude que vale mais que qualquer algoritmo daqui. 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 naquela situação um símbolo de antecipação não basta. É uma afirmação sobre a gramática, verdadeira e verificável, não sobre o algoritmo.
As causas de conflito formam um catálogo curto. Duas produções que começam pela própria variável do lado esquerdo indicam recursão à esquerda remanescente; prefixo de símbolos compartilhado indica falta de fatoração; e se nenhuma das duas se aplica sobre gramática já preparada, a causa provável é ambiguidade real, que nenhuma transformação mecânica resolve.
O exemplo canônico do terceiro caso é o condicional com parte alternativa opcional. Fatorado, ele fica com S' \to \mathbf{else}\;S \mid \varepsilon, e o terminal \mathbf{else} está ao mesmo tempo nos primeiros da primeira produção e nos seguidores de S', porque a construção pode aparecer aninhada. A fatoração não resolveu porque o problema não era prefixo comum: era ambiguidade. O que se faz é resolver o conflito por convenção, associando a parte alternativa ao condicional mais próximo — e registrando a decisão por escrito, em vez de deixá-la implícita na ordem em que o código testa alternativas.
Delimitando a classe: nenhuma gramática ambígua é LL(1), nenhuma com recursão à esquerda é, e nenhuma com duas produções da mesma variável começando pelo mesmo terminal é. Mais interessante ainda, existem linguagens livres de contexto determinísticas que não admitem gramática LL(k) para k algum — a união de a^n b^n com a^n c^n exigiria decidir, no primeiro passo, uma informação que só aparece depois de n símbolos. É o argumento honesto a favor dos métodos ascendentes.
1.6 As duas realizações do método
A primeira realização é tão direta que quem a vê desconfia que falta alguma coisa: escreve-se uma função para cada variável da gramática, e o corpo de cada função é a transcrição das produções daquela variável. Para cada terminal, verifica-se o símbolo atual e avança-se; para cada variável, chama-se a função correspondente; a produção vazia é não fazer nada e retornar.
A segunda usa uma pilha explícita e um laço único, dirigido pela tabela. Se o topo é terminal, compara-se com a entrada; se é variável, consulta-se a célula, desempilha-se a variável e empilham-se os símbolos do lado direito em ordem inversa — detalhe que confunde na primeira leitura e cuja razão é simples: a pilha guarda o que ainda falta reconhecer, na ordem em que será reconhecido, e o topo é o próximo.
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
Ganha em legibilidade por larga margem: ler o código é ler a gramática, e uma alteração na gramática vira alteração localizada numa função. Ganha também em qualidade de diagnóstico, porque cada ponto de falha está dentro de uma função com nome e contexto. Perde quando a modificação é sistemática — instrumentar todas as decisões exige tocar em todas as funções.
Ganha em compacidade: o laço é o mesmo para qualquer gramática, e o que muda é o conteúdo da tabela. Daí a consequência decisiva de que é muito mais fácil gerar uma tabela do que gerar código, razão pela qual quase todos os geradores automáticos produzem tabelas. Perde em transparência — o que se depura é uma matriz, e a falha é sempre a mesma, célula vazia.
Uma propriedade da versão recursiva merece destaque especial: a pilha de chamadas do programa é a pilha do autômato. Cada chamada empilha o corpo de uma produção, cada retorno desempilha um símbolo reconhecido. O autômato de pilha do módulo anterior não sumiu — está ali, materializado na estrutura de execução, sem uma linha de código de pilha escrita. Some isso à transparência e você tem um método de trabalho: escreva a gramática de um lado e o código do outro, produção a produção.
E quando a condição LL(1) falha por pouco? Fatorar resolve os conflitos por prefixo comum, que são a maioria; reescrever a linguagem, e não a gramática, costuma ser melhor do que parece; e há a antecipação local, em que uma função olha dois ou três símbolos à frente naquele ponto e só naquele ponto, legítima desde que documentada no código, com o motivo.
1.7 Recuperação de erros
Um analisador que aborta no primeiro erro é fácil de escrever e desagradável de usar. A alternativa é continuar depois do erro, e é aí que a dificuldade começa.
O critério, e ele não é o que parece. A qualidade de uma estratégia de recuperação não se mede pelo número de erros reportados, e sim pela correspondência entre os erros reportados e os defeitos reais da entrada. Uma mensagem correta vale mais que dez, e um erro real seguido de vinte erros inventados é pior do que reportar apenas o primeiro e parar.
A métrica errada é sedutora: contar mensagens é fácil, conferir se cada uma corresponde a um defeito é trabalhoso. Um analisador mal calibrado produz cascatas, e quem lê a saída aprende a ignorar tudo menos a primeira linha. O teste honesto é preparar um arquivo com um número conhecido de defeitos, em posições conhecidas, e conferir que há uma mensagem para cada um e no lugar de cada um.
A estratégia mais simples e de melhor retorno é o modo pânico: ao detectar o erro, reporta-se o diagnóstico e descartam-se símbolos até encontrar um que permita retomar. Tudo depende dos símbolos de sincronização, e há três fontes. Os delimitadores de fim de construção são a escolha óbvia e insuficiente: se o próximo ponto e vírgula está dentro da construção seguinte, o descarte apaga um trecho correto. As palavras que iniciam construção corrigem isso, com um detalhe decisivo — devem parar o descarte sem serem consumidas. E o próprio conjunto de seguidores é a terceira fonte: ao falhar dentro do procedimento de A, sincronizar até um terminal de \mathrm{SEG}(A) e retornar é bem fundamentado, porque é o que se veria se A tivesse sido reconhecida — ideia popularizada por Niklaus Wirth nos seus compiladores didáticos.
E há uma distinção que o descuido apaga: o ponto e vírgula encerra a construção em que o erro ocorreu e vai junto com o descarte, ao passo que a chave de fechamento pertence ao bloco de fora, e consumi-la gera erro derivado logo em seguida. Tratar os dois casos igualmente é uma das causas mais comuns de cascata.
A segunda estratégia é mais ambiciosa: corrigir localmente, inserindo o terminal esperado, removendo o inesperado ou substituindo um pelo outro, e reportando a correção como diagnóstico — a mensagem passa de “erro de sintaxe” para “faltou um ponto e vírgula aqui”. Em analisador recursivo isso sai quase de graça onde se espera um terminal específico: reporta-se o esperado pelo nome e finge-se que ele estava lá. Dois riscos: a correção pode estar errada, e pode gerar laço infinito se não consumir símbolo algum — sintoma que é o compilador travar sem mensagem nenhuma.
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
Daí as duas salvaguardas obrigatórias. A garantia de progresso: todo laço que chama a recuperação verifica se a iteração consumiu ao menos um símbolo e, se não consumiu, força um avanço — necessária justamente quando a recuperação melhora, porque as paradas sem consumo são a fonte natural do laço sem progresso. E a supressão durante a recuperação: enquanto o analisador se reorganiza, os erros que encontra são quase certamente consequência do primeiro, então um sinalizador silencia os diagnósticos até que um símbolo esperado seja consumido com sucesso.
Trate a recuperação como escopo mínimo, não como refinamento. É a parte que se deixa por último e que, deixada por último, não é feita. Adiá-la até o analisador estar “pronto” obriga a alterar todas as funções que já funcionavam, porque a decisão de como reportar e onde sincronizar atravessa o analisador inteiro. Decida a política antes de escrever a segunda função.
1.8 A árvore sintática abstrata
Reconhecer não basta: a saída da fase é uma árvore, e a árvore que interessa não é a de derivação. A árvore sintática abstrata tem nós que representam as construções da linguagem, sem os símbolos cuja única função é delimitar ou separar e sem as variáveis auxiliares introduzidas pelas transformações. Essa definição é deliberadamente menos rígida que as anteriores, e a flexibilidade é intencional: a árvore de derivação é determinada pela gramática, ao passo que a abstrata é projetada. Não existe árvore abstrata canônica — existe a que você decidiu construir.
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 que sai fora se agrupa em três categorias. Os delimitadores e separadores existiram para tornar a análise determinística, e a informação que carregavam já está na forma da árvore — o parêntese que agrupava virou aninhamento. As palavras reservadas que apenas identificam a construção ficam supérfluas assim que o nó tem tipo. E as variáveis auxiliares não correspondem a nada na linguagem: fazê-las aparecer exporia às fases seguintes uma decisão de implementação do analisador.
Sobre o conteúdo dos nós, dois itens eu trataria como obrigatórios. O primeiro é a posição no texto-fonte, em todo nó, sem exceção — guardá-la só onde parece necessário é erro, porque as fases seguintes precisarão reportar erros e a posição só existe naturalmente aqui. Um verificador de tipos que diga “operação inválida” sem dizer onde é praticamente inútil, e a diferença entre ele e um que aponta linha e coluna é um campo em cada nó. O segundo é o tipo do nó, numa forma sobre a qual as fases seguintes despachem de modo barato e exaustivo.
E aqui pago a dívida deixada na preparação da gramática. A eliminação da recursão à esquerda inverteu a associatividade, e a transcrição recursiva literal, que monta a árvore na volta da recursão, agrupa à direita. A correção é escrever a função como um laço com uma árvore acumulada: reconhece-se o primeiro operando e, enquanto o símbolo atual for o operador, consome-se o operador, reconhece-se o próximo operando e cria-se um nó cujo filho esquerdo é a árvore acumulada até ali. O agrupamento sai à esquerda porque cada nova operação envolve tudo o que veio antes.
Este é o defeito mais caro do módulo, porque não impede o programa de funcionar. Um analisador com a associatividade errada aceita exatamente as mesmas entradas e passa em qualquer teste de aceitação e rejeição. O erro só se manifesta quando alguém avaliar a árvore, dois ou três módulos adiante, e apenas para operadores não associativos, como a subtração e a divisão. O teste que denuncia é direto: três operandos, um operador não associativo, e conferência do agrupamento.
Falta a estrutura de dados, com duas soluções de custos opostos: a hierarquia de tipos, que impede estados inválidos pela própria estrutura ao custo de volume de código, e o nó uniforme com marcador de tipo, conciso e fácil de percorrer, que não impede um nó de carregar campos sem sentido — risco que um construtor único mantém sob controle. Não há resposta universal; o que não vale é decidir por hábito.
1.9 O caso conduzido
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 começa a programar antes de preparar a gramática gasta uma sessão depurando uma recursão infinita cuja causa estava escrita na gramática desde o início.
1.9.1 8.1 A gramática antes e depois da preparação
A gramática da linguagem Peneira, escrita no capítulo sobre gramáticas livres de contexto, tinha onze variáveis, vinte e um terminais e vinte e duas produções, e foi escrita deliberadamente sem nenhuma produção vazia — decisão que simplificou os algoritmos daquele capítulo e que este vai desfazer. Ela também é recursiva à esquerda nos dois operadores binários, exatamente pelo motivo geral da Seção 2.1: é isso que dá associatividade à esquerda às condições compostas.
A preparação começa pela detecção do que não precisa ser tratado. Antes de eliminar qualquer coisa, verifiquei a ausência de recursão à esquerda indireta, e o resultado foi o esperado: nenhum ciclo. Implementei a detecção e não a eliminação geral, pelo argumento da Seção 2.3 — escrever o algoritmo caro sem caso de uso produziria código que ninguém exercita. Verificar a ausência custa poucas linhas e protege contra a gramática mudar.
10_transformacao.h
#ifndef PENEIRA_10_TRANSFORMACAO_H
#define PENEIRA_10_TRANSFORMACAO_H
#include <string>
#include <vector>
#include "08_gramatica.h"
namespace peneira {
// Registro de uma transformação aplicada à gramática. Sem ele, a gramática
// transformada aparece do nada e não há como conferir que ela ainda descreve
// a mesma linguagem.
struct Transformacao {
std::string tipo;
std::string variavel;
std::string descricao;
};
struct ResultadoTransformacao {
Gramatica gramatica;
std::vector<Transformacao> registro;
};
// Elimina recursão à esquerda IMEDIATA. Para `A -> A a1 | ... | b1 | ...`,
// produz `A -> b1 A' | ...` e `A' -> a1 A' | ... | e`.
//
// A transformação preserva a linguagem e MUDA as árvores: o que era recursão
// à esquerda, e portanto associatividade à esquerda, vira recursão à direita.
// A associatividade terá de ser reconstruída na montagem da árvore sintática
// abstrata — dívida registrada no módulo 9 e paga no analisador.
//
// Introduz produções vazias numa gramática que não tinha nenhuma. É o preço, e
// é o que torna obrigatório o tratamento de anuláveis no cálculo dos conjuntos.
ResultadoTransformacao eliminarRecursaoAEsquerda(const Gramatica& g);
// Detecta recursão à esquerda INDIRETA — o ciclo `A` deriva `B` deriva `A`,
// sem consumir nada no caminho. A eliminação geral exige ordenar as variáveis
// e substituir umas nas outras; não a implementei porque a gramática da
// Peneira não tem nenhuma, e implementar um algoritmo sem caso de uso seria
// código morto. Esta função existe para que a ausência seja verificada em vez
// de suposta.
std::vector<std::string> ciclosDeRecursaoIndireta(const Gramatica& g);
// Fatoração à esquerda: quando duas ou mais produções da mesma variável
// começam igual, o analisador de um símbolo de antecipação não consegue
// escolher entre elas. A fatoração adia a escolha até depois do prefixo comum.
ResultadoTransformacao fatorarAEsquerda(const Gramatica& g);
// Aplica as duas transformações na ordem correta e devolve o registro
// acumulado. A ordem importa: fatorar depois de eliminar a recursão evita
// fatorar prefixos que a eliminação teria dissolvido.
ResultadoTransformacao prepararParaDescida(const Gramatica& g);
} // namespace peneira
#endif // PENEIRA_10_TRANSFORMACAO_H
Repare em três decisões registradas na própria interface. A eliminação trata apenas o caso imediato, e o cabeçalho declara isso em vez de deixar o leitor descobrir. Cada transformação produz um registro — tipo, variável e descrição —, sem o qual a gramática transformada apareceria do nada e não haveria como conferir que ela ainda descreve a mesma linguagem. E a função que aplica as duas transformações fixa a ordem entre elas, pelo motivo da Seção 2.4: fatorar depois de eliminar evita fatorar prefixos que a eliminação teria dissolvido.
Sobre a gramática da Peneira, a preparação aplicou seis transformações: duas eliminações de recursão à esquerda, nas duas variáveis de expressão, e quatro fatorações. A mais interessante é a da ação, cujas duas produções compartilham quatro símbolos de prefixo e divergem apenas no quinto, entre a palavra que introduz a condição e a seta que introduz o efeito. Um analisador de um símbolo não teria como escolher no início; a fatoração adia a escolha até depois do prefixo, que é onde a informação aparece. Note que foi o desenho da linguagem que tornou essa fatoração inevitável — a condição é opcional, e opcionalidade no meio de uma construção é sempre prefixo comum.
A gramática cresceu de vinte e duas para vinte e oito produções e ganhou cinco variáveis anuláveis onde não havia nenhuma. É o terceiro preço da Seção 2.5, cobrado na íntegra: o capítulo sobre gramáticas evitou o problema das produções vazias, e este o reintroduz sem alternativa.
1.9.2 8.2 Os conjuntos e a tabela
Com a gramática preparada, os dois conjuntos e a tabela.
10_conjuntos.h
#ifndef PENEIRA_10_CONJUNTOS_H
#define PENEIRA_10_CONJUNTOS_H
#include <map>
#include <set>
#include <string>
#include <vector>
#include "08_gramatica.h"
namespace peneira {
// Marcador do fim da entrada nos conjuntos de seguidores. Precisa ser um
// símbolo que não colida com terminal algum da gramática.
extern const char* const kFimDeEntrada;
// Marcador da cadeia vazia dentro dos conjuntos de primeiros.
extern const char* const kVazio;
using Conjuntos = std::map<std::string, std::set<std::string>>;
// Primeiros: os terminais que podem iniciar uma cadeia derivada do símbolo.
// Inclui o marcador de vazio quando o símbolo é anulável.
//
// O cálculo é por ponto fixo, e o ponto que mais custa é o das variáveis
// anuláveis: quando um símbolo do corpo pode desaparecer, os primeiros do
// próximo também entram. Esquecer isso produz conjuntos menores que o
// correto, e a tabela resultante rejeita programas válidos.
Conjuntos calcularPrimeiros(const Gramatica& g);
// Primeiros de uma sequência de símbolos, e não de um só. É o que a construção
// da tabela consome de fato.
std::set<std::string> primeirosDaSequencia(const std::vector<std::string>& seq,
const Conjuntos& primeiros,
const Gramatica& g);
// Seguidores: os terminais que podem aparecer logo depois do símbolo em alguma
// forma sentencial. O inicial sempre segue com o marcador de fim.
Conjuntos calcularSeguidores(const Gramatica& g, const Conjuntos& primeiros);
// Uma entrada da tabela de análise: qual produção usar quando a variável está
// no topo e o terminal está na entrada.
struct EntradaDaTabela {
std::string variavel;
std::string terminal;
std::vector<Producao> producoes; // mais de uma significa conflito
bool ehConflito() const { return producoes.size() > 1; }
};
struct TabelaLL1 {
std::vector<EntradaDaTabela> entradas;
std::vector<EntradaDaTabela> conflitos;
bool ehLL1() const { return conflitos.empty(); }
const std::vector<Producao>* consultar(const std::string& variavel,
const std::string& terminal) const;
};
// Constrói a tabela e separa os conflitos.
//
// Conflito não é falha do algoritmo: é informação sobre a gramática. Duas
// produções disputando a mesma célula significa que um símbolo de antecipação
// não basta para escolher entre elas, e a causa costuma ser recursão à
// esquerda remanescente, prefixo comum não fatorado ou ambiguidade real.
TabelaLL1 construirTabela(const Gramatica& g, const Conjuntos& primeiros,
const Conjuntos& seguidores);
std::string formatarConjuntos(const Gramatica& g, const Conjuntos& c,
const std::string& titulo);
} // namespace peneira
#endif // PENEIRA_10_CONJUNTOS_H
Três detalhes de interface que valem comentário, porque cada um evita um defeito discutido no capítulo. O marcador de fim de entrada é um símbolo explícito e nomeado, escolhido para não colidir com terminal algum da gramática — a alternativa, usar uma cadeia qualquer, funciona até o dia em que a linguagem ganhar um terminal parecido. Os primeiros de uma sequência têm função própria, separada dos primeiros de um símbolo, porque é ela que a construção da tabela consome de fato, e escrever a lógica duas vezes garante que as duas versões divirjam na primeira correção. E a entrada da tabela guarda um vetor de produções, não uma só: é isso que permite representar o conflito como dado em vez de como exceção, e é o que torna possível listar os conflitos e agrupá-los por causa.
Sobre a gramática preparada, a tabela tem quarenta e nove células e zero conflitos. A condição da Definição 4.2 é satisfeita, e um símbolo de antecipação basta em toda situação. É exatamente a adivinhação que o autômato de pilha do capítulo anterior fazia às cegas, agora decidida por consulta.
O número interessante, porém, é o outro. Construí a mesma tabela sobre a gramática original, sem preparo, e o resultado foram trinta células e dezenove conflitos. Dezenove lugares em que a descida recursiva ingênua não saberia o que fazer — e eles se agrupam limpamente por causa: os das duas variáveis de expressão vêm da recursão à esquerda; os das listas, da ação e da comparação vêm dos prefixos comuns. Cada conflito aponta uma das seis transformações que a preparação aplicou. É a Seção 4.3 em números: o conflito não é falha do algoritmo, é a gramática informando o que lhe falta.
1.9.3 8.3 A árvore que a fase produz
Antes do analisador, o que ele produz. Decidir a forma da árvore é decisão de projeto com consequência em três capítulos adiante, e a decidi antes de escrever a primeira função do analisador — na ordem inversa, o formato da árvore acaba sendo o subproduto acidental do código que a monta.
10_ast.h
#ifndef PENEIRA_10_AST_H
#define PENEIRA_10_AST_H
#include <cstdint>
#include <memory>
#include <string>
#include <vector>
#include "01_source.h"
namespace peneira {
// Árvore sintática ABSTRATA — não é a árvore de derivação.
//
// A diferença é o que fica de fora. A árvore de derivação do módulo 8 tem um
// nó para cada aplicação de produção, incluindo as variáveis auxiliares que a
// eliminação de recursão criou e os terminais de pontuação. A abstrata guarda
// só o que as fases seguintes precisam: nada de ponto e vírgula, nada de
// parênteses, nada de `expr'`.
//
// Decidir o que ela carrega é decisão de projeto com consequência nos módulos
// 12 a 14, que a percorrem. Guardei a posição em todo nó, porque a análise
// semântica precisa reportar erro em algum lugar, e o tipo de nó como
// enumerado, porque os percursos seguintes vão despachar sobre ele.
enum class TipoAst : std::uint8_t {
Programa,
DeclPadrao, // texto = nome do padrão, conteudo = a expressão regular
BlocoRegra,
Acao, // texto = padrão referenciado, conteudo = variável de ligação
Ou,
E,
Comparacao, // texto = operador
Referencia, // texto = nome
LiteralNumero,
LiteralTexto,
ValorDe, // texto = nome da variável de ligação
Emissao, // texto = rótulo emitido
};
const char* nomeDoTipoAst(TipoAst t) noexcept;
struct NoAst;
using AstPtr = std::unique_ptr<NoAst>;
// Nó com marcador de tipo, em vez de hierarquia de classes com despacho
// virtual. A troca é consciente: os percursos dos módulos 12 a 14 vão decidir
// sobre o tipo de qualquer forma, e o nó uniforme mantém curtos o código de
// impressão e o de travessia. O custo é que a estrutura não impede um nó de
// carregar filhos que não fazem sentido para o seu tipo — risco que o
// construtor único, usado por todo o analisador, mantém sob controle.
struct NoAst {
TipoAst tipo;
std::string texto;
std::string conteudo;
double numero = 0.0;
Position posicao{0, 0, 0};
std::vector<AstPtr> filhos;
};
AstPtr criarNo(TipoAst tipo, Position posicao, std::string texto = "",
std::string conteudo = "");
std::string desenharAst(const NoAst& raiz);
// Conta os nós, para comparar com a árvore de derivação concreta.
std::size_t contarNos(const NoAst& raiz);
} // namespace peneira
#endif // PENEIRA_10_AST_H
As duas obrigações da Seção 7.2 estão atendidas: posição em todo nó, sem exceção, e tipo como enumerado, sobre o qual os percursos seguintes despacham. As doze construções listadas são exatamente as da linguagem, e nenhuma delas corresponde a delimitador, a palavra reservada ou a variável auxiliar criada pela preparação — as auxiliares cumpriram o seu papel no reconhecimento e não atravessam a fronteira da fase.
Optei pelo nó uniforme com marcador, e não pela hierarquia de tipos, com a troca registrada no cabeçalho nos termos da Seção 7.4. Os percursos das fases seguintes vão decidir sobre o tipo de qualquer maneira, e o nó uniforme mantém curtos tanto o código de impressão quanto o de travessia. O custo é real e está declarado: a estrutura não impede um nó de carregar filhos que não fazem sentido para o seu tipo. O que mantém esse risco sob controle é o construtor único, usado por todo o analisador — a disciplina substitui a garantia que o sistema de tipos não está dando.
1.9.4 8.4 O analisador
10_parser.h
#ifndef PENEIRA_10_PARSER_H
#define PENEIRA_10_PARSER_H
#include <cstddef>
#include <string>
#include <vector>
#include "01_diagnostico.h"
#include "01_source.h"
#include "07_lexer.h"
#include "07_token.h"
#include "10_ast.h"
namespace peneira {
// Analisador sintático por descida recursiva.
//
// Uma função por variável da gramática preparada, na mesma ordem em que elas
// aparecem. É a realização concreta do autômato de pilha do módulo 9: a pilha
// de chamadas do programa É a pilha do autômato, e cada retorno de função é um
// símbolo saindo do topo.
//
// Consome o analisador léxico do módulo 7 pela interface sob demanda, com um
// símbolo de antecipação. Um só basta porque a gramática é LL(1) — verificado
// pela construção da tabela, não suposto.
class AnalisadorSintatico {
public:
AnalisadorSintatico(const SourceFile& fonte, DiagnosticBag& diagnosticos);
// Analisa o programa inteiro. Devolve a árvore mesmo quando houve erro:
// uma árvore parcial vale mais que nenhuma, porque as fases seguintes
// podem reportar problemas adicionais na parte que foi entendida.
AstPtr analisar();
std::size_t errosSintaticos() const noexcept;
private:
const SimboloLexico& atual() const noexcept;
bool ehCategoria(Categoria c) const noexcept;
bool ehLexema(const std::string& lexema) const noexcept;
void avancar();
// Consome o símbolo esperado ou reporta erro. Devolve o lexema consumido,
// ou vazio quando falhou.
std::string consumirLexema(const std::string& lexema,
const std::string& contexto);
std::string consumirCategoria(Categoria c, const std::string& nome,
const std::string& contexto);
// Modo pânico: descarta símbolos até encontrar um que permita retomar.
// Os pontos de sincronização são o ponto e vírgula e a chave de
// fechamento — os dois delimitadores que marcam fim de construção nesta
// linguagem.
void sincronizar();
void erro(const std::string& mensagem);
// Uma função por variável.
AstPtr programa();
AstPtr declaracao();
AstPtr declPadrao();
AstPtr blocoRegra();
AstPtr acao();
AstPtr expressao();
AstPtr expressaoE();
AstPtr comparacao();
AstPtr primaria();
const SourceFile& fonte_;
DiagnosticBag& diagnosticos_;
AnalisadorLexico lexer_;
SimboloLexico atual_;
std::size_t erros_ = 0;
bool emRecuperacao_ = false;
// Conta símbolos consumidos. Serve de garantia de progresso: os laços que
// chamam a recuperação comparam o contador antes e depois e, se nada foi
// consumido, forçam um avanço. Sem isso, uma sincronização que para sem
// consumir faz o laço girar para sempre — e foi o que aconteceu na
// primeira versão desta recuperação.
std::size_t consumidos_ = 0;
};
// Atalho para as demonstrações. Recebe o arquivo por referência, e não o texto:
// o analisador guarda uma referência ao fonte, então quem chama precisa manter
// o objeto vivo enquanto a análise durar.
AstPtr analisarArquivo(const SourceFile& arquivo, DiagnosticBag& diagnosticos,
std::size_t& erros);
} // namespace peneira
#endif // PENEIRA_10_PARSER_H
Uma função por variável da gramática preparada, na mesma ordem em que elas aparecem — a Seção 5.1 realizada literalmente. Repare que não há estrutura de pilha em lugar nenhum da classe: a pilha do autômato é a pilha de chamadas do programa, e cada retorno de função é um símbolo saindo do topo.
Três decisões de interface merecem leitura atenta. A primeira é que a análise devolve a árvore mesmo quando houve erro: uma árvore parcial vale mais que nenhuma, porque as fases seguintes podem reportar problemas adicionais na parte que foi entendida, e porque uma ferramenta que consome a árvore para outros fins continua tendo o que consumir. A segunda é o contador de símbolos consumidos, que existe pela razão exata da Seção 6.4 — é a garantia de progresso, e a sua ausência foi o que travou a primeira versão. A terceira é o sinalizador de recuperação, que implementa a supressão de cascata.
Sobre o programa de exemplo do livro, o resultado: duzentos e cinquenta e sete caracteres viram quarenta e seis símbolos, que viram treze nós, com zero erros léxicos e zero sintáticos. A diferença entre quarenta e seis e treze não é perda de informação: os trinta e três terminais que sumiram são pontuação, parênteses e palavras reservadas, que a árvore de derivação concreta guardaria e que nenhuma fase seguinte consulta.
A dívida da Seção 7.3 foi paga onde eu disse que seria. A função das condições compostas é um laço, e cada nova operação recebe como filho esquerdo a árvore acumulada até ali. Sobre três operadores encadeados, o nó mais externo tem outro nó do mesmo tipo como filho esquerdo — o agrupamento à esquerda que a gramática original garantia e que a eliminação da recursão havia destruído. Uma implementação recursiva ingênua produziria o agrupamento oposto: mesma linguagem, árvore diferente, significado diferente na fase seguinte.
Registro também o contraste que a Seção 7.3 antecipou: a função da comparação usa um teste condicional simples, e não um laço. A gramática não permite encadear comparações, e a diferença entre as duas construções de controle é exatamente o que faz o analisador recusar em vez de aceitar.
1.9.5 8.5 Recuperação, e três defeitos que só a execução revelou
A recuperação me custou duas iterações, e as duas ilustram pontos do capítulo.
A primeira versão sincronizava apenas em ponto e vírgula e chave de fechamento. Parecia razoável e produzia o defeito descrito na Seção 6.2: um sinal de igualdade faltando em uma linha fazia o descarte correr até o ponto e vírgula seguinte, que estava dentro do bloco da linha de baixo, apagando um bloco inteiro que estava correto. O segundo erro reportado apontava um lugar sem defeito.
A correção foi acrescentar as palavras que iniciam construção como pontos de parada, sem consumi-las. Foi essa mudança que criou o laço sem progresso, e que exigiu o contador de símbolos consumidos. E restou a terceira sutileza, também prevista na Seção 6.2: o ponto e vírgula encerra a construção em que o erro ocorreu e é consumido junto; a chave de fechamento pertence ao bloco de fora e precisa ser vista por quem chamou. Consumi-la produzia um erro derivado apontando a construção seguinte.
Com as três correções, sobre um arquivo com dois defeitos deliberados, o analisador produz duas mensagens, cada uma apontando exatamente o símbolo que falta, e recupera as quatro declarações do arquivo — inclusive a que vinha depois do bloco com problema. É o critério da Seção 6.1 satisfeito: uma mensagem por defeito, no lugar de cada defeito.
Aviso
Dois defeitos de programação que nenhuma revisão de código teria encontrado.
O primeiro foi um uso após movimento: eu testava o resultado de uma função depois de já o ter transferido para o vetor de filhos, e o ponteiro, já transferido, era nulo. Consequência: toda declaração bem-sucedida disparava um erro falso, e a recuperação subsequente engolia a declaração seguinte. O sintoma era desconcertante — o analisador reclamava que esperava uma declaração apontando justamente a palavra que inicia uma declaração. A correção é guardar o resultado do teste antes de transferir.
O segundo foi o laço sem progresso já mencionado. O sintoma não é mensagem errada: é o compilador travar em silêncio, que é a falha mais difícil de atribuir.
Os dois apareceram rodando, e nenhum deles é o tipo de defeito que se enxerga relendo o código. É a razão pela qual insisto que o analisador seja exercitado contra entradas com defeito deliberado desde a primeira versão, e não ao final.
Um último número, que é o teste de aceitação da fase inteira: a contagem de declarações reconhecidas precisa bater com o que está escrito no arquivo. Foi exatamente esse teste — dois padrões declarados, e a contagem dizendo um — que denunciou o defeito de uso após movimento. Medir uma grandeza por dois caminhos independentes e comparar os resultados é, de longe, a técnica de verificação que mais defeitos encontrou ao longo deste livro.
1.10 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 ela é a certa porque nela o prefixo de terminais só cresce. Para que a decisão seja determinística, a gramática precisa ser preparada, e as transformações cobram legibilidade, associatividade e a introdução de produções vazias — este terceiro preço é o que torna obrigatório o tratamento das anuláveis no cálculo dos dois conjuntos, exatamente onde quase todo erro acontece. A tabela sai de uma regra só, a condição LL(1) é que nenhuma célula receba duas produções, e o conflito é diagnóstico da gramática, não falha do algoritmo. Das duas realizações, a recursiva materializa o autômato de pilha na própria pilha de chamadas e espelha a gramática; a dirigida por tabela é o que os geradores produzem.
Volto à máquina que adivinha, da abertura. Ela não sumiu: foi domesticada. As escolhas que o autômato de pilha fazia por sorte agora são consultas a uma tabela cujos valores saíram da própria gramática, e a prova de que um símbolo de antecipação basta é a tabela sem conflito. Com isso, a metade de análise do front-end está completa: o texto entra como sequência de caracteres e sai como estrutura verificada quanto à forma. O que vem a seguir tem duas continuações — a outra família de analisadores, que reconhece mais gramáticas e paga em opacidade, e o salto para o significado, porque a árvore que você acabou de construir pode estar sintaticamente impecável e ainda assim usar um nome nunca declarado.