1 Gramáticas livres de contexto — Projeto do Professor
Este é o projeto de referência do professor — as tarefas do Projeto Integrador deste módulo resolvidas do começo ao fim, com as decisões justificadas uma a uma. É o modelo do que cada grupo deve produzir no próprio projeto, e existe para ser estudado, não copiado: a gramática é a da sua linguagem, e as transformações que ela vai exigir dependem do recorte que você fixou. O que se copia daqui é o método — escrever por extenso, medir o defeito em vez de suspeitar dele, e registrar a forma anterior ao lado da final.
1.1 Visão Geral
Este é o módulo de projeto do percurso, e o de maior risco de dívida silenciosa. Quase não há capacidade nova a acrescentar ao sistema: o produto do módulo é uma gramática correta, e uma gramática errada não quebra nada hoje. Ela quebra o analisador do módulo seguinte, que passará a tutoria inteira sendo depurado no lugar de ser construído — e o custo aparece dois módulos depois de a decisão errada ter sido tomada, que é a distância exata que impede a suspeita de cair no lugar certo.
A decisão que organiza a solução inteira cabe numa frase: a gramática é representada como dado, e não como um comentário ao lado do analisador. É essa escolha que torna verificável tudo o que as três tarefas pedem. Sendo dado, a gramática é percorrível — dá para perguntar a ela onde há recursão à esquerda, onde há prefixo comum, e quantas derivações distintas ela admite para uma mesma sentença. Sendo comentário, ela seria apenas uma promessa sobre o código ao lado, e a promessa se desfaz na primeira correção feita no código e não no comentário.
A consequência mais forte disso aparece na ambiguidade. Ela deixa de ser afirmada e passa a ser contada: o programa enumera as derivações de uma sentença, e duas derivações mais à esquerda distintas para a mesma sentença é a definição de ambiguidade. Na demonstração, a gramática de expressão escrita numa regra só devolve duas derivações e duas árvores para a and b or c; a versão estratificada devolve uma. Nada disso é dito ao leitor esperando que ele acredite.
O reconhecedor que faz essa contagem é uma busca com retrocesso, e não o analisador do módulo seguinte. A diferença é parte do argumento do módulo: aqui queremos todas as derivações, e encontrá-las custa exponencial; lá queremos uma, decidida localmente e sem retroceder — e é a gramática transformada aqui que torna essa decisão possível. Este módulo existe, entre outras coisas, para tornar visível o preço que o módulo seguinte deixa de pagar.
Todo o conteúdo teórico do módulo é coberto: a definição formal está na estrutura de dados; as derivações mais à esquerda e mais à direita são dois percursos da mesma árvore, e o programa produz os dois; a árvore de derivação é reconstruída e impressa; a ambiguidade é contada; a precedência e a associatividade aparecem como propriedades da forma das regras; e as três transformações preparatórias — eliminação de recursão à esquerda direta, eliminação da indireta e fatoração à esquerda — são implementadas, exercitadas e registradas com a forma anterior ao lado da final.
1.2 Tarefa 1: Escrever por extenso a gramática da sua linguagem
O que a tarefa pede
Escrever a gramática da linguagem que o seu sistema aceita, por extenso e por completo, sem recursão à esquerda e devidamente fatorada, com a precedência e a associatividade dos operadores expressas na própria estrutura das regras — e não em uma tabela à parte que o analisador teria de consultar. Esta é a etapa de projeto mais exigente do percurso: quase não há código a escrever, e é justamente por isso que ela costuma ser tratada como se fosse rápida. A gramática não descreve uma linguagem nova; descreve, com precisão que o texto do primeiro capítulo não tinha, a mesma linguagem fixada lá.
08_gramatica.h
// 08_gramatica.h — A gramática como dado, e as transformações que a preparam.
//
// Este é o arco de PROJETO do percurso. Quase não há capacidade nova a
// acrescentar ao sistema, e é justamente por isso que ele costuma ser tratado
// como se fosse rápido: o produto do arco é uma gramática correta, e uma
// gramática errada não quebra nada hoje — quebra o analisador do arco seguinte,
// que passará a tutoria inteira sendo depurado no lugar de ser construído.
//
// A DECISÃO CENTRAL DO ARQUIVO é representar a gramática como DADO, e não como
// um comentário ao lado do analisador. Sendo dado, ela é percorrível: dá para
// perguntar a ela onde há recursão à esquerda, onde há prefixo comum, quantas
// derivações ela admite para uma mesma sentença. Sendo comentário, ela seria
// apenas uma promessa sobre o código ao lado — e a promessa se desfaz na
// primeira correção feita no código e não no comentário.
//
// Uma consequência dessa escolha vale ser antecipada, porque ela é o que torna a
// ambiguidade demonstrável em vez de afirmada: com a gramática como dado, o
// programa ENUMERA as derivações de uma sentença. Duas derivações mais à
// esquerda distintas para a mesma sentença é a definição de ambiguidade, e
// contá-las é medir a ambiguidade em vez de suspeitar dela.
//
// O reconhecedor deste arquivo é uma BUSCA COM RETROCESSO, e não o analisador do
// arco seguinte. A diferença é de propósito: aqui queremos todas as derivações,
// e o custo de encontrá-las é exponencial; lá queremos uma, decidida localmente e
// sem retroceder, e é a gramática transformada aqui que torna essa decisão
// possível. Este arquivo existe, entre outras coisas, para tornar visível o preço
// que o arco seguinte deixa de pagar.
#ifndef PENEIRA_08_GRAMATICA_H
#define PENEIRA_08_GRAMATICA_H
#include <cstddef>
#include <string>
#include <vector>
namespace peneira {
// Uma forma sentencial é uma sequência de símbolos, terminais e não-terminais
// misturados. É o objeto que a derivação transforma passo a passo.
using FormaSentencial = std::vector<std::string>;
// Corpo vazio é a produção vazia. Não usamos um símbolo especial para ela: o
// vazio é a ausência de símbolos, e inventar um nome para a ausência produz o
// erro de tratá-la como símbolo em algum ponto do percurso.
struct Producao {
std::string cabeca;
FormaSentencial corpo;
};
class Gramatica {
public:
Gramatica() = default;
Gramatica(std::string inicial, std::vector<Producao> producoes);
const std::string& inicial() const;
const std::vector<Producao>& producoes() const;
// Um símbolo é não-terminal quando aparece como cabeça de alguma produção.
// Não há declaração à parte de terminais: a lista de produções já diz tudo,
// e uma declaração redundante seria mais um lugar para divergir.
bool ehNaoTerminal(const std::string& simbolo) const;
const std::vector<std::string>& naoTerminais() const;
std::vector<FormaSentencial> alternativasDe(const std::string& cabeca) const;
// Um não-terminal é anulável quando deriva a forma vazia. Precisamos disso
// para detectar recursão à esquerda escondida atrás de um prefixo que some.
bool ehAnulavel(const std::string& simbolo) const;
private:
void recalcular();
std::string inicial_;
std::vector<Producao> producoes_;
std::vector<std::string> naoTerminais_; // na ordem de primeira aparição
std::vector<std::string> anulaveis_;
};
std::string formatarSimbolos(const FormaSentencial& simbolos);
std::string formatarGramatica(const Gramatica& gramatica);
// --- diagnóstico -----------------------------------------------------------
// Os não-terminais com recursão à esquerda DIRETA: alguma alternativa começa
// pelo próprio não-terminal, eventualmente depois de um prefixo anulável.
std::vector<std::string> recursoesDiretas(const Gramatica& gramatica);
// Os ciclos de recursão à esquerda INDIRETA, cada um na ordem em que se fecha.
// É a forma que não se vê olhando uma produção por vez, e é por isso que ela
// costuma sobreviver a uma revisão feita a olho.
std::vector<std::vector<std::string>> ciclosIndiretos(const Gramatica& gramatica);
// Os pares de alternativas do mesmo não-terminal que compartilham prefixo, na
// forma "naoTerminal: prefixo". Prefixo comum é o que impede a decisão local do
// analisador do arco seguinte: diante do primeiro símbolo, ele não sabe qual das
// duas alternativas seguir.
std::vector<std::string> prefixosComuns(const Gramatica& gramatica);
// --- transformações --------------------------------------------------------
// O registro que a terceira tarefa pede: o motivo, a forma anterior e a forma
// final, lado a lado. Guardar só o resultado guarda o que o sistema precisa e
// perde o que a pessoa precisa quando a gramática mudar meses depois.
struct Transformacao {
std::string motivo;
std::string antes;
std::string depois;
};
// Precondição da eliminação, e ela é da teoria, não da implementação: a
// gramática não pode ter ciclo de produções unitárias. A da Peneira não tem.
Gramatica eliminarRecursaoAEsquerda(const Gramatica& gramatica,
std::vector<Transformacao>& registro);
Gramatica fatorarAEsquerda(const Gramatica& gramatica,
std::vector<Transformacao>& registro);
std::string formatarTransformacoes(const std::vector<Transformacao>& registro);
// --- derivação --------------------------------------------------------------
struct PassoDeDerivacao {
// Vazio no passo zero, que é a forma sentencial inicial e não vem de
// aplicação de produção alguma.
std::string cabeca;
FormaSentencial corpo;
FormaSentencial forma;
std::string producaoAplicada() const;
};
using Derivacao = std::vector<PassoDeDerivacao>;
struct BuscaDeDerivacoes {
std::vector<Derivacao> derivacoes;
std::size_t expansoes = 0;
bool orcamentoEsgotado = false;
};
// Enumera derivações mais à esquerda da sequência de terminais, até `maximo`.
// Duas poda o espaço de busca: o orçamento de expansões, que é a rede de
// segurança, e a contagem de terminais ainda pendentes na pilha — nenhuma
// derivação válida pode ter mais terminais por casar do que entrada restante, e
// é essa poda que faz uma gramática recursiva à esquerda terminar aqui.
BuscaDeDerivacoes derivar(const Gramatica& gramatica,
const std::vector<std::string>& entrada, std::size_t maximo,
std::size_t orcamento);
std::string formatarDerivacao(const Derivacao& derivacao);
// --- a árvore, e as duas ordens de derivação --------------------------------
//
// A árvore de derivação é o registro da ESTRUTURA, e a ordem em que as produções
// foram aplicadas não faz parte dela. É por isso que a mesma árvore devolve tanto
// a derivação mais à esquerda quanto a mais à direita: as duas são percursos
// diferentes do mesmo objeto. Quem confunde ordem de derivação com estrutura
// conclui que existem duas análises onde existe uma, e não reconhece a
// ambiguidade quando ela de fato aparece — que é o caso de duas ÁRVORES.
struct NoDeDerivacao {
std::string simbolo;
std::vector<std::size_t> filhos;
// Um não-terminal que derivou a forma vazia não tem filhos, e sem esta marca
// seria indistinguível de um terminal na hora de refazer o percurso.
bool expandido = false;
};
struct ArvoreDeDerivacao {
std::vector<NoDeDerivacao> nos;
std::size_t raiz = 0;
};
// Refaz a árvore a partir de uma derivação mais à esquerda.
ArvoreDeDerivacao arvoreDe(const Gramatica& gramatica, const Derivacao& derivacao);
// O mesmo objeto percorrido pela direita: a cada passo expande-se o não-terminal
// mais à direita da forma sentencial.
Derivacao derivacaoMaisADireita(const ArvoreDeDerivacao& arvore);
std::string formatarArvoreDeDerivacao(const ArvoreDeDerivacao& arvore);
// --- as gramáticas desta linguagem -----------------------------------------
// A gramática da Peneira escrita POR EXTENSO, sem açúcar de repetição. É a forma
// de partida da tarefa, e é nela que a recursão à esquerda aparece — o `*` da
// notação do primeiro arco não a elimina, apenas a esconde.
Gramatica gramaticaPorExtenso();
// A gramática de expressão escrita da forma ambígua, para contraste. Uma única
// regra com o operador no meio, sem estratificação: aceita a mesma linguagem e
// admite mais de uma derivação para a mesma sentença.
Gramatica gramaticaAmbigua();
// O recorte estratificado da expressão, ainda recursivo à esquerda. A
// estratificação é o que carrega a precedência: cada nível só chama o de baixo.
Gramatica gramaticaEstratificada();
// Gramática de bolso com recursão à esquerda INDIRETA, para exercitar o caso que
// a da Peneira não tem. Sem ela, o ramo indireto da eliminação seria código não
// exercitado, que é código não verificado.
Gramatica gramaticaComRecursaoIndireta();
} // namespace peneira
#endif // PENEIRA_08_GRAMATICA_H08_gramatica.cpp
#include "08_gramatica.h"
#include <algorithm>
#include <sstream>
namespace peneira {
namespace {
bool contem(const std::vector<std::string>& lista, const std::string& item) {
return std::find(lista.begin(), lista.end(), item) != lista.end();
}
std::string preencher(const std::string& texto, const std::size_t largura) {
std::string saida = texto;
while (saida.size() < largura) {
saida += ' ';
}
return saida;
}
// A tabela de trabalho das transformações: cabeça e alternativas, na ordem em
// que serão impressas. Trabalhamos sobre ela e reconstruímos a gramática ao
// final, porque as duas transformações inserem não-terminais no meio da lista e
// mexer na lista de produções diretamente embaralharia a ordem de leitura.
using Entrada = std::pair<std::string, std::vector<FormaSentencial>>;
using Tabela = std::vector<Entrada>;
Tabela tabelaDe(const Gramatica& gramatica) {
Tabela tabela;
for (const std::string& nome : gramatica.naoTerminais()) {
tabela.emplace_back(nome, gramatica.alternativasDe(nome));
}
return tabela;
}
Gramatica gramaticaDe(const std::string& inicial, const Tabela& tabela) {
std::vector<Producao> producoes;
for (const Entrada& entrada : tabela) {
for (const FormaSentencial& alternativa : entrada.second) {
producoes.push_back(Producao{entrada.first, alternativa});
}
}
return Gramatica{inicial, producoes};
}
std::size_t indiceDe(const Tabela& tabela, const std::string& nome) {
for (std::size_t i = 0; i < tabela.size(); ++i) {
if (tabela[i].first == nome) {
return i;
}
}
return tabela.size();
}
std::string formatarAlternativas(const std::string& nome,
const std::vector<FormaSentencial>& alternativas) {
std::ostringstream saida;
for (std::size_t i = 0; i < alternativas.size(); ++i) {
saida << (i == 0 ? nome + " := " : std::string(nome.size() + 1, ' ') + "| ");
saida << formatarSimbolos(alternativas[i]);
if (i + 1 < alternativas.size()) {
saida << '\n';
}
}
return saida.str();
}
// O primeiro conjunto de não-terminais que podem encabeçar uma alternativa,
// atravessando prefixos anuláveis. É o que transforma "olhar o primeiro símbolo"
// em detecção correta: sem atravessar o anulável, uma recursão à esquerda
// escondida atrás de um prefixo que some passa despercebida.
std::vector<std::string> cabecalhosDe(const Gramatica& gramatica,
const FormaSentencial& alternativa) {
std::vector<std::string> cabecalhos;
for (const std::string& simbolo : alternativa) {
if (!gramatica.ehNaoTerminal(simbolo)) {
break;
}
if (!contem(cabecalhos, simbolo)) {
cabecalhos.push_back(simbolo);
}
if (!gramatica.ehAnulavel(simbolo)) {
break;
}
}
return cabecalhos;
}
std::size_t comprimentoDoPrefixoComum(const FormaSentencial& primeira,
const FormaSentencial& segunda) {
std::size_t i = 0;
while (i < primeira.size() && i < segunda.size() && primeira[i] == segunda[i]) {
++i;
}
return i;
}
std::string nomeLivre(const Tabela& tabela, const std::string& base) {
std::string candidato = base + "'";
while (indiceDe(tabela, candidato) != tabela.size()) {
candidato += "'";
}
return candidato;
}
// A busca por derivações mais à esquerda. A pilha guarda a parte não derivada da
// forma sentencial, com o símbolo mais à esquerda no fim do vetor.
struct Buscador {
const Gramatica& gramatica;
const std::vector<std::string>& entrada;
std::size_t maximo = 1;
std::size_t orcamento = 0;
BuscaDeDerivacoes resultado;
FormaSentencial casados;
Derivacao caminho;
void expandir(const FormaSentencial& pilha, std::size_t posicao);
};
void Buscador::expandir(const FormaSentencial& pilha, const std::size_t posicao) {
if (resultado.derivacoes.size() >= maximo || resultado.orcamentoEsgotado) {
return;
}
// A poda que faz uma gramática recursiva à esquerda terminar aqui: nenhuma
// derivação válida tem mais terminais por casar do que entrada restante.
std::size_t terminaisPendentes = 0;
for (const std::string& simbolo : pilha) {
if (!gramatica.ehNaoTerminal(simbolo)) {
++terminaisPendentes;
}
}
if (terminaisPendentes > entrada.size() - posicao) {
return;
}
if (pilha.empty()) {
if (posicao == entrada.size()) {
resultado.derivacoes.push_back(caminho);
}
return;
}
const std::string topo = pilha.back();
FormaSentencial resto(pilha.begin(), pilha.end() - 1);
if (!gramatica.ehNaoTerminal(topo)) {
if (posicao < entrada.size() && entrada[posicao] == topo) {
casados.push_back(topo);
expandir(resto, posicao + 1);
casados.pop_back();
}
return;
}
for (const FormaSentencial& alternativa : gramatica.alternativasDe(topo)) {
if (++resultado.expansoes > orcamento) {
resultado.orcamentoEsgotado = true;
return;
}
FormaSentencial nova = resto;
for (std::size_t i = alternativa.size(); i > 0; --i) {
nova.push_back(alternativa[i - 1]);
}
PassoDeDerivacao passo;
passo.cabeca = topo;
passo.corpo = alternativa;
passo.forma = casados;
for (std::size_t i = nova.size(); i > 0; --i) {
passo.forma.push_back(nova[i - 1]);
}
caminho.push_back(passo);
expandir(nova, posicao);
caminho.pop_back();
}
}
} // namespace
// --- Gramatica --------------------------------------------------------------
Gramatica::Gramatica(std::string inicial, std::vector<Producao> producoes)
: inicial_(std::move(inicial)), producoes_(std::move(producoes)) {
recalcular();
}
void Gramatica::recalcular() {
naoTerminais_.clear();
for (const Producao& producao : producoes_) {
if (!contem(naoTerminais_, producao.cabeca)) {
naoTerminais_.push_back(producao.cabeca);
}
}
// Ponto fixo dos anuláveis: um não-terminal é anulável se alguma alternativa
// é vazia ou tem todos os símbolos anuláveis. Repetimos até nada mudar.
anulaveis_.clear();
bool mudou = true;
while (mudou) {
mudou = false;
for (const Producao& producao : producoes_) {
if (contem(anulaveis_, producao.cabeca)) {
continue;
}
bool todosAnulaveis = true;
for (const std::string& simbolo : producao.corpo) {
if (!contem(naoTerminais_, simbolo) || !contem(anulaveis_, simbolo)) {
todosAnulaveis = false;
break;
}
}
if (todosAnulaveis) {
anulaveis_.push_back(producao.cabeca);
mudou = true;
}
}
}
}
const std::string& Gramatica::inicial() const { return inicial_; }
const std::vector<Producao>& Gramatica::producoes() const { return producoes_; }
const std::vector<std::string>& Gramatica::naoTerminais() const { return naoTerminais_; }
bool Gramatica::ehNaoTerminal(const std::string& simbolo) const {
return contem(naoTerminais_, simbolo);
}
bool Gramatica::ehAnulavel(const std::string& simbolo) const {
return contem(anulaveis_, simbolo);
}
std::vector<FormaSentencial> Gramatica::alternativasDe(const std::string& cabeca) const {
std::vector<FormaSentencial> alternativas;
for (const Producao& producao : producoes_) {
if (producao.cabeca == cabeca) {
alternativas.push_back(producao.corpo);
}
}
return alternativas;
}
std::string formatarSimbolos(const FormaSentencial& simbolos) {
if (simbolos.empty()) {
return "ε";
}
std::string saida;
for (std::size_t i = 0; i < simbolos.size(); ++i) {
if (i > 0) {
saida += ' ';
}
saida += simbolos[i];
}
return saida;
}
std::string formatarGramatica(const Gramatica& gramatica) {
std::ostringstream saida;
for (const std::string& nome : gramatica.naoTerminais()) {
saida << formatarAlternativas(nome, gramatica.alternativasDe(nome)) << '\n';
}
return saida.str();
}
// --- diagnóstico ------------------------------------------------------------
// recorte:inicio recursao-direta-detectada
std::vector<std::string> recursoesDiretas(const Gramatica& gramatica) {
std::vector<std::string> encontradas;
for (const std::string& nome : gramatica.naoTerminais()) {
for (const FormaSentencial& alternativa : gramatica.alternativasDe(nome)) {
if (contem(cabecalhosDe(gramatica, alternativa), nome) &&
!contem(encontradas, nome)) {
encontradas.push_back(nome);
}
}
}
return encontradas;
}
// recorte:fim recursao-direta-detectada
std::vector<std::vector<std::string>> ciclosIndiretos(const Gramatica& gramatica) {
std::vector<std::vector<std::string>> ciclos;
// recorte:inicio recursao-indireta-e-um-ciclo
// Busca em profundidade sobre o grafo "pode começar por": um ciclo de
// comprimento maior que um é recursão à esquerda indireta.
for (const std::string& raiz : gramatica.naoTerminais()) {
// Percurso iterativo simples: como as gramáticas aqui são pequenas,
// enumeramos caminhos e registramos quando fechamos sobre a raiz.
struct Estado {
std::string nome;
std::vector<std::string> caminho;
};
std::vector<Estado> aVisitar{Estado{raiz, {raiz}}};
// recorte:fim recursao-indireta-e-um-ciclo
while (!aVisitar.empty()) {
const Estado atual = aVisitar.back();
aVisitar.pop_back();
for (const FormaSentencial& alternativa : gramatica.alternativasDe(atual.nome)) {
for (const std::string& proximo : cabecalhosDe(gramatica, alternativa)) {
if (proximo == raiz && atual.caminho.size() > 1) {
std::vector<std::string> ciclo = atual.caminho;
ciclo.push_back(raiz);
// Só registramos o ciclo a partir do menor nome, para não
// listar a mesma volta uma vez por ponto de partida.
if (*std::min_element(ciclo.begin(), ciclo.end() - 1) == raiz) {
ciclos.push_back(ciclo);
}
continue;
}
if (contem(atual.caminho, proximo)) {
continue;
}
Estado seguinte{proximo, atual.caminho};
seguinte.caminho.push_back(proximo);
aVisitar.push_back(seguinte);
}
}
}
}
return ciclos;
}
// recorte:inicio prefixo-comum-entre-alternativas
std::vector<std::string> prefixosComuns(const Gramatica& gramatica) {
std::vector<std::string> achados;
for (const std::string& nome : gramatica.naoTerminais()) {
const std::vector<FormaSentencial> alternativas = gramatica.alternativasDe(nome);
for (std::size_t i = 0; i < alternativas.size(); ++i) {
for (std::size_t j = i + 1; j < alternativas.size(); ++j) {
const std::size_t comum =
comprimentoDoPrefixoComum(alternativas[i], alternativas[j]);
if (comum == 0) {
continue;
}
const FormaSentencial prefixo(alternativas[i].begin(),
alternativas[i].begin() +
static_cast<std::ptrdiff_t>(comum));
achados.push_back(nome + ": " + formatarSimbolos(prefixo));
}
}
}
return achados;
}
// recorte:fim prefixo-comum-entre-alternativas
// --- transformações ---------------------------------------------------------
Gramatica eliminarRecursaoAEsquerda(const Gramatica& gramatica,
std::vector<Transformacao>& registro) {
Tabela tabela = tabelaDe(gramatica);
const std::vector<std::string> ordem = gramatica.naoTerminais();
for (std::size_t i = 0; i < ordem.size(); ++i) {
const std::size_t indiceI = indiceDe(tabela, ordem[i]);
// Substituição: toda alternativa de Ai que comece por um Aj já tratado é
// trocada pelas alternativas de Aj. É este passo que traz a recursão
// indireta para a superfície, onde a eliminação direta a alcança.
for (std::size_t j = 0; j < i; ++j) {
const std::size_t indiceJ = indiceDe(tabela, ordem[j]);
std::vector<FormaSentencial> substituidas;
bool mudou = false;
for (const FormaSentencial& alternativa : tabela[indiceI].second) {
if (!alternativa.empty() && alternativa[0] == ordem[j]) {
mudou = true;
for (const FormaSentencial& deJ : tabela[indiceJ].second) {
FormaSentencial nova = deJ;
nova.insert(nova.end(), alternativa.begin() + 1, alternativa.end());
substituidas.push_back(nova);
}
} else {
substituidas.push_back(alternativa);
}
}
if (mudou) {
Transformacao transformacao;
transformacao.motivo = "substituicao de " + ordem[j] + " em " + ordem[i] +
" (expoe a recursao indireta)";
transformacao.antes =
formatarAlternativas(ordem[i], tabela[indiceI].second);
tabela[indiceI].second = substituidas;
transformacao.depois =
formatarAlternativas(ordem[i], tabela[indiceI].second);
registro.push_back(transformacao);
}
}
// Eliminação direta: A := A α1 | ... | β1 | ... vira
// A := β1 A' | ... e A' := α1 A' | ... | ε.
std::vector<FormaSentencial> recursivas;
std::vector<FormaSentencial> demais;
for (const FormaSentencial& alternativa : tabela[indiceI].second) {
// recorte:inicio separar-recursivas-das-demais
if (!alternativa.empty() && alternativa[0] == ordem[i]) {
recursivas.push_back(FormaSentencial(alternativa.begin() + 1,
alternativa.end()));
} else {
demais.push_back(alternativa);
}
// recorte:fim separar-recursivas-das-demais
}
if (recursivas.empty()) {
continue;
}
// recorte:inicio transformacao-com-motivo-registrado
const std::string novoNome = nomeLivre(tabela, ordem[i]);
Transformacao transformacao;
transformacao.motivo = "recursao a esquerda direta em " + ordem[i];
transformacao.antes = formatarAlternativas(ordem[i], tabela[indiceI].second);
// recorte:fim transformacao-com-motivo-registrado
std::vector<FormaSentencial> novasDeI;
for (const FormaSentencial& beta : demais) {
FormaSentencial nova = beta;
nova.push_back(novoNome);
novasDeI.push_back(nova);
}
std::vector<FormaSentencial> novasDoAuxiliar;
for (const FormaSentencial& alfa : recursivas) {
FormaSentencial nova = alfa;
nova.push_back(novoNome);
novasDoAuxiliar.push_back(nova);
}
novasDoAuxiliar.push_back(FormaSentencial{});
tabela[indiceI].second = novasDeI;
tabela.insert(tabela.begin() + static_cast<std::ptrdiff_t>(indiceI) + 1,
Entrada{novoNome, novasDoAuxiliar});
transformacao.depois = formatarAlternativas(ordem[i], novasDeI) + "\n" +
formatarAlternativas(novoNome, novasDoAuxiliar);
registro.push_back(transformacao);
}
return gramaticaDe(gramatica.inicial(), tabela);
}
Gramatica fatorarAEsquerda(const Gramatica& gramatica,
std::vector<Transformacao>& registro) {
Tabela tabela = tabelaDe(gramatica);
bool mudou = true;
std::size_t rodadas = 0;
while (mudou && rodadas < 100) {
mudou = false;
++rodadas;
for (std::size_t indice = 0; indice < tabela.size() && !mudou; ++indice) {
const std::vector<FormaSentencial>& alternativas = tabela[indice].second;
// O prefixo mais longo compartilhado por ao menos duas alternativas.
std::size_t melhor = 0;
FormaSentencial prefixo;
for (std::size_t i = 0; i < alternativas.size(); ++i) {
for (std::size_t j = i + 1; j < alternativas.size(); ++j) {
const std::size_t comum =
comprimentoDoPrefixoComum(alternativas[i], alternativas[j]);
if (comum > melhor) {
melhor = comum;
prefixo.assign(alternativas[i].begin(),
alternativas[i].begin() +
static_cast<std::ptrdiff_t>(comum));
}
}
}
if (melhor == 0) {
continue;
}
std::vector<FormaSentencial> comPrefixo;
std::vector<FormaSentencial> semPrefixo;
for (const FormaSentencial& alternativa : alternativas) {
if (alternativa.size() >= melhor &&
std::equal(prefixo.begin(), prefixo.end(), alternativa.begin())) {
comPrefixo.push_back(FormaSentencial(
alternativa.begin() + static_cast<std::ptrdiff_t>(melhor),
alternativa.end()));
} else {
semPrefixo.push_back(alternativa);
}
}
const std::string nome = tabela[indice].first;
const std::string novoNome = nomeLivre(tabela, nome);
Transformacao transformacao;
transformacao.motivo = "prefixo comum em " + nome + ": " +
formatarSimbolos(prefixo);
transformacao.antes = formatarAlternativas(nome, alternativas);
FormaSentencial fatorada = prefixo;
fatorada.push_back(novoNome);
std::vector<FormaSentencial> novasDeNome{fatorada};
novasDeNome.insert(novasDeNome.end(), semPrefixo.begin(), semPrefixo.end());
tabela[indice].second = novasDeNome;
tabela.insert(tabela.begin() + static_cast<std::ptrdiff_t>(indice) + 1,
Entrada{novoNome, comPrefixo});
transformacao.depois = formatarAlternativas(nome, novasDeNome) + "\n" +
formatarAlternativas(novoNome, comPrefixo);
registro.push_back(transformacao);
mudou = true;
}
}
return gramaticaDe(gramatica.inicial(), tabela);
}
std::string formatarTransformacoes(const std::vector<Transformacao>& registro) {
std::ostringstream saida;
for (std::size_t i = 0; i < registro.size(); ++i) {
saida << "[" << i + 1 << "] " << registro[i].motivo << "\n\n";
saida << " antes:\n";
std::istringstream antes(registro[i].antes);
std::string linha;
while (std::getline(antes, linha)) {
saida << " " << linha << '\n';
}
saida << " depois:\n";
std::istringstream depois(registro[i].depois);
while (std::getline(depois, linha)) {
saida << " " << linha << '\n';
}
saida << '\n';
}
return saida.str();
}
// --- derivação --------------------------------------------------------------
BuscaDeDerivacoes derivar(const Gramatica& gramatica,
const std::vector<std::string>& entrada, const std::size_t maximo,
const std::size_t orcamento) {
Buscador buscador{gramatica, entrada, maximo, orcamento, BuscaDeDerivacoes{}, {}, {}};
const FormaSentencial inicial{gramatica.inicial()};
PassoDeDerivacao primeiro;
primeiro.forma = inicial;
buscador.caminho.push_back(primeiro);
buscador.expandir(inicial, 0);
return buscador.resultado;
}
std::string PassoDeDerivacao::producaoAplicada() const {
if (cabeca.empty()) {
return "(forma inicial)";
}
return cabeca + " := " + formatarSimbolos(corpo);
}
std::string formatarDerivacao(const Derivacao& derivacao) {
std::ostringstream saida;
for (std::size_t i = 0; i < derivacao.size(); ++i) {
saida << preencher("[" + std::to_string(i) + "]", 6)
<< preencher(formatarSimbolos(derivacao[i].forma), 62) << " "
<< derivacao[i].producaoAplicada() << '\n';
}
return saida.str();
}
// --- a árvore, e as duas ordens de derivação ---------------------------------
ArvoreDeDerivacao arvoreDe(const Gramatica& gramatica, const Derivacao& derivacao) {
ArvoreDeDerivacao arvore;
if (derivacao.empty() || derivacao.front().forma.size() != 1) {
return arvore;
}
arvore.nos.push_back(NoDeDerivacao{derivacao.front().forma.front(), {}, false});
arvore.raiz = 0;
// Os não-terminais ainda por expandir, com o mais à esquerda no fim do vetor.
// Como a derivação é mais à esquerda, o alvo de cada passo é exatamente o
// topo desta lista — refazer a árvore é consumir a derivação em ordem.
std::vector<std::size_t> pendentes{0};
for (std::size_t i = 1; i < derivacao.size() && !pendentes.empty(); ++i) {
const std::size_t alvo = pendentes.back();
pendentes.pop_back();
arvore.nos[alvo].expandido = true;
std::vector<std::size_t> naoTerminaisFilhos;
for (const std::string& simbolo : derivacao[i].corpo) {
arvore.nos.push_back(NoDeDerivacao{simbolo, {}, false});
const std::size_t indice = arvore.nos.size() - 1;
arvore.nos[alvo].filhos.push_back(indice);
if (gramatica.ehNaoTerminal(simbolo)) {
naoTerminaisFilhos.push_back(indice);
}
}
// Só os não-terminais voltam para a lista, invertidos para que o mais à
// esquerda fique no topo. Terminal é folha e nunca é expandido.
for (std::size_t k = naoTerminaisFilhos.size(); k > 0; --k) {
pendentes.push_back(naoTerminaisFilhos[k - 1]);
}
}
return arvore;
}
Derivacao derivacaoMaisADireita(const ArvoreDeDerivacao& arvore) {
Derivacao derivacao;
if (arvore.nos.empty()) {
return derivacao;
}
std::vector<std::size_t> fronteira{arvore.raiz};
PassoDeDerivacao primeiro;
primeiro.forma = FormaSentencial{arvore.nos[arvore.raiz].simbolo};
derivacao.push_back(primeiro);
while (true) {
std::size_t posicao = fronteira.size();
for (std::size_t i = fronteira.size(); i > 0; --i) {
if (arvore.nos[fronteira[i - 1]].expandido) {
posicao = i - 1;
break;
}
}
if (posicao == fronteira.size()) {
break;
}
const std::size_t alvo = fronteira[posicao];
PassoDeDerivacao passo;
passo.cabeca = arvore.nos[alvo].simbolo;
for (const std::size_t filho : arvore.nos[alvo].filhos) {
passo.corpo.push_back(arvore.nos[filho].simbolo);
}
fronteira.erase(fronteira.begin() + static_cast<std::ptrdiff_t>(posicao));
fronteira.insert(fronteira.begin() + static_cast<std::ptrdiff_t>(posicao),
arvore.nos[alvo].filhos.begin(), arvore.nos[alvo].filhos.end());
for (const std::size_t indice : fronteira) {
passo.forma.push_back(arvore.nos[indice].simbolo);
}
derivacao.push_back(passo);
}
return derivacao;
}
namespace {
void escreverArvore(const ArvoreDeDerivacao& arvore, const std::size_t indice,
const std::string& recuo, std::ostringstream& saida) {
saida << recuo << arvore.nos[indice].simbolo;
if (arvore.nos[indice].expandido && arvore.nos[indice].filhos.empty()) {
saida << " -> ε";
}
saida << '\n';
for (const std::size_t filho : arvore.nos[indice].filhos) {
escreverArvore(arvore, filho, recuo + " ", saida);
}
}
} // namespace
std::string formatarArvoreDeDerivacao(const ArvoreDeDerivacao& arvore) {
std::ostringstream saida;
if (!arvore.nos.empty()) {
escreverArvore(arvore, arvore.raiz, " ", saida);
}
return saida.str();
}
// --- as gramáticas desta linguagem ------------------------------------------
Gramatica gramaticaPorExtenso() {
// Os terminais são os nomes de categoria que o reconhecedor de símbolos
// entrega. Não há um segundo vocabulário: a gramática fala exatamente a
// língua que a fase anterior produz, e é isso que torna as duas encaixáveis.
const std::vector<Producao> producoes{
{"program", {"program", "decl"}},
{"program", {}},
{"decl", {"patternDecl"}},
{"decl", {"ruleBlock"}},
{"patternDecl", {"PATTERN", "ID", "IGUAL", "REGEX", "PONTO_VIRGULA"}},
{"ruleBlock", {"RULE", "ABRE_CHAVE", "acoes", "FECHA_CHAVE"}},
{"acoes", {"acoes", "action"}},
{"acoes", {}},
{"action",
{"ON", "ID", "ABRE_PAR", "ID", "FECHA_PAR", "WHERE", "expr", "SETA", "EMIT",
"ABRE_PAR", "TEXTO", "VIRGULA", "expr", "FECHA_PAR", "PONTO_VIRGULA"}},
{"action",
{"ON", "ID", "ABRE_PAR", "ID", "FECHA_PAR", "SETA", "EMIT", "ABRE_PAR", "TEXTO",
"VIRGULA", "expr", "FECHA_PAR", "PONTO_VIRGULA"}},
{"expr", {"expr", "OR", "andExpr"}},
{"expr", {"andExpr"}},
{"andExpr", {"andExpr", "AND", "cmpExpr"}},
{"andExpr", {"cmpExpr"}},
{"cmpExpr", {"primary", "comparador", "primary"}},
{"cmpExpr", {"primary"}},
{"comparador", {"MENOR"}},
{"comparador", {"MAIOR"}},
{"comparador", {"MENOR_IGUAL"}},
{"comparador", {"MAIOR_IGUAL"}},
{"comparador", {"IGUAL_IGUAL"}},
{"comparador", {"DIFERENTE"}},
{"primary", {"ID"}},
{"primary", {"NUMERO"}},
{"primary", {"TEXTO"}},
{"primary", {"VALUE", "ABRE_PAR", "ID", "FECHA_PAR"}},
{"primary", {"ABRE_PAR", "expr", "FECHA_PAR"}},
};
return Gramatica{"program", producoes};
}
Gramatica gramaticaAmbigua() {
const std::vector<Producao> producoes{
{"expr", {"expr", "AND", "expr"}},
{"expr", {"expr", "OR", "expr"}},
{"expr", {"primary"}},
{"primary", {"ID"}},
{"primary", {"NUMERO"}},
};
return Gramatica{"expr", producoes};
}
Gramatica gramaticaEstratificada() {
const std::vector<Producao> producoes{
{"expr", {"expr", "OR", "andExpr"}},
{"expr", {"andExpr"}},
{"andExpr", {"andExpr", "AND", "primary"}},
{"andExpr", {"primary"}},
{"primary", {"ID"}},
{"primary", {"NUMERO"}},
};
return Gramatica{"expr", producoes};
}
Gramatica gramaticaComRecursaoIndireta() {
const std::vector<Producao> producoes{
{"S", {"A", "a"}},
{"S", {"b"}},
{"A", {"S", "c"}},
{"A", {"d"}},
};
return Gramatica{"S", producoes};
}
} // namespace peneiraA primeira descoberta da tarefa foi que a forma registrada no primeiro capítulo não servia, e não pela razão que se esperaria. Ela usa açúcar de repetição: uma sequência de declarações é escrita como declaração seguida de asterisco, uma sequência de comparações ligadas pelo mesmo operador é escrita como o operando seguido do grupo repetido. Escrita assim, a gramática parece não ter recursão à esquerda.
Essa aparência é o problema. O asterisco é uma abreviação, e a abreviação corresponde a uma regra recursiva — ele não consta da definição de gramática livre de contexto. A expressão escrita por extenso vira uma alternativa que começa pelo próprio não-terminal, que é recursão à esquerda pela definição. A recursão sempre esteve lá; o que o açúcar fazia era escondê-la de quem lê, e é por isso que a tarefa pede a forma por extenso: é a forma em que o defeito é visível.
O programa mede a diferença. Sobre a gramática por extenso, o diagnóstico acusa recursão à esquerda direta em quatro não-terminais e prefixo comum em dois — seis problemas que a forma abreviada não mostrava e que nenhuma revisão a olho encontraria com confiança, porque encontrar recursão indireta olhando uma produção por vez é uma tarefa em que o erro é o resultado normal.
Uma decisão de projeto merece destaque, porque ela é o que faz as duas fases encaixarem. Os terminais da gramática são os nomes de categoria que o reconhecedor de símbolos entrega, e não um segundo vocabulário inventado aqui. Não há tradução no meio, não há tabela de correspondência a manter, e a sequência que a busca de derivações consome vem direto da fase anterior. Um segundo vocabulário seria mais uma coisa a manter em acordo, e a divergência entre os dois só apareceria quando um símbolo fosse renomeado de um lado só.
Onde é fácil errar. Escrever a gramática que se gostaria de ter em vez da que a linguagem tem. É tentador simplificar uma regra difícil “por enquanto”, e a simplificação sobrevive: o analisador do módulo seguinte é construído contra a gramática escrita, e passa a recusar programas que a linguagem sempre aceitou. Como verificar que está correta: derive com ela o exemplo escrito à mão no primeiro capítulo. Se não derivar, ou a gramática está errada, ou o exemplo está fora do recorte — e as duas descobertas custam uma tarde agora e um módulo depois.
1.3 Tarefa 2: Derivar o exemplo passo a passo
O que a tarefa pede
Exibir a derivação completa, passo a passo, do exemplo escrito à mão no primeiro capítulo a partir da gramática que você acabou de escrever. É a verificação que não admite atalho: uma gramática que não deriva o próprio exemplo de referência está errada, ou o exemplo está fora do recorte, e as duas descobertas são baratas agora e caras depois que o analisador existir.
A tarefa é uma verificação, e por isso ela virou teste, e não figura. A demonstração lê o exemplo do primeiro capítulo, o entrega ao reconhecedor de símbolos do capítulo anterior, toma a sequência de quarenta e seis categorias que sai de lá e a deriva com a gramática preparada. Quarenta e dois passos, cento e oito expansões tentadas pela busca, uma derivação. O dia em que a gramática mudar e deixar de derivar o exemplo, ou passar a derivá-lo de duas maneiras, a reconstrução acusa.
Vale explicar as duas exigências separadamente, porque elas verificam coisas diferentes. Derivar o exemplo verifica que a gramática aceita o que a linguagem deve aceitar. Derivá-lo de uma única maneira verifica que ela não é ambígua naquela sentença — e as duas juntas são a condição de saída deste módulo.
A busca que produz a derivação merece uma nota, porque o modo como ela funciona é o argumento do módulo. Ela expande sempre o não-terminal mais à esquerda, tenta as alternativas na ordem, e retrocede quando o caminho não casa a entrada. Isso é um analisador — é o mais ingênuo que existe, e ele funciona para qualquer gramática livre de contexto, ambígua ou não, recursiva à esquerda ou não. O preço é o retrocesso, que no pior caso é exponencial no tamanho da entrada, e o custo real está impresso na saída: cento e oito expansões para quarenta e seis símbolos, com a gramática preparada. É pouco justamente porque a gramática foi preparada.
Duas podas fazem a busca terminar, e uma delas é mais interessante do que parece. A primeira é o orçamento de expansões, que é rede de segurança e nada mais. A segunda é a contagem de terminais ainda pendentes: nenhuma derivação válida tem mais terminais por casar do que entrada restante. Essa poda é o que permite executar a busca sobre uma gramática recursiva à esquerda sem laço infinito — e é por isso que a demonstração consegue contar as derivações da gramática ambígua, que é recursiva à esquerda por natureza e cuja versão sem recursão não teria a mesma ambiguidade a exibir.
Onde é fácil errar. Conferir a derivação por leitura em vez de por execução. Uma derivação escrita à mão num relatório é conferida pelo autor, que sabe o que quis escrever, e a passagem defeituosa é justamente a que ele lê rápido porque tem certeza. Como verificar que está correta: faça a derivação ser produzida pelo programa a partir da gramática que o programa guarda. Se as duas coisas forem o mesmo dado, não há como divergirem.
1.4 Tarefa 3: Registrar cada transformação aplicada
O que a tarefa pede
Para cada transformação aplicada à gramática — eliminação de recursão à esquerda, fatoração, ajuste de precedência —, registrar a forma anterior ao lado da forma final. É a comparação que torna a transformação compreensível meses depois, quando a gramática precisar mudar e ninguém mais lembrar por que aquela regra tem a forma estranha que tem. Registrar apenas o resultado guarda o que o sistema precisa e perde o que você precisa.
docs/08_gramatica.md
# A gramática da Peneira: a forma de partida, as transformações e por que cada uma
Registro escrito das decisões deste arco. O programa emite a gramática por extenso, as
transformações com a forma anterior ao lado da final e a derivação do exemplo de referência — tudo
mecanicamente, e por isso sem risco de envelhecer. O que **não** se deriva de código é o motivo de
cada transformação, e é ele que este documento guarda.
## Por que a forma do primeiro arco não servia
A gramática registrada no primeiro arco usa açúcar de repetição: `program := decl*`,
`ruleBlock := "rule" "{" action* "}"`, `expr := andExpr ( "or" andExpr )*`. Escrita assim, ela parece
não ter recursão à esquerda — e essa aparência é exatamente o problema.
O `*` não é um operador da definição de gramática livre de contexto. Ele é uma abreviação, e a
abreviação corresponde a uma regra recursiva. Escrever `expr := andExpr ( "or" andExpr )*` por
extenso dá `expr := expr "or" andExpr | andExpr`, que é recursiva à esquerda. A recursão sempre
esteve lá; o que o açúcar fazia era escondê-la de quem lê.
Daí a primeira tarefa pedir a gramática **por extenso**: é a forma em que o defeito é visível. O
programa detecta recursão à esquerda direta em quatro não-terminais (`program`, `acoes`, `expr`,
`andExpr`) e prefixo comum em dois (`action`, `cmpExpr`) — seis problemas que a forma abreviada não
mostrava.
## Por que a recursão à esquerda precisa sair
Não por elegância, e não porque a gramática esteja errada: ela descreve exatamente a linguagem
pretendida, e um analisador ascendente a trataria sem reclamar. O motivo é a estratégia de análise
adotada no arco seguinte.
Um analisador descendente decide qual regra aplicar **antes** de consumir qualquer símbolo. Diante de
`expr := expr "or" andExpr`, a primeira coisa que ele faria para reconhecer `expr` é tentar
reconhecer `expr` — sem ter consumido nada, no mesmo ponto do texto. É recursão infinita, e ela não
aparece como resultado errado: aparece como pilha estourada, o que faz o defeito parecer de
implementação quando é de gramática.
A transformação troca recursão à esquerda por recursão à direita, e o preço tem nome:
**a associatividade sai da gramática**. A forma `expr := expr "or" andExpr` agrupa à esquerda por
construção; a forma transformada `expr := andExpr expr'` com `expr' := "or" andExpr expr' | ε` não
agrupa — ela apenas enfileira. As duas aceitam a mesma linguagem, e é por isso que a transformação é
legítima; mas a árvore que o analisador construir a partir da segunda precisa **restaurar** o
agrupamento à esquerda explicitamente. Isso é dívida deste arco a ser paga no seguinte, e está
registrada aqui para não ser descoberta lá.
## Por que o prefixo comum precisa sair
Mesmo motivo, causa diferente. As duas alternativas de `action` começam com os mesmos cinco símbolos,
e a diferença entre elas está no sexto. Um analisador que decide olhando um símbolo à frente não tem
como escolher: os dois caminhos começam igual.
A fatoração adia a decisão até o ponto em que ela é possível. Depois dela, `action` tem uma
alternativa só — o prefixo comum seguido de `action'` — e `action'` decide entre `where` e a seta,
que são distinguíveis pelo primeiro símbolo. A escolha não desapareceu; foi movida para onde há
informação para fazê-la.
O caso de `cmpExpr` é o mesmo com uma diferença que vale notar: uma das duas alternativas era o
prefixo inteiro, e o sufixo dela é vazio. A fatoração produz `cmpExpr' := comparador primary | ε`, e
a produção vazia é a resposta correta para "não havia comparação nenhuma". Produção vazia não é
lacuna a preencher.
## Por que a precedência não é uma tabela
O contraste que o programa executa: a gramática de expressão escrita numa regra só
(`expr := expr op expr | primary`) admite **duas** derivações mais à esquerda distintas para
`a and b or c`, e as duas correspondem a agrupamentos diferentes — logo, a resultados diferentes.
A gramática estratificada, com um nível por precedência, admite **uma**.
A precedência, então, é uma propriedade da **forma das regras**, e não um dado à parte que o
analisador consultaria. Cada nível chama apenas o de baixo, e é a ordem dos níveis que decide o
agrupamento. Uma tabela de precedência ao lado de uma gramática ambígua descreve o que se pretendia;
a gramática estratificada descreve o que acontece.
A escolha de níveis desta linguagem é `or` no topo, `and` abaixo, comparação abaixo dela, e o átomo
no fundo — a mesma ordem das linguagens correntes, e ela não foi inventada aqui: mudá-la
surpreenderia quem escreve na Peneira, e surpresa é o custo que não se paga por uma decisão de
sintaxe.
## Ambiguidade não se elimina em geral
Vale registrar o limite, porque ele explica por que a verificação deste arco é experimental e não uma
prova. Não existe procedimento que decida se uma gramática livre de contexto qualquer é ambígua — o
problema é indecidível. O que existe são construções conhecidas que **produzem** gramáticas não
ambíguas para casos frequentes, e a estratificação por precedência é uma delas.
Por isso a verificação aqui é: enumerar as derivações de sentenças concretas e contar. Uma contagem
igual a um não prova que a gramática é não ambígua; prova que ela não é ambígua **naquela sentença**.
É menos do que se gostaria e é muito mais do que a alternativa, que seria afirmar sem verificar.
## O que ficou de fora, e por quê
A gramática desta linguagem tem recursão à esquerda **direta** apenas. O programa implementa também a
eliminação do caso **indireto** — a substituição que traz a volta longa para a superfície — e a
exercita numa gramática de bolso, porque um ramo de código que nenhuma execução percorre é um ramo
que ninguém verificou.
Ficou de fora a eliminação de ciclos de produções unitárias, que é precondição do algoritmo de
eliminação e que esta gramática satisfaz por construção. Se a linguagem ganhar uma regra do tipo
`A := B` com `B := A`, a precondição deixa de valer e o algoritmo precisa de um passo a mais — a
nota está aqui para que a descoberta não seja feita por depuração.O registro tem duas metades, e a divisão entre elas é a decisão de projeto desta tarefa. A metade mecânica — a forma anterior e a forma final de cada uma das seis transformações — é produzida pelo programa, porque ela é derivável da gramática e de nada mais, e um registro derivável escrito à mão envelhece na primeira mudança. A metade não derivável — por que cada transformação foi necessária, o que ela custou, e o que fica devendo — está no documento escrito, porque nenhum código a produz.
O que o documento guarda e o programa não guardaria é o coração da tarefa. A eliminação de recursão à esquerda existe porque o analisador do módulo seguinte decide qual regra aplicar antes de consumir símbolo algum, e diante de uma regra que começa por si mesma a primeira coisa que ele faria para reconhecer a expressão seria tentar reconhecer a expressão, no mesmo ponto do texto. É recursão infinita, e ela não se manifesta como resultado errado — manifesta-se como pilha estourada, o que faz o defeito parecer de implementação quando é de gramática.
E a transformação cobra um preço que precisa ser registrado agora para não ser descoberto depois: a associatividade sai da gramática. A forma recursiva à esquerda agrupa à esquerda por construção; a forma transformada apenas enfileira. As duas aceitam exatamente a mesma linguagem — é por isso que a transformação é legítima —, mas a árvore que o analisador construir a partir da segunda precisa restaurar o agrupamento explicitamente. Isso é dívida deste módulo a ser paga no seguinte, e um registro que dissesse apenas “removida a recursão à esquerda” a esconderia.
A fatoração tem a mesma natureza e causa diferente. As duas alternativas da ação começam com os mesmos cinco símbolos e diferem no sexto; um analisador que decide olhando um símbolo à frente não tem como escolher, porque os dois caminhos começam iguais. A fatoração adia a decisão até o ponto em que há informação para tomá-la: a escolha não desapareceu, foi movida.
Um detalhe do resultado merece atenção porque costuma ser lido como defeito. Uma das duas alternativas fatoradas era o prefixo inteiro, e o sufixo dela é vazio — a fatoração produz uma produção vazia, e a produção vazia é a resposta correta para “não havia comparação nenhuma”. Produção vazia não é lacuna a preencher.
Vale registrar também o que ficou de fora, e por quê. A gramática desta linguagem tem recursão à esquerda direta apenas; a implementação cobre também o caso indireto — a substituição que traz a volta longa para a superfície — e o exercita numa gramática de bolso escrita para isso, porque um ramo de código que nenhuma execução percorre é um ramo que ninguém verificou. Ficou de fora a eliminação de ciclos de produções unitárias, que é precondição do algoritmo e que esta gramática satisfaz por construção; a nota está no documento para que a descoberta não seja feita por depuração no dia em que a linguagem ganhar uma regra que a viole.
Onde é fácil errar. Registrar a transformação e não o motivo. Meia dúzia de pares “antes e depois” sem explicação é exatamente o que ninguém consegue usar meses depois, porque a pergunta que se faz naquele momento é se aquilo ainda precisa ser assim, e não o que mudou. Como verificar que está correta: dê o registro a alguém e peça que diga o que aconteceria se a transformação fosse desfeita. Se a pessoa não souber responder, o registro guardou o resultado e perdeu a razão.
1.5 Derivação à esquerda, à direita, e a árvore que as duas percorrem
Este é o ponto do módulo em que a confusão mais cara se forma, e a solução a desfaz com uma demonstração em vez de uma definição.
A árvore de derivação é o registro da estrutura, e a ordem em que as produções foram aplicadas não faz parte dela. O programa reconstrói a árvore a partir da derivação mais à esquerda e depois percorre a mesma árvore pela direita, produzindo a derivação mais à direita. As duas listas de passos são visivelmente diferentes; a árvore impressa entre elas é uma só. Derivação é percurso; árvore é registro.
A consequência prática é o que importa. Quem confunde ordem de derivação com estrutura conclui que existem duas análises onde existe uma — e, pior, deixa de reconhecer a ambiguidade quando ela de fato aparece, porque o sinal dela é duas árvores, e não duas derivações quaisquer. A demonstração exibe exatamente esse contraste em sequência: primeiro duas árvores diferentes para a mesma sentença, na gramática ambígua; depois duas derivações diferentes com uma árvore só, na gramática estratificada.
Vale dizer por que a derivação mais à direita não é curiosidade acadêmica. Ela é a ordem em que um analisador ascendente reconhece a entrada, ao contrário — cada redução que ele faz corresponde a um passo da derivação mais à direita, tomado de trás para frente. O módulo que trata dessa estratégia vem adiante no percurso, e ter as duas ordens produzidas aqui, da mesma árvore, é o que torna aquela afirmação verificável quando ela for feita, em vez de mais uma coisa a acreditar.
1.6 Ambiguidade: de onde vem, o que custa, e como se elimina
A origem da ambiguidade nesta linguagem é a mesma de quase toda linguagem de programação: uma regra que coloca o operador entre dois operandos do mesmo nível. Escrita assim, ela não diz nada sobre como agrupar quando dois operadores aparecem seguidos — e não dizer é permitir os dois agrupamentos.
O custo é o que a demonstração torna visível. As duas árvores de a and b or c correspondem a agrupamentos diferentes, e agrupamentos diferentes produzem resultados diferentes quando a árvore virar código. Uma gramática ambígua é um programa cujo significado depende de qual análise o analisador escolheu, e essa escolha não está escrita em lugar nenhum.
A técnica de eliminação usada aqui é a estratificação por precedência: um nível de não-terminal por nível de precedência, cada um chamando apenas o de baixo. Não é a única técnica conhecida — há também a introdução de delimitadores obrigatórios, que resolve a ambiguidade tornando o agrupamento explícito no texto e cobra o preço de encher a linguagem de parênteses —, e a escolha entre elas é uma decisão de projeto de linguagem, não de implementação.
Um limite explica por que a verificação deste módulo é experimental, e não uma prova. Não existe procedimento que decida se uma gramática livre de contexto qualquer é ambígua — o problema é indecidível. O que existe são construções conhecidas que produzem gramáticas não ambíguas para casos frequentes, e a estratificação é uma delas. Por isso a verificação aqui é enumerar as derivações de sentenças concretas e contar: uma contagem igual a um não prova que a gramática é não ambígua, prova que ela não é ambígua naquela sentença. A verificação entrega menos do que se gostaria e bem mais do que a alternativa, que seria afirmar sem verificar.
1.7 Precedência e associatividade escritas na forma das regras
A tarefa pede que a precedência esteja na estrutura das regras e não numa tabela à parte, e vale explicar por que a diferença não é de estilo.
Uma tabela de precedência ao lado de uma gramática ambígua descreve o que se pretendia. A gramática estratificada descreve o que acontece. Nos dois casos existe um analisador que precisa resolver o agrupamento; a diferença é que no primeiro a resolução vive fora da gramática, num lugar que nada obriga a manter em acordo com ela, e no segundo ela é consequência da forma das regras e não pode divergir delas.
A ordem de níveis desta linguagem coloca a disjunção no topo, a conjunção abaixo, a comparação abaixo dela e o átomo no fundo. É a ordem das linguagens correntes, herdada e não inventada aqui, e mudá-la surpreenderia quem escreve na Peneira. Surpresa é o custo que não se paga por uma decisão de sintaxe, e essa é a única justificativa que a escolha precisa.
A associatividade é a metade menos lembrada do par, e é onde mora a dívida que a Tarefa 3 registra. Na forma recursiva à esquerda, a associatividade à esquerda é consequência da forma. Depois da transformação, ela não é mais — a gramática transformada aceita a mesma linguagem e não agrupa. Quem esquecer isso vai construir, no módulo seguinte, uma árvore associada à direita para operadores que a linguagem promete associar à esquerda, e o defeito não aparece em expressão com um operador só. Aparece com dois, no dia em que alguém escrever a expressão que ninguém tinha escrito.
1.8 O que este módulo entrega ao arco seguinte
Fica dito, para fechar, o que muda no sistema depois deste capítulo — porque a resposta não é “a linguagem tem uma gramática”.
Muda que a gramática deixou de ser um documento e virou artefato verificável. Ela é percorrida por três diagnósticos que respondem sim ou não, e é executada contra o exemplo de referência a cada reconstrução. Um documento que descreve o sistema envelhece em silêncio; um artefato que o sistema executa não tem como envelhecer sem acusar.
Muda também o estatuto do que vem depois. O analisador do módulo seguinte não é uma peça nova a inventar: ele é a gramática preparada, escrita como procedimento — um procedimento por não-terminal, uma alternativa por caminho, e a decisão local possível porque não há recursão à esquerda nem prefixo comum. A transcrição é quase mecânica, e ela é mecânica porque este módulo foi feito. Um grupo que sai daqui com a gramática “quase pronta” descobre isso ao contrário: gasta a tutoria seguinte depurando recursão à esquerda em vez de construir o analisador, e perde os dois módulos.
E fica registrada a dívida, que é a única coisa deste capítulo que o próximo precisa lembrar sem ter como redescobrir sozinho: a associatividade saiu da gramática na transformação, e precisa voltar na construção da árvore. Está no documento escrito, ao lado da transformação que a causou — que é exatamente o lugar onde alguém a procuraria se soubesse que ela existe, e o único lugar onde alguém a encontraria sem saber.