flowchart LR
AF["Autômato finito<br/>memória: só o estado corrente"]
CT["Contador<br/>memória: um número natural"]
PD["Pilha<br/>memória: uma sequência<br/>acesso só pelo topo"]
DP["Duas pilhas<br/>poder de máquina de Turing"]
AF --> CT --> PD --> DP
AF -.-> R1["reconhece pouco<br/>decide tudo"]
PD -.-> R2["reconhece as linguagens<br/>livres de contexto<br/>ainda decide o essencial"]
DP -.-> R3["reconhece tudo<br/>quase nada é decidível"]
1 Módulo 09: Autômatos de Pilha
Bem-vindo ao módulo mais teórico do semestre. É o único que não termina com uma peça nova do compilador rodando, e isso é de propósito: aqui você monta o modelo abstrato do analisador sintático, que no módulo seguinte vira código. Quem faz o traçado à mão antes chega lá reconhecendo o que implementa; quem pula acha que aquelas funções recursivas funcionam por sorte.
1.1 O problema: quanta memória dar à máquina
Começo com uma pergunta que parece boba e não é: se o autômato finito falha por ter pouca memória, por que não damos memória a ele e encerramos o assunto?
Vale levar a pergunta a sério, porque a resposta organiza o módulo inteiro. Já provamos que existem linguagens que nenhum autômato finito reconhece, e o exemplo era o mais prático possível: parênteses balanceados. A falha é estrutural — o estado depois de ler um prefixo é a única coisa que a máquina carrega adiante, e como os estados são finitos e os prefixos infinitos, dois prefixos diferentes colidem no mesmo estado e passam a ser tratados como iguais. Repara no que falta: uma contagem sem limite superior, consumida na ordem inversa da que foi produzida — os parênteses abertos por último são os primeiros a fechar. Isso já sugere a memória que resolve o problema.
Agora a alternativa oposta. Se a máquina puder ler e escrever livremente numa fita infinita, você obtém a máquina de Turing, sobre a qual quase nada é decidível: nem se ela para, nem se duas delas reconhecem a mesma linguagem. E um compilador precisa de garantias — saber que o analisador termina, que termina rápido, e que reconhece a linguagem documentada e não outra.
Entre os extremos há degraus. O primeiro é o contador — uma máquina finita com um registrador que guarda um número natural, incrementa, decrementa e testa contra zero. Ele resolve contagem casada e parênteses de um tipo só, mas não parênteses de tipos diferentes aninhados, porque guarda uma quantidade e não uma sequência: sabe que há três aberturas pendentes, não sabe quais. O degrau seguinte é a pilha, que guarda a sequência. E logo acima está o abismo — uma máquina finita com duas pilhas já equivale a uma máquina de Turing: uma guarda a fita à esquerda da cabeça, a outra o que está à direita, e mover a cabeça é transferir um símbolo de uma para a outra.
Pare e pense. Se a segunda pilha custa a decidibilidade inteira, o que exatamente a primeira compra? Guarde a sua resposta e confira ao fim do módulo — ela é o resumo honesto de tudo o que vem a seguir.
Ou seja: o que a gente quer não é mais memória, é a quantidade certa e a forma certa de acesso a ela — capacidade ilimitada, acesso só por uma extremidade. É a severidade dessa restrição que devolve a capacidade de demonstrar coisas, e o mesmo princípio volta toda vez que restringirmos a classe de gramáticas que um método aceita.
Antes de entrar na formalização, quero situar este capítulo dentro do percurso do livro, porque ele é o único, até aqui, que não termina com uma peça nova do compilador em funcionamento — e essa ausência é deliberada.
O caso conduzido deste livro é a Peneira, a linguagem de reconhecimento de padrões cujo compilador venho construindo capítulo a capítulo. Nos capítulos anteriores ela ganhou um analisador léxico completo, apoiado na conversão de expressões regulares em autômatos finitos determinísticos, e ganhou uma gramática livre de contexto que descreve a sua estrutura hierárquica: a lista de declarações, as declarações de padrão, os blocos de regra e as expressões de condição, com precedência e associatividade codificadas na forma das produções. O que ainda não existe é o programa que lê uma sequência de símbolos e decide se ela obedece a essa gramática.
Este capítulo não escreve esse programa. Ele constrói o modelo de máquina que torna esse programa possível, e o faz sobre gramáticas de brinquedo — expressões aritméticas, cadeias com contagem casada, palíndromos — porque é sobre objetos pequenos que a formalização fica visível. A realização concreta sobre a gramática da Peneira é assunto do capítulo seguinte, e chega lá em forma de código.
Há uma razão para não antecipá-la. O analisador que o capítulo seguinte constrói parece, para quem chega sem este capítulo, um algoritmo tirado do nada: uma coleção de funções mutuamente recursivas que, por algum motivo, reconhece exatamente a linguagem certa. Para quem chega tendo entendido o autômato de pilha construído a partir da gramática, ele é outra coisa — é esse mesmo autômato, com as escolhas não determinísticas substituídas por uma consulta ao próximo símbolo da entrada, e com a pilha implícita na pilha de chamadas da linguagem hospedeira. A diferença entre as duas experiências de leitura é grande, e é toda ela produzida aqui.
Sugiro, portanto, que você trate o traçado manual da seção 4 como trabalho prático, e não como ilustração. Pegue a gramática do seu próprio projeto, aplique a construção a ela e trace o reconhecimento de um programa curto seu, passo a passo, com a pilha escrita à mão em uma tabela. É a única atividade deste capítulo que produz artefato, e é a que faz o capítulo seguinte parecer natural.
1.2 A máquina, com todo o rigor
Formalmente, um autômato de pilha é uma sétupla M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F): estados, alfabeto de entrada, alfabeto de pilha — finito e possivelmente diferente do de entrada —, função de transição, estado inicial, símbolo inicial de pilha e estados finais. A função de transição tem a assinatura
\delta : Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \longrightarrow \mathcal{P}_{\text{fin}}(Q \times \Gamma^{*}).
Essa assinatura costuma ser lida depressa demais, e carrega o modelo inteiro.
flowchart TB
ENT["Entrada<br/>lida da esquerda para a direita,<br/>sem retorno, ou não lida<br/>quando a transição é vazia"]
TOPO["Topo da pilha<br/>único símbolo visível"]
CTRL["Controle finito<br/>estado corrente"]
ACAO["Transição escolhida<br/>troca o topo por uma cadeia de símbolos<br/>e muda de estado"]
PILHA["Pilha<br/>altura ilimitada<br/>o resto do conteúdo é invisível"]
ENT --> CTRL
TOPO --> CTRL
CTRL --> ACAO
ACAO --> PILHA
PILHA --> TOPO
A segunda componente do domínio inclui \varepsilon: há transições executadas sem consumir símbolo algum da entrada, em que a máquina mexe na pilha e muda de estado por conta própria — e a construção central deste módulo é feita quase toda delas. A terceira exige sempre um símbolo de pilha, ou seja, toda transição consulta o topo; logo, uma máquina com a pilha vazia está travada, e é isso que dará sentido à aceitação por pilha vazia. E o contradomínio é um conjunto de pares: é aí que mora o não determinismo. A cadeia em cada par substitui o topo — vazia, o topo some; com um símbolo, é trocado; com vários, a pilha cresce.
A convenção que produz o erro mais comum do módulo. O símbolo mais à esquerda da cadeia substituta fica no topo. Quem empilha o conteúdo dela na ordem em que está escrito obtém a ordem invertida, e o autômato passa a reconhecer as cadeias espelhadas. Pior: o defeito é invisível quando a cadeia tem zero ou um símbolo, que é o caso dos primeiros exemplos que qualquer um testa. Trate a substituição como troca de bloco, nunca como sequência de empilhamentos.
Para falar da computação sem ambiguidade eu preciso de uma noção de situação completa, e o estado sozinho não basta mais. Uma descrição instantânea é a tripla formada pelo estado corrente, pela parte ainda não lida da entrada e pela pilha escrita do topo para a base; escrevo um passo como (q, aw, X\beta) \vdash (p, w, \gamma\beta) quando o par (p, \gamma) está em \delta(q, a, X). A notação registra de graça que a porção \beta abaixo do topo atravessa o passo intocada, porque a máquina não a vê.
Um autômato pequeno fixa isso tudo. Para \{a^{n}b^{n} : n \ge 1\} bastam três estados e um alfabeto de pilha com uma marca e o símbolo de fundo: cada a empilha uma marca; o primeiro b muda de estado e desempilha; os demais continuam desempilhando; e quando o símbolo de fundo reaparece no topo — só se todas as marcas foram consumidas — uma transição vazia leva ao estado final. O projeto se prova é nas cadeias de fora: sobre aab sobra uma marca e a máquina trava fora do estado final; sobre abb ela chega ao estado final com um b por ler e não tem para onde ir. Três estados e uma pilha resolvem o que nenhum autômato finito resolve com nenhuma quantidade de estados.
Esse exemplo é determinístico, o que pode sugerir que o não determinismo da definição é generosidade desnecessária. Considere então os palíndromos de comprimento par: empilha-se a primeira metade e, na segunda, exige-se que cada símbolo lido case com o topo — só que falta à máquina saber onde termina a primeira metade, e ela resolve adivinhando, a cada posição, se continua empilhando ou se o meio é ali. Um dos ramos acerta, e a aceitação existencial faz o resto.
1.3 Duas maneiras de dizer sim
Aqui há duas definições razoáveis de sucesso, ambas correntes na literatura.
A cadeia é aceita quando a máquina consome a entrada inteira e chega a um estado de F; o conteúdo final da pilha é irrelevante. É a convenção mais próxima do autômato finito e a padrão para máquinas determinísticas.
A cadeia é aceita quando a máquina consome a entrada inteira e a pilha fica vazia, esteja ela no estado que estiver; o conjunto de estados finais costuma ser tomado vazio. É a convenção mais cômoda quando o autômato nasce de uma gramática.
Nas duas, a condição é existencial: basta que alguma sequência de escolhas chegue à aceitação, e os ramos que travam ou entram em laço não contam. Confortável na teoria, e exatamente o que ninguém sabe implementar de forma eficiente.
flowchart LR
VAZIA["Aceitação por pilha vazia<br/>o estado final não importa"]
FINAL["Aceitação por estado final<br/>o conteúdo da pilha não importa"]
VAZIA -->|"acrescenta marcador de fundo<br/>e um estado final novo,<br/>alcançado quando o marcador aparece"| FINAL
FINAL -->|"acrescenta marcador de fundo<br/>e um estado de limpeza<br/>que desempilha tudo"| VAZIA
VAZIA -.-> OBS["Equivalentes no caso não determinístico.<br/>No caso determinístico não são:<br/>pilha vazia só reconhece<br/>linguagens livres de prefixos"]
As duas reconhecem a mesma classe de linguagens, e as construções que estabelecem isso dependem do mesmo truque: acrescentar ao fundo da pilha um símbolo novo, fora do alfabeto original. Para ir de pilha vazia a estado final, a tentação é declarar finais os estados em que a pilha esvazia — e não funciona, porque ao esvaziar a máquina trava e não sinaliza nada. Com o marcador no fundo, o evento invisível “a pilha real acabou” vira observável e habilita a transição para o novo estado final. No sentido inverso, acrescenta-se um estado de limpeza, alcançado por transição vazia a partir de qualquer estado final, que desempilha tudo; aqui o marcador é defensivo, porque sem ele a pilha poderia esvaziar no meio da simulação — e, nessa convenção, esvaziar é aceitar.
Uma consequência dessa segunda convenção reaparece como defeito real em analisadores: se a pilha passa pelo vazio num instante intermediário, o prefixo lido até ali também é aceito, e por isso uma máquina determinística assim só reconhece linguagens em que nenhum elemento é prefixo próprio de outro. É a razão teórica de todo analisador real exigir um marcador explícito de fim de entrada antes de declarar sucesso — sem ele, quem esvazia a pilha ao completar a primeira declaração do programa reporta “programa válido” e ignora o resto do arquivo.
1.4 Da gramática ao autômato: o coração do módulo
Chegamos ao que interessa à construção de compiladores: quem entende esta construção entende o analisador descendente antes de vê-lo.
Dada uma gramática livre de contexto, construo um autômato de pilha com um único estado, aceitação por pilha vazia, alfabeto de pilha igual à união das variáveis com os terminais e símbolo inicial de pilha igual ao da gramática. A função de transição tem duas famílias, só isso. Expansão: havendo uma variável no topo, troque-a pelo corpo de alguma produção dela, sem consumir entrada. Casamento: havendo um terminal no topo, remova-o exigindo que o mesmo terminal esteja na entrada.
flowchart TB
INI["Pilha começa com o símbolo<br/>inicial da gramática"]
DEC{"O que está no topo?"}
EXP["Expande<br/>troca a variável pelo corpo<br/>de uma de suas produções<br/>sem consumir entrada"]
CASA["Casa<br/>remove o terminal do topo<br/>e consome o mesmo símbolo da entrada"]
FIM["Pilha vazia:<br/>aceita se a entrada também acabou"]
INI --> DEC
DEC -->|"uma variável"| EXP
DEC -->|"um terminal"| CASA
EXP --> DEC
CASA --> DEC
DEC -->|"nada"| FIM
Um estado só merece pausa: todo o poder do modelo está na pilha, e nenhum no controle finito. E o que importa levar adiante é o invariante que governa a construção: se u é o prefixo já consumido e \alpha é a pilha lida do topo para a base, a gramática deriva u\alpha por uma derivação mais à esquerda. Em português: a pilha contém a parte da forma sentencial que ainda não foi casada com a entrada.
A pilha é uma lista de obrigações
Uma variável no topo significa “ainda tenho de reconhecer algo derivável dela, e depois disso tudo o que está embaixo”. Expandir troca uma obrigação por obrigações menores; casar cumpre uma obrigação elementar; aceitar é não sobrar obrigação nem entrada. Na análise ascendente a mesma estrutura guarda o oposto, o que já foi reconhecido — lá, pergunte a cada passo se a pilha guarda dívida ou patrimônio.
Ao traçado, sobre a gramática clássica de expressões, com precedência estratificada em três variáveis: E \to E + T \mid T, T \to T * F \mid F, F \to (\,E\,) \mid \text{id}.
| Passo | Pilha (topo à esquerda) | Entrada restante | Transição |
|---|---|---|---|
| 0 | E | \text{id} + \text{id} | configuração inicial |
| 1 | E + T | \text{id} + \text{id} | expande E \to E + T |
| 2 | T + T | \text{id} + \text{id} | expande E \to T |
| 3 | F + T | \text{id} + \text{id} | expande T \to F |
| 4 | \text{id} + T | \text{id} + \text{id} | expande F \to \text{id} |
| 5 | +\,T | +\,\text{id} | casa \text{id} |
| 6 | T | \text{id} | casa + |
| 7 | F | \text{id} | expande T \to F |
| 8 | \text{id} | \text{id} | expande F \to \text{id} |
| 9 | vazia | vazia | casa \text{id} |
Três coisas que o traçado torna concretas. Os quatro primeiros passos não consomem nada da entrada: a máquina reorganiza a pilha antes de ler o primeiro símbolo, assinatura da estratégia descendente, em que a decisão vem antes da evidência que a justificaria. Depois, uma conferência que recomendo sempre: os casamentos têm de ser tantos quantos os terminais da entrada, e as expansões, tantas quantos os nós internos da árvore — aqui, três e seis. E a ordem de empilhamento no passo 1: empilhando o corpo na ordem de escrita, a pilha sai invertida e a linguagem reconhecida é outra.
Agora o resultado que dá sentido a tudo: a sequência de produções das expansões de uma computação que aceita é exatamente a de uma derivação mais à esquerda. Foram E \to E+T, E \to T, T \to F, F \to \text{id}, T \to F, F \to \text{id}, ou seja,
E \Rightarrow E + T \Rightarrow T + T \Rightarrow F + T \Rightarrow \text{id} + T \Rightarrow \text{id} + F \Rightarrow \text{id} + \text{id}.
Não é analogia: é o mesmo objeto. O autômato, executando, é a derivação mais à esquerda construída passo a passo — e é isso que quero que sobreviva ao módulo, porque o analisador descendente constrói a árvore da raiz para as folhas seguindo essa mesma derivação.
Falta o incômodo: o traçado parece determinístico e não é. No passo 1 havia E no topo, duas produções disponíveis e, como a expansão é transição vazia, a máquina não olhou a entrada para escolher — adivinhou, e o mesmo vale nos passos 2, 3 e 4.
A armadilha do traçado desonesto. Traçando à mão é quase irresistível espiar a entrada para decidir qual produção expandir; o traçado sai certo e esconde o que deveria mostrar. Em cada expansão com mais de uma produção possível, anote que houve escolha e qual informação a dispensaria — é a anotação, e não o traçado, que ensina.
O que resolveria cada adivinhação é onde nasce o próximo módulo. A do passo 4 é fácil: um símbolo de antecipação basta, já que os corpos de F começam por símbolos diferentes. A do passo 1 não se resolve com antecipação nenhuma, porque E \to E + T é recursiva à esquerda e a expansão recoloca E no topo sem consumir nada. No modelo isso não incomoda, porque ele não executa ramos, quantifica. Uma implementação determinística não tem esse luxo — uma função que chama a si mesma antes de consumir qualquer símbolo não retorna nunca, e esse é o modo mais comum de um analisador descendente travar na primeira execução.
1.5 Do autômato à gramática, e o que a volta ensina
A direção inversa completa a equivalência e revela algo que a construção fácil esconde. A dificuldade é que a gramática é um formalismo estrutural, sem noção de estado, enquanto a computação combina estado e pilha. A saída é engenhosa: cada variável codifica um trecho de computação. Para cada tripla formada por um estado de partida, um símbolo de pilha e um estado de chegada, cria-se uma variável que deriva as cadeias consumidas ao remover aquele símbolo da pilha — a tarefa completa de desempilhá-lo, incluindo tudo o que se empilhe por cima dele nesse meio-tempo.
flowchart TB
VAR["Variável da gramática construída:<br/>a tripla estado inicial, símbolo de pilha,<br/>estado final do trecho"]
SIG["Significado pretendido:<br/>deriva exatamente as cadeias que a máquina<br/>consome ao remover aquele símbolo da pilha"]
PROD["Uma produção para cada escolha<br/>possível dos estados intermediários"]
CUSTO["Explosão combinatória:<br/>a gramática existe para demonstrar o teorema,<br/>não para ser usada"]
LICAO["Lição: estado e pilha são recursos<br/>intercambiáveis, um absorve o outro"]
VAR --> SIG --> PROD --> CUSTO --> LICAO
As produções seguem da ideia, com um porém: quando uma transição empilha vários símbolos é preciso removê-los em sequência, e os estados intermediários são desconhecidos — a gramática gera todas as combinações. Daí a explosão, com boa parte das variáveis inútil. Ninguém usa essa construção para produzir gramáticas; ela existe para demonstrar o teorema central do módulo: uma linguagem é gerada por alguma gramática livre de contexto se e somente se é aceita por algum autômato de pilha. O resultado é do início dos anos 1960, em trabalhos independentes de Noam Chomsky, de 1962, de Robert Evey e de Marcel-Paul Schützenberger — o mesmo papel que o teorema de Kleene cumpre no nível regular.
A lição é esta: numa direção os estados eram dispensáveis; na outra, precisam ser codificados dentro das variáveis, e é isso que faz a gramática explodir. Estado e pilha não são recursos independentes, e o eco prático é direto: num analisador recursivo o estado está todo na pilha de chamadas; num analisador dirigido por tabela existe um estado explícito consultado a cada passo.
1.6 Determinismo, e o que ele custa
Agora o resultado que distingue este andar de tudo que veio antes e contraria a intuição formada na determinização. Um autômato de pilha é determinístico quando, para cada estado e cada símbolo de topo, há no máximo uma continuação por símbolo de entrada e a existência de uma transição vazia exclui todas as que leem símbolo naquela configuração. Essa segunda cláusula costuma passar despercebida: sem ela, a máquina escolheria entre agir por conta própria e ler a entrada, e isso é não determinismo disfarçado.
flowchart TB
subgraph REG["Nível regular"]
AFN["Autômato finito<br/>não determinístico"]
AFD["Autômato finito<br/>determinístico"]
AFN -->|"construção de subconjuntos<br/>preço: explosão de estados"| AFD
end
subgraph LLC["Nível livre de contexto"]
APN["Autômato de pilha<br/>não determinístico"]
APD["Autômato de pilha<br/>determinístico"]
APN -.->|"não existe construção geral:<br/>um ramo carrega uma pilha,<br/>e conjuntos de pilhas não cabem<br/>em estrutura finita"| APD
end
REG --> LLC
A classe reconhecida por autômatos de pilha determinísticos está estritamente contida nas linguagens livres de contexto, e o exemplo canônico é o dos palíndromos de comprimento par, que nenhum determinístico reconhece. Uma máquina sem escolhas teria de decidir, a cada símbolo, se ele pertence à primeira ou à segunda metade — decisão que depende do comprimento total, conhecido só no fim. Ela precisa decidir cedo o que só se sabe tarde.
Por que o método do nível regular não sobe de andar? A construção de subconjuntos funcionava porque o determinístico simulava todos os ramos de uma vez, guardando o conjunto dos estados possíveis, e subconjuntos de um conjunto finito ainda são finitos. Aqui um ramo é um estado e uma pilha, então simular todos exigiria guardar um conjunto de pilhas, objetos ilimitados que divergem entre ramos. É essa a fronteira, e ela explica por que a análise léxica se resolve com um algoritmo único e a sintática não.
| Aspecto | Nível regular | Nível livre de contexto |
|---|---|---|
| Modelo reconhecedor | autômato finito | autômato de pilha |
| Determinismo e não determinismo | equivalentes | não equivalentes |
| Conversão do não determinístico | construção de subconjuntos | não existe em geral |
| Fechamento sob complemento | vale para a classe inteira | só para a subclasse determinística |
| Custo do reconhecimento | linear | linear só nas subclasses determinísticas |
A tradução para a engenharia é severa. Não sabemos executar não determinismo em tempo razoável, e o algoritmo geral que trata qualquer gramática livre de contexto reconhece uma cadeia de comprimento n em tempo proporcional a n^{3} — inaceitável para arquivos de dezenas de milhares de símbolos. E tempo linear exige determinismo. Daí a decisão que você vai herdar: a análise sintática real se restringe a subclasses determinísticas, aceitando que há gramáticas legítimas que nenhum analisador prático vai tratar. A escolha da gramática vira parte do projeto do compilador, e é também a razão de existir uma família de métodos, cada um cobrindo uma faixa da escala.
Não é só perda. A subclasse determinística é fechada sob complemento, o que dá à linguagem um critério de rejeição bem definido — e é isso que sustenta a detecção de erro sintático em posição precisa. Um reconhecedor não determinístico não tem “ponto do erro” a reportar: só sabe que nenhum ramo funcionou. E a equivalência entre dois autômatos de pilha determinísticos é decidível — resultado difícil, do fim dos anos 1990, de Géraud Sénizergues, reconhecido com o Prêmio Gödel em 2002 —, enquanto a mesma pergunta sobre gramáticas quaisquer é indecidível. Restrição deliberada de novo: a subclasse mais fraca é aquela sobre a qual se consegue provar mais.
1.7 Os limites da classe
Como no nível regular, precisamos de uma ferramenta para provar que uma linguagem não pertence à classe. O lema do bombeamento tem aqui a mesma forma e uma diferença estrutural: a decomposição é em cinco partes, z = uvwxy, e duas são bombeadas juntas, na mesma quantidade, com o trecho central confinado a uma janela limitada e sem que ambas sejam vazias.
flowchart TB
LONGA["Cadeia longa na linguagem"]
ALTA["Árvore de derivação alta:<br/>algum caminho da raiz até uma folha<br/>repete uma mesma variável"]
DEC["Decomposição em cinco partes:<br/>u, v, w, x, y"]
BOMBA["A variável repetida permite repetir ou apagar<br/>o trecho intermediário: v e x crescem juntos"]
JANELA["Restrição decisiva:<br/>o trecho central cabe numa janela<br/>de tamanho limitado pela gramática"]
LONGA --> ALTA --> DEC --> BOMBA
DEC --> JANELA
A intuição vem da árvore, e não do autômato — curioso: a ferramenta que limita o modelo de máquina é demonstrada pelo formalismo gerativo. Numa gramática em forma normal de Chomsky cada nó interno tem no máximo dois filhos, então uma árvore com muitas folhas precisa ser alta; sendo alta, algum caminho da raiz a uma folha tem mais nós internos do que variáveis na gramática, e pelo princípio das casas dos pombos alguma se repete nele. Repetir ou apagar o trecho entre as duas ocorrências dessa variável é o bombeamento. As duas versões do lema aparecem no mesmo trabalho de Yehoshua Bar-Hillel, Micha Perles e Eliahu Shamir, de 1961.
Aplico à linguagem com três blocos de contagens iguais, \{a^{n}b^{n}c^{n} : n \ge 1\}. Suponha que fosse livre de contexto e tome a cadeia com os blocos do tamanho da constante do lema. A restrição sobre a janela faz o trabalho: o trecho central não alcança ao mesmo tempo o bloco dos a e o dos c, porque há um bloco inteiro de b entre eles, logo as partes bombeadas tocam no máximo dois blocos. Bombeando uma vez, um bloco cresce e outro fica parado, e a cadeia sai da linguagem.
A frase que resume tudo. Uma pilha conta uma coisa de cada vez. Ela conta os a e desconta com os b, mas ao fim dessa verificação a quantidade foi consumida e não há de onde tirá-la de novo para conferir os c — consultar uma pilha em profundidade exige destruí-la. Essa frase explica, sem formalização nenhuma, metade dos resultados negativos deste módulo.
Numa demonstração dessas você escolhe a cadeia e o adversário escolhe a decomposição, então escolha cadeias em que as partes que precisam corresponder fiquem o mais distantes possível. E vale a advertência de sempre: o lema é condição necessária, não suficiente.
O fechamento reserva a segunda surpresa. União, concatenação, fecho e reverso continuam fechados, demonstráveis sobre gramáticas com um novo símbolo inicial. Interseção e complemento, não: a linguagem que casa a com b deixando os c livres é livre de contexto, a que casa b com c deixando os a livres também é, e a interseção das duas é a dos três blocos iguais que acabamos de excluir — a não clausura sob complemento sai daí por De Morgan. Já a interseção com uma linguagem regular é fechada, e não por acidente: o produto do autômato de pilha com o finito funciona porque o finito não traz uma segunda pilha.
A decidibilidade também encolhe. Continuam decidíveis a pertinência, em tempo cúbico; a vacuidade, por ponto fixo; e a finitude, por detecção de ciclos. Tornam-se indecidíveis a equivalência de duas gramáticas e a ambiguidade de uma — perguntas que, no nível regular, eram rotina. A segunda tem consequência imediata: não existe, nem pode existir, ferramenta que responda com certeza se uma gramática é ambígua. As reais verificam se ela pertence a uma subclasse específica, o que é decidível, e reportam conflitos quando não pertence. Conflito não é sinônimo de ambiguidade, e confundir os dois custa horas procurando um defeito que não existe.
1.8 A hierarquia retomada
Com o autômato de pilha estabelecido, temos dois dos quatro andares da hierarquia de Chomsky cobertos.
flowchart TB
T3["Tipo 3 — regulares<br/>autômato finito<br/>análise léxica, custo linear"]
T2["Tipo 2 — livres de contexto<br/>autômato de pilha<br/>análise sintática, só nas subclasses determinísticas"]
T1["Tipo 1 — sensíveis ao contexto<br/>autômato linearmente limitado<br/>formalismo recusado por custo na análise semântica"]
T0["Tipo 0 — irrestritas<br/>máquina de Turing<br/>fronteira do decidível"]
T3 --> T2 --> T1 --> T0
T0 -.-> LIM["Daqui vêm os limites de qualquer fase:<br/>perguntas sobre o comportamento do programa<br/>são indecidíveis em geral"]
A leitura vertical é o que interessa: a restrição sobre a forma das produções determina ao mesmo tempo a classe alcançada e a máquina necessária para reconhecê-la. Afrouxando a restrição, a classe cresce, a máquina fica mais poderosa, o custo sobe e o conjunto de perguntas decidíveis encolhe. A diferença entre os tipos 2 e 1 é a que dá nome à classe: numa produção livre de contexto o lado esquerdo é uma única variável e a substituição vale independentemente do que esteja em volta, e é a ausência dessa dependência do entorno que torna o tipo 2 tratável.
O lugar do compilador no mapa fica então preciso a ponto de você repeti-lo sem consultar. A análise léxica vive no tipo 3, com custo linear e algoritmo único, porque ali determinismo e não determinismo são equivalentes. A análise sintática vive no tipo 2, e não nele inteiro: nas subclasses determinísticas. A análise semântica seria de tipo 1 e não é feita com esse formalismo — uma gramática sensível ao contexto que exprima “todo nome usado foi declarado” é um emaranhado ilegível e caro de reconhecer, então a prática o abandona de olhos abertos e verifica isso por código ou por gramáticas de atributos. E o tipo 0 delimita o que nenhuma fase pode fazer: qualquer pergunta sobre o comportamento do programa compilado é indecidível em geral, e a resposta da engenharia é a aproximação conservadora, errando sempre para o mesmo lado. A arquitetura do compilador é, em boa medida, um retrato da hierarquia.
1.9 Amarrando: o que levar para o próximo módulo
Volto à pergunta da abertura. A primeira pilha compra o que faltava ao autômato finito — as correspondências aninhadas, com contagem sem limite — sem entregar a decidibilidade, que a segunda destruiria de uma vez. É a restrição de acesso, e não a capacidade, que faz o modelo valer a pena.
flowchart LR
ADV1["Adivinhação local:<br/>qual produção usar quando os corpos<br/>começam por símbolos diferentes"]
ADV2["Adivinhação global:<br/>quantas vezes aplicar uma produção<br/>recursiva à esquerda"]
FER1["Conjuntos de símbolos iniciais<br/>e de símbolos seguidores"]
FER2["Transformação da gramática:<br/>eliminação de recursão à esquerda<br/>e fatoração"]
RES["Autômato sem adivinhações:<br/>analisador descendente em tempo linear"]
ADV1 --> FER1 --> RES
ADV2 --> FER2 --> RES
O núcleo do que ficou é a equivalência entre gramáticas livres de contexto e autômatos de pilha, com destaque para a construção que parte da gramática: um autômato de um estado, duas famílias de transição, e o invariante de que a pilha guarda o que ainda falta reconhecer. A sequência de expansões de uma computação que aceita é uma derivação mais à esquerda, e é essa identidade que faz o analisador descendente parecer natural em vez de mágico. O que muda a engenharia é a não equivalência entre determinismo e não determinismo, que força a análise sintática a viver em subclasses. E os limites da classe vêm da mesma frase: uma pilha conta uma coisa de cada vez.
O trabalho do módulo, no projeto do seu grupo, é o traçado. Pegue a gramática que vocês escreveram para a própria linguagem, aplique a construção, escolha um programa curto e trace o reconhecimento numa tabela, com a pilha à mão e a orientação fixada. Anote, em cada expansão com mais de uma produção possível, que houve escolha e que informação a dispensaria — é essa anotação que vira, adiante, o conjunto de símbolos iniciais e a decisão de transformar a gramática. E explique, na fundamentação, por que a análise sintática se restringe a subclasses determinísticas.
Faça isso antes do próximo módulo. Quem chega ao analisador descendente tendo traçado reconhece o que vai implementar; quem pulou encontra um algoritmo que parece surgir do nada.