1 Módulo 11: Projeto do Professor — O Caminho que Não Tomamos
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 é um estudo comparativo aplicado à gramática do próprio grupo, 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 11
Este é o segundo e último módulo do semestre em que o projeto não recebe código novo, e a razão é diferente da do módulo 9. Lá, o autômato de pilha não virou código porque sua realização concreta viria no módulo seguinte. Aqui, o método estudado não vai virar código nunca — o projeto tomou o caminho descendente no módulo 10, à mão, e essa decisão está travada. Estudar o método ascendente é estudar a alternativa que descartamos.
Vale dizer de saída por que isso não é perda de tempo, porque é a pergunta que os grupos fazem. A família ascendente é a que a maioria dos compiladores de produção usa, e é a que está por trás de todo gerador de analisadores que um egresso vai encontrar. Quem nunca construiu uma tabela dessas à mão lê um relatório de conflito como quem lê horóscopo: sabe que algo está errado, não sabe o quê nem onde. Quem construiu uma, mesmo pequena, reconhece no relatório os itens, os estados e a decisão que não pôde ser tomada. É a diferença entre operar uma ferramenta e ser operado por ela.
A atividade pede três coisas encadeadas. Tomar um recorte pequeno da gramática do projeto — três ou quatro produções com algum ponto de decisão interessante —, construir à mão a tabela de análise ascendente e identificar os conflitos, se houver. Sobre essa base concreta, escrever a comparação entre as duas famílias aplicada ao caso do projeto. E, como a tutoria deste módulo já olha para o terceiro bloco, entregar o plano dos módulos 12 a 15 com divisão de trabalho.
Resolvi a atividade e o resultado me surpreendeu em um ponto que eu não previa. O recorte que escolhi foi o das expressões — justamente aquele que, no módulo 10, custou a transformação mais cara do semestre. A gramática ascendente o aceita sem transformação alguma. Não é que ela tolere a recursão à esquerda: ela a prefere. O que gastei uma tarefa inteira eliminando é, do outro lado, a forma canônica.
1.2 Tarefa 1: Escolher o recorte e construir o autômato de itens
A atividade — escolher três ou quatro produções da gramática do projeto com um ponto de decisão interessante e construir manualmente a coleção canônica de itens.
O recorte tem de ser pequeno o bastante para caber no papel e interessante o bastante para produzir uma decisão de verdade. Descartei a parte declarativa da gramática — declPadrao e blocoRegra são sequências fixas de terminais, e a tabela delas seria uma fileira de deslocamentos sem nenhuma decisão. Escolhi as expressões, e por três motivos: elas têm recursão à esquerda, elas têm dois níveis de precedência, e elas foram o ponto caro do módulo anterior. Se a comparação vai valer alguma coisa, tem de incidir sobre o lugar onde as duas famílias divergem.
O recorte, tomado da gramática do módulo 8 e reduzido ao mínimo que preserva o ponto de decisão:
(0) S' -> expr
(1) expr -> expr or exprE
(2) expr -> exprE
(3) exprE -> exprE and ID
(4) exprE -> IDDuas reduções honestas em relação à gramática original. A cadeia comparacao -> primaria -> ID foi colapsada em ID: ela acrescenta dois estados de redução encadeada e nenhuma decisão nova, e o custo de mantê-la seria papel, não entendimento. E a produção S' -> expr não estava na gramática — é o aumento, a produção artificial que todo método ascendente exige. Ela existe para que exista um único ponto de aceitação: reduzir por ela é o único jeito de terminar, e sem isso o analisador não saberia distinguir “terminei” de “reduzi ao símbolo inicial no meio do caminho”.
Antes da tabela, a mecânica. A estratégia ascendente lê a entrada da esquerda para a direita e reduz ao símbolo inicial, ao contrário do módulo 10, que partia do símbolo inicial e expandia. São duas operações e só duas. Deslocar empilha o próximo símbolo da entrada. Reduzir retira do topo da pilha os símbolos que formam o corpo de uma produção e coloca no lugar a variável do lado esquerdo. O analisador aceita quando a pilha contém apenas o símbolo inicial e a entrada acabou.
E aqui está a inversão que organiza o módulo inteiro, e que vale escrever no quadro ao lado do traçado do módulo 9: a pilha guarda o que já foi reconhecido. No método descendente ela guardava o que faltava reconhecer. Mesma estrutura, significado oposto. Quem carrega a intuição do módulo 9 para cá lê a pilha ao contrário e não entende nada; quem faz os dois traçados lado a lado sobre a mesma cadeia entende os dois de uma vez.
O trecho que se retira ao reduzir tem nome: alça. Formalmente, é a subcadeia que casa com o corpo de uma produção e cuja redução é um passo da derivação mais à direita percorrida ao contrário. A palavra importa porque o problema inteiro da análise ascendente se resume a uma pergunta: onde está a alça, e por qual produção reduzir. Não é óbvio — o topo da pilha pode casar com o corpo de várias produções ao mesmo tempo, e pode casar sem que aquele seja o momento de reduzir.
1.2.1 O autômato de itens
A resposta para “onde está a alça” é um autômato finito, e é uma das ideias mais bonitas do assunto: um autômato finito basta para reconhecer prefixos viáveis, isto é, para saber, a cada instante, quais produções ainda estão em jogo. A pilha guarda a informação de contexto ilimitado; os estados guardam a informação de posição.
Um item é uma produção com um ponto marcando o quanto dela já está na pilha. O item expr -> expr . or exprE diz: já reconheci a parte à esquerda do ponto, e espero o que está à direita. Um estado do autômato é um conjunto de itens — todas as posições em que o analisador pode plausivelmente estar. A construção tem duas operações. O fecho acrescenta, para todo item cujo ponto precede uma variável, todos os itens iniciais das produções daquela variável: se espero uma exprE, então espero também qualquer coisa por onde uma exprE possa começar. O desvio move o ponto sobre um símbolo e aplica o fecho ao resultado.
Partindo do fecho de S' -> . expr, a coleção canônica do recorte tem oito estados. Escrevi-os um a um:
| Estado | Itens | Desvios |
|---|---|---|
| 0 | S' -> . expr expr -> . expr or exprE expr -> . exprE exprE -> . exprE and ID exprE -> . ID |
expr→1, exprE→2, ID→3 |
| 1 | S' -> expr . expr -> expr . or exprE |
or→4 |
| 2 | expr -> exprE . exprE -> exprE . and ID |
and→5 |
| 3 | exprE -> ID . |
— |
| 4 | expr -> expr or . exprE exprE -> . exprE and ID exprE -> . ID |
exprE→6, ID→3 |
| 5 | exprE -> exprE and . ID |
ID→7 |
| 6 | expr -> expr or exprE . exprE -> exprE . and ID |
and→5 |
| 7 | exprE -> exprE and ID . |
— |
Repare nos estados 1, 2 e 6. Cada um deles contém um item completo — o ponto no fim, sinalizando que há uma alça pronta — e, ao mesmo tempo, um item que pede deslocamento. O autômato, sozinho, não decide. É exatamente aí que vive a diferença entre os quatro métodos da família, e é o assunto da tarefa seguinte.
Onde é fácil errar aqui. Esquecer o fecho ao construir o estado 4. Depois de deslocar or, é tentador escrever apenas expr -> expr or . exprE e parar, porque foi o único item que veio do estado anterior. Mas o ponto precede a variável exprE, e as duas produções de exprE têm de entrar. Sem elas, o estado não tem desvio por ID e o analisador trava na primeira expressão com or. É o erro mais comum na construção à mão, e ele produz um autômato que funciona para cadeias de um operando só.
Como verificar. Dois testes baratos. O primeiro é que todo estado alcançável por um desvio sobre um terminal t só contém itens cujo símbolo imediatamente antes do ponto é t — se aparecer um item que não satisfaz isso, o desvio foi calculado errado. O segundo é que o número de estados não pode passar do total de itens distintos da gramática; com cinco produções e corpos curtos, o teto é confortável, e oito estados está dentro dele.
1.3 Tarefa 2: A tabela, e o que cada nível da família resolve
A atividade — construir a tabela de análise, identificar e classificar os conflitos, e explicar sua origem.
A tabela tem duas metades. A metade de ação, indexada por estado e terminal, diz o que fazer: deslocar para um estado, reduzir por uma produção, aceitar, ou erro. A metade de desvio, indexada por estado e variável, diz para onde ir depois de uma redução. A metade de desvio sai direto do autômato da tarefa anterior, sem decisão nenhuma. Toda a dificuldade está na de ação.
1.3.1 O nível mais fraco, e por que ele falha
O método mais simples da família decide sem olhar a entrada: se o estado tem um item completo, reduz; se tem um item pedindo deslocamento, desloca. Aplicado ao nosso recorte, ele quebra em dois lugares.
No estado 2, o item expr -> exprE . manda reduzir e o item exprE -> exprE . and ID manda deslocar quando vier and. Sem olhar a entrada, não há como escolher. É um conflito de deslocamento-redução, e é o mais comum dos dois tipos. O estado 6 tem exatamente o mesmo problema, entre expr -> expr or exprE . e o mesmo item de deslocamento.
Dois conflitos, e ambos com a mesma origem: o autômato sabe que há uma alça possível e não sabe se ela é a alça agora. Falta informação, e a informação que falta é o próximo símbolo.
1.3.2 O nível seguinte: olhar um símbolo, e usar os seguidores
O refinamento é econômico e é o que torna o método utilizável à mão: só reduza por uma produção se o próximo símbolo da entrada puder legitimamente seguir a variável do lado esquerdo dela. Os conjuntos de seguidores são os mesmos que calculei no módulo 10 — a mesma ferramenta, reaproveitada por um método que decide de outro jeito.
Para o recorte, os seguidores são estes. expr é seguido por or, porque a produção expr -> expr or exprE põe or logo depois dele, e pelo fim de entrada, porque o aumento faz dele o símbolo inicial. exprE herda tudo que segue expr — pelas produções expr -> exprE e expr -> expr or exprE, em que exprE está no fim — e ganha and, pela produção exprE -> exprE and ID.
SEGUIDORES(expr) = { or, $ }
SEGUIDORES(exprE) = { or, and, $ }Agora os dois conflitos desaparecem, e desaparecem pelo mesmo motivo. No estado 2, a redução por expr -> exprE só é permitida quando o próximo símbolo está em SEGUIDORES(expr), isto é, or ou fim de entrada. O símbolo em disputa era and, que não está lá. Então em and só resta deslocar. O estado 6 resolve identicamente.
A tabela completa, oito estados por quatro terminais mais duas colunas de desvio:
| Estado | or |
and |
ID |
$ |
expr |
exprE |
|---|---|---|---|---|---|---|
| 0 | desloca 3 | 1 | 2 | |||
| 1 | desloca 4 | aceita | ||||
| 2 | reduz (2) | desloca 5 | reduz (2) | |||
| 3 | reduz (4) | reduz (4) | reduz (4) | |||
| 4 | desloca 3 | 6 | ||||
| 5 | desloca 7 | |||||
| 6 | reduz (1) | desloca 5 | reduz (1) | |||
| 7 | reduz (3) | reduz (3) | reduz (3) |
Vinte células preenchidas, zero conflitos. As células em branco são erro de sintaxe, e cada uma delas carrega a informação de qual símbolo era esperado ali — que é a matéria-prima de uma boa mensagem de erro.
E há um detalhe que vale nomear, porque ele decide a semântica da linguagem e passa despercebido. Nos estados 2 e 6, a coluna and ficou com deslocamento. Isso significa que, diante de a or b and c, o analisador escolhe continuar montando a exprE em vez de fechar a expr. O resultado é que and agrupa mais forte que or — a precedência que o módulo 8 codificou escrevendo dois níveis de variável aparece aqui como uma escolha de célula. Precedência, no método ascendente, é uma propriedade da tabela.
1.3.3 Traçado do reconhecimento
Tracei ID or ID and ID, que exercita os dois operadores e passa pelos dois estados que eram conflituosos.
| Passo | Pilha (base à esquerda) | Entrada restante | Ação |
|---|---|---|---|
| 0 | 0 |
ID or ID and ID $ |
desloca 3 |
| 1 | 0 ID 3 |
or ID and ID $ |
reduz (4), desvio para 2 |
| 2 | 0 exprE 2 |
or ID and ID $ |
reduz (2), desvio para 1 |
| 3 | 0 expr 1 |
or ID and ID $ |
desloca 4 |
| 4 | 0 expr 1 or 4 |
ID and ID $ |
desloca 3 |
| 5 | 0 expr 1 or 4 ID 3 |
and ID $ |
reduz (4), desvio para 6 |
| 6 | 0 expr 1 or 4 exprE 6 |
and ID $ |
desloca 5 |
| 7 | 0 expr 1 or 4 exprE 6 and 5 |
ID $ |
desloca 7 |
| 8 | 0 … and 5 ID 7 |
$ |
reduz (3), desvio para 6 |
| 9 | 0 expr 1 or 4 exprE 6 |
$ |
reduz (1), desvio para 1 |
| 10 | 0 expr 1 |
$ |
aceita |
Cinco deslocamentos, um para cada terminal da entrada, e cinco reduções, uma para cada aplicação de produção. O passo 6 é o que decide a precedência: a pilha tinha expr or exprE, que é uma alça válida para a produção (1), e o analisador não reduziu porque o próximo símbolo era and.
Vale confrontar com o traçado do módulo 9. Lá, os quatro primeiros passos não consumiam nada — o analisador reorganizava a pilha antes de ler o primeiro símbolo, decidindo qual produção usar antes de ver a evidência. Aqui é o oposto: o analisador lê primeiro e decide depois, e a produção (1) só é escolhida no passo 9, quando a expressão inteira já está na pilha. É essa postergação que dá à família ascendente o poder maior, e é ela também que torna a mensagem de erro mais difícil de escrever — quando o erro aparece, o analisador acumulou muito contexto e pouca expectativa.
1.3.4 Onde este nível ainda falha, e os dois acima dele
O uso dos seguidores é uma aproximação, e é generosa demais. Ele pergunta se o símbolo pode seguir a variável em algum lugar da gramática, quando a pergunta certa seria se ele pode segui-la naquele estado. Existem gramáticas em que a diferença importa, e nelas o método baseado em seguidores acusa conflito onde não há.
O nível acima corrige isso carregando, dentro de cada item, o conjunto de símbolos que podem segui-lo naquele contexto — informação mais fina, coleção de estados muito maior. O exemplo canônico dessa distinção é a gramática de atribuição com referência, discutida por Aho e outros em Compiladores: princípios, técnicas e ferramentas, em que o lado esquerdo e o lado direito de uma atribuição derivam a mesma coisa: o método por seguidores acusa um conflito de deslocamento-redução que o método com contexto por item resolve. Registro que a gramática da Peneira não exibe esse caso — ela não tem atribuição, e o recorte que construí é resolvido pelo nível mais barato. Digo isso porque a tentação de fabricar um exemplo próprio é grande, e um exemplo fabricado ensina errado.
O nível intermediário, que é o que os geradores de fato usam, funde estados do nível mais fino que diferem apenas nos conjuntos de contexto. Fica quase do tamanho da tabela barata e resolve quase tudo que a tabela cara resolve. O “quase” tem preço conhecido: a fusão pode criar conflitos de redução-redução que não existiam antes, e nunca cria conflitos de deslocamento-redução novos.
A leitura que quero que fique não é a das quatro tabelas. É a progressão: cada nível existe porque o anterior falhou em um caso concreto, e o custo sobe junto com o poder.
Onde é fácil errar aqui. Preencher a linha de um estado com item completo reduzindo em todos os terminais, por reflexo. É o método fraco disfarçado, e ele reintroduz os dois conflitos que os seguidores tinham resolvido. Cada redução tem de ser restrita ao conjunto de seguidores da variável reduzida — nas linhas 2 e 6 da tabela acima, é justamente a ausência de reduz na coluna and que faz o método funcionar.
Como verificar. Três invariantes, todos baratos. O número de deslocamentos em um traçado aceito é igual ao número de terminais da entrada. O número de reduções é igual ao número de passos da derivação mais à direita. E a sequência de reduções, lida ao contrário, é essa derivação: aqui, (4), (2), (4), (3), (1) invertida dá expr ⇒ expr or exprE ⇒ expr or exprE and ID ⇒ expr or ID and ID ⇒ exprE or ID and ID ⇒ ID or ID and ID, que é a derivação mais à direita da cadeia.
1.4 Tarefa 3: Fabricar um conflito, para saber lê-lo
A atividade — como o recorte saiu limpo, provocar deliberadamente os dois tipos de conflito e interpretar o diagnóstico.
O recorte que escolhi não tem conflito, e um estudo que para aí não cumpre o objetivo do módulo. Então provoquei os dois tipos, cada um por uma modificação plausível da linguagem — modificações que não estão na gramática do projeto e que registro como hipóteses de trabalho, não como parte dele.
1.4.1 Deslocamento-redução, por ambiguidade de operador
O módulo 8 tomou uma decisão deliberada: a comparação não é recursiva, e a > b > c é recusado como erro de sintaxe. Suponha que tivéssemos escrito o contrário, permitindo encadeamento:
comparacao -> comparacao OPREL comparacao | primariaEssa produção é ambígua — a > b > c tem duas árvores, uma agrupando à esquerda e outra à direita. Na tabela, a ambiguidade aparece como um estado que contém comparacao -> comparacao OPREL comparacao . junto com comparacao -> comparacao . OPREL comparacao, e o símbolo OPREL está tanto no conjunto de seguidores da variável reduzida quanto na posição de deslocamento. Conflito de deslocamento-redução, e desta vez ele não some com nenhum nível da família: nenhuma quantidade de antecipação resolve uma gramática ambígua, porque a indecisão não é falta de informação, é falta de resposta.
Há duas saídas. A primeira é reescrever a gramática desambiguando, que foi o que o módulo 8 fez ao usar dois níveis de variável para or e and. A segunda é declarar precedência e associatividade e deixar o gerador resolver a célula: associatividade à esquerda faz a célula virar redução, à direita faz virar deslocamento, e a declaração de não associatividade faz virar erro — que é precisamente a semântica que a gramática do projeto obteve estruturalmente, sem declarar nada.
Isso merece ser dito com clareza, porque é a lição de engenharia do módulo. Declaração de precedência não é atalho: é a mesma decisão, expressa em outro lugar. Quem declara sem entender o conflito está resolvendo por sorte, e o sintoma clássico é o analisador que compila sem aviso e aceita programas com significado errado.
1.4.2 O caso clássico: o condicional sem alternativa obrigatória
O exemplo de conflito de deslocamento-redução mais conhecido da literatura não vem de ambiguidade de operador, e vale enunciá-lo porque quem for programar em qualquer linguagem com condicionais vai encontrá-lo. Numa gramática em que o comando condicional tem a alternativa opcional — uma produção com a parte alternativa e outra sem —, a cadeia com dois condicionais aninhados e uma só alternativa é genuinamente ambígua: a alternativa pode pertencer ao condicional interno ou ao externo.
Na tabela, isso aparece como um estado que já tem o condicional interno completo na pilha e vê a palavra da alternativa à frente. Reduzir associa a alternativa ao condicional externo; deslocar associa ao interno. Nenhum nível da família resolve, de novo porque a gramática é ambígua e não porque falte antecipação.
A convenção universal das linguagens de programação é associar ao condicional mais próximo, o que corresponde a deslocar — e essa é, por sorte, exatamente a resolução padrão dos geradores. Daí a situação curiosa de o conflito mais famoso do assunto ser um que quase todo mundo resolve certo sem perceber, apenas ignorando o aviso. Registro que a Peneira não tem condicional, e portanto não exibe este conflito: a linguagem tem uma cláusula de condição sobre a regra, que é uma expressão e não um comando, sem alternativa alguma. Trago o caso porque ele é o vocabulário compartilhado da área, não porque o projeto o encontre.
1.4.3 Redução-redução, por sobreposição de categorias
Este é o tipo mais raro e quase sempre indica erro de projeto da gramática, não falta de poder do método. Suponha uma extensão em que a ação pudesse emitir diretamente o nome de um padrão declarado, e não só uma expressão:
acao -> on ID ( ID ) => emit ( TEXTO , nomePadrao ) ;
nomePadrao -> ID
primaria -> IDCom um ID no topo da pilha e ) à frente, o analisador tem duas reduções possíveis e nenhum critério: reduzir por nomePadrao -> ID ou por primaria -> ID. Ambas as variáveis podem ser seguidas por ) naquele ponto. Conflito de redução-redução.
O diagnóstico correto aqui não é aumentar o poder do método. É perceber que a gramática criou duas categorias sintaticamente indistinguíveis para a mesma forma superficial, e que a distinção entre elas é semântica — pertence à tabela de símbolos do módulo 12, não à sintaxe. A correção é fundir as duas produções e resolver a distinção depois. Este é o padrão geral: conflito de deslocamento-redução costuma ser questão de poder ou de precedência, conflito de redução-redução costuma ser questão de projeto.
1.4.4 Lendo o relatório de um gerador
Um gerador de analisadores ascendentes recebe a gramática e produz o código da tabela, e quando encontra conflitos ele os resolve por regra padrão — deslocamento vence redução, e entre duas reduções vence a produção escrita primeiro — e avisa. A linha de resumo é do tipo “N conflitos deslocamento/redução, M conflitos redução/redução”, e é onde a maioria dos usuários para de ler.
O que interessa está no relatório detalhado, que o gerador emite sob pedido em um arquivo à parte: ele lista cada estado com seus itens e, no estado conflituoso, a ação escolhida e a descartada. É o mesmo objeto da tarefa 1 — conjunto de itens com o ponto marcando a posição — impresso por um programa. Quem construiu à mão os oito estados do recorte abre esse relatório e reconhece a estrutura; quem não construiu vê uma parede.
O procedimento que recomendo, e que usei ao interpretar os dois conflitos fabricados acima, tem três passos. Localizar o estado citado no relatório e ler seus itens. Identificar, entre eles, o item completo e o item que pede deslocamento — ou os dois itens completos. E perguntar qual construção da linguagem põe o analisador naquele estado, reconstruindo um programa de exemplo que chegue lá. O terceiro passo é o que converte o conflito de sintoma em causa, e é o que quase ninguém faz.
Onde é fácil errar aqui. Aceitar a resolução padrão porque “compilou e os testes passam”. A resolução padrão do gerador é uma escolha arbitrária que só por acaso coincide com a intenção; quando não coincide, o analisador aceita a entrada e produz a árvore errada, e o defeito aparece três fases depois como um erro de semântica incompreensível.
Como verificar. Um conflito genuinamente resolvido some do relatório. Se o número de conflitos não caiu depois da correção, a correção não corrigiu nada — e conflitos silenciados por declaração de precedência continuam sendo decisões, que precisam estar documentadas com o motivo.
1.5 Tarefa 4: A comparação, aplicada a este projeto
A atividade — comparar as duas famílias quanto a poder, legibilidade, diagnóstico e manutenção, especificamente para a gramática da Peneira.
Uma comparação que valeria para qualquer projeto não demonstra entendimento. Então a minha parte de números concretos, colhidos do trabalho do módulo 10 e da tabela da tarefa 2.
1.5.1 Poder: o que a preparação da gramática custou
A gramática original tinha 22 produções e nenhuma produção vazia, escrita assim de propósito. Preparar essa gramática para a descida recursiva exigiu seis transformações — duas eliminações de recursão à esquerda e quatro fatorações —, elevou-a a 28 produções e introduziu cinco variáveis anuláveis que não existiam. A tabela resultante tem 49 células e zero conflitos; a tabela da gramática original, sem preparo, tinha 19 conflitos.
O método ascendente não teria pedido nenhuma dessas seis transformações. A recursão à esquerda, que era fatal na descida recursiva, é a forma preferida aqui: o traçado da tarefa 2 mostra a produção expr -> expr or exprE sendo reconhecida sem nenhum artifício, com a recursão consumida naturalmente pela pilha. E a fatoração mais cara do módulo 10 — o prefixo de quatro símbolos on ID ( ID ), comum às duas produções de acao — simplesmente não seria necessária: o método ascendente empilha os quatro símbolos e só decide entre where e => quando chega lá, porque ele decide depois de ver, não antes.
Este é o ganho concreto e mensurável: seis transformações, seis produções a mais e cinco anuláveis introduzidos, tudo isso é preço pago pela escolha descendente. Do outro lado, seria zero.
1.5.2 Custo: o que a escolha ascendente teria cobrado
O recorte de cinco produções produziu oito estados. Não vou estimar quantos estados a gramática completa produziria, porque não construí essa coleção e não tenho como saber — e chutar um número aqui seria exatamente o tipo de afirmação que este material não faz. O que posso afirmar com base no que construí é a escala do trabalho: cinco produções curtas custaram oito estados e uma tarde de papel. Vinte e duas produções, várias com corpos de sete e nove símbolos, estão fora do que se constrói à mão em prazo de semestre.
E aqui está o argumento decisivo, que não é sobre poder e sim sobre a restrição do projeto. A escolha ascendente, na prática, implica usar um gerador. A decisão de construir tudo à mão, sem gerador, não é capricho: ela existe para que cada peça do compilador seja código que os alunos escreveram e entendem. Adotar o método ascendente equivaleria a substituir a fase inteira por uma caixa cujo interior o curso não abre — e o front-end deixaria de ser o objeto de estudo para virar dependência.
1.5.3 Legibilidade e manutenção
Aqui a diferença é grande e favorece o caminho tomado. O analisador do módulo 10 tem uma função por variável da gramática, e a estrutura do código é a estrutura da gramática: quem lê a função reconhece a produção. Um analisador ascendente gerado é uma tabela numérica e um laço; a relação com a gramática existe, mas passa pelo arquivo de entrada do gerador, não pelo código.
Para manutenção isso se inverte em parte. Acrescentar uma construção à linguagem, no caminho descendente, exige reverificar à mão a condição de decisão com um símbolo — pode ser preciso fatorar de novo, e a transformação propaga. No caminho ascendente, acrescenta-se a produção e o gerador diz se quebrou. É a vantagem real da ferramenta: ela verifica o que aqui é verificado por disciplina.
1.5.4 Diagnóstico de erro
Este é o ponto em que o caminho descendente vence com folga, e é o que mais pesou na decisão. No módulo 10, cada função sabe o que está tentando reconhecer, e a mensagem sai naturalmente na forma “esperava tal coisa ao analisar tal construção”. A recuperação por sincronização também sai natural, porque cada função conhece os símbolos que a delimitam.
No método ascendente, quando o erro aparece o analisador está em um estado que representa várias produções ao mesmo tempo, e a mensagem honesta seria uma lista de terminais aceitáveis — informação verdadeira e pouco útil. Mensagens boas em analisadores gerados existem, e custam trabalho manual sobre os estados de erro, feito estado a estado.
1.5.5 O veredicto, com a restrição e sem ela
Com a restrição pedagógica de construir tudo à mão, a escolha descendente é a única viável, e as seis transformações são o preço aceito de olhos abertos.
Sem a restrição, e se a Peneira fosse produto em vez de material de curso, eu escolheria o caminho ascendente com gerador — pela ausência de transformações, pela verificação automática a cada mudança da gramática e pela liberdade de escrever a gramática na forma que expressa a semântica desejada, sem contorcê-la para caber no método. Investiria o tempo economizado exatamente onde o método é fraco: nas mensagens de erro.
O que não mudaria é a fronteira. A gramática continuaria sendo escrita à mão, as decisões de precedência continuariam sendo decisões de projeto, e o relatório de conflitos continuaria exigindo que alguém soubesse ler itens e estados. É por isso que este módulo não tem código e mesmo assim não é dispensável.
1.6 Tarefa 5: O plano do terceiro bloco
A atividade — planejar os módulos 12 a 15, com divisão de trabalho.
A tutoria deste módulo já olha para frente, e por um motivo estrutural: as três fases restantes dependem umas das outras de forma mais rígida do que as anteriores. Análise léxica e sintática podiam ser desenvolvidas com alguma independência; análise semântica, geração de código e execução, não. A tabela de símbolos que a semântica constrói é consumida pela geração de código, e o formato que a geração emite é o que a execução interpreta. Um formato mal decidido cedo custa retrabalho nas três.
O plano da referência tem quatro marcos e uma decisão adiantada.
A decisão adiantada é o formato do objeto emitido, que pertence formalmente ao módulo 13 e precisa estar acordada antes do 12. A razão é que a tabela de símbolos só sabe o que guardar depois que se sabe o que a geração vai precisar consultar. Deixar essa decisão para quando chegar a vez dela obriga a revisitar a tabela.
O módulo 12 constrói a tabela de símbolos com escopos aninhados e as verificações de declaração e de tipo sobre a árvore que o front-end já produz — inclusive a verificação de que o identificador ligado por uma cláusula de condição corresponde a um padrão declarado, que é o caso concreto de erro semântico mais provável em programas reais da linguagem. O módulo 13 fixa a representação intermediária e o modelo de execução. O módulo 14 emite o objeto: as tabelas de transição dos autômatos determinísticos e o código de pilha das regras. O módulo 15 fecha a execução ponta a ponta sobre entrada real, com casamento mais longo e ligação de variáveis.
Sobre divisão de trabalho, a orientação que dou aos grupos e que vale registrar: dividir por fase é o que parece natural e é o que dá errado neste bloco, justamente pelo acoplamento. Dividir por caminho de dados funciona melhor — uma frente cuida das estruturas que atravessam as três fases, outra cuida das verificações e da emissão, e as duas se encontram no formato acordado. E vale reservar o último módulo inteiro para integração e correção, sem função nova, porque o bloco só é demonstrável quando as três fases rodam juntas.
Onde é fácil errar aqui. Escrever o plano como cronograma de datas sem nomear as interfaces entre as partes. O plano útil é o que diz o que uma frente entrega para a outra e em que formato; o que só distribui módulos por nome não previne nenhum dos conflitos que ele deveria prevenir.
1.7 Verificação da entrega
| Item | Como conferir | Estado nesta referência |
|---|---|---|
| Recorte escolhido | Três a quatro produções, com ponto de decisão real | Cinco produções com o aumento, recursão à esquerda e dois níveis de precedência |
| Coleção de itens | Estados com itens e desvios, fecho aplicado | Oito estados, tabulados |
| Tabela de análise | Metades de ação e desvio, células de erro identificadas | Vinte células preenchidas |
| Conflitos identificados | Cada estado com item completo examinado | Dois no nível mais fraco, ambos deslocamento-redução, resolvidos pelos seguidores |
| Conflitos classificados | Os dois tipos exibidos e distinguidos por origem | Um de cada, provocados por modificação declarada como hipotética |
| Traçado | Pilha, entrada e ação a cada passo | Onze passos, cinco deslocamentos e cinco reduções |
| Correspondência com a derivação | Reduções lidas ao contrário formam a derivação mais à direita | Confirmado |
| Comparação específica | Números do próprio projeto, não afirmações genéricas | Seis transformações, 22 para 28 produções, cinco anuláveis, 49 células |
| Escala dos métodos | Cada nível motivado pelo conflito que o anterior não resolve | Atende, com o caso do nível fino atribuído à fonte e marcado como ausente nesta gramática |
| Leitura de relatório | Procedimento de três passos do resumo até a causa | Atende |
| Plano dos módulos 12 a 15 | Marcos, decisão adiantada e critério de divisão | 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 mede uma coisa difícil de medir: se o grupo entendeu o método que não implementou. A tabela de oito estados é a prova, porque não há como construí-la sem entender o que é um item, o que é o fecho e por que a redução precisa ser restrita. E a comparação que sai dela é a única honesta — quem escreve o texto comparativo antes de construir a tabela produz afirmações que valeriam para qualquer gramática, e é exatamente isso que a exigência da tabela existe para impedir.
Fica também o registro de uma inversão que vale carregar para o resto do curso. Passei o módulo 10 eliminando a recursão à esquerda, e o módulo 11 mostrando que ela era o problema de um método e a forma natural do outro. Nenhuma dificuldade que enfrentamos é dificuldade do problema; toda ela é dificuldade da abordagem escolhida. Saber qual é qual é o que distingue quem escolhe uma ferramenta de quem apenas usa a que aprendeu.