1 Análise sintática ascendente — Projeto do Professor

Este é o projeto de referência do professor, e este capítulo é a segunda exceção do percurso: não há tarefa do Projeto Integrador a resolver aqui, e não há código novo a produzir. A decisão é declarada, não é omissão — o artefato segue o caminho descendente por inteiro, e construir uma segunda família completa de analisadores custaria mais do que renderia. O que se pede a cada grupo neste ponto é um argumento escrito e curto sobre a própria gramática: o que mudaria se a estratégia fosse a ascendente, que conflitos apareceriam e o que eles revelariam. É esse argumento que este documento demonstra, resolvido sobre a gramática do sistema de referência.

1.1 Visão Geral

Começo pela pergunta que o capítulo tem de responder antes de qualquer outra, porque ela é a pergunta que o estudante faz em silêncio: se o analisador já está pronto e funcionando, para que estudar a família que não vamos usar? A resposta é que a escolha entre as duas famílias foi feita por mim, no início do percurso, e até aqui ela foi uma decisão que o estudante herdou sem poder avaliar. Um profissional que só conhece uma estratégia não escolheu nada — ele fez a única coisa que sabia fazer. A competência deste capítulo é diagnóstica e comparativa, e ela se avalia.

Há uma segunda razão, e ela é a mais concreta das duas. A gramática natural da linguagem de referência — aquela que eu escreveria se ninguém me falasse de analisadores — é recursiva à esquerda, e é assim que ela está escrita no sistema até hoje. A produção da expressão é expr → expr OR andExpr; a lista de ações é acoes → acoes action. Essa forma é a que expressa diretamente a associatividade à esquerda dos dois operadores, e foi preciso deformá-la para que o analisador descendente pudesse trabalhar. Um analisador ascendente aceita a forma natural sem transformação alguma. O capítulo inteiro gira em torno dessa assimetria: uma família cobra a preparação da gramática, a outra cobra a construção da tabela — e é bom saber qual das duas dívidas se está contraindo.

O que faço aqui, então, é quatro coisas, e nenhuma delas envolve escrever código de sistema. Executo deslocamento e redução à mão sobre um fragmento real da nossa gramática, para que a mecânica seja vista antes de ser nomeada. Construo os primeiros conjuntos de itens da mesma gramática, para mostrar de onde a máquina tira a decisão de reduzir. Percorro as quatro famílias e digo o que separa uma da outra, sem transformar isso em taxonomia decorada. E leio um conflito real da nossa própria gramática ambígua — aquela que o sistema guarda desde o capítulo das gramáticas justamente para servir de contraexemplo — como o que ele é: informação sobre a linguagem, e não defeito da ferramenta.

Vale registrar de saída a assimetria de esforço, porque ela é o eixo do argumento comparativo que fecha o capítulo. No caminho descendente, o trabalho intelectual está antes do analisador: eliminar recursão à esquerda, fatorar prefixos comuns, calcular os conjuntos, verificar que a decisão local basta. Feito isso, o analisador é quase uma transcrição. No caminho ascendente, o trabalho está dentro da construção da tabela: a gramática entra como está, e é o algoritmo que descobre se ela serve. As duas quantidades de trabalho não são iguais, e a diferença tem nome — a segunda é automatizável, a primeira não é.

1.2 Deslocamento e redução, à mão

Antes de qualquer formalismo, executo a máquina. Uso a gramática estratificada que o sistema já guarda desde o capítulo das gramáticas — quatro produções de expressão e duas de átomo, todas recursivas à esquerda, exatamente na forma natural.

A gramática do exercício

\text{expr} \to \text{expr}\ \texttt{OR}\ \text{andExpr} \ \mid\ \text{andExpr} \text{andExpr} \to \text{andExpr}\ \texttt{AND}\ \text{primary} \ \mid\ \text{primary} \text{primary} \to \texttt{ID} \ \mid\ \texttt{NUMERO} Aumentada com \text{S}' \to \text{expr}, que é o que dá à máquina um critério de aceitação sem ambiguidade.

A máquina tem uma pilha e uma entrada, e a cada passo escolhe entre duas ações. Deslocar é empurrar o próximo símbolo da entrada para o topo da pilha. Reduzir é reconhecer que os símbolos no topo formam o corpo de uma produção e substituí-los pela cabeça. O trecho do topo que se reconhece assim tem nome — chama-se handle, e encontrá-lo é o problema inteiro. A tabela a seguir é a execução completa sobre a entrada ID OR ID, e cada linha é verificável à mão.

Pilha	Entrada restante	Ação
	ID OR ID	deslocar ID
ID	OR ID	reduzir \text{primary} \to \texttt{ID}
primary	OR ID	reduzir \text{andExpr} \to \text{primary}
andExpr	OR ID	reduzir \text{expr} \to \text{andExpr}
expr	OR ID	deslocar OR
expr OR	ID	deslocar ID
expr OR ID		reduzir \text{primary} \to \texttt{ID}
expr OR primary		reduzir \text{andExpr} \to \text{primary}
expr OR andExpr		reduzir \text{expr} \to \text{expr}\ \texttt{OR}\ \text{andExpr}
expr		aceitar

São três deslocamentos e seis reduções. Repare no que a coluna do meio revela: a redução final só acontece quando a entrada já acabou, e as três reduções em cadeia do começo acontecem sem que a máquina tenha olhado para o OR que vem depois — ela subiu de ID até expr com informação puramente local. Guarde esse ponto, porque é exatamente ali que os conflitos nascem: a máquina precisa decidir se reduz agora ou se espera mais um símbolo, e nem sempre a decisão é óbvia.

Compare agora com o que o analisador descendente faz sobre a mesma entrada. Lá, a árvore se constrói de cima para baixo: parte-se de expr, escolhe-se uma produção olhando o símbolo à frente, e desce-se até os terminais. Aqui a árvore se constrói de baixo para cima, das folhas para a raiz, e a produção só é escolhida depois que todo o corpo dela já está na pilha. Essa é a inversão que dá nome às duas famílias, e ela tem uma consequência que não é estética. Adiar a escolha da produção até ver o corpo inteiro é ter mais informação na hora de decidir — e é por isso que a família ascendente reconhece estritamente mais gramáticas.

E há o ponto que o capítulo prometeu. A gramática acima é recursiva à esquerda em duas produções, e a máquina não se incomodou. A recursão à esquerda, que para o analisador descendente é um laço infinito, aqui é apenas um símbolo que reaparece no fundo da pilha enquanto se empilha o resto. A transformação que o capítulo das gramáticas exigiu — e que deformou a forma natural — é, para esta família, trabalho que não precisaria ter sido feito.

1.3 Itens e a máquina que decide a redução

A execução acima foi feita por mim, com discernimento. Para automatizá-la é preciso responder de onde vem a decisão de reduzir, e a resposta é uma construção que vale conhecer porque é engenhosa.

Definição — item

Um item é uma produção com uma posição marcada no corpo, escrita A \to \alpha \cdot \beta. Ele significa: já vi \alpha na pilha e espero ver \beta na entrada. O item com o ponto no fim, A \to \alpha \cdot, indica que o corpo está completo e a redução é possível.

A ideia é que o conjunto de itens compatíveis com o que está na pilha é uma informação finita, e que essa informação pode ser mantida por um autômato finito — o mesmo tipo de máquina do primeiro arco da disciplina, agora rodando sobre símbolos da gramática em vez de caracteres do texto. É o reaproveitamento mais elegante do percurso: o autômato finito, que parecia ter esgotado seu papel na análise léxica, volta como o cérebro do analisador sintático.

O estado inicial se obtém por fecho. Parte-se de \text{S}' \to \cdot\, \text{expr} e, sempre que o ponto está antes de um não terminal, acrescentam-se todos os itens desse não terminal com o ponto no início. Sobre a nossa gramática o fecho inicial fica com sete itens: \text{S}' \to \cdot\,\text{expr}, as duas produções de expr com o ponto no início, as duas de andExpr, e as duas de primary. A leitura desses sete é direta e vale explicitá-la: no começo da análise, o que pode estar sendo iniciado é uma expressão, ou uma conjunção, ou um átomo — as três hipóteses convivem, e o autômato as carrega todas até que a entrada decida.

Os demais estados saem por transição: a partir de um conjunto, ler um símbolo da gramática avança o ponto em todos os itens em que ele aparece logo depois, e refaz-se o fecho. Lendo ID a partir do estado inicial chega-se a um estado com o item único \text{primary} \to \texttt{ID} \cdot — ponto no fim, corpo completo, redução disponível e nenhuma alternativa. Lendo expr chega-se a um estado com dois itens: \text{S}' \to \text{expr} \cdot, que autoriza aceitar, e \text{expr} \to \text{expr} \cdot \texttt{OR}\ \text{andExpr}, que autoriza deslocar o OR. Esses dois itens no mesmo estado são a forma técnica de dizer que a máquina precisa olhar o que vem à frente antes de concluir a análise, e é o primeiro lugar em que a antecipação aparece como necessidade, e não como conveniência.

A tabela de análise é a transcrição desse autômato: para cada estado e cada terminal, deslocar e ir a um estado, ou reduzir por uma produção; para cada estado e cada não terminal, o estado de destino após a redução. Uma célula com duas entradas é um conflito, e é o assunto da próxima seção.

1.4 As famílias e o que separa uma da outra

As famílias ascendentes se distinguem por uma única coisa: quanta informação a máquina consulta para decidir reduzir. É uma escala de refinamento em que cada degrau resolve um problema concreto do anterior.

O caso mais simples reduz sempre que o ponto chega ao fim, sem olhar a entrada. Funciona em pouquíssimas gramáticas reais, e falha exatamente onde a nossa falharia: um estado que contém ao mesmo tempo um item completo e um item que espera um terminal — como o par \text{S}' \to \text{expr}\cdot e \text{expr} \to \text{expr}\cdot\texttt{OR}\ \text{andExpr} que acabamos de encontrar — não tem como decidir sem antecipação.

O degrau seguinte acrescenta um símbolo de antecipação da forma mais barata possível: reduz por A \to \alpha apenas quando o símbolo à frente pertence ao conjunto dos seguidores de A. Aproveita os conjuntos que já calculamos para o caminho descendente, o que é conveniente, e resolve a maioria dos casos. Sua fraqueza é conhecida e vale entender, porque ela explica a existência dos dois degraus acima: o conjunto de seguidores é global, reúne todos os contextos em que A pode aparecer em qualquer lugar da gramática, e usá-lo num estado específico autoriza reduções que naquele contexto particular são impossíveis.

O degrau de maior alcance corrige isso levando o símbolo de antecipação para dentro do item: cada item passa a carregar o contexto em que aquela redução é válida, e a decisão deixa de ser global. Custa um número de estados que cresce rapidamente. O degrau intermediário — o que os geradores de uso corrente implementam — funde estados que diferem apenas nos símbolos de antecipação, recuperando o tamanho da tabela do degrau anterior com quase todo o poder do mais forte. O “quase” é honesto: a fusão pode introduzir conflitos de redução contra redução que não existiam, embora nunca introduza conflito de deslocamento contra redução.

O resultado que fecha a escala é de Knuth, de 1965, e já o mencionei no capítulo dos autômatos de pilha: 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. Isso faz da família ascendente o limite superior do que uma decisão local alcança — não há estratégia determinística de maior alcance já inventada. A família descendente que o nosso sistema usa é estritamente mais restrita, e a diferença não é pequena: gramáticas naturais e legíveis caem fora dela com facilidade, e caem dentro da outra sem retoque.

1.5 O conflito como diagnóstico

Chego ao ponto em que este capítulo entrega a competência que se avalia. O sistema guarda, desde o capítulo das gramáticas, uma gramática deliberadamente ambígua, que existe ali como contraexemplo — e ela serve agora para uma segunda finalidade.

A gramática ambígua do sistema

\text{expr} \to \text{expr}\ \texttt{AND}\ \text{expr} \ \mid\ \text{expr}\ \texttt{OR}\ \text{expr} \ \mid\ \text{primary} \text{primary} \to \texttt{ID} \ \mid\ \texttt{NUMERO}

Analise ID AND ID OR ID com a máquina da primeira seção e o problema aparece sozinho. Chega-se ao ponto em que a pilha contém expr AND expr e o símbolo à frente é OR. Duas ações são legítimas. Reduzir por \text{expr} \to \text{expr}\ \texttt{AND}\ \text{expr} agrupa a conjunção primeiro e produz a leitura em que AND liga mais forte. Deslocar o OR adia a redução e produz a leitura oposta. É um conflito de deslocamento contra redução, e ele é a ambiguidade da gramática aparecendo no relatório do gerador. A segunda leitura da mesma pilha, com AND à frente em vez de OR, é o mesmo conflito manifestando a falta de associatividade declarada.

Esta é a lição central do capítulo, e ela se enuncia numa frase: o gerador não está reclamando de si mesmo, está lhe contando um fato sobre a sua linguagem. A gramática estratificada da primeira seção — a que o sistema de fato usa — não produz nenhum desses conflitos, e o motivo é que a estratificação em três níveis já responde, na forma da gramática, às duas perguntas que o conflito fazia: quem liga mais forte, e para que lado uma cadeia de operadores iguais se agrupa. O conflito era a pergunta; a estratificação é a resposta escrita.

Há uma segunda espécie, o conflito de redução contra redução, e ele tem leitura diferente. Aparece quando duas produções distintas podem ser reduzidas no mesmo estado com o mesmo símbolo à frente, e quase sempre significa que a gramática usa dois não terminais para descrever a mesma coisa, ou que uma distinção que se quis fazer na sintaxe não é decidível ali — pertence à análise semântica. Trata-se de um sinal mais grave que o primeiro, porque raramente se resolve com precedência.

Decida antes de ler adiante. A pilha tem expr AND expr, o símbolo à frente é OR, e as duas ações são legítimas. Um gerador de analisadores encontra esse conflito ao construir a tabela. Ele para e exige que você escolha, ou escolhe sozinho? E, se escolhe, por qual das duas? Fixe as duas respostas antes de seguir.

E aqui está a decisão que os geradores tomam em silêncio, que é o que o capítulo pede que o estudante saiba. Diante de um conflito de deslocamento contra redução, um gerador típico não para: ele resolve a favor do deslocamento, emite um aviso e segue. O analisador sai pronto, roda, aceita programas — e adota uma associatividade que ninguém escolheu. As declarações de precedência e associatividade que essas ferramentas oferecem são exatamente um modo de tomar essa decisão explicitamente, em vez de deixá-la ao critério padrão. Ignorar a contagem de conflitos porque “compilou” é o erro mais caro que se comete com essas ferramentas, e ele é invisível até o dia em que uma expressão é avaliada ao contrário.

Executo esse dia, porque descrever a falha e vê-la acontecer são coisas diferentes. Retomo ID AND ID OR ID no ponto exato do conflito e deixo a resolução padrão agir:

Pilha	Entrada restante	Ação
expr AND expr	OR ID	conflito — o padrão desloca
expr AND expr OR	ID	deslocar ID
expr AND expr OR ID		reduzir \text{primary} \to \texttt{ID}
expr AND expr OR primary		reduzir \text{expr} \to \text{primary}
expr AND expr OR expr		reduzir \text{expr} \to \text{expr}\ \texttt{OR}\ \text{expr}
expr AND expr		reduzir \text{expr} \to \text{expr}\ \texttt{AND}\ \text{expr}
expr		aceitar

A análise termina, o analisador aceita a entrada e nenhum erro é reportado em tempo de execução. A árvore que ele construiu, porém, é ID AND (ID OR ID) — o OR foi agrupado primeiro, e a convenção que todo mundo carrega da matemática e de toda linguagem de programação diz o contrário.

O efeito na Peneira é uma emissão que some. Tome a ação

on numero(n) where value(n) > 100 and value(n) < 900 or n == "0" => emit("achado", n);

e a entrada contendo 0. A leitura pretendida é (value(n) > 100 and value(n) < 900) or n == "0", e por ela o 0 casa a terceira condição e sai na saída. A leitura que o analisador construiu é value(n) > 100 and (value(n) < 900 or n == "0"), e por ela o primeiro fator é falso — 0 não é maior que 100 — e a ação inteira falha. O 0 deixa de ser emitido, sem mensagem alguma. Quem escreveu a descrição vai procurar o defeito no padrão, na entrada e na condição, nesta ordem, e o defeito está na tabela do analisador.

A correção tem duas formas e vale saber qual é qual. A imediata é declarar a precedência e a associatividade à parte, o que faz o gerador resolver o conflito do jeito declarado em vez do jeito padrão. A estrutural é a estratificação em três níveis da primeira seção, que dissolve o conflito porque responde as duas perguntas na própria forma da gramática. A primeira conserta esta tabela; a segunda faz o problema deixar de existir, e é por isso que o sistema usa a gramática estratificada.

1.6 O argumento sobre a nossa gramática

O que se pede aos grupos neste capítulo é um argumento escrito e curto sobre a própria gramática. Resolvo aqui o mesmo exercício sobre a gramática do sistema de referência, e é este o modelo — o critério é a qualidade técnica do raciocínio, não a extensão do texto.

O que mudaria. A gramática voltaria à forma natural, e a mudança não é cosmética. As duas eliminações de recursão à esquerda seriam desfeitas: acoes → acoes action | ε e as três produções de expressão voltariam a expressar a associatividade à esquerda diretamente, em vez de codificá-la numa cauda recursiva à direita que o analisador percorre em laço. A estratificação em três níveis — expressão, conjunção, comparação — permaneceria, mas por outro motivo: ela deixaria de ser exigência técnica e passaria a ser escolha de legibilidade, já que a precedência poderia ser declarada à parte. A árvore construída seria a mesma, porque a árvore nunca foi a árvore de derivação.

Que conflitos apareceriam. Sobre a gramática estratificada, nenhum — e afirmo isso com base na estrutura, não em suposição: a estratificação resolve precedência e associatividade na forma da gramática, que é precisamente o que os conflitos apontariam. Sobre a gramática ambígua que o sistema guarda, os dois conflitos da seção anterior, ambos de deslocamento contra redução, ambos resolvidos por declaração de precedência. E há um terceiro ponto que mereceria atenção e que é mais sutil: a produção vazia da lista de ações, acoes → ε, obriga a máquina a decidir se reduz o vazio antes de ter visto qualquer ação — decisão que depende do símbolo à frente e que é exatamente o tipo de coisa que a família mais fraca da escala erra.

O que isso revela sobre a gramática. Revela que a nossa linguagem é folgada em relação ao que qualquer das duas famílias exige, e a razão é de projeto: cada construção começa com uma palavra reservada distinta — pattern, rule, on —, o que torna a decisão local trivial em qualquer estratégia. Uma linguagem projetada assim não distingue as famílias, e é honesto dizer isso em vez de fabricar uma superioridade. A distinção apareceria numa linguagem com construções que começam igual e divergem tarde, e é aí que a escolha passaria a ser técnica.

Por que, mesmo assim, o percurso é descendente. Porque o valor didático está no que se constrói à mão. Um analisador ascendente completo não se escreve à mão em tempo razoável, e usar um gerador colocaria a peça central do artefato dentro de uma caixa que ninguém abriu — o mesmo antipadrão que recusamos na análise léxica ao construir o autômato em vez de invocar uma biblioteca. A troca é declarada: aceitamos uma família mais restrita e uma gramática deformada em troca de um analisador cujo fluxo de controle é inteiramente legível. Essa é a resposta que eu espero de um grupo, com os termos trocados pelos da linguagem dele.

1.7 O que este capítulo entrega ao arco seguinte

No código não muda nada, e é a segunda vez que escrevo isso no percurso. Muda o estatuto de três coisas.

Muda o que significa “a gramática está pronta”. Até aqui, pronta queria dizer analisável pelo nosso analisador. Agora quer dizer analisável, e sabendo-se o preço da forma que se escolheu — as transformações do capítulo das gramáticas deixam de ser ritual e passam a ser a dívida de uma estratégia específica, contraída conscientemente.

Muda a leitura de uma ferramenta de terceiros. Quem chegar a um gerador de analisadores depois desta disciplina lê a saída dele: sabe o que uma contagem de conflitos significa, sabe que a resolução padrão toma uma decisão de projeto sem perguntar, e sabe que uma declaração de precedência é a forma de assumir essa decisão. É a diferença entre usar a ferramenta e ser usado por ela, e ela só existe porque o percurso construiu tudo à mão antes — o estudante sabe o que o gerador faria por ele porque já fez.

E fica registrado o limite que a análise sintática não ultrapassa, porque ele é a ponte para o capítulo seguinte. Nenhuma das duas famílias, por maior que seja o alcance dela, recusa uma ação que cita um padrão nunca declarado, ou um nome ligado que ninguém usa. As duas coisas são sintaticamente perfeitas em qualquer gramática que se escreva, e insistir em recusá-las na sintaxe produz uma gramática monstruosa que ainda assim não dá conta. O que falta é contexto, e contexto é o assunto do capítulo seguinte, com a tabela de símbolos que a árvore vinha esperando.

Onde é fácil errar. Ler a contagem de conflitos como um aviso de qualidade do gerador, do tipo que se silencia. Ela é uma medida da sua gramática, e cada unidade dela é uma decisão de projeto que a ferramenta tomou no seu lugar. Um analisador com dezessete conflitos resolvidos por omissão compila, roda e passa nos testes que quem o escreveu imaginou — a análise acima mostra em que condição ele começa a discordar de quem o escreveu.

Como verificar que está correta: pegue a gramática que você escreveu e, para cada operador binário dela, responda por escrito duas perguntas — quem liga mais forte, e para que lado uma cadeia de operadores iguais se agrupa. Depois procure, na forma da gramática, onde cada resposta está escrita. Resposta que você sabe dizer e não consegue apontar na gramática é um conflito esperando o gerador, e é você quem decide agora ou a ferramenta quem decide depois.