1 Autômatos de pilha — Projeto do Professor
Este é o projeto de referência do professor, e este módulo é a exceção do percurso: não há tarefa do Projeto Integrador a resolver aqui, e não há código novo a produzir. O que este documento entrega é a peça teórica que liga o que já existe ao que vem a seguir — a gramática escrita no módulo anterior e o analisador construído no próximo. O modelo do que cada grupo deve produzir, neste módulo, é um argumento escrito sobre a própria gramática, e é isso que demonstramos aqui.
1.1 Visão Geral
A ausência de código neste módulo é uma decisão de projeto. O autômato de pilha é o modelo abstrato da classe em que entramos no módulo anterior, e a realização concreta dele no nosso sistema é o analisador sintático descendente do módulo seguinte. Implementar aqui um autômato de pilha genérico — uma máquina que lê uma descrição de transições e a executa — produziria uma peça que o sistema não usa, para demonstrar uma correspondência que o analisador do próximo módulo demonstra por existir. Seria código órfão, e código órfão é o que ninguém mantém.
Há uma segunda razão, e ela é pedagógica. Antecipar a implementação inverteria a ordem que faz o módulo seguinte ser barato: o analisador descendente é quase uma transcrição da gramática preparada, e ele é quase uma transcrição porque a correspondência entre gramática e máquina de pilha foi entendida antes. Quem implementa primeiro e entende depois escreve um analisador que funciona nos casos testados e não sabe dizer por que funciona — e, principalmente, não sabe dizer onde ele vai parar de funcionar.
O que fazemos aqui, então, é estabelecer quatro coisas, e todas as quatro têm consequência direta sobre decisões que serão tomadas com código na mão daqui a um módulo. A primeira é a definição da máquina e o que exatamente a pilha acrescenta. A segunda são os dois critérios de aceitação e a equivalência entre eles — que é mais interessante do que parece, porque ela deixa de valer no caso determinístico. A terceira é a equivalência entre a máquina e as gramáticas livres de contexto, que é o resultado central da classe. A quarta é a assimetria entre determinismo e não determinismo, que contraria frontalmente a intuição construída no arco de autômatos finitos e que é a origem técnica de existirem duas famílias de analisadores.
Uma observação sobre o que o sistema já tem. O reconhecedor de derivações construído no módulo anterior — a busca com retrocesso que enumera as derivações mais à esquerda de uma sentença — já é um autômato de pilha não determinístico, ainda que não tenha sido apresentado assim. A pilha dele é a cadeia de símbolos pendentes da forma sentencial corrente; o não determinismo dele é a escolha de alternativa; o retrocesso é a exploração dos ramos. Voltarei a isso adiante, porque é o modo mais barato de tornar a equivalência verificável em vez de acreditada: a máquina já está rodando no sistema, e o que falta é reconhecê-la.
1.2 A pilha como memória de acesso restrito
Definição 9.1 — autômato de pilha
Um autômato de pilha é uma sétupla M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F), em que Q é um conjunto finito de estados, \Sigma o alfabeto de entrada, \Gamma o alfabeto da pilha, q_0 \in Q o estado inicial, Z_0 \in \Gamma o símbolo inicial da pilha, F \subseteq Q o conjunto de estados finais, e \delta : Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \longrightarrow \mathcal{P}_{\text{fin}}\big(Q \times \Gamma^{*}\big) a função de transição. Uma configuração é uma tripla (q, w, \alpha) \in Q \times \Sigma^{*} \times \Gamma^{*}, e escreve-se (q, aw, X\beta) \vdash (p, w, \gamma\beta) quando (p, \gamma) \in \delta(q, a, X).
Repare no que a assinatura de \delta diz, porque cada detalhe dela é uma decisão de projeto do modelo. O terceiro argumento é um símbolo de \Gamma: a máquina consulta o topo da pilha, e apenas o topo. Não há índice, não há leitura do meio, não há consulta ao tamanho. A máquina não sabe sequer quão alta a própria pilha está. É a restrição que dá nome ao modelo, e é ela que separa esta classe da classe das máquinas de propósito geral — uma memória que crescesse com acesso irrestrito nos levaria direto para lá, com problemas indecidíveis onde ainda temos algoritmos.
O resultado da transição é um par: o estado novo e uma cadeia de \Gamma^{*} que substitui o símbolo consultado. Essa forma unifica as três operações que se esperaria ver separadas. Empilhar é devolver uma cadeia mais longa que o símbolo retirado; desempilhar é devolver a cadeia vazia; trocar o topo é devolver uma cadeia de comprimento um. Não há operação de pilha na definição, e é elegante que não haja: há uma substituição, e as operações são casos dela.
O segundo argumento pode ser \varepsilon, e essa possibilidade é o que permite à máquina mexer na pilha sem consumir entrada. Sem ela, cada movimento de pilha custaria um símbolo do texto, e a máquina não conseguiria, por exemplo, esvaziar uma pilha profunda ao chegar ao fim da entrada. É uma conveniência técnica com uma consequência que discuto adiante: transições em \varepsilon são uma das duas fontes de não determinismo, e restringi-las é parte de definir o caso determinístico.
O contradomínio é o conjunto das partes finitas de Q \times \Gamma^{*}, e é aí que o não determinismo mora: para um mesmo estado, símbolo de entrada e topo de pilha, pode haver várias transições possíveis. Guarde a observação de que o não determinismo está embutido na definição padrão, e não é uma extensão dela — no caso finito era assim também, e lá isso não custava nada, porque a determinização era sempre possível. Aqui vai custar.
1.3 Os dois critérios de aceitação
Há duas maneiras naturais de dizer que a máquina aceitou uma entrada, e a literatura mantém as duas.
Definição 9.2 — as duas linguagens de uma máquina
A linguagem aceita por estado final é L(M) = \{\, w \in \Sigma^{*} \mid (q_0, w, Z_0) \vdash^{*} (q, \varepsilon, \alpha),\ q \in F,\ \alpha \in \Gamma^{*} \,\}. A linguagem aceita por pilha vazia é N(M) = \{\, w \in \Sigma^{*} \mid (q_0, w, Z_0) \vdash^{*} (q, \varepsilon, \varepsilon) \,\}. No segundo caso o conjunto F é irrelevante e costuma ser tomado vazio.
A diferença entre os dois é sobre onde fica registrada a conclusão de que a entrada terminou bem. No primeiro critério, o registro está no controle: a máquina chegou a um estado que declaramos de aceitação, e o que sobrou na pilha não importa. No segundo, o registro está na memória: a máquina consumiu tudo o que havia empilhado, e o estado em que ela parou não importa. São dois modos de contabilidade, e cada um é mais conveniente para um tipo de construção — o primeiro deles admite que a máquina termine com a pilha entulhada e ainda assim seja aprovada.
Teorema 9.1 — equivalência dos dois critérios
Para toda máquina M_1 existe M_2 com N(M_2) = L(M_1), e para toda máquina M_2 existe M_1 com L(M_1) = N(M_2). As duas famílias de linguagens coincidem, e é essa família que se chama das linguagens livres de contexto.
As duas construções usam o mesmo truque, e ele reaparece em outros lugares: acrescenta-se um símbolo de fundo de pilha novo, abaixo do original, que só a máquina construída conhece. Para converter estado final em pilha vazia, ao chegar num estado de F a máquina passa a um estado de limpeza que desempilha tudo, inclusive o fundo novo. Para converter pilha vazia em estado final, a máquina detecta o fundo novo aparecendo no topo — o que só acontece quando a pilha original esvaziou — e transita para um estado final.
O fundo de pilha novo tem uma função precisa. Sem ele, a máquina que desempilha tudo não teria como distinguir “esvaziei porque terminei” de “esvaziei no meio do caminho e agora não posso mais fazer nada” — e a segunda situação, numa máquina que aceita por pilha vazia, seria aceitação indevida. O símbolo extra é o que torna a condição de término observável de dentro da máquina.
Guarde este teorema com uma etiqueta de validade, porque ela é o ponto que este módulo mais precisa deixar plantado: a equivalência vale para as máquinas não determinísticas. No caso determinístico, aceitar por pilha vazia é estritamente mais fraco, e mostro por quê ao tratar do determinismo.
1.4 A equivalência com as gramáticas livres de contexto
Chego ao resultado central da classe, e ele fecha, para as gramáticas do módulo anterior, o mesmo tipo de correspondência que a expressão regular e o autômato finito estabeleceram no arco anterior.
Teorema 9.2 — gramáticas e máquinas descrevem a mesma classe
Uma linguagem L é gerada por alguma gramática livre de contexto se, e somente se, L = N(M) para alguma máquina de pilha M. Combinado ao Teorema 9.1, o mesmo vale para aceitação por estado final.
A direção que interessa ao nosso sistema é a que parte da gramática, e a construção dela é curta a ponto de ser descrita por inteiro. Constrói-se uma máquina de um único estado, cujo alfabeto de pilha é a união dos terminais e não terminais da gramática, e cujo símbolo inicial de pilha é o símbolo inicial da gramática. As transições são duas famílias. Para cada produção A \to \gamma, uma transição em \varepsilon que, com A no topo, o substitui por \gamma. Para cada terminal a, uma transição que, lendo a da entrada e com a no topo, o desempilha. Aceita-se por pilha vazia.
O que essa máquina faz, olhada de perto, é manter na pilha o sufixo pendente da forma sentencial corrente de uma derivação mais à esquerda. Expandir um não terminal é aplicar uma produção; casar um terminal é consumi-lo da entrada e retirá-lo da pilha. A correspondência é literal: uma sequência aceitante de movimentos da máquina é uma derivação mais à esquerda da entrada, e vice-versa. Esse é o conteúdo real do teorema, e é a razão de o nosso analisador poder ser escrito do jeito que será.
Aqui a demonstração deste módulo se apoia no que o sistema já tem, e é o motivo de não haver código novo. O reconhecedor de derivações construído no módulo anterior implementa exatamente essa máquina, sem tê-la nomeado: a forma sentencial pendente é a pilha, as alternativas de cada produção são o não determinismo, e o retrocesso é a exploração de todos os ramos. As duas podas que fazem aquela busca terminar têm, sob esta luz, leitura nova — a que compara terminais pendentes com entrada restante é uma cota sobre o quanto a pilha pode conter de terminais, e é ela que impede a máquina de expandir indefinidamente uma recursão à esquerda. Sem essa cota, a máquina expande, expande e expande, satisfeitíssima consigo mesma.
Vale executar essa falha em vez de anunciá-la, porque o sintoma dela engana. Tome a produção recursiva à esquerda da nossa gramática de partida, expr := expr "or" andExpr | andExpr, e a entrada a or b. A máquina do teorema começa com expr na pilha e aplica a primeira alternativa:
A coluna do meio nunca muda: em movimento algum a máquina consumiu um símbolo da entrada. A transição de expansão é em \varepsilon, e a alternativa recursiva devolve expr ao topo — mesmo estado, mesmo topo, mesma entrada pendente, e a pilha um pouco mais alta a cada passo. Uma implementação ingênua fica aqui até a memória acabar.
A cota conserta, e o conserto cabe numa linha. A terceira configuração já tem dois terminais or pendentes na pilha, e a entrada restante tem um. Como a expansão nunca remove terminal, esse ramo perdeu a chance de casar, e a busca o abandona ali: a recursão infinita vira um ramo que morre no terceiro movimento.
Um remendo que parece resolver e não resolve: limitar a profundidade da busca. Com teto de mil, a máquina empilha mil vezes, desiste, e relata que não reconheceu — a mesma resposta que ela daria a uma sentença genuinamente inválida. O sintoma some do terminal e o defeito continua na gramática, que é onde o conserto tem de ser feito.
A direção inversa do teorema, que parte da máquina e produz a gramática, é bem mais trabalhosa: os não terminais da gramática construída são triplas que registram estado de partida, símbolo de pilha consumido e estado de chegada, e a demonstração de correção é uma indução sobre o número de movimentos. Não a percorro aqui, e digo por quê: ela não sustenta nenhuma decisão que tomaremos com código na mão. O que sustenta é a direção gramática para máquina, e essa vale conhecer nos detalhes. A demonstração completa das duas direções está em Hopcroft, Motwani e Ullman, e em português na obra de Menezes.
1.5 Determinismo e não determinismo nesta classe
Esta é a parte do módulo que contraria a intuição construída no arco anterior, e a que tem a consequência prática mais direta. Peço atenção redobrada, porque a expectativa errada aqui é a mais natural que existe.
Definição 9.3 — máquina de pilha determinística
Uma máquina de pilha M é determinística quando, para todo q \in Q, todo a \in \Sigma e todo X \in \Gamma, valem as duas condições: \delta(q, a, X) e \delta(q, \varepsilon, X) têm, juntos, no máximo um elemento; e, se \delta(q, \varepsilon, X) é não vazio, então \delta(q, b, X) é vazio para todo b \in \Sigma. Escreve-se DCFL para a família das linguagens aceitas por estado final por alguma máquina determinística.
A segunda condição costuma passar despercebida e é a mais importante das duas. Ela diz que, se a máquina tem um movimento disponível sem consultar a entrada, então ela não pode ter movimento algum consultando-a naquele ponto. Sem essa exigência, a máquina teria de escolher entre agir agora e esperar para ver o próximo símbolo — e escolher é o que o determinismo proíbe. É a formalização precisa de uma coisa que o analisador do próximo módulo vive na prática: diante de uma produção vazia, decidir se a aplica exige saber o que vem depois.
Teorema 9.3 — a determinização não é possível nesta classe
\text{DCFL} \subsetneq \text{CFL}. Existem linguagens livres de contexto que nenhuma máquina de pilha determinística aceita — a linguagem dos palíndromos de comprimento par sobre um alfabeto de dois símbolos é o exemplo clássico.
Compare com o arco anterior e a diferença fica clara. Lá havia a construção por subconjuntos, que transformava qualquer máquina finita não determinística numa determinística equivalente, ao custo de um número de estados eventualmente exponencial — o poder de reconhecimento era o mesmo, só o tamanho mudava. Aqui não há construção análoga, e não há porque não pode haver: a inclusão é estrita, e isso é um teorema, não uma limitação do que se conhece hoje.
A intuição por trás do exemplo dos palíndromos é acessível. Para reconhecer que a segunda metade da cadeia é o reverso da primeira, a máquina precisa empilhar enquanto lê a primeira metade e desempilhar comparando enquanto lê a segunda. O ponto em que ela deve trocar de comportamento é o meio da cadeia — e nada no texto o assinala. Uma máquina não determinística resolve isso adivinhando o meio, isto é, explorando todos os pontos de troca; uma determinística teria de acertar de primeira, o que equivale a adivinhar o meio de uma cadeia cujo fim ela ainda não viu.
Decida antes de ler adiante. Uma máquina determinística aceita por pilha vazia, e a palavra ab pertence à linguagem dela. Lida a entrada ab, a pilha esvaziou. A entrada, porém, continua: abc também pertence à linguagem. Que movimento a máquina faz a partir dali? Responda antes de seguir; o parágrafo abaixo entrega a resposta, e lê-lo primeiro apaga o exercício.
Agora a consequência que prometi ao tratar dos dois critérios de aceitação, e que é o ponto mais fino deste módulo. Para máquinas determinísticas, aceitar por pilha vazia não é equivalente a aceitar por estado final: as linguagens aceitas por pilha vazia por uma máquina determinística são exatamente as que têm a propriedade de que nenhuma palavra da linguagem é prefixo próprio de outra. A razão é direta — esvaziada a pilha, a máquina não tem mais movimento algum, de modo que ela não pode aceitar uma palavra e continuar lendo para aceitar uma extensão dela. O Teorema 9.1 escapava disso porque o não determinismo permite manter um ramo que aceita e outro que segue.
O desdobramento prático fecha o módulo e abre o seguinte. As duas famílias de analisadores sintáticos que a literatura apresenta correspondem a restrições determinísticas sobre esta máquina, e a escolha entre elas é técnica. Knuth demonstrou, em 1965, que uma linguagem é determinística livre de contexto se, e somente se, ela tem uma gramática analisável da esquerda para a direita com um símbolo de antecipação — o que faz da família ascendente o limite superior do que uma decisão local alcança. A família descendente, que é a do nosso analisador, é estritamente mais restrita: aceita menos gramáticas, em troca de um analisador que se escreve à mão e cujo fluxo de controle é legível. É a troca que fizemos, e ela agora está justificada em vez de assumida.
1.6 O que este módulo entrega ao arco seguinte
Fica dito, para fechar, o que muda no sistema depois deste módulo — e no código não muda nada, o que é exatamente o ponto.
Muda que a pergunta do módulo seguinte passa a ter forma precisa: “que decisão local o analisador precisa tomar em cada ponto, e com que informação ele conta para tomá-la”, no lugar de “como escrevo um analisador para esta gramática”. A primeira pergunta se responde tentando; a segunda se responde calculando, e o cálculo é o assunto do próximo módulo — os conjuntos de símbolos que podem iniciar cada construção e os que podem segui-la, que são precisamente a informação que a definição de determinismo exige que exista.
Muda também o estatuto das transformações do módulo anterior. Eliminar recursão à esquerda e fatorar deixam de ser receitas e passam a ser o trabalho de colocar a gramática numa forma em que a máquina correspondente é determinística com um símbolo de antecipação. A recursão à esquerda produzia uma transição em \varepsilon que empilha sem consumir e reincide no mesmo ponto — a violação literal da segunda condição da Definição 9.3. O prefixo comum produzia duas transições disponíveis para o mesmo topo e o mesmo símbolo de entrada — a violação da primeira. As duas transformações eram, o tempo todo, a mesma coisa: tornar determinística uma máquina que não era.
E fica registrado o limite, que é a única coisa deste módulo que o estudante não tem como redescobrir sozinho e que evita uma frustração previsível: nem toda gramática se conserta. Como a inclusão do Teorema 9.3 é estrita, existem linguagens para as quais nenhuma transformação produz uma gramática analisável de forma determinística — e existem, dentro das determinísticas, linguagens que a família descendente não alcança. Quando uma gramática resistir às transformações, a resposta correta pode ser mudar a linguagem, e não insistir na transformação. Saber disso antes de tentar é a diferença entre uma decisão de projeto e uma tarde perdida.
Onde é fácil errar. Guardar o Teorema 9.1 como se ele valesse sempre. Ele é o único resultado deste módulo com etiqueta de validade, e a etiqueta cai justamente no caso que interessa ao nosso analisador — o determinístico. Quem sai daqui com “os dois critérios de aceitação são equivalentes” na memória vai construir, dois módulos adiante, um argumento sobre a própria gramática apoiado numa premissa que não vale ali.
Como verificar que está correta: percorra os três teoremas deste módulo e escreva, ao lado de cada um, se ele continua valendo quando a máquina é determinística. São três respostas — uma “vale”, uma “não vale” e uma que só faz sentido no caso determinístico. Se as suas três forem iguais, alguma leitura passou reto, e o parágrafo que a corrige está acima.