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 — Resumo
Esta é a versão de revisão. Recapitulo aqui, em ritmo de véspera, o módulo mais lápis-e-papel do semestre; nenhuma construção aparece por inteiro, e para isso existem a versão completa do material deste módulo e o livro. Use este texto para conferir se você consegue montar a tabela e ler um conflito — o critério de sucesso do módulo.
No módulo anterior nós estragamos a gramática de propósito: eliminamos recursão à esquerda, fatoramos prefixos comuns, criamos variáveis auxiliares que não significam nada. Escreva agora E -> E + T e mostre a um analisador da família deste módulo: ele processa sem artifício nenhum. O que lá era fatal, aqui é a forma preferida. Guarde esse desconforto — é ele que a última linha da síntese vai cobrar de você.
1.1 Deslocar, reduzir e a pilha virada do avesso
A economia do método impressiona: duas operações. Um deslocamento transfere o próximo símbolo da entrada para o topo da pilha. Uma redução por A \to \beta remove do topo os símbolos que formam \beta e empilha A no lugar. Aceita-se quando a entrada acabou e sobrou só o símbolo inicial. Repare no detalhe que carrega o módulo inteiro: a redução exige que o topo coincida com o corpo de uma produção, mas não garante que aquele seja o momento certo de reduzir.
Aqui é onde eu perco mais gente, e eu mesmo demorei a arrumar isso na cabeça. No método descendente dirigido por tabela, a pilha guardava o que ainda falta reconhecer. Neste, ela guarda o que já foi reconhecido: começa vazia e é um resumo do prefixo processado. Mesma estrutura, significado oposto.
O trecho que uma redução consome tem nome: alça — o par formado por uma produção e a posição do corpo correspondente ao último passo de uma derivação mais à direita, com só terminais à sua direita. Traduzindo: reduzir a alça desfaz o último passo daquela derivação. Daí sai a consequência mais útil para quem faz traçado à mão: a sequência de reduções, lida ao contrário, é uma derivação mais à direita da cadeia. Terminou um traçado? Leia as reduções de trás para a frente e veja se a cadeia se regenera. É o teste de verificação mais barato do assunto.
O problema, então, é um só: decidir em tempo constante se o topo da pilha é uma alça e por qual produção reduzi-la. Antes da maquinaria, a ideia que eu considero a mais elegante do módulo. Um prefixo viável é uma sequência de símbolos que pode legitimamente estar na pilha durante o reconhecimento de alguma cadeia da linguagem. Knuth demonstrou, em 1965, que para toda gramática livre de contexto o conjunto dos prefixos viáveis é uma linguagem regular — logo, reconhecível por autômato finito.
Por que isso não contradiz os limites das linguagens regulares. A memória ilimitada continua sendo exigida, e mora na pilha. O autômato não guarda o aninhamento: guarda em que ponto de que produções estamos — informação finita.
1.2 Itens, fecho e desvio: montando o autômato
A gramática de referência é a clássica das expressões com dois níveis de precedência, escrita com recursão à esquerda, mais uma linha nova: o símbolo inicial aumentado S' -> E, para que exista um ponto de aceitação único.
O objeto central é o item: uma produção com um ponto marcando posição no corpo. Leia sempre assim — já empilhei o que está à esquerda do ponto, espero encontrar o que está à direita. O item T \to T \cdot {*} F diz que um T já está na pilha e que, se vierem * e F, o corpo estará completo. Ponto no fim significa item completo, isto é, alça possível.
Um estado não é um item, é um conjunto de itens, porque o analisador em geral não sabe em qual produção está e carrega todas as posições plausíveis até a evidência eliminar as inadequadas. Se soa familiar, é porque esta construção é a mesma determinização por subconjuntos dos autômatos finitos.
Duas operações constroem tudo. O fecho acrescenta as expectativas implicadas — se o ponto precede uma variável, entram os itens iniciais de todas as produções dela, e a regra se reaplica até estabilizar. 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 nasce do fecho do item inicial, com desvios calculados até não surgirem estados novos: doze, na nossa gramática.
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
Os dois erros que arruínam a construção à mão. Calcular o fecho uma vez só — os itens trazidos pelo próprio fecho também podem exigir fecho, e o sintoma é um estado sem transição por um símbolo que deveria tê-la. E 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 os identifica constrói uma árvore infinita em vez de um autômato finito.
A tabela de análise é essa coleção em forma consultável em tempo constante. A metade de desvio, indexada por estado e variável, sai direto do autômato. A metade de ação, indexada por estado e terminal, é onde mora a dificuldade: em quais colunas registrar a redução por um item completo? A resposta mais barata é registrá-la nas colunas dos terminais que podem seguir a variável reduzida — e com \mathrm{SEG}(E) = \{+, ), \$\} a tabela sai sem célula em disputa.
Olhe a linha do estado que tem E \to T \cdot junto com T \to T \cdot {*} F: a redução aparece em +, ) e $; na coluna * aparece deslocamento, porque * não segue E. Com * à frente, não se reduz T a E — se reduzisse, a multiplicação deixaria de agrupar mais forte. No método ascendente, precedência é propriedade da tabela.
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 causam quase todo engano de traçado. A redução não consome entrada: o símbolo de antecipação continua lá e será reexaminado. E o estado consultado para o desvio é o que ficou exposto depois do desempilhamento. Como cada passo custa uma consulta constante, a análise é linear e sem voltar atrás — o ganho da família não é velocidade, é quais gramáticas ela aceita. As células em branco também trabalham: cada uma é um erro detectável no primeiro token que torna a pilha inviável, e nenhum método detecta mais cedo — o que não é o mesmo que explicar bem.
1.3 A escala dos quatro métodos
O que separa os métodos é uma pergunta só: o que fazer num estado que tem item completo e item de deslocamento ao mesmo tempo. Cada nível é uma resposta, e 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 LR(0) decide sem olhar a entrada: havendo item completo, reduz. Quebra em três estados da nossa gramática minúscula, e seu valor é conceitual. O SLR(1) é o refinamento mais barato possível — olhe um símbolo à frente e só reduza por A \to \beta se ele puder seguir A —, é o da tabela acima e reusa os mesmos estados e os conjuntos de seguidores já calculados no módulo anterior. Frank DeRemer sistematizou essa simplificação na tese de doutorado de 1969 no MIT, e foi ela que tirou a família do papel: as tabelas de Knuth não cabiam nas máquinas da época.
A limitação do SLR é ser generoso demais: pergunta se o símbolo segue A em algum lugar da gramática, quando o correto seria perguntar se segue naquele estado. O LR(1) canônico corrige carregando dentro de cada item os símbolos que podem segui-lo naquele contexto, componente que só tem efeito quando o item é completo. Resolve, e custa caro em número de estados — por isso foi tido como impraticável por quase uma década. A saída é o LALR(1), também de DeRemer: o núcleo de um estado é o conjunto de itens sem as antecipações, e estados de mesmo núcleo são fundidos, unindo as antecipações item a item. 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 cria conflito de deslocamento-redução novo; pode criar conflito de redução-redução, quando as antecipações são disjuntas e trocadas entre si. Mesmo então o analisador não aceita cadeias fora da linguagem, só adia a detecção do erro: a fusão degrada o diagnóstico, não a correção.
Duas consequências de Knuth fecham a escala: 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. O método é a realização algorítmica do autômato de pilha determinístico que estudamos antes.
1.4 Conflitos: ler, classificar, resolver
Conflito é célula à qual a construção tenta atribuir dois valores. Deslocamento-redução: um item completo cuja antecipação inclui um terminal convive com um item que pede deslocamento desse mesmo terminal. Redução-redução: dois itens completos com antecipações que se intersectam. A cada tipo a experiência associa uma causa provável — heurística, não lei. O primeiro costuma ser questão de poder ou de precedência. O segundo costuma ser projeto da gramática: duas categorias indistinguíveis pela forma, cuja diferença real é semântica; nenhum nível resolve, e o certo é fundir as produções e distinguir depois na tabela de símbolos.
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"]
A distinção que custa horas quando ignorada é outra. Gramática não ambígua com conflito: o problema é de informação, e subir de nível resolve. Gramática ambígua: existem duas árvores, e nenhuma antecipação escolhe entre elas. O teste prático é tentar construir uma cadeia curta com duas árvores — conseguiu, é ambiguidade; não conseguiu, é aproximação grosseira. O caso mais comum é o dos operadores em um nível só, E -> E + E | E * E | ( E ) | id: ou se reescreve desambiguando, que é o que a gramática de dois níveis faz, ou se declara precedência e associatividade, convenção estabelecida pelo gerador que Stephen Johnson escreveu nos laboratórios Bell em meados dos anos 1970 e distribuiu com o Unix.
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 resolve por sorte, e o sintoma clássico é o analisador que compila sem aviso e aceita programas cuja árvore não corresponde ao pretendido — defeito que só aparece muitas fases depois, como resultado errado em execução.
Chegamos à habilidade que este módulo existe para formar. O gerador resolve conflitos 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 quase todo mundo para de ler. O que interessa está no relatório detalhado, que lista cada estado com seus itens: o objeto que você construiu à mão.
O terceiro passo é o que quase ninguém dá. Localize o estado citado; identifique o item completo, o item de deslocamento e o terminal em disputa; e então reconstrua um programa de exemplo que leve o analisador até ali, lendo os símbolos à esquerda dos pontos dos itens do núcleo. É esse passo que transforma uma lista de itens numa construção concreta da linguagem, sobre a qual dá para decidir. Verificação: conflito genuinamente resolvido some do relatório.
1.5 As duas famílias, critério a critério
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"]
| 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 de poupar trabalho: gramática que não precisa ser transformada pode ser escrita na forma que expressa a semântica pretendida, enquanto no caminho descendente a implementada é uma versão contorcida da documentada. Em diagnóstico a direção se inverte, porque o analisador recursivo sabe, em cada função, o que tenta reconhecer, e o gerado para dentro de um laço genérico. Avisa cedo e explica mal — o perfil da família inteira.
É por isso que a entrega deste módulo não tem código. Seu grupo toma um recorte pequeno da própria gramática — três ou quatro produções com um ponto de decisão de verdade —, constrói a tabela ascendente à mão, explica os conflitos e escreve a comparação entre as famílias aplicada ao caso do projeto; junto vai o plano dos módulos 12 a 15 com divisão de trabalho. Escolher o recorte já é metade do trabalho: a parte declarativa da gramática só produz fileiras de deslocamento.
1.6 Síntese
A análise ascendente sobe das folhas à raiz com duas operações, e a pilha guarda o que já foi reconhecido — inversão exata em relação ao módulo anterior, e fonte de metade das confusões. Reduções lidas ao contrário dão uma derivação mais à direita, e esse é o teste barato de todo traçado. 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 de itens construído com fecho e desvio. Sozinho ele não decide entre deslocar e reduzir, e daí a escala de quatro níveis, com a fusão de núcleos como ponto de equilíbrio dos geradores. Sobre conflitos, o que importa não é o tipo, é a causa: falta de informação sobe de nível, ambiguidade não sobe nível nenhum. E fica a lição que eu prometi cobrar: nenhuma das dificuldades do módulo anterior era dificuldade do problema, todas eram da abordagem escolhida. Distinguir uma coisa da outra separa quem escolhe uma técnica de quem aplica a primeira que aprendeu.