flowchart LR
subgraph DESC["Método descendente"]
direction TB
D1["A pilha guarda<br/>o que ainda falta reconhecer"]
D2["Começa com o<br/>símbolo inicial"]
D3["Cada passo expande<br/>uma previsão"]
D4["Termina vazia"]
D2 --> D1 --> D3 --> D4
end
subgraph ASC["Método ascendente"]
direction TB
A1["A pilha guarda<br/>o que já foi reconhecido"]
A2["Começa vazia"]
A3["Cada passo condensa<br/>uma evidência"]
A4["Termina com o<br/>símbolo inicial"]
A2 --> A1 --> A3 --> A4
end
DESC -.->|"mesma estrutura de dados,<br/>significado oposto"| ASC
1 Módulo 11: Análise Sintática Ascendente
Bem-vindo ao módulo mais lápis-e-papel do curso. Aqui não há arquivo para compilar: há uma tabela para construir à mão e uma decisão de engenharia para tomar com os dois lados na mesa. Ao fim desta leitura você deve conseguir abrir o relatório de conflitos de um gerador de analisadores e entender o que ele diz — de longe a habilidade deste assunto que mais gente usa na vida profissional e menos gente possui.
1.1 O problema: a gramática que tivemos de estragar
Vamos por partes, começando por uma confissão sobre o módulo anterior.
Para fazer o analisador descendente funcionar, nós mexemos na gramática. Eliminamos recursão à esquerda, porque uma produção que começa pela própria variável faz o analisador recursivo chamar a si mesmo sem consumir nada e afundar até estourar a pilha de chamadas. Fatoramos prefixos comuns, porque duas produções que começam iguais não dá para distinguir olhando um símbolo à frente. Cada transformação preservou a linguagem e estragou outra coisa: a gramática cresceu, ganhou variáveis auxiliares que não significam nada e passou a produzir árvores que já não refletem a estrutura que tínhamos em mente.
Eu aceitei aquilo como se fosse o preço da análise sintática. Não é: é o preço de um método de análise sintática. Existe uma segunda família para a qual a recursão à esquerda não é obstáculo — é a forma preferida. Escreva E -> E + T e o analisador processa sem artifício nenhum.
O nome da família vem da direção: o método anterior partia da raiz e descia até as folhas, adivinhando qual produção usar antes de ver a evidência; este parte das folhas e vai combinando pedaços já reconhecidos até sobrar só a raiz, e nunca adivinha, porque só decide depois de ver. Se a família ascendente é mais poderosa, por que aprendemos a outra primeiro? A resposta honesta é a lição mais transferível do módulo, e eu a construo ao longo do texto para enunciá-la no fim.
Antes de começar, quero ser explícito sobre o que este capítulo pressupõe e sobre o lugar que ele ocupa no percurso, porque o segundo ponto costuma gerar desconfiança legítima.
Pressuponho o vocabulário de gramáticas livres de contexto — produções, variáveis, terminais, derivação, árvore de derivação, ambiguidade —, os conjuntos de primeiros e de seguidores com o algoritmo de ponto fixo que os calcula, e a experiência de ter escrito à mão um analisador descendente recursivo para uma gramática pequena, com uma função por variável. Pressuponho também a noção de autômato de pilha, que é o modelo abstrato ao qual tudo o que vem a seguir corresponde. Se algum desses itens estiver frouxo, o ponto mais econômico de revisão é o cálculo dos seguidores: ele reaparece aqui com uma função diferente, e quem o calcula errado constrói uma tabela errada sem perceber.
E aqui está o ponto que precisa ser dito de frente. O compilador de referência que acompanha este percurso segue o caminho descendente, escrito à mão, sem gerador de analisadores — decisão de projeto tomada para que cada peça do sistema seja código legível e explicável, e não uma caixa cujo interior o leitor nunca abre. Isso significa que o método deste capítulo não vai virar código no compilador de referência. Estudá-lo é estudar a alternativa descartada.
Não é desperdício, e a razão é prática. A família ascendente é a que sustenta a maior parte dos compiladores de produção e é a que está por trás de praticamente todo gerador de analisadores que alguém vai encontrar na vida profissional. Quem nunca construiu uma dessas tabelas à mão lê um relatório de conflito como quem lê um horóscopo: percebe que algo está errado, não sabe o quê nem onde. Quem construiu uma, ainda que minúscula, reconhece no relatório os itens, os estados e a decisão que não pôde ser tomada. A diferença entre as duas situações é a diferença entre operar uma ferramenta e ser operado por ela.
Há ainda um segundo motivo, menos utilitário e mais formativo. Boa parte do trabalho do capítulo anterior consistiu em transformar a gramática para caber no método descendente: eliminar recursão à esquerda, fatorar prefixos comuns, tolerar variáveis anuláveis que não existiam na versão original. Neste capítulo você vai descobrir que a recursão à esquerda, que era fatal lá, é a forma preferida aqui. Nenhuma daquelas dificuldades era dificuldade do problema; todas eram dificuldade da abordagem escolhida. Saber distinguir uma coisa da outra é o que separa quem escolhe uma ferramenta de quem apenas usa a que aprendeu primeiro.
1.2 Deslocar, reduzir, e a pilha que virou do avesso
O método tem uma economia notável: duas operações, mais dois casos terminais. Um deslocamento transfere o próximo símbolo da entrada para o topo da pilha. Uma redução por uma produção A \to \beta remove do topo da pilha os símbolos que formam \beta e empilha A no lugar. O analisador aceita quando a entrada acabou e a pilha contém só o símbolo inicial, e rejeita quando nenhuma das duas se aplica. Repare: a redução exige que o topo da pilha coincida com o corpo da produção, mas não que essa coincidência seja o momento certo de reduzir — e é aí que mora o problema inteiro do módulo.
Agora o ponto em que eu perco mais gente. No método descendente dirigido por tabela, a pilha guardava o que ainda falta reconhecer: começava com o símbolo inicial e era, a todo instante, uma previsão do resto da entrada. Aqui ela guarda o que já foi reconhecido: começa vazia, cresce à medida que símbolos são consumidos e agrupados, e é um resumo do prefixo já processado. Mesma estrutura de dados, significado exatamente oposto.
Pare e faça isto agora. Pegue uma cadeia curta, trace o reconhecimento pelos dois métodos lado a lado na mesma folha e observe as duas pilhas evoluindo em espelho. Custa poucos minutos e imuniza você contra a confusão que estraga todos os traçados seguintes.
O trecho que uma redução consome tem nome próprio: alça. A alça de uma forma sentencial à direita é o par formado por uma produção A \to \beta e a posição de \beta correspondente ao último passo de uma derivação mais à direita — o que está à direita da alça é sempre só terminais. Traduzindo: reduzir a alça é desfazer o último passo de uma derivação mais à direita. Daí sai o resultado que organiza tudo: se o analisador reduz sempre a alça, a sequência de produções aplicadas, lida ao contrário, é uma derivação mais à direita da cadeia. Não é enfeite teórico, é o teste de verificação mais barato que existe — terminado um traçado à mão, leia as reduções de trás para a frente e veja se a derivação regenera a cadeia original.
O problema, então, é este e só este: decidir, em tempo constante, se o topo da pilha é uma alça e por qual produção reduzi-la.
Antes da maquinaria, o conceito que delimita o espaço do problema, e que eu considero a ideia mais elegante do assunto. Um prefixo viável é uma sequência de símbolos que pode legitimamente aparecer na pilha durante o reconhecimento de alguma cadeia da linguagem: enquanto o que está lá for prefixo viável, ainda há esperança. E aqui vem o teorema que sustenta a família inteira, publicado por Donald Knuth em 1965: para toda gramática livre de contexto, o conjunto dos prefixos viáveis é uma linguagem regular — e portanto reconhecível por um autômato finito.
Por que isso não é uma contradição. Reconhecer uma linguagem livre de contexto exige memória ilimitada, como demonstramos ao estudar os limites das linguagens regulares. A resolução está na divisão de trabalho: a memória ilimitada mora na pilha; o autômato não guarda o aninhamento, guarda apenas em que ponto de que produções estamos — informação finita, porque a gramática tem um número finito de produções de corpo finito.
1.3 Itens, fecho e desvio: montando o autômato
A gramática do módulo é a clássica das expressões com dois níveis de precedência, escrita com recursão à esquerda — a forma que o método anterior não tolerava. A única preparação exigida é acrescentar um símbolo inicial novo, para que exista um ponto de aceitação único:
(0) S' -> E
(1) E -> E + T
(2) E -> T
(3) T -> T * F
(4) T -> F
(5) F -> ( E )
(6) F -> idUma linha acrescentada, e seguimos.
O objeto central da construção é o item: uma produção com um ponto marcando uma posição no corpo. A leitura é direta — já empilhei a parte à esquerda do ponto, espero encontrar a parte à direita. O item T \to T \cdot {*} F diz que uma T já está na pilha e que, se vier * seguido de F, o corpo da produção (3) estará completo. Com o ponto no fim, o item é completo e sinaliza alça possível.
Um estado do autômato não é um item, é um conjunto de itens, porque o analisador, olhando a pilha, em geral não sabe em qual produção está: carrega todas as posições plausíveis até que a evidência elimine as inadequadas. É o mesmo raciocínio da determinização por subconjuntos, e não é coincidência — esta construção é, no fundo, uma determinização.
Duas operações constroem o autômato. O fecho acrescenta a um conjunto de itens as expectativas implicadas: se o ponto de algum item precede uma variável, entram os itens iniciais de todas as produções dela, e a regra se reaplica até estabilizar — esperar uma variável significa esperar tudo por onde ela possa começar. O desvio por um símbolo seleciona os itens cujo ponto o precede, avança o ponto e aplica o fecho. A coleção canônica sai do fecho do item inicial, calculando desvios até não surgirem estados novos.
Os dois erros que arruínam a construção à mão. O primeiro é calcular o fecho uma vez só: os itens que o próprio fecho acrescentou também podem exigir fecho. O sintoma é um estado sem transição por um símbolo que deveria tê-la. O segundo é não reconhecer estados repetidos — dois conjuntos de itens iguais são o mesmo estado, ainda que alcançados por caminhos diferentes. Quem não identifica o desvio de I_4 por T com I_2 constrói uma árvore infinita em vez de um autômato finito.
Para a nossa gramática, a coleção tem doze estados. Vale conferir a sua contra a minha.
| Estado | Itens | Desvios |
|---|---|---|
| 0 | S'→.E E→.E+T E→.T T→.T*F T→.F F→.(E) F→.id |
E→1, T→2, F→3, (→4, id→5 |
| 1 | S'→E. E→E.+T |
+→6 |
| 2 | E→T. T→T.*F |
*→7 |
| 3 | T→F. |
— |
| 4 | F→(.E) E→.E+T E→.T T→.T*F T→.F F→.(E) F→.id |
E→8, T→2, F→3, (→4, id→5 |
| 5 | F→id. |
— |
| 6 | E→E+.T T→.T*F T→.F F→.(E) F→.id |
T→9, F→3, (→4, id→5 |
| 7 | T→T*.F F→.(E) F→.id |
F→10, (→4, id→5 |
| 8 | F→(E.) E→E.+T |
)→11, +→6 |
| 9 | E→E+T. T→T.*F |
*→7 |
| 10 | T→T*F. |
— |
| 11 | F→(E). |
— |
flowchart LR
I0(("I0")) -->|"id"| I5(("I5"))
I0 -->|"("| I4(("I4"))
I0 -->|"E"| I1(("I1"))
I0 -->|"T"| I2(("I2"))
I0 -->|"F"| I3(("I3"))
I1 -->|"+"| I6(("I6"))
I2 -->|"*"| I7(("I7"))
I4 -->|"E"| I8(("I8"))
I4 -->|"T"| I2
I4 -->|"F"| I3
I4 -->|"id"| I5
I4 -->|"("| I4
I6 -->|"T"| I9(("I9"))
I6 -->|"F"| I3
I6 -->|"id"| I5
I6 -->|"("| I4
I7 -->|"F"| I10(("I10"))
I7 -->|"id"| I5
I7 -->|"("| I4
I8 -->|")"| I11(("I11"))
I8 -->|"+"| I6
I9 -->|"*"| I7
Dois testes baratos localizam a maioria dos enganos. Coerência local: em todo estado alcançado por desvio sobre um símbolo, todo item ou tem esse símbolo imediatamente à esquerda do ponto, ou é item inicial trazido pelo fecho. Completude do fecho: se algum ponto precede uma variável, os itens iniciais de todas as produções dela estão presentes.
E agora o ponto que separa o assunto em duas metades: os estados 1, 2 e 9 têm, cada um, um item completo mandando reduzir e um item pedindo deslocamento. O autômato sozinho não decide entre os dois, e é aqui que a família se divide em níveis.
1.4 Da tabela ao traçado
A tabela de análise é a coleção canônica em forma consultável em tempo constante, com duas metades. A de desvio, indexada por estado e variável, sai direto do autômato. A de ação, indexada por estado e terminal, é onde mora a dificuldade: a pergunta difícil é em quais colunas registrar a redução por um item completo. Por ora adoto a resposta mais econômica — registrá-la nas colunas dos terminais que podem seguir a variável reduzida. Com \mathrm{SEG}(E) = \{+, ), \$\} e \mathrm{SEG}(T) = \mathrm{SEG}(F) = \{+, *, ), \$\}, a tabela sai assim, com d para deslocamento e r para redução:
| Estado | id |
+ |
* |
( |
) |
$ |
E |
T |
F |
|---|---|---|---|---|---|---|---|---|---|
| 0 | d5 | d4 | 1 | 2 | 3 | ||||
| 1 | d6 | aceita | |||||||
| 2 | r2 | d7 | r2 | r2 | |||||
| 3 | r4 | r4 | r4 | r4 | |||||
| 4 | d5 | d4 | 8 | 2 | 3 | ||||
| 5 | r6 | r6 | r6 | r6 | |||||
| 6 | d5 | d4 | 9 | 3 | |||||
| 7 | d5 | d4 | 10 | ||||||
| 8 | d6 | d11 | |||||||
| 9 | r1 | d7 | r1 | r1 | |||||
| 10 | r3 | r3 | r3 | r3 | |||||
| 11 | r5 | r5 | r5 | r5 |
Olhe a linha 2, porque ela contém a decisão inteira. A redução por (2) aparece em +, ) e $, os seguidores de E; na coluna * aparece deslocamento, porque * não segue E. Com * à frente, não se reduz T a E — exatamente do que precisávamos. Repare no efeito colateral: se as linhas 2 e 9 trouxessem redução em *, a multiplicação deixaria de agrupar mais forte. No método ascendente, precedência é propriedade da tabela.
O analisador propriamente dito é um laço curto e independente da gramática. A pilha guarda estados intercalados com símbolos e começa contendo só o estado zero.
flowchart TD
INI["Pilha com o estado 0<br/>entrada com marcador de fim"] --> CONS{"Consulta a célula de ação<br/>do estado do topo com o<br/>símbolo de antecipação"}
CONS -->|"deslocar para t"| DESL["Empilha o símbolo e o estado t<br/>e avança na entrada"]
CONS -->|"reduzir por A → beta"| RED["Desempilha o dobro do<br/>comprimento do corpo<br/>empilha A e o desvio<br/>sem avançar na entrada"]
CONS -->|"aceitar"| OK["Reconhecimento concluído"]
CONS -->|"célula vazia"| ERR["Erro de sintaxe no ponto<br/>mais cedo possível"]
DESL --> CONS
RED --> CONS
Dois detalhes são fonte recorrente de engano. A redução não consome entrada: o símbolo de antecipação que motivou a decisão continua lá e será reexaminado. E o estado consultado para o desvio é o que ficou exposto depois do desempilhamento, porque é o estado a partir do qual a variável recém-formada começou a ser construída.
Tracei id * id + id, e o momento decisivo é este: quando a pilha contém apenas T e a antecipação é *, o item completo E \to T \cdot está disponível e o analisador não reduz, porque a tabela manda deslocar; só com + à frente a redução por (2) acontece. As reduções, na ordem, foram (6), (4), (6), (3), (2), (6), (4), (1); lidas ao contrário regeneram a cadeia, e é assim que eu sei que o traçado está certo.
Como cada operação custa uma consulta constante, o analisador processa a entrada em tempo linear e sem voltar atrás — a mesma garantia do método anterior. O ganho da família ascendente não está em velocidade; está em quais gramáticas ela aceita.
E as células em branco não são desperdício: cada uma é um erro detectável, e o analisador nunca desloca um símbolo que torne inviável o conteúdo da pilha, anunciando o erro no primeiro token que não admite continuação válida. Nenhum método detecta mais cedo. Só não confunda detectar cedo com explicar bem: ali o estado representa várias produções simultaneamente, e a mensagem que a tabela sustenta sozinha é uma lista de terminais aceitáveis — verdadeira, e de utilidade limitada.
1.5 A escala dos quatro métodos
O que separa os métodos da família é uma pergunta só: o que fazer num estado que tem item completo e item de deslocamento ao mesmo tempo. Cada nível é uma resposta diferente, e a progressão é motivada — cada degrau existe porque o anterior falhou num caso concreto.
flowchart LR
N0["Sem antecipação<br/>reduz sempre que houver<br/>item completo"]
N1["Por seguidores globais<br/>reduz nas colunas<br/>dos seguidores"]
N2["Com fusão de núcleos<br/>reduz nas antecipações<br/>locais fundidas"]
N3["Canônico<br/>reduz nas antecipações<br/>locais exatas"]
N0 -->|"falha nos estados com<br/>item completo e deslocamento"| N1
N1 -->|"falha quando o seguidor<br/>global é generoso demais"| N2
N2 -->|"pode criar conflito<br/>de redução-redução"| N3
N0 -.->|"os três primeiros níveis<br/>compartilham os mesmos estados"| N2
O nível mais fraco, o LR(0), decide sem olhar a entrada: se há item completo, reduz. Na nossa gramática ele quebra nos estados 1, 2 e 9. Praticamente nenhuma gramática de linguagem de programação o satisfaz, e a nossa, minúscula, já não satisfaz. O valor dele é conceitual: deixa visível o que falta ao autômato de itens.
O primeiro refinamento, o SLR(1), é o mais barato possível: olhe um símbolo à frente e só reduza por A \to \beta se esse símbolo puder seguir A. É o método da tabela acima, e os três conflitos somem. Ele reusa os estados anteriores, e os conjuntos de seguidores de que precisa já tinham sido calculados para o método descendente. Foi Frank DeRemer, na tese de doutorado de 1969 no MIT, quem sistematizou essa simplificação e a seguinte, e foram elas que tiraram a família do papel: as tabelas de Knuth eram grandes demais para as máquinas da época, e as simplificadas cabiam.
A limitação é que a aproximação é generosa demais: pergunta se o símbolo pode seguir A em algum lugar da gramática, quando o correto seria perguntar se pode segui-la naquele estado. O contraexemplo clássico é uma gramática mínima de atribuição com indireção, em que L designa o lado esquerdo de uma atribuição, R o lado direito, e uma produção diz que todo L serve de R. No estado alcançado pelo desvio por L há um item pedindo deslocamento de = e um item completo mandando reduzir L a R; como = está globalmente nos seguidores de R, as duas ações caem na mesma célula. O conflito é espúrio: ali reduzir nunca é correto, porque não existe forma sentencial começando com R =.
A correção, que é o LR(1) canônico de Knuth, é óbvia e cara: carregue dentro de cada item o conjunto de símbolos que podem segui-lo naquele contexto. Um item com antecipação é o par formado por um item e um terminal, e a segunda componente só tem efeito quando o item é completo, autorizando a redução apenas diante daquele símbolo. No exemplo acima o conflito some, porque o item completo entra com antecipação de fim de entrada e não com =. O preço é o tamanho, e é por isso que o método foi considerado impraticável por quase uma década.
A saída elegante é o LALR(1), segundo trabalho de DeRemer. O núcleo de um estado é o conjunto de itens sem as antecipações; estados distintos da coleção canônica frequentemente têm o mesmo núcleo, e a ideia é fundi-los, unindo as antecipações item a item. O resultado tem o número de estados do nível mais fraco com quase todo o poder do caro, e é o que os geradores usam.
O preço da fusão, delimitado com precisão
Fundir estados de mesmo núcleo nunca introduz conflito de deslocamento-redução que não existisse antes: os itens de deslocamento pertencem ao núcleo, idêntico em todos os estados fundidos, e a antecipação do item completo veio de um estado onde já coexistia com aquele deslocamento. Mas a fusão pode introduzir conflito de redução-redução, quando dois estados de mesmo núcleo têm antecipações disjuntas e trocadas entre si. Ainda assim o analisador fundido não aceita cadeias fora da linguagem: apenas adia a detecção do erro. A fusão degrada o diagnóstico, não a correção.
As letras desses nomes dizem o que o método faz: leitura da entrada da esquerda para a direita, produzindo uma derivação mais à direita, com o número de símbolos de antecipação entre parênteses.
| Método | Estados | Critério de redução | Poder relativo |
|---|---|---|---|
| LR(0) | núcleos | sempre que houver item completo | o mais fraco; quase nenhuma gramática real |
| SLR(1) | núcleos | nas colunas dos seguidores globais | resolve a maioria dos casos simples |
| LALR(1) | núcleos | nas antecipações locais fundidas | o padrão dos geradores |
| LR(1) canônico | muito mais | nas antecipações locais exatas | o mais forte com um símbolo |
Duas consequências teóricas fecham a seção, ambas de Knuth. Aumentar a antecipação além de um símbolo não amplia a classe de linguagens alcançável. E a família com um símbolo caracteriza exatamente as linguagens livres de contexto determinísticas, as reconhecidas por autômato de pilha determinístico: o método é a realização algorítmica daquele modelo. Quanto às duas famílias, toda gramática tratável pelo descendente é tratável pelo ascendente canônico, e a recíproca é falsa, com a recursão à esquerda como contraexemplo.
1.6 Conflitos: ler, classificar, resolver
Um conflito é uma célula à qual a construção tenta atribuir dois valores. Há dois tipos, e a distinção é o melhor instrumento de diagnóstico que temos. Deslocamento-redução: um estado tem item completo cuja antecipação inclui um terminal e, ao mesmo tempo, um item que pede deslocamento desse terminal. Redução-redução: dois itens completos com antecipações que se intersectam.
A experiência associa a cada tipo uma causa provável — heurística, não lei. Deslocamento-redução costuma ser questão de poder ou de precedência. Redução-redução costuma ser questão de projeto da gramática: quase sempre indica duas categorias sintáticas indistinguíveis pela forma, cuja diferença real é semântica. Se a gramática declara duas variáveis distintas derivando o mesmo identificador, nenhum nível resolve, porque a informação necessária não está na sintaxe; o certo é fundir as produções e distinguir os usos depois, na tabela de símbolos.
E há uma distinção de natureza que, ignorada, custa horas. Quando a gramática não é ambígua, o problema é de informação, e um método mais fino resolve. Quando ela é ambígua, o problema é de resposta: existem genuinamente duas árvores, e nenhuma antecipação escolhe entre elas — um analisador determinístico produz uma única derivação mais à direita, e a gramática ambígua tem duas.
flowchart TD
C["O gerador acusou um conflito"] --> T{"Que tipo?"}
T -->|"deslocamento-redução"| A{"A gramática admite<br/>duas árvores para<br/>alguma cadeia curta?"}
T -->|"redução-redução"| B["Suspeite primeiro do projeto<br/>da gramática: duas categorias<br/>indistinguíveis pela forma"]
A -->|"não consegui construir"| P["Falta de informação:<br/>subir um nível na escala<br/>costuma resolver"]
A -->|"consegui"| M["Ambiguidade genuína:<br/>nível nenhum resolve"]
M --> M1["Reescrever a gramática<br/>desambiguando"]
M --> M2["Declarar precedência<br/>e associatividade"]
B --> B1["Fundir as produções e<br/>distinguir os usos na<br/>fase seguinte"]
P --> V{"A contagem de conflitos<br/>caiu no relatório?"}
M1 --> V
M2 --> V
B1 --> V
V -->|"sim"| OK["Conflito resolvido"]
V -->|"não"| NAO["A alteração apenas<br/>mudou o problema de lugar"]
O teste prático para separar os dois casos: tente construir uma cadeia curta com duas árvores. Conseguiu, é ambiguidade; não conseguiu, é aproximação grosseira, e subir de nível resolve.
O caso mais comum de ambiguidade genuína é o dos operadores escritos em um nível só, como E -> E + E | E * E | ( E ) | id. Há duas saídas. A primeira é reescrever desambiguando, que é o que a gramática de dois níveis faz: ao introduzir T e F, torna estruturalmente impossível agrupar a soma antes do produto. A segunda é manter a gramática ambígua e declarar precedência e associatividade, deixando o gerador resolver as células — convenção estabelecida pelo gerador que Stephen Johnson escreveu nos laboratórios Bell em meados dos anos 1970 e distribuiu com o Unix, em que os operadores são declarados em ordem crescente de precedência, com a associatividade de cada um; a não associatividade produz erro, e é assim que se recusa a < b < c.
Declarar precedência não é atalho para entender o conflito. É a mesma decisão, tomada em outro lugar. Quem declara sem examinar o estado conflituoso está resolvendo por sorte, e o sintoma clássico é o analisador que passa a compilar sem aviso e aceita programas cuja árvore não corresponde ao que quem os escreveu pretendia. O defeito aparece muitas fases depois, como resultado errado em tempo de execução.
O conflito mais famoso da literatura é o do condicional com alternativa opcional: com dois condicionais aninhados e uma única alternativa, ela pode pertencer ao interno ou ao externo. A convenção universal das linguagens é associá-la ao mais próximo, o que corresponde a deslocar — e a resolução padrão dos geradores, diante de um conflito de deslocamento-redução não declarado, é justamente preferir o deslocamento. Daí o conflito mais conhecido do assunto ser um que quase todo mundo resolve corretamente sem perceber, ignorando o aviso. Não recomendo o hábito: o aviso ignorado por sorte treina o hábito de ignorar avisos, e o próximo pode não ser sorte.
Chegamos, enfim, à habilidade que este módulo existe para formar. Um gerador, ao encontrar conflitos, resolve por regras padrão — deslocamento vence redução, e entre duas reduções vence a produção escrita primeiro — e avisa. O aviso é uma linha de resumo, e é onde a maioria para de ler. O que interessa está no relatório detalhado, que lista cada estado com seus itens e, nos conflituosos, a ação escolhida e a descartada: é o objeto que você construiu à mão, impresso por um programa.
O terceiro passo é o que quase ninguém faz. Localize o estado citado no aviso e leia seus itens; identifique o item completo e o que pede deslocamento, anotando o terminal em disputa; e então reconstrua um programa de exemplo que leve o analisador àquele estado, lendo os símbolos à esquerda dos pontos dos itens do núcleo. É ele que transforma uma lista de itens em uma construção concreta da linguagem, sobre a qual dá para decidir. Critério de verificação: um conflito genuinamente resolvido some do relatório.
1.7 As duas famílias, critério a critério
Com tudo construído, posso montar a comparação sem declarar vencedor antes do fim.
| Critério | Descendente recursivo | Ascendente com gerador |
|---|---|---|
| Poder | menor; exige eliminar recursão à esquerda e fatorar | maior; nenhuma transformação da gramática |
| Legibilidade | a estrutura do código é a da gramática | laço genérico mais matriz de inteiros |
| Diagnóstico | mensagem sai do nome da função, de graça | detecção ótima, explicação pobre |
| Manutenção | verificação por disciplina humana | verificação automática a cada alteração |
O argumento mais forte do lado ascendente vai além da economia de trabalho: uma gramática que não precisa ser transformada pode ser escrita na forma que expressa a semântica pretendida. No caminho descendente, a gramática implementada é uma versão contorcida da que se quis escrever, e a documentação costuma apresentar a original — discrepância permanente entre o documentado e o implementado.
Em legibilidade e diagnóstico a direção se inverte com folga. O analisador recursivo tem uma função por variável, e cada uma sabe o que está tentando reconhecer, de modo que a mensagem sai na forma “esperava tal coisa ao analisar tal construção”. No gerado, o ponto de parada cai dentro do laço genérico, e mensagens boas custam trabalho manual sobre os estados de erro, refeito sempre que a gramática muda.
Em manutenção o quadro é misto, e é a resposta menos óbvia. No caminho descendente, acrescentar uma construção exige verificar à mão que a condição de decisão continua satisfeita — o tipo de verificação que se pula quando o prazo aperta. No ascendente, acrescenta-se a produção e o gerador diz se quebrou: rede de segurança real, sobretudo em projetos com várias pessoas mexendo na gramática ao longo de anos. Em contrapartida, entender o que quebrou exige a habilidade da seção anterior. A rede avisa cedo e explica mal, que é o perfil da família inteira.
flowchart TD
Q{"O que estou construindo?"}
Q -->|"aprender a análise sintática<br/>construindo-a"| D["Descendente recursivo à mão"]
Q -->|"compilador de produção com<br/>gramática que vai evoluir"| A["Ascendente com gerador"]
D --> D1["Ganha: código legível<br/>correspondência direta com a gramática<br/>mensagens de erro naturais"]
D --> D2["Paga: preparar a gramática<br/>verificar à mão a cada alteração"]
A --> A1["Ganha: nenhuma transformação<br/>verificação automática do gerador<br/>gramática que expressa a semântica"]
A --> A2["Paga: mensagens de erro trabalhadas à mão<br/>depuração via relatório de estados"]
1.8 Síntese
A análise ascendente constrói a árvore das folhas para a raiz com duas operações apenas, e a pilha guarda o que já foi reconhecido — inversão exata em relação ao método anterior, e fonte de metade das confusões de quem estuda o assunto. A sequência de reduções lida ao contrário é uma derivação mais à direita, e essa correspondência é o teste mais barato de qualquer traçado feito à mão. O problema central é localizar a alça, e a resposta veio de um resultado surpreendente: o conjunto dos prefixos viáveis é regular, logo reconhecível por um autômato finito construído com itens, fecho e desvio. Sozinho, ele não decide entre deslocar e reduzir — daí a escala de quatro níveis, cada um resolvendo o conflito concreto que derrubou o anterior, com a fusão de núcleos como ponto de equilíbrio adotado pelos geradores. E sobre conflitos, a distinção que importa não é entre os dois tipos, e sim entre as duas causas: falta de informação sobe de nível, ambiguidade não sobe nível nenhum.
Volto, então, à pergunta da abertura. Se o objetivo é entender a análise sintática construindo-a, o caminho descendente recursivo é superior — não por ser mais fácil, mas porque o código é legível, as mensagens saem boas de graça e nada é delegado a uma ferramenta cujo interior permanece fechado. Se o objetivo é um compilador de produção com uma gramática que vai evoluir, o ascendente com gerador é superior, pela ausência de transformações e pela verificação automática a cada alteração. O que não muda entre os dois cenários é a fronteira do que é humano: as decisões de precedência continuam sendo decisões de projeto de linguagem, e o relatório de conflitos continua exigindo alguém capaz de ler itens e estados. A ferramenta automatiza a construção da tabela, não a compreensão de por que ela não pôde ser construída.
E fica a lição mais transferível do percurso. Passamos um módulo inteiro eliminando recursão à esquerda como se ela fosse defeito da gramática, e este descobrindo que ela era a forma preferida de outro método. Nenhuma das dificuldades que enfrentamos era dificuldade do problema; todas eram dificuldade da abordagem escolhida. Distinguir uma coisa da outra é o hábito mental que separa quem escolhe uma técnica de quem apenas aplica a primeira que aprendeu.