Moacyr Francischetti Corrêa

1 Módulo 09: Projeto do Professor — O Analisador Sintático em Embrião

Este é o projeto de referência resolvido pelo professor: a mesma atividade que cada grupo vai executar neste módulo, feita por inteiro. Módulo sem tarefa de implementação — a entrega é teórica, e este documento é o modelo do que o seu grupo deve escrever, não algo a copiar.

1.1 Visão Geral do Módulo 09

Este é um dos dois módulos do semestre em que o projeto não recebe código novo, e vale dizer de saída por que a decisão está certa. O autômato de pilha é o modelo abstrato correspondente às gramáticas do módulo anterior. A realização concreta dele, neste projeto, é o analisador sintático de descida recursiva do módulo 10. Implementar um autômato de pilha genérico produziria código que nenhuma outra parte do compilador usaria — contrariando o caráter cumulativo da implementação de referência, em que tudo que se escreve continua em uso até o último módulo.

O que a atividade pede é um documento de fundamentação: mostrar como a gramática escrita no módulo 8 se traduz no modelo de pilha, ilustrar com o traçado manual do reconhecimento de um programa curto, e discutir por que a análise sintática prática se restringe a subclasses determinísticas — com as consequências disso para as escolhas do módulo seguinte.

Resolvi a atividade e, ao fazê-lo, encontrei três coisas que valem mais que o exercício em si. A primeira é que o autômato de pilha construído a partir da gramática já é o analisador do módulo 10, faltando apenas a parte que elimina as adivinhações. A segunda é que as adivinhações que ele precisa fazer são exatamente aquelas que a antecipação de um símbolo vai resolver. E a terceira é que a recursão à esquerda, inofensiva no modelo não determinístico, é fatal na implementação determinística — o que explica, com precisão, por que o módulo 10 começa eliminando-a.

1.2 Tarefa 1: Traduzir a gramática para o modelo de pilha

A atividade — explicar como a gramática da Peneira se traduziria em um autômato de pilha, seguindo a construção vista em aula.

A construção que parte da gramática é a mais instrutiva das duas, e é enganosamente simples. O autômato resultante tem um único estado. Toda a informação vive na pilha, e o controle finito não precisa lembrar de nada — o que é, em si, um resultado curioso: a memória que faltava ao autômato finito estava toda na estrutura, não nos estados.

A construção tem duas famílias de transições, e só duas.

A primeira expande: para cada produção da gramática, uma transição que não consome símbolo algum da entrada, retira a variável do topo da pilha e coloca no lugar o corpo da produção, com o primeiro símbolo do corpo ficando no topo. Para a produção declPadrao -> pattern ID = PADRAO ;, a transição tira declPadrao do topo e empilha os cinco símbolos, com pattern acima.

A segunda casa: para cada terminal do alfabeto, uma transição que consome esse terminal da entrada quando ele está no topo da pilha, e o retira. É o passo que faz progresso na leitura; o primeiro nunca lê nada.

O autômato começa com o símbolo inicial da gramática sozinho na pilha e aceita quando a pilha esvazia junto com a entrada. Nada mais.

Vale enunciar o que essa construção significa, porque é o coração do módulo: a pilha guarda o que ainda falta reconhecer. Em qualquer instante, o conteúdo da pilha, lido do topo para a base, é a parte da forma sentencial que ainda não foi casada com a entrada. As expansões substituem uma obrigação por obrigações menores; os casamentos cumprem obrigações. O autômato aceita quando não sobra obrigação nenhuma.

Essa leitura é a inversão exata do que acontecerá no módulo 11, com a análise ascendente, em que a pilha guarda o que já foi reconhecido. Duas estratégias, dois significados opostos para a mesma estrutura, e é útil ter os dois na cabeça antes de estudar o segundo.

Onde é fácil errar aqui. Empilhar o corpo da produção na ordem em que está escrito. O primeiro símbolo do corpo precisa terminar no topo, o que significa empilhar de trás para frente. Quem empilha na ordem direta obtém um autômato que reconhece a linguagem dos corpos invertidos — e, o que é pior, ele funciona para produções de um símbolo só, que costumam ser as primeiras testadas.

Como verificar. O autômato construído precisa aceitar exatamente as cadeias que a gramática deriva. Como cada expansão corresponde a uma aplicação de produção e cada casamento a um terminal já derivado, a sequência de expansões executadas em uma aceitação é precisamente uma derivação mais à esquerda. Conferir isso num exemplo é a tarefa 2.

1.3 Tarefa 2: O traçado manual

A atividade — traçar à mão o reconhecimento de um programa curto, mostrando o conteúdo da pilha a cada passo.

Tomei o menor programa Peneira que exercita uma declaração completa:

pattern email = /[a-z]+/;

O analisador léxico do módulo 7 o converte em cinco símbolos, que a gramática vê como os terminais pattern, ID, =, PADRAO e ;. O traçado abaixo mostra, a cada passo, o que resta na pilha (topo à esquerda), o que resta da entrada, e a transição aplicada.

Passo	Pilha (topo à esquerda)	Entrada restante	Transição
0	programa	pattern ID = PADRAO ;	início
1	listaDecl	pattern ID = PADRAO ;	expande programa -> listaDecl
2	decl	pattern ID = PADRAO ;	expande listaDecl -> decl
3	declPadrao	pattern ID = PADRAO ;	expande decl -> declPadrao
4	pattern ID = PADRAO ;	pattern ID = PADRAO ;	expande declPadrao -> pattern ID = PADRAO ;
5	ID = PADRAO ;	ID = PADRAO ;	casa pattern
6	= PADRAO ;	= PADRAO ;	casa ID
7	PADRAO ;	PADRAO ;	casa =
8	;	;	casa PADRAO
9	vazia	vazia	casa ;

Aceita, por pilha vazia, em nove passos. Quatro expansões e cinco casamentos — um casamento por terminal, como tem de ser.

Duas observações que o traçado torna concretas.

Os quatro primeiros passos não consomem nada da entrada. O autômato passa um bom tempo reorganizando a pilha antes de ler o primeiro símbolo. Isso é característico da estratégia descendente e é o que a distingue da ascendente: aqui, a decisão sobre qual produção usar é tomada antes de ver a evidência que a justificaria.

E a sequência de expansões — programa, listaDecl, decl, declPadrao — é exatamente a derivação mais à esquerda que o enumerador do módulo 8 produziu para este mesmo programa. Não é semelhança: é o mesmo objeto. O autômato de pilha, executando, é a derivação mais à esquerda sendo construída passo a passo.

1.3.1 Onde estão as adivinhações

O traçado acima parece determinístico, e não é. No passo 2, a variável listaDecl tem duas produções:

listaDecl -> decl listaDecl
listaDecl -> decl

Nada no topo da pilha distingue os dois casos, e o autômato não olhou a entrada — a transição de expansão não consome símbolo. Ele adivinha. No modelo não determinístico isso é legítimo: a máquina explora todos os caminhos ao mesmo tempo e aceita se algum der certo. Com uma declaração só, o caminho certo é o segundo; com duas, seria o primeiro.

A mesma adivinhação aparece no passo 3, entre declPadrao e blocoRegra, e apareceria dentro das expressões, entre os quatro tipos de primaria.

Repare no que resolveria cada uma delas. Para escolher entre declPadrao e blocoRegra, bastaria olhar um símbolo à frente: pattern indica o primeiro, rule o segundo. Para escolher entre as duas formas de listaDecl, bastaria saber se ainda há entrada. É isso que o módulo 10 vai formalizar com os conjuntos de primeiros e de seguidores, e é por isso que aquele módulo é a continuação direta deste, e não um assunto novo.

Onde é fácil errar aqui. Traçar o reconhecimento consultando a entrada nas expansões — isto é, escrevendo o traçado como se o autômato já fosse determinístico. O traçado fica certo e esconde exatamente o que o módulo quer mostrar. O honesto é registrar, em cada expansão com mais de uma produção possível, que houve escolha, e qual informação a teria dispensado.

Como verificar. O número de casamentos tem de ser igual ao número de terminais da entrada, e o número de expansões tem de ser igual ao número de nós internos da árvore de derivação. Neste exemplo, cinco e quatro — e a árvore que o módulo 8 desenhou tem exatamente quatro nós internos.

1.4 Tarefa 3: Determinismo, e o que ele custa

A atividade — discutir por que a análise sintática prática se restringe a subclasses determinísticas e o que isso implica para o módulo 10.

Aqui está o resultado que distingue este nível da hierarquia de tudo que veio antes, e ele contraria a intuição formada no módulo 5.

Lá, autômatos finitos determinísticos e não determinísticos se mostraram equivalentes: a construção de subconjuntos converte qualquer um no outro, e o preço é tamanho, não expressividade. Aqui, a equivalência não vale. Existem linguagens livres de contexto que nenhum autômato de pilha determinístico reconhece.

O exemplo canônico é a linguagem dos palíndromos de comprimento par sobre dois símbolos — cadeias formadas por uma parte seguida do seu reverso. Um autômato de pilha não determinístico a reconhece empilhando a primeira metade e desempilhando na segunda; o problema é saber onde é o meio. A máquina não determinística adivinha, e acerta em algum ramo. Uma máquina determinística teria de decidir com base no que já leu, e nenhuma informação local revela o ponto de virada.

A consequência prática é grande e é o que organiza os dois módulos seguintes. Como não sabemos executar não determinismo em tempo razoável, a análise sintática de verdade se restringe a subclasses determinísticas das linguagens livres de contexto. Isso significa aceitar de antemão que existem gramáticas legítimas que nenhum analisador prático vai tratar, e que a escolha da gramática é parte do projeto do compilador — não uma formalidade posterior.

É também a razão de existir uma família de métodos de análise, em vez de um só. As subclasses determinísticas formam uma escala, e cada método cobre uma faixa: os descendentes com um símbolo de antecipação cobrem menos, os ascendentes cobrem mais, e ainda assim nenhum cobre tudo. No módulo 5, um algoritmo resolvia o problema inteiro; daqui em diante, é preciso escolher.

1.4.1 A recursão à esquerda, e por que ela é fatal adiante

Esta é a descoberta que mais rende para o módulo 10, e ela sai do traçado.

A gramática da Peneira tem recursão à esquerda nas expressões, e por decisão consciente — foi ela que deu associatividade à esquerda aos operadores:

expr  -> expr or exprE | exprE

Trace o autômato de pilha sobre isso. Com expr no topo, uma das expansões possíveis põe de volta expr or exprE, com expr novamente no topo. Nada foi consumido da entrada, e o estado da pilha piorou. Nada impede que a máquina faça isso de novo, e de novo.

No modelo não determinístico isso não é problema. A definição de aceitação diz que basta algum ramo levar à aceitação, e o ramo que expande a quantidade certa de vezes existe. O ramo infinito também existe, e simplesmente não importa.

Numa implementação determinística, importa muito. Uma função que, para reconhecer uma expressão, começa chamando a si mesma sem antes consumir símbolo algum, não retorna nunca. É recursão infinita, e é o modo mais comum de o analisador descendente de um grupo travar na primeira execução.

Daí a ordem de trabalho do módulo 10: eliminar a recursão à esquerda antes de qualquer implementação. E daí, também, um custo que precisa ser aceito de olhos abertos — a transformação preserva a linguagem e muda as árvores. A gramática transformada não é mais à esquerda-recursiva, e a associatividade que a recursão à esquerda garantia terá de ser reconstruída na hora de montar a árvore sintática abstrata. O que era estrutura da gramática vira responsabilidade do código.

Registro isso aqui, no módulo 9, porque é agora que a razão fica clara. No módulo 10, no meio da transformação, ela pareceria um detalhe técnico.

1.5 Referência teórica: as duas convenções de aceitação

O modelo admite duas definições de aceitação — por estado final e por pilha vazia — e elas reconhecem a mesma classe de linguagens. A demonstração é uma construção em cada sentido, e vale saber que ela é mais sutil do que parece.

Para converter aceitação por pilha vazia em aceitação por estado final, não basta marcar como final o estado em que a pilha esvazia: é preciso um símbolo de fundo, empilhado antes de tudo, que só é retirado quando a pilha “real” já está vazia — e é a retirada dele que leva ao estado final. Sem o símbolo de fundo, o autômato aceitaria prefixos, porque a pilha passa por configurações vazias no meio do caminho em algumas gramáticas.

No sentido inverso, converter aceitação por estado final em pilha vazia exige um estado de limpeza que esvazia a pilha ao chegar num final, e de novo um símbolo de fundo — desta vez para impedir que o autômato original esvazie a pilha por acidente e aceite antes da hora.

A construção que usei na tarefa 1 aceita por pilha vazia, que é a mais natural quando se parte da gramática: a pilha guarda o que falta reconhecer, e não faltar nada é exatamente a condição de aceitação. Escolher a outra convenção teria exigido o símbolo de fundo e um estado a mais, sem ganho.

1.6 Referência teórica: o que a classe perde ao subir de nível

Duas propriedades que valiam para as linguagens regulares deixam de valer aqui, e a diferença é instrutiva.

A classe das linguagens livres de contexto é fechada sob união, concatenação e fecho, como a regular. Mas não é fechada sob interseção nem sob complemento.

O contraexemplo para a interseção é conhecido e vale reproduzir porque é limpo. A linguagem das cadeias com um número qualquer de letras c precedido por igual número de a e de b é livre de contexto — a pilha conta os a, desconta com os b, e os c passam livres. A linguagem simétrica, com um número qualquer de a seguido de igual número de b e c, também é. A interseção das duas exige contagem igual nos três, e essa não é livre de contexto: uma pilha só não conta duas coisas ao mesmo tempo.

Como a classe é fechada sob união, a não clausura sob interseção implica a não clausura sob complemento — se fosse fechada sob complemento, a interseção poderia ser obtida por complemento de união de complementos, e acabamos de ver que não pode.

Vale conectar com o módulo 6, porque a diferença tem consequência prática direta neste projeto. Lá implementei interseção e complemento sobre autômatos finitos, e as construções eram diretas: produto de estados para a interseção, inversão de finalidade para o complemento. Nenhuma das duas se estende para cá. O produto de dois autômatos de pilha precisaria de duas pilhas, e duas pilhas dão poder de máquina de Turing. A inversão de finalidade falha porque o autômato não determinístico pode ter ramos que aceitam e ramos que não, e negar isso não é negar a aceitação.

Se em algum momento o projeto precisar decidir inclusão ou equivalência entre gramáticas — coisa que o módulo 6 tornou trivial para expressões regulares —, a resposta é que não dá: equivalência de gramáticas livres de contexto é indecidível. A ferramenta que existe para o nível regular não tem contrapartida aqui, e saber disso evita procurar por ela.

1.7 Referência teórica: bombeamento no nível livre de contexto

O lema do bombeamento tem uma versão para esta classe, com uma diferença estrutural em relação à do módulo 6: em vez de um trecho bombeável, há dois, e eles são bombeados juntos e na mesma quantidade.

A intuição vem da árvore de derivação, não do autômato. Numa árvore suficientemente alta, algum caminho da raiz até uma folha repete uma variável — casa dos pombos de novo, agora sobre a altura em vez do comprimento. O trecho da árvore entre as duas ocorrências dessa variável pode ser removido ou duplicado quantas vezes se queira, e o que ele deriva à esquerda e à direita da subárvore interna são os dois trechos bombeados.

A consequência para o uso é que as demonstrações ficam mais trabalhosas: o adversário escolhe a decomposição em cinco partes, não em três, e há mais casos a descartar. Não implementei uma versão do decompositor do módulo 6 para este nível, e o motivo é o mesmo que justifica o módulo inteiro não ter código: seria uma ferramenta que nenhuma outra parte do compilador usaria. A decomposição do módulo 6 existia porque operava sobre os autômatos que o projeto já tinha.

1.8 Tarefa 4: O registro de pendências

A atividade — registrar o que foi saldado em pendências durante o módulo.

O módulo 9 é o último respiro antes do mais denso do semestre, e a entrega inclui o registro do que foi acertado. Auditei o projeto de referência e o estado é este.

O código está limpo: as trinta unidades de tradução compilam sem nenhum aviso sob o modo estrito, e as demonstrações dos oito módulos anteriores rodam. Os corpora das seis categorias léxicas passam integralmente, e a gramática do módulo 8 não tem símbolo inútil nem produção vazia.

A pendência de verdade foi saldada no módulo 7 e vale relembrá-la aqui, porque é o tipo de coisa que o registro existe para capturar: a notação de PONTUACAO estava escrita como prosa legível e reconhecia a linguagem errada, tendo atravessado cinco módulos sem ser executada. A correção mudou números publicados em dois documentos, que foram atualizados.

O que continua em aberto é de natureza editorial, não técnica: os documentos dos módulos 7 e 8 ainda não estão registrados nos perfis de publicação, o que significa que existem e não são gerados. Não afeta o código nem o conteúdo, e precisa ser resolvido antes de o material ir para a turma.

E há uma dívida deliberada, que registro como dívida e não como esquecimento: as decisões de precedência e associatividade tomadas no módulo 8 vão ser parcialmente desfeitas no módulo 10, pela eliminação da recursão à esquerda. A associatividade terá de ser reconstruída na montagem da árvore sintática abstrata. Está previsto, o motivo está escrito acima, e o custo é conhecido.

Onde é fácil errar aqui. Usar o registro de pendências como formalidade e escrever “nada pendente”. Um projeto de oito módulos sempre tem algo — e o valor do registro está justamente em nomear o que se escolheu adiar, para que a escolha não vire esquecimento.

1.9 Verificação da entrega

Item	Como conferir	Estado nesta referência
Tradução da gramática	Duas famílias de transição descritas, com a ordem de empilhamento correta	Atende
Traçado manual	Pilha e entrada a cada passo, com a transição aplicada	Nove passos, quatro expansões e cinco casamentos
Adivinhações identificadas	Cada expansão com mais de uma produção possível está marcada	Passos 2 e 3, com a informação que as resolveria
Correspondência com a derivação	Sequência de expansões igual à derivação mais à esquerda do módulo 8	Confirmado
Discussão sobre determinismo	Não equivalência enunciada, com exemplo e consequência prática	Atende
Consequência para o módulo 10	Recursão à esquerda identificada como fatal, com o motivo	Atende
Convenções de aceitação	As duas descritas, com a sutileza do símbolo de fundo	Atende
Propriedades de fechamento	O que se perde ao subir de nível, com contraexemplo	Atende
Registro de pendências	Auditoria honesta, incluindo dívida deliberada	Atende
Código de projeto	Nenhum, conforme a decisão registrada para este módulo	Nada foi criado

O que quero deixar registrado sobre esta entrega é que ela não produz artefato executável e mesmo assim é trabalho de projeto. O traçado de nove passos que fiz à mão é o analisador do módulo 10 rodando em câmera lenta, e as duas adivinhações que identifiquei nele são exatamente o que a antecipação de um símbolo vai eliminar. Quem chega ao módulo 10 tendo feito este traçado reconhece a estrutura do que vai implementar; quem pulou vai encontrar um algoritmo que parece surgir do nada.