1 Análise sintática descendente — 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 árvore é a da sua linguagem, e os campos que ela vai precisar dependem das fases que você planeja construir depois. O que se copia daqui é o método — justificar cada campo por um consumidor nomeado, transcrever a gramática em vez de inventar o analisador, e tratar a recusa como parte do produto.
1.1 Visão Geral
Este é o módulo de maior volume de implementação do percurso, e é também o que menos exige invenção. Quase tudo o que se escreve aqui é transcrição da gramática preparada no capítulo anterior, e o volume vem da quantidade de regras a transcrever, não da dificuldade de cada uma. Cada não terminal vira um procedimento, cada terminal vira o consumo de um símbolo, cada alternativa vira uma decisão sobre o símbolo que está à frente, e cada cauda recursiva que a eliminação de recursão à esquerda produziu vira um laço. Quem chegou aqui com a gramática correta escreve o analisador quase mecanicamente; quem chegou com ela pela metade descobre, regra a regra, que o trabalho que não foi feito lá é cobrado aqui com juros.
A solução se organiza em torno de três decisões, e as três estão nas tarefas. A primeira é que a árvore que produzimos não é a árvore de derivação. A segunda é que o analisador é recursivo descendente, escrito por inteiro, e a pilha do autômato do capítulo anterior sobrevive nele como pilha de chamadas. A terceira é que ele não encerra no primeiro erro — ele se recupera e continua, porque quem escreve a descrição precisa ver os cinco problemas de uma vez.
Além das três tarefas, o módulo tem teoria que não cabe naturalmente em nenhuma delas e que a solução cobre com código próprio: os conjuntos de primeiros e de seguidores, a condição que caracteriza as gramáticas analisáveis com um símbolo de antecipação, e a variante dirigida por tabela. Elas são o que permite verificar que a gramática preparada serve, em vez de descobrir isso quando o analisador começar a se comportar de forma estranha em um caso particular.
Um número resume o módulo. Sobre a descrição de referência, a árvore de derivação da gramática preparada tem oitenta e oito nós; a árvore que este analisador produz tem dez. As duas descrevem o mesmo texto.
1.2 Tarefa 1: Projetar a árvore como estrutura própria
O que a tarefa pede
Projetar a estrutura em árvore que representa a descrição lida, distinta da derivação que a gramática induz. A derivação registra como a gramática chegou àquele texto; a árvore registra o que as etapas seguintes precisam consumir, e as duas coisas raramente coincidem. O critério vale campo a campo: cada campo precisa ser justificável por um consumidor posterior nomeado, e campo sem consumidor é campo a remover.
10_ast.h
// 10_ast.h — A árvore que as fases seguintes consomem.
//
// Esta é a estrutura da primeira tarefa do arco, e a decisão que a organiza é
// declarada antes de qualquer campo: ela NÃO é a árvore de derivação. A árvore de
// derivação, que o arco de gramáticas já constrói, registra como a gramática
// chegou àquele texto — cada não-terminal aplicado vira um nó, inclusive os que
// existem só para resolver precedência. Esta registra o que as fases seguintes
// precisam consumir. As duas raramente coincidem, e tratá-las como a mesma coisa
// é o defeito mais caro do percurso, porque ele só cobra dois arcos adiante.
//
// O CRITÉRIO, CAMPO A CAMPO: cada campo abaixo é justificado por um consumidor
// posterior NOMEADO. Campo sem consumidor é campo a remover, e o custo de
// mantê-lo não é a memória que ocupa — é a obrigação de preenchê-lo corretamente
// em todos os pontos que constroem a árvore, para sempre, sem que nada acuse
// quando alguém esquecer.
//
// A CONSEQUÊNCIA MAIS VISÍVEL do critério: não existe nó de parênteses. Na
// derivação, `( expr )` é uma produção aplicada e vira nó; aqui, o parêntese
// cumpriu a sua função — agrupar — no instante em que a análise decidiu quem é
// filho de quem, e a estrutura resultante já carrega esse agrupamento. Um nó de
// parêntese na árvore obrigaria toda fase seguinte a atravessá-lo antes de
// perguntar qualquer coisa, e nenhuma delas ganharia nada em troca. Pela mesma
// razão não há nó para os níveis de precedência: `cmpExpr` e `andExpr` são
// andaimes da gramática, e a precedência que eles carregam já está na forma da
// árvore.
#ifndef PENEIRA_10_AST_H
#define PENEIRA_10_AST_H
#include <cstddef>
#include <memory>
#include <string>
#include <vector>
#include "07_lexer.h"
namespace peneira {
enum class TipoDeExpressao {
Nome, // o identificador ligado pelo `on`
Numero, // literal numérico
Texto, // literal de texto
ValorDe, // `value(n)` — a conversão do lexema casado em número
Comparacao, // dois operandos e um operador de comparação
Conjuncao, // `and`
Disjuncao, // `or`
};
// Um nó de expressão. Os campos não usados por um tipo de nó ficam vazios, e a
// alternativa — uma hierarquia com uma classe por tipo de nó — foi recusada por
// uma razão concreta neste sistema: as fases seguintes percorrem a expressão por
// despacho sobre o tipo (verificação de tipos, depois geração de código de
// pilha), e uma hierarquia obrigaria a um visitante para cada percurso, com mais
// arquivos e nenhuma verificação a mais.
struct Expressao {
TipoDeExpressao tipo = TipoDeExpressao::Nome;
// Consumidor: a tabela de símbolos (resolve `Nome` e o argumento de
// `ValorDe`) e o gerador de código (emite os literais de `Numero` e `Texto`).
std::string lexema;
// Consumidor: o gerador de código, que emite uma instrução de comparação por
// operador. Só é significativo em `Comparacao`, e guardar o TIPO DE TOKEN, e
// não o texto do operador, evita que a geração de código volte a comparar
// cadeias de caracteres para decidir o que emitir.
TipoDeToken operador = TipoDeToken::FimDeArquivo;
// Consumidores: verificação de tipos e geração de código, os dois em
// pós-ordem. Nós folha deixam os dois nulos; `ValorDe` também, porque o
// argumento dele é um nome e cabe em `lexema` — um filho ali seria um nó a
// percorrer para chegar a uma cadeia que já se tem.
std::unique_ptr<Expressao> esquerda;
std::unique_ptr<Expressao> direita;
// Consumidor: a mensagem de recusa da análise semântica. Sem a posição no nó,
// a recusa de "nome não declarado" não teria onde apontar, e a fase seguinte
// seria obrigada a reencontrar o token — que é reabrir uma fase fechada.
Posicao posicao;
};
// A declaração de um padrão. O que a árvore guarda é o TEXTO da expressão, não a
// máquina construída a partir dele: construir o autômato aqui misturaria análise
// com geração de código, e a fase seguinte perderia a chance de recusar um padrão
// declarado e nunca usado antes de pagar o custo de compilá-lo.
struct DeclaracaoDePadrao {
// Consumidor: a tabela de símbolos, que responde se o `on` cita um padrão
// declarado.
std::string nome;
// Consumidor: o gerador de código, que o compila em autômato determinístico
// pelo mesmo caminho já construído nos primeiros arcos.
std::string expressao;
// Consumidor: a recusa de padrão declarado duas vezes, que precisa apontar a
// segunda declaração e citar a primeira.
Posicao posicao;
};
// Uma ação do bloco de regras. A ordem das ações na lista é significativa e é
// consumida pela máquina de execução, que a usa como critério de desempate entre
// padrões que casam trechos de mesmo comprimento — o mesmo critério de ordem que
// o reconhecedor de símbolos já usa.
struct Acao {
// Consumidor: a tabela de símbolos, que liga o nome ao padrão declarado.
std::string padrao;
Posicao posicaoDoPadrao;
// Consumidor: a tabela de símbolos, que abre com este nome o escopo em que a
// condição e o valor emitido são verificados.
std::string ligacao;
// Consumidor: o gerador de código, que emite o bytecode da condição; nulo
// quando a ação não tem `where`, e o nulo é informação — significa "sempre
// verdadeira", e não "condição a ser verificada depois".
std::unique_ptr<Expressao> condicao;
// Consumidores: o gerador de código, que emite o rótulo como literal, e a
// máquina de execução, que o imprime na saída.
std::string rotulo;
std::unique_ptr<Expressao> valor;
Posicao posicao;
};
struct Programa {
std::vector<DeclaracaoDePadrao> padroes;
std::vector<Acao> acoes;
// Consumidor: a análise semântica. Sem esta marca, uma descrição sem bloco de
// regras seria indistinguível de um bloco de regras vazio, e a recusa diria a
// coisa errada a quem escreveu — "nenhuma ação declarada" no lugar de
// "faltou o bloco de regras".
bool temBlocoDeRegras = false;
};
// Constrói nós. Existem para que o analisador não repita a inicialização campo a
// campo em quinze lugares, que é onde um campo esquecido passa despercebido.
std::unique_ptr<Expressao> folha(TipoDeExpressao tipo, std::string lexema, Posicao posicao);
std::unique_ptr<Expressao> binaria(TipoDeExpressao tipo, TipoDeToken operador,
std::unique_ptr<Expressao> esquerda,
std::unique_ptr<Expressao> direita, Posicao posicao);
std::string formatarExpressao(const Expressao& expressao);
std::string formatarPrograma(const Programa& programa);
// A contagem de nós da árvore, usada para comparar o tamanho desta estrutura com
// o da árvore de derivação da mesma descrição. É a medida que torna a diferença
// entre as duas árvores um número, e não uma impressão.
std::size_t contarNos(const Programa& programa);
} // namespace peneira
#endif // PENEIRA_10_AST_H10_ast.cpp
// 10_ast.cpp — Construção, impressão e medida da árvore.
#include "10_ast.h"
#include <sstream>
#include <utility>
namespace peneira {
namespace {
std::string textoDoOperador(const TipoDeToken operador) {
switch (operador) {
case TipoDeToken::Menor: return "<";
case TipoDeToken::Maior: return ">";
case TipoDeToken::MenorOuIgual: return "<=";
case TipoDeToken::MaiorOuIgual: return ">=";
case TipoDeToken::IgualIgual: return "==";
case TipoDeToken::Diferente: return "!=";
default: return "?";
}
}
void imprimirExpressao(std::ostringstream& saida, const Expressao& expressao,
const std::string& recuo) {
saida << recuo;
switch (expressao.tipo) {
case TipoDeExpressao::Nome:
saida << "nome " << expressao.lexema << '\n';
return;
case TipoDeExpressao::Numero:
saida << "numero " << expressao.lexema << '\n';
return;
case TipoDeExpressao::Texto:
saida << "texto " << expressao.lexema << '\n';
return;
case TipoDeExpressao::ValorDe:
saida << "valor-de " << expressao.lexema << '\n';
return;
case TipoDeExpressao::Comparacao:
saida << "comparacao " << textoDoOperador(expressao.operador) << '\n';
break;
case TipoDeExpressao::Conjuncao:
saida << "conjuncao\n";
break;
case TipoDeExpressao::Disjuncao:
saida << "disjuncao\n";
break;
}
if (expressao.esquerda) {
imprimirExpressao(saida, *expressao.esquerda, recuo + " ");
}
if (expressao.direita) {
imprimirExpressao(saida, *expressao.direita, recuo + " ");
}
}
std::size_t contarNos(const Expressao& expressao) {
std::size_t total = 1;
if (expressao.esquerda) {
total += contarNos(*expressao.esquerda);
}
if (expressao.direita) {
total += contarNos(*expressao.direita);
}
return total;
}
} // namespace
std::unique_ptr<Expressao> folha(const TipoDeExpressao tipo, std::string lexema,
const Posicao posicao) {
auto no = std::make_unique<Expressao>();
no->tipo = tipo;
no->lexema = std::move(lexema);
no->posicao = posicao;
return no;
}
std::unique_ptr<Expressao> binaria(const TipoDeExpressao tipo, const TipoDeToken operador,
std::unique_ptr<Expressao> esquerda,
std::unique_ptr<Expressao> direita, const Posicao posicao) {
auto no = std::make_unique<Expressao>();
no->tipo = tipo;
no->operador = operador;
no->esquerda = std::move(esquerda);
no->direita = std::move(direita);
no->posicao = posicao;
return no;
}
std::string formatarExpressao(const Expressao& expressao) {
std::ostringstream saida;
imprimirExpressao(saida, expressao, "");
return saida.str();
}
std::string formatarPrograma(const Programa& programa) {
std::ostringstream saida;
saida << "programa\n";
for (const DeclaracaoDePadrao& padrao : programa.padroes) {
saida << " padrao " << padrao.nome << " = " << padrao.expressao << '\n';
}
if (!programa.temBlocoDeRegras) {
return saida.str();
}
saida << " regras\n";
for (const Acao& acao : programa.acoes) {
saida << " acao sobre " << acao.padrao << " ligando " << acao.ligacao << '\n';
if (acao.condicao) {
saida << " condicao\n";
imprimirExpressao(saida, *acao.condicao, " ");
}
saida << " emite " << acao.rotulo << '\n';
if (acao.valor) {
imprimirExpressao(saida, *acao.valor, " ");
}
}
return saida.str();
}
std::size_t contarNos(const Programa& programa) {
// O programa, cada padrão e cada ação contam como nó; as expressões contam
// pela própria árvore. É a mesma unidade de contagem da árvore de derivação,
// e é por isso que os dois números são comparáveis.
std::size_t total = 1 + programa.padroes.size() + programa.acoes.size();
for (const Acao& acao : programa.acoes) {
if (acao.condicao) {
total += contarNos(*acao.condicao);
}
if (acao.valor) {
total += contarNos(*acao.valor);
}
}
return total;
}
} // namespace peneiraResolvemos esta tarefa antes de escrever uma linha do analisador. O analisador é uma função que produz a árvore; escrevê-lo antes de saber o que ele produz é escrever uma função sem tipo de retorno, e o resultado previsível é uma árvore que foi sendo inventada campo a campo, à medida que cada procedimento precisou guardar alguma coisa. Uma estrutura projetada assim tem exatamente os campos que a análise achou conveniente produzir, e não os que as fases seguintes precisam consumir — que é o defeito de fundo que a tarefa existe para prevenir.
O critério de projeto foi aplicado ao pé da letra, e o resultado está nos comentários do cabeçalho: cada campo carrega o nome de quem vai lê-lo. O nome do padrão está lá porque a tabela de símbolos precisa responder se o on cita um padrão declarado. O texto da expressão do padrão está lá porque o gerador de código vai compilá-lo em autômato determinístico pelo mesmo caminho já construído nos primeiros capítulos. A posição de origem está em quase todo nó porque a recusa da análise semântica precisa de onde apontar — sem ela, aquela fase seria obrigada a reencontrar o símbolo no texto, o que é reabrir uma fase que já fechou.
A consequência mais visível do critério é a que a tarefa antecipa: não existe nó de parênteses. Na derivação, ( expr ) é uma produção aplicada e portanto vira nó. Aqui, o parêntese cumpriu a sua função — agrupar — no instante em que a análise decidiu quem é filho de quem, e a estrutura resultante já carrega esse agrupamento. Um nó de parêntese obrigaria toda fase seguinte a atravessá-lo antes de perguntar qualquer coisa, e nenhuma delas ganharia nada em troca. Pela mesma razão desapareceram os níveis de precedência: os não terminais intermediários da expressão são andaimes da gramática, e a precedência que eles carregam já está na forma da árvore que restou.
A demonstração mede isso em vez de afirmá-lo. Ela analisa duas descrições que dizem a mesma coisa, uma com quatro pares de parênteses redundantes em volta da condição e outra sem nenhum, e compara as duas árvores: sete nós nas duas, com a mesma forma impressa. Se algum dia um par de parênteses voltar a deixar rastro na estrutura, esse número muda e a bateria de testes reprova — o que transforma uma decisão de projeto em uma propriedade verificada.
Duas decisões menores merecem registro porque foram tomadas contra o hábito. A primeira é que o nó de expressão é uma estrutura única com um campo de tipo, e não uma hierarquia com uma classe por espécie de nó. A hierarquia seria mais elegante em abstrato e cobraria, neste sistema, um visitante para cada percurso — e os percursos que virão são dois, a verificação de tipos e a geração de código de pilha. A segunda é que o operador de comparação é guardado como categoria de símbolo, e não como o texto do operador: guardar o texto obrigaria a geração de código a comparar cadeias de caracteres para decidir o que emitir, que é reprocessar uma decisão já tomada.
Onde é fácil errar. Guardar “por garantia”. É tentador manter na árvore o símbolo original de cada nó, ou a produção que o gerou, porque um dia pode ser útil. O custo desse campo é a obrigação de preenchê-lo corretamente em todos os pontos que constroem a árvore, para sempre, sem que nada acuse quando alguém esquecer. Como verificar que está correta: pegue cada campo e diga em voz alta o nome da fase que o lê. Se a resposta for “alguma fase adiante”, o campo não tem consumidor — tem uma esperança.
1.3 Tarefa 2: Construir o analisador descendente
O que a tarefa pede
Implementar o analisador que consome a sequência de símbolos e produz essa árvore. É a etapa de maior volume de código do percurso, e a que mais recompensa o trabalho feito na gramática: cada regra bem fatorada se transcreve quase mecanicamente, e cada regra mal transformada exige uma decisão local que o código não tem informação para tomar. A tarefa se cumpre quando a descrição de exemplo produz a árvore esperada.
10_parser.h
// 10_parser.h — O analisador descendente recursivo, e a recusa que não desiste.
//
// A correspondência que organiza o arquivo inteiro é de uma linha: CADA
// NÃO-TERMINAL DA GRAMÁTICA PREPARADA VIRA UM PROCEDIMENTO, e o corpo do
// procedimento é a leitura literal do corpo da produção. Terminal vira consumo de
// um símbolo; não-terminal vira chamada; alternativa vira decisão sobre o símbolo
// de antecipação; a cauda recursiva que a eliminação de recursão à esquerda
// produziu vira laço. Não há invenção nenhuma nesta fase — há transcrição, e é
// exatamente por isso que o trabalho feito no arco anterior se paga aqui.
//
// A pilha do autômato do arco anterior também não sumiu: ela é a PILHA DE
// CHAMADAS. O reconhecedor dirigido por tabela do arquivo vizinho mantém a pilha
// explícita, num vetor que dá para imprimir; aqui a mesma pilha está implícita
// nas chamadas aninhadas, e é essa a única diferença entre os dois. Um aninhamento
// arbitrariamente profundo de parênteses é reconhecido pelos dois pela mesma
// razão, e nenhuma expressão regular o reconheceria.
//
// A TERCEIRA DECISÃO, que é a da terceira tarefa: o analisador NÃO PARA no
// primeiro erro. Parar é mais fácil de escrever e é a razão pela qual muita
// ferramenta é desagradável de usar — quem escreveu a descrição corrige um
// problema, executa de novo, descobre o seguinte, e repete cinco vezes. A conduta
// implementada aqui é o modo de pânico: registra-se a recusa, descartam-se
// símbolos até um ponto de sincronização confiável, e a análise recomeça dali. O
// preço é conhecido e é aceito — depois do primeiro erro, os seguintes podem ser
// consequência dele, e nenhuma técnica de recuperação elimina isso.
#ifndef PENEIRA_10_PARSER_H
#define PENEIRA_10_PARSER_H
#include <cstddef>
#include <memory>
#include <string>
#include <vector>
#include "07_lexer.h"
#include "10_ast.h"
namespace peneira {
// A recusa dirigida a quem escreveu a descrição. Herda a forma da recusa léxica
// do arco anterior — posição, trecho ofensor, mensagem — e acrescenta o que só a
// sintaxe sabe: o que se esperava naquele ponto. Sem esse campo, a mensagem seria
// "erro de sintaxe", que é a mensagem que não ajuda ninguém.
struct ErroSintatico {
Posicao posicao;
std::string encontrado;
std::string esperado;
std::string mensagem;
};
struct ResultadoSintatico {
Programa programa;
std::vector<ErroSintatico> erros;
// Quantos símbolos a recuperação descartou. É a medida do estrago: descarte
// grande é sinal de que os pontos de sincronização estão mal escolhidos.
std::size_t simbolosDescartados = 0;
bool ok() const;
};
class AnalisadorSintatico {
public:
explicit AnalisadorSintatico(std::vector<Token> tokens);
// A árvore devolvida em caso de erro é PARCIAL, e isso é deliberado: as ações
// que estavam corretas continuam lá, e é isso que permite a uma fase seguinte
// de verificação encontrar mais problemas na mesma execução. Quem quiser
// parar no primeiro erro consulta `ok()`.
ResultadoSintatico analisar();
private:
// --- o vocabulário mínimo sobre o fluxo de símbolos ---
const Token& adiante() const;
bool ehTipo(TipoDeToken tipo) const;
Token consumir();
// Consome se o tipo casar; caso contrário registra a recusa e devolve falso.
// Devolver o resultado, em vez de lançar, é o que mantém a recuperação sob
// controle de quem chama — que é quem sabe até onde vale a pena descartar.
bool esperar(TipoDeToken tipo, const std::string& ondeEstavamos);
void registrarErro(const std::string& esperado, const std::string& ondeEstavamos);
// Modo de pânico. Descarta símbolos até um ponto em que a análise pode
// recomeçar sem inventar estrutura: o fim de uma declaração, o começo da
// próxima, o fecho do bloco, ou o fim do arquivo.
void sincronizarNoNivelDeDeclaracao();
void sincronizarDentroDoBloco();
// --- um procedimento por não-terminal ---
void analisarPrograma();
void analisarDeclaracaoDePadrao();
void analisarBlocoDeRegras();
bool analisarAcao(Acao& acao);
std::unique_ptr<Expressao> analisarExpressao();
std::unique_ptr<Expressao> analisarConjuncao();
std::unique_ptr<Expressao> analisarComparacao();
std::unique_ptr<Expressao> analisarPrimaria();
bool ehComparador(TipoDeToken tipo) const;
std::vector<Token> tokens_;
std::size_t posicao_ = 0;
ResultadoSintatico resultado_;
// Trava contra cascata: depois de uma recusa, as seguintes só são registradas
// quando a análise já voltou a consumir símbolo. Sem ela, um único símbolo
// fora do lugar produz uma recusa por procedimento aninhado, e a saída vira
// ruído que esconde o problema real.
bool emRecuperacao_ = false;
};
std::string formatarErroSintatico(const std::string& texto, const ErroSintatico& erro);
} // namespace peneira
#endif // PENEIRA_10_PARSER_H10_parser.cpp
// 10_parser.cpp — Um procedimento por não-terminal, e a recuperação em modo de pânico.
#include "10_parser.h"
#include <sstream>
#include <utility>
namespace peneira {
namespace {
// O nome pelo qual a mensagem se refere a cada símbolo. É deliberadamente o nome
// que quem escreve a descrição usa — `;`, `=>`, `pattern` —, e não o nome interno
// da categoria: a recusa fala com quem escreveu o texto, e essa pessoa nunca viu
// a nossa tabela de categorias.
std::string textoEsperado(const TipoDeToken tipo) {
switch (tipo) {
case TipoDeToken::PalavraPattern: return "`pattern`";
case TipoDeToken::PalavraRule: return "`rule`";
case TipoDeToken::PalavraOn: return "`on`";
case TipoDeToken::PalavraWhere: return "`where`";
case TipoDeToken::PalavraEmit: return "`emit`";
case TipoDeToken::PalavraValue: return "`value`";
case TipoDeToken::Identificador: return "um nome";
case TipoDeToken::Numero: return "um numero";
case TipoDeToken::Texto: return "um texto entre aspas";
case TipoDeToken::ExpressaoDePadrao: return "uma expressao entre barras";
case TipoDeToken::AbreParenteses: return "`(`";
case TipoDeToken::FechaParenteses: return "`)`";
case TipoDeToken::AbreChaves: return "`{`";
case TipoDeToken::FechaChaves: return "`}`";
case TipoDeToken::PontoEVirgula: return "`;`";
case TipoDeToken::Virgula: return "`,`";
case TipoDeToken::Igual: return "`=`";
case TipoDeToken::Seta: return "`=>`";
default: return nomeDoTipo(tipo);
}
}
// A linha inteira em que o deslocamento cai, para que a mensagem mostre o texto e
// não apenas coordenadas. É a mesma forma de recusa do arco anterior.
std::string linhaDe(const std::string& texto, const std::size_t deslocamento) {
if (texto.empty()) {
return {};
}
const std::size_t posicao = deslocamento < texto.size() ? deslocamento : texto.size() - 1;
std::size_t inicio = posicao;
while (inicio > 0 && texto[inicio - 1] != '\n') {
--inicio;
}
std::size_t fim = posicao;
while (fim < texto.size() && texto[fim] != '\n') {
++fim;
}
return texto.substr(inicio, fim - inicio);
}
} // namespace
bool ResultadoSintatico::ok() const { return erros.empty(); }
AnalisadorSintatico::AnalisadorSintatico(std::vector<Token> tokens)
: tokens_{std::move(tokens)} {
// A fase anterior sempre entrega o marcador de fim. Se ela não entregar — uma
// lista construída à mão num teste, por exemplo —, acrescentamos: o analisador
// inteiro assume que existe sempre um símbolo à frente, e essa é a suposição
// que evita uma verificação de limite em cada um dos procedimentos.
if (tokens_.empty() || tokens_.back().tipo != TipoDeToken::FimDeArquivo) {
Token fim;
fim.tipo = TipoDeToken::FimDeArquivo;
if (!tokens_.empty()) {
fim.posicao = tokens_.back().posicao;
}
tokens_.push_back(fim);
}
}
const Token& AnalisadorSintatico::adiante() const {
return posicao_ < tokens_.size() ? tokens_[posicao_] : tokens_.back();
}
bool AnalisadorSintatico::ehTipo(const TipoDeToken tipo) const { return adiante().tipo == tipo; }
Token AnalisadorSintatico::consumir() {
const Token atual = adiante();
if (atual.tipo != TipoDeToken::FimDeArquivo) {
++posicao_;
}
// Consumir símbolo é a prova de que a análise voltou a andar, e é o único
// ponto em que a trava contra cascata se solta.
emRecuperacao_ = false;
return atual;
}
void AnalisadorSintatico::registrarErro(const std::string& esperado,
const std::string& ondeEstavamos) {
if (emRecuperacao_) {
return;
}
emRecuperacao_ = true;
const Token& atual = adiante();
ErroSintatico erro;
erro.posicao = atual.posicao;
erro.encontrado =
atual.tipo == TipoDeToken::FimDeArquivo ? std::string{"o fim do arquivo"} : atual.lexema;
erro.esperado = esperado;
erro.mensagem = "esperava " + esperado + ' ' + ondeEstavamos + ", e encontrou " +
erro.encontrado;
resultado_.erros.push_back(std::move(erro));
}
bool AnalisadorSintatico::esperar(const TipoDeToken tipo, const std::string& ondeEstavamos) {
if (ehTipo(tipo)) {
consumir();
return true;
}
registrarErro(textoEsperado(tipo), ondeEstavamos);
return false;
}
// recorte:inicio sincronizar-para-prosseguir
void AnalisadorSintatico::sincronizarNoNivelDeDeclaracao() {
// Os pontos de sincronização não são escolhidos por comodidade: são os
// símbolos que só aparecem no começo ou no fim de uma declaração, e por isso
// dizem, sozinhos, onde a estrutura recomeça.
while (!ehTipo(TipoDeToken::FimDeArquivo)) {
if (ehTipo(TipoDeToken::PalavraPattern) || ehTipo(TipoDeToken::PalavraRule)) {
return;
}
const bool fimDeDeclaracao = ehTipo(TipoDeToken::PontoEVirgula);
++posicao_;
++resultado_.simbolosDescartados;
if (fimDeDeclaracao) {
return;
}
}
}
// recorte:fim sincronizar-para-prosseguir
void AnalisadorSintatico::sincronizarDentroDoBloco() {
while (!ehTipo(TipoDeToken::FimDeArquivo)) {
if (ehTipo(TipoDeToken::PalavraOn) || ehTipo(TipoDeToken::FechaChaves)) {
return;
}
const bool fimDeAcao = ehTipo(TipoDeToken::PontoEVirgula);
++posicao_;
++resultado_.simbolosDescartados;
if (fimDeAcao) {
return;
}
}
}
// --- os procedimentos, um por não-terminal -----------------------------------
ResultadoSintatico AnalisadorSintatico::analisar() {
analisarPrograma();
return std::move(resultado_);
}
// program -> ( patternDecl | ruleBlock )* FIM
// recorte:inicio um-procedimento-por-nao-terminal
void AnalisadorSintatico::analisarPrograma() {
while (!ehTipo(TipoDeToken::FimDeArquivo)) {
if (ehTipo(TipoDeToken::PalavraPattern)) {
analisarDeclaracaoDePadrao();
} else if (ehTipo(TipoDeToken::PalavraRule)) {
analisarBlocoDeRegras();
} else {
registrarErro("`pattern` ou `rule`", "no inicio de uma declaracao");
sincronizarNoNivelDeDeclaracao();
}
}
}
// recorte:fim um-procedimento-por-nao-terminal
// patternDecl -> PATTERN ID IGUAL REGEX PONTO_VIRGULA
void AnalisadorSintatico::analisarDeclaracaoDePadrao() {
consumir(); // `pattern`
if (!ehTipo(TipoDeToken::Identificador)) {
registrarErro("o nome do padrao", "depois de `pattern`");
sincronizarNoNivelDeDeclaracao();
return;
}
const Token nome = consumir();
if (!esperar(TipoDeToken::Igual, "depois do nome do padrao")) {
sincronizarNoNivelDeDeclaracao();
return;
}
if (!ehTipo(TipoDeToken::ExpressaoDePadrao)) {
registrarErro("a expressao do padrao, entre barras", "depois de `=`");
sincronizarNoNivelDeDeclaracao();
return;
}
const Token expressao = consumir();
if (!esperar(TipoDeToken::PontoEVirgula, "no fim da declaracao do padrao")) {
sincronizarNoNivelDeDeclaracao();
return;
}
DeclaracaoDePadrao declaracao;
declaracao.nome = nome.lexema;
declaracao.expressao = expressao.lexema;
declaracao.posicao = nome.posicao;
resultado_.programa.padroes.push_back(std::move(declaracao));
}
// ruleBlock -> RULE ABRE_CHAVE action* FECHA_CHAVE
void AnalisadorSintatico::analisarBlocoDeRegras() {
consumir(); // `rule`
// A marca é posta ANTES de qualquer verificação: um bloco malformado continua
// sendo um bloco declarado, e a análise semântica precisa distinguir isso de
// uma descrição que não tem bloco algum.
resultado_.programa.temBlocoDeRegras = true;
if (!esperar(TipoDeToken::AbreChaves, "depois de `rule`")) {
sincronizarNoNivelDeDeclaracao();
return;
}
while (!ehTipo(TipoDeToken::FechaChaves) && !ehTipo(TipoDeToken::FimDeArquivo)) {
if (!ehTipo(TipoDeToken::PalavraOn)) {
registrarErro("`on` ou `}`", "dentro do bloco de regras");
sincronizarDentroDoBloco();
continue;
}
Acao acao;
if (analisarAcao(acao)) {
resultado_.programa.acoes.push_back(std::move(acao));
} else {
sincronizarDentroDoBloco();
}
}
esperar(TipoDeToken::FechaChaves, "no fim do bloco de regras");
}
// action -> ON ID ABRE_PAR ID FECHA_PAR [ WHERE expr ] SETA EMIT ABRE_PAR TEXTO
// VIRGULA expr FECHA_PAR PONTO_VIRGULA
//
// A parte opcional é a marca do `where`. Na gramática preparada ela é um
// não-terminal com uma alternativa vazia; aqui é um `if` sobre o símbolo de
// antecipação — e as duas formas são a mesma coisa dita em notações diferentes.
bool AnalisadorSintatico::analisarAcao(Acao& acao) {
const Token inicio = consumir(); // `on`
acao.posicao = inicio.posicao;
if (!ehTipo(TipoDeToken::Identificador)) {
registrarErro("o nome de um padrao declarado", "depois de `on`");
return false;
}
const Token padrao = consumir();
acao.padrao = padrao.lexema;
acao.posicaoDoPadrao = padrao.posicao;
if (!esperar(TipoDeToken::AbreParenteses, "depois do nome do padrao")) {
return false;
}
if (!ehTipo(TipoDeToken::Identificador)) {
registrarErro("o nome a ligar ao trecho casado", "dentro dos parenteses do `on`");
return false;
}
acao.ligacao = consumir().lexema;
if (!esperar(TipoDeToken::FechaParenteses, "depois do nome ligado")) {
return false;
}
if (ehTipo(TipoDeToken::PalavraWhere)) {
consumir();
acao.condicao = analisarExpressao();
if (!acao.condicao) {
return false;
}
}
if (!esperar(TipoDeToken::Seta, "depois do cabecalho da acao")) {
return false;
}
if (!esperar(TipoDeToken::PalavraEmit, "depois de `=>`")) {
return false;
}
if (!esperar(TipoDeToken::AbreParenteses, "depois de `emit`")) {
return false;
}
if (!ehTipo(TipoDeToken::Texto)) {
registrarErro("o rotulo entre aspas", "como primeiro argumento de `emit`");
return false;
}
acao.rotulo = consumir().lexema;
if (!esperar(TipoDeToken::Virgula, "entre o rotulo e o valor emitido")) {
return false;
}
acao.valor = analisarExpressao();
if (!acao.valor) {
return false;
}
if (!esperar(TipoDeToken::FechaParenteses, "no fim dos argumentos de `emit`")) {
return false;
}
return esperar(TipoDeToken::PontoEVirgula, "no fim da acao");
}
// expr -> andExpr ( OR andExpr )*
//
// O laço é a cauda que a eliminação de recursão à esquerda produziu, escrita como
// laço em vez de chamada recursiva — e é ele que dá a associatividade à esquerda:
// cada volta pendura o que já foi construído como filho ESQUERDO do nó novo.
std::unique_ptr<Expressao> AnalisadorSintatico::analisarExpressao() {
std::unique_ptr<Expressao> esquerda = analisarConjuncao();
if (!esquerda) {
return nullptr;
}
while (ehTipo(TipoDeToken::OperadorOr)) {
const Token operador = consumir();
std::unique_ptr<Expressao> direita = analisarConjuncao();
if (!direita) {
return nullptr;
}
esquerda = binaria(TipoDeExpressao::Disjuncao, operador.tipo, std::move(esquerda),
std::move(direita), operador.posicao);
}
return esquerda;
}
// andExpr -> cmpExpr ( AND cmpExpr )*
std::unique_ptr<Expressao> AnalisadorSintatico::analisarConjuncao() {
std::unique_ptr<Expressao> esquerda = analisarComparacao();
if (!esquerda) {
return nullptr;
}
while (ehTipo(TipoDeToken::OperadorAnd)) {
const Token operador = consumir();
std::unique_ptr<Expressao> direita = analisarComparacao();
if (!direita) {
return nullptr;
}
esquerda = binaria(TipoDeExpressao::Conjuncao, operador.tipo, std::move(esquerda),
std::move(direita), operador.posicao);
}
return esquerda;
}
bool AnalisadorSintatico::ehComparador(const TipoDeToken tipo) const {
return tipo == TipoDeToken::Menor || tipo == TipoDeToken::Maior ||
tipo == TipoDeToken::MenorOuIgual || tipo == TipoDeToken::MaiorOuIgual ||
tipo == TipoDeToken::IgualIgual || tipo == TipoDeToken::Diferente;
}
// cmpExpr -> primary [ comparador primary ]
//
// Sem laço, e de propósito: a comparação não é associativa nesta linguagem, e
// `a < b < c` é recusado em vez de aceito com um significado inventado. A recusa
// vem de graça — o segundo comparador simplesmente não é consumido, e o
// procedimento que chamou vai encontrá-lo fora de lugar.
std::unique_ptr<Expressao> AnalisadorSintatico::analisarComparacao() {
std::unique_ptr<Expressao> esquerda = analisarPrimaria();
if (!esquerda) {
return nullptr;
}
if (!ehComparador(adiante().tipo)) {
return esquerda;
}
const Token operador = consumir();
std::unique_ptr<Expressao> direita = analisarPrimaria();
if (!direita) {
return nullptr;
}
return binaria(TipoDeExpressao::Comparacao, operador.tipo, std::move(esquerda),
std::move(direita), operador.posicao);
}
// primary -> ID | NUMERO | TEXTO | VALUE ABRE_PAR ID FECHA_PAR | ABRE_PAR expr FECHA_PAR
//
// O último caso é onde a decisão da árvore aparece em código: a expressão entre
// parênteses é devolvida COMO ESTÁ. Os dois símbolos foram consumidos, cumpriram
// a função de agrupar, e não deixam nó atrás de si.
std::unique_ptr<Expressao> AnalisadorSintatico::analisarPrimaria() {
if (ehTipo(TipoDeToken::Identificador)) {
const Token nome = consumir();
return folha(TipoDeExpressao::Nome, nome.lexema, nome.posicao);
}
if (ehTipo(TipoDeToken::Numero)) {
const Token numero = consumir();
return folha(TipoDeExpressao::Numero, numero.lexema, numero.posicao);
}
if (ehTipo(TipoDeToken::Texto)) {
const Token texto = consumir();
return folha(TipoDeExpressao::Texto, texto.lexema, texto.posicao);
}
if (ehTipo(TipoDeToken::PalavraValue)) {
const Token palavra = consumir();
if (!esperar(TipoDeToken::AbreParenteses, "depois de `value`")) {
return nullptr;
}
if (!ehTipo(TipoDeToken::Identificador)) {
registrarErro("um nome", "dentro dos parenteses de `value`");
return nullptr;
}
const Token nome = consumir();
if (!esperar(TipoDeToken::FechaParenteses, "depois do argumento de `value`")) {
return nullptr;
}
return folha(TipoDeExpressao::ValorDe, nome.lexema, palavra.posicao);
}
if (ehTipo(TipoDeToken::AbreParenteses)) {
consumir();
std::unique_ptr<Expressao> interna = analisarExpressao();
if (!interna) {
return nullptr;
}
if (!esperar(TipoDeToken::FechaParenteses, "no fim da expressao entre parenteses")) {
return nullptr;
}
return interna;
}
registrarErro("um nome, um numero, um texto, `value` ou `(`", "no inicio de uma expressao");
return nullptr;
}
std::string formatarErroSintatico(const std::string& texto, const ErroSintatico& erro) {
std::ostringstream saida;
saida << "erro de sintaxe em " << erro.posicao.linha << ":" << erro.posicao.coluna << " — "
<< erro.mensagem << '\n';
saida << " " << linhaDe(texto, erro.posicao.deslocamento) << '\n';
saida << " " << std::string(erro.posicao.coluna - 1, ' ') << "^\n";
return saida.str();
}
} // namespace peneiraA correspondência que organiza o arquivo inteiro cabe numa linha, e ela é o conteúdo teórico central do módulo: cada não terminal da gramática preparada vira um procedimento, e o corpo do procedimento é a leitura literal do corpo da produção. Escrevemos os procedimentos na ordem em que os não terminais aparecem na gramática, e deixamos, em comentário sobre cada um, a produção que ele transcreve. Esse comentário é o que permite conferir o analisador contra a gramática lendo os dois lado a lado, e é o que torna visível, meses depois, que uma alteração na gramática exige uma alteração aqui.
A transcrição tem quatro regras, e são elas o método que o aluno leva para o próprio projeto. Terminal vira consumo de um símbolo. Não terminal vira chamada de procedimento. Alternativa vira decisão sobre o símbolo que está à frente — e é aqui que os conjuntos de primeiros entram, embora o código não os consulte em tempo de execução: quem escolhe o ramo do if é quem escreveu o procedimento, com o conjunto na mão. A cauda recursiva que a eliminação de recursão à esquerda produziu vira laço, e o laço pendura o que já foi construído como filho esquerdo do nó novo, o que dá de graça a associatividade à esquerda dos operadores.
A pilha do capítulo anterior não sumiu no caminho: ela é a pilha de chamadas. Um aninhamento arbitrariamente profundo de parênteses é reconhecido porque cada chamada aninhada guarda o seu ponto de retorno, e é exatamente essa memória sem teto que a classe regular não tem. É o mesmo argumento do capítulo do lema do bombeamento, agora visto do outro lado: lá mostramos que o autômato finito não conseguia; aqui está a máquina que consegue, e o que ela tem a mais é a pilha.
Uma escolha de assinatura merece justificativa, porque ela decide como a tarefa seguinte fica possível. Os procedimentos que podem falhar devolvem o insucesso em vez de interromper a execução com uma exceção. Interromper seria mais curto de escrever e transferiria para um ponto distante a decisão sobre até onde descartar símbolos — e quem sabe até onde vale a pena descartar é quem está no meio da estrutura, não quem está na borda. Essa decisão é o que permite ao bloco de regras perder uma ação defeituosa e continuar analisando as seguintes, em vez de perder o bloco inteiro.
Registramos também uma recusa. A comparação não é associativa nesta linguagem, e a transcrição da regra correspondente não tem laço: depois de um operador de comparação e do segundo operando, o procedimento devolve. Uma expressão com dois comparadores encadeados é recusada porque o segundo comparador simplesmente não é consumido, e o procedimento que chamou o encontra fora de lugar. Não escrevemos nenhuma verificação para isso — a recusa é consequência da forma da regra, que é o mesmo mecanismo pelo qual a precedência já era consequência da estratificação.
Onde é fácil errar. Escrever o analisador contra a gramática que se lembra, e não contra a que está escrita. O sintoma é sempre o mesmo e demora a aparecer: um caso que a linguagem sempre aceitou passa a ser recusado, e o defeito está numa alternativa que existia na gramática e não foi transcrita. Como verificar que está correto: analise a descrição de referência e compare a árvore impressa com a que você desenha à mão a partir da derivação do capítulo anterior. A demonstração faz essa conferência automaticamente — exige dois padrões, duas ações, e condição apenas na segunda — e reprova quando a forma muda.
1.4 Tarefa 3: Recuperar-se do erro em vez de encerrar
O que a tarefa pede
Fazer uma descrição sintaticamente inválida produzir uma mensagem dirigida a quem a escreveu, e fazer o analisador prosseguir depois do erro em vez de encerrar no primeiro problema. A diferença entre as duas condutas é a diferença entre um sistema que aponta os cinco problemas de uma descrição em uma passada e um que obriga quem a escreveu a corrigir um, executar de novo, descobrir o seguinte, e repetir cinco vezes.
A mensagem vem primeiro, porque ela decide o resto. A recusa registra três coisas: onde, o que se esperava naquele ponto, e o que foi encontrado. O campo do que se esperava é o que separa uma mensagem útil de um “erro de sintaxe” que não ajuda ninguém, e ele é escrito no vocabulário de quem escreve a descrição — o símbolo aparece como ; ou =>, e não pelo nome interno da categoria, que essa pessoa nunca viu. A forma da mensagem é herdada da recusa léxica do capítulo anterior, com a linha de origem impressa e o cursor sob a coluna; manter as duas famílias com a mesma aparência é o que faz o sistema parecer um só.
A conduta de recuperação implementada é o modo de pânico: registra-se a recusa, descartam-se símbolos até um ponto em que a análise pode recomeçar sem inventar estrutura, e a análise recomeça dali. Os pontos de sincronização são os símbolos que só aparecem no começo ou no fim de uma unidade — o fim de uma declaração, o início da próxima, o fecho do bloco — e por isso dizem, sozinhos, onde a estrutura recomeça. Escolher mal esses pontos produz o pior dos dois mundos: o analisador continua, mas continua no lugar errado, e as recusas seguintes falam de problemas que não existem.
Contra esse mesmo risco existe uma trava explícita no analisador. Depois de uma recusa, as seguintes só passam a ser registradas quando a análise voltou a consumir um símbolo de verdade. Sem ela, um único símbolo fora do lugar produz uma recusa por procedimento aninhado — a expressão reclama, a ação reclama, o bloco reclama — e a saída vira ruído que esconde o problema real. É um detalhe de três linhas com efeito grande sobre a utilidade da ferramenta.
A verificação é a descrição que existe para ser recusada, e ela carrega três defeitos de famílias diferentes: um símbolo faltando entre dois que estão certos, um separador faltando dentro de uma chamada, e uma expressão que termina antes de terminar. A execução produz as três recusas de uma vez, descartando treze símbolos no caminho, e — este é o ponto — a declaração válida que vem depois do primeiro erro e a ação válida que vem depois do terceiro são analisadas normalmente e sobrevivem na árvore. É essa sobrevivência que distingue recuperar-se de encerrar: a árvore devolvida é parcial e continua útil, e uma fase seguinte de verificação pode encontrar mais problemas na mesma execução.
Uma limitação fica de pé. Depois do primeiro erro, os seguintes podem ser consequência dele, e nenhuma técnica de recuperação elimina isso. O que se pode fazer é reduzir a incidência — que é o papel dos pontos de sincronização bem escolhidos e da trava contra cascata — e medir o estrago, que é por isso que a solução conta quantos símbolos a recuperação descartou. Descarte grande é sinal de que os pontos de sincronização estão mal escolhidos, e é um número que vale acompanhar quando a linguagem crescer.
Onde é fácil errar. Recuperar sem garantir progresso. Um laço de recuperação que não consome nenhum símbolo em algum caminho produz repetição infinita, e o sintoma é um programa que trava numa descrição malformada em vez de recusá-la. Cada ponto de descarte desta solução consome ao menos um símbolo antes de devolver o controle, e essa é uma propriedade a conferir explicitamente. Como verificar que está correta: escreva a descrição defeituosa antes de escrever a recuperação, e fixe quantas recusas ela deve produzir. Se a contagem mudar sozinha depois, alguma coisa parou de funcionar.
1.5 Os conjuntos que sustentam a decisão local
O capítulo anterior deixou a gramática sem recursão à esquerda e sem prefixo comum, e é tentador tratar isso como sinal verde. A ausência dos dois defeitos é necessária e não é suficiente. O que decide se a análise pode escolher o ramo olhando um único símbolo à frente é a relação entre o que cada alternativa pode começar e o que pode vir depois do não terminal — e essas duas coisas são os conjuntos de primeiros e de seguidores.
10_ll1.h
// 10_ll1.h — Os conjuntos que sustentam a decisão local, e a tabela que ela produz.
//
// O arco anterior deixou a gramática preparada: sem recursão à esquerda e sem
// prefixo comum. Preparada, porém, não é o mesmo que analisável com um símbolo de
// antecipação — a ausência daqueles dois defeitos é NECESSÁRIA e não é
// SUFICIENTE. O que decide é a relação entre o que cada alternativa pode começar
// e o que pode vir depois do não-terminal, e essas duas coisas são os conjuntos
// deste arquivo.
//
// A DECISÃO CENTRAL DO ARQUIVO é a mesma do arco de gramáticas, levada um passo
// adiante: os conjuntos são calculados a partir da gramática como dado, e não
// escritos à mão ao lado do analisador. Escritos à mão, eles são uma promessa
// sobre a gramática — e a promessa se desfaz na primeira regra alterada. Sendo
// calculados, a alteração da gramática recalcula os conjuntos, e a condição de
// analisabilidade é reverificada sem que ninguém precise lembrar de fazê-lo.
//
// A tabela que sai daqui não é o analisador que o sistema usa: o analisador do
// sistema é o recursivo do arquivo seguinte. Ela existe por duas razões que valem
// o código que custa. A primeira é que ela TORNA VISÍVEL o que o analisador
// recursivo esconde na forma dos procedimentos — a decisão que o `if` toma está
// numa célula, e uma célula com duas produções é o conflito que numa cadeia de
// `if` passaria despercebido. A segunda é que ela é o autômato de pilha do arco
// anterior, agora concreto: pilha, símbolo de antecipação e uma tabela de
// transição. O modelo abstrato vira, aqui, um laço de vinte linhas.
#ifndef PENEIRA_10_LL1_H
#define PENEIRA_10_LL1_H
#include <cstddef>
#include <string>
#include <unordered_map>
#include <vector>
#include "08_gramatica.h"
namespace peneira {
// O marcador de fim de entrada. É o mesmo nome que o reconhecedor de símbolos já
// dá à sua última entrega, e usá-lo aqui evita um segundo vocabulário para dizer
// a mesma coisa.
inline const std::string kFimDeEntrada = "FIM";
// Um conjunto de terminais, mais a marca de que a forma pode derivar o vazio. A
// marca fica SEPARADA da lista de propósito: o vazio não é um terminal, e
// guardá-lo como se fosse é o que produz o analisador que tenta casar o vazio na
// entrada e trava.
struct ConjuntoDeSimbolos {
std::vector<std::string> terminais; // na ordem de primeira inserção
bool derivaVazio = false;
bool contem(const std::string& terminal) const;
// Devolve true se acrescentou algo — é o que faz o cálculo por ponto fixo
// saber que ainda não terminou.
bool acrescentar(const std::string& terminal);
bool acrescentarTerminaisDe(const ConjuntoDeSimbolos& outro);
};
// Os primeiros e os seguidores de cada não-terminal, calculados por ponto fixo.
class ConjuntosDeAnalise {
public:
explicit ConjuntosDeAnalise(const Gramatica& gramatica);
const ConjuntoDeSimbolos& primeirosDe(const std::string& naoTerminal) const;
const ConjuntoDeSimbolos& seguidoresDe(const std::string& naoTerminal) const;
// Os primeiros de uma forma sentencial inteira: percorre símbolo a símbolo
// enquanto o anterior puder derivar o vazio. É esta função, e não a anterior,
// que a construção da tabela usa — a célula é decidida pela ALTERNATIVA, não
// pelo não-terminal.
ConjuntoDeSimbolos primeirosDaForma(const FormaSentencial& forma) const;
private:
void calcularPrimeiros();
void calcularSeguidores();
Gramatica gramatica_;
std::unordered_map<std::string, ConjuntoDeSimbolos> primeiros_;
std::unordered_map<std::string, ConjuntoDeSimbolos> seguidores_;
};
// Duas alternativas do mesmo não-terminal disputando a mesma célula. O campo
// `origem` distingue as duas famílias, porque elas se corrigem de maneiras
// diferentes: primeiros contra primeiros pede fatoração; primeiros contra
// seguidores pede rever a produção vazia, e às vezes o recorte da linguagem.
struct ConflitoLL1 {
std::string naoTerminal;
std::string simbolo;
std::vector<std::size_t> producoes; // índices em gramatica.producoes()
std::string origem;
};
// A tabela de análise: para cada par (não-terminal, terminal), qual produção
// aplicar. Célula com mais de uma produção é conflito, e conflito é a prova de
// que a gramática não é analisável com um símbolo de antecipação.
class TabelaDeAnalise {
public:
static constexpr std::size_t kSemProducao = static_cast<std::size_t>(-1);
TabelaDeAnalise(const Gramatica& gramatica, const ConjuntosDeAnalise& conjuntos);
std::size_t producaoPara(const std::string& naoTerminal, const std::string& terminal) const;
const std::vector<ConflitoLL1>& conflitos() const;
bool ehLL1() const;
// Os terminais que a tabela indexa, na ordem em que apareceram. São as
// colunas, e serve à impressão.
const std::vector<std::string>& terminais() const;
private:
std::unordered_map<std::string, std::size_t> celulas_;
std::vector<ConflitoLL1> conflitos_;
std::vector<std::string> terminais_;
};
// Um passo do reconhecedor dirigido por tabela, guardado para impressão. Guardar
// o traço é o que transforma o autômato de pilha de afirmação em observação.
struct PassoDaPilha {
std::string pilha;
std::string entrada;
std::string acao;
};
struct AnaliseDirigidaPorTabela {
std::vector<PassoDaPilha> passos;
std::size_t passosTotais = 0;
bool aceita = false;
std::string erro;
};
// O autômato de pilha do arco anterior, concreto. `maximoDePassosRegistrados`
// limita apenas o TRAÇO impresso, nunca a análise: o reconhecimento vai até o
// fim, e o que se corta é o volume de saída.
AnaliseDirigidaPorTabela analisarComTabela(const Gramatica& gramatica,
const TabelaDeAnalise& tabela,
const std::vector<std::string>& entrada,
std::size_t maximoDePassosRegistrados);
std::string formatarConjuntos(const Gramatica& gramatica, const ConjuntosDeAnalise& conjuntos);
std::string formatarConflitos(const Gramatica& gramatica, const std::vector<ConflitoLL1>& conflitos);
std::string formatarTabela(const Gramatica& gramatica, const TabelaDeAnalise& tabela);
std::string formatarTraco(const AnaliseDirigidaPorTabela& analise);
} // namespace peneira
#endif // PENEIRA_10_LL1_H10_ll1.cpp
// 10_ll1.cpp — Implementação dos conjuntos, da tabela e do reconhecedor de pilha.
#include "10_ll1.h"
#include <algorithm>
#include <sstream>
namespace peneira {
namespace {
// A chave de célula junta os dois índices num só. O separador é um byte que não
// pode aparecer em nome de símbolo, e por isso não há como duas células
// diferentes colidirem por concatenação.
std::string chaveDeCelula(const std::string& naoTerminal, const std::string& terminal) {
return naoTerminal + '\x01' + terminal;
}
std::string producaoFormatada(const Gramatica& gramatica, const std::size_t indice) {
const Producao& producao = gramatica.producoes()[indice];
return producao.cabeca + " -> " + formatarSimbolos(producao.corpo);
}
} // namespace
// --- conjuntos ---------------------------------------------------------------
bool ConjuntoDeSimbolos::contem(const std::string& terminal) const {
return std::find(terminais.begin(), terminais.end(), terminal) != terminais.end();
}
bool ConjuntoDeSimbolos::acrescentar(const std::string& terminal) {
if (contem(terminal)) {
return false;
}
terminais.push_back(terminal);
return true;
}
bool ConjuntoDeSimbolos::acrescentarTerminaisDe(const ConjuntoDeSimbolos& outro) {
bool mudou = false;
for (const std::string& terminal : outro.terminais) {
mudou = acrescentar(terminal) || mudou;
}
return mudou;
}
ConjuntosDeAnalise::ConjuntosDeAnalise(const Gramatica& gramatica) : gramatica_{gramatica} {
for (const std::string& naoTerminal : gramatica_.naoTerminais()) {
primeiros_[naoTerminal] = ConjuntoDeSimbolos{};
seguidores_[naoTerminal] = ConjuntoDeSimbolos{};
}
calcularPrimeiros();
calcularSeguidores();
}
void ConjuntosDeAnalise::calcularPrimeiros() {
// recorte:inicio primeiros-por-ponto-fixo
// Ponto fixo: repete a varredura inteira enquanto alguma coisa mudar. É mais
// lento do que uma ordem topológica e é imune à ordem em que as produções
// foram escritas — e a ordem das produções é justamente o que muda toda vez
// que a gramática é editada.
bool mudou = true;
while (mudou) {
mudou = false;
for (const Producao& producao : gramatica_.producoes()) {
ConjuntoDeSimbolos& destino = primeiros_[producao.cabeca];
bool todosAnulaveis = true;
for (const std::string& simbolo : producao.corpo) {
if (!gramatica_.ehNaoTerminal(simbolo)) {
mudou = destino.acrescentar(simbolo) || mudou;
todosAnulaveis = false;
break;
}
const ConjuntoDeSimbolos& doSimbolo = primeiros_[simbolo];
mudou = destino.acrescentarTerminaisDe(doSimbolo) || mudou;
if (!doSimbolo.derivaVazio) {
todosAnulaveis = false;
break;
}
}
// recorte:fim primeiros-por-ponto-fixo
// Corpo vazio, ou corpo inteiro anulável: o não-terminal deriva o
// vazio. Os dois casos caem aqui, e não por acaso — o corpo vazio é o
// caso-limite de "todos os símbolos derivam o vazio", com zero
// símbolos.
if (todosAnulaveis && !destino.derivaVazio) {
destino.derivaVazio = true;
mudou = true;
}
}
}
}
void ConjuntosDeAnalise::calcularSeguidores() {
// O fim de entrada segue o símbolo inicial. Sem esta linha, todo não-terminal
// que pode encerrar o programa ficaria sem nada em seus seguidores, e a
// produção vazia dele nunca seria escolhida.
seguidores_[gramatica_.inicial()].acrescentar(kFimDeEntrada);
bool mudou = true;
while (mudou) {
mudou = false;
for (const Producao& producao : gramatica_.producoes()) {
for (std::size_t i = 0; i < producao.corpo.size(); ++i) {
const std::string& simbolo = producao.corpo[i];
if (!gramatica_.ehNaoTerminal(simbolo)) {
continue;
}
const FormaSentencial resto(producao.corpo.begin() +
static_cast<std::ptrdiff_t>(i) + 1,
producao.corpo.end());
const ConjuntoDeSimbolos primeirosDoResto = primeirosDaForma(resto);
mudou = seguidores_[simbolo].acrescentarTerminaisDe(primeirosDoResto) || mudou;
// O que segue a cabeça também segue este símbolo quando o resto
// do corpo pode sumir. É o caso que a olho quase sempre escapa, e
// é o que decide a produção vazia mais adiante.
if (primeirosDoResto.derivaVazio) {
mudou = seguidores_[simbolo].acrescentarTerminaisDe(
seguidores_[producao.cabeca]) ||
mudou;
}
}
}
}
}
const ConjuntoDeSimbolos& ConjuntosDeAnalise::primeirosDe(const std::string& naoTerminal) const {
static const ConjuntoDeSimbolos vazio{};
const auto encontrado = primeiros_.find(naoTerminal);
return encontrado == primeiros_.end() ? vazio : encontrado->second;
}
const ConjuntoDeSimbolos& ConjuntosDeAnalise::seguidoresDe(const std::string& naoTerminal) const {
static const ConjuntoDeSimbolos vazio{};
const auto encontrado = seguidores_.find(naoTerminal);
return encontrado == seguidores_.end() ? vazio : encontrado->second;
}
ConjuntoDeSimbolos ConjuntosDeAnalise::primeirosDaForma(const FormaSentencial& forma) const {
ConjuntoDeSimbolos resultado;
for (const std::string& simbolo : forma) {
if (!gramatica_.ehNaoTerminal(simbolo)) {
resultado.acrescentar(simbolo);
return resultado;
}
const ConjuntoDeSimbolos& doSimbolo = primeirosDe(simbolo);
resultado.acrescentarTerminaisDe(doSimbolo);
if (!doSimbolo.derivaVazio) {
return resultado;
}
}
resultado.derivaVazio = true;
return resultado;
}
// --- tabela ------------------------------------------------------------------
TabelaDeAnalise::TabelaDeAnalise(const Gramatica& gramatica, const ConjuntosDeAnalise& conjuntos) {
const std::vector<Producao>& producoes = gramatica.producoes();
for (std::size_t indice = 0; indice < producoes.size(); ++indice) {
const Producao& producao = producoes[indice];
const ConjuntoDeSimbolos primeiros = conjuntos.primeirosDaForma(producao.corpo);
// recorte:inicio celula-vem-da-alternativa
// A célula é decidida pelos primeiros da ALTERNATIVA. Um erro recorrente
// aqui é usar os primeiros do não-terminal: a tabela sai preenchida, cada
// alternativa reivindica tudo o que a cabeça pode começar, e todas as
// células viram conflito.
std::vector<std::string> gatilhos = primeiros.terminais;
std::string origem = "primeiros";
if (primeiros.derivaVazio) {
for (const std::string& seguidor : conjuntos.seguidoresDe(producao.cabeca).terminais) {
if (std::find(gatilhos.begin(), gatilhos.end(), seguidor) == gatilhos.end()) {
gatilhos.push_back(seguidor);
}
}
origem = "primeiros e seguidores";
}
// recorte:fim celula-vem-da-alternativa
for (const std::string& terminal : gatilhos) {
if (std::find(terminais_.begin(), terminais_.end(), terminal) == terminais_.end()) {
terminais_.push_back(terminal);
}
const std::string chave = chaveDeCelula(producao.cabeca, terminal);
const auto ocupada = celulas_.find(chave);
if (ocupada == celulas_.end()) {
celulas_[chave] = indice;
continue;
}
// recorte:inicio conflito-guarda-as-duas
// Célula disputada. Guardamos as duas produções, e não apenas a
// segunda: a mensagem útil é "estas duas", nunca "esta aqui".
const auto jaRegistrado =
std::find_if(conflitos_.begin(), conflitos_.end(),
[&](const ConflitoLL1& conflito) {
return conflito.naoTerminal == producao.cabeca &&
conflito.simbolo == terminal;
});
// recorte:fim conflito-guarda-as-duas
if (jaRegistrado == conflitos_.end()) {
conflitos_.push_back(
ConflitoLL1{producao.cabeca, terminal, {ocupada->second, indice}, origem});
} else {
jaRegistrado->producoes.push_back(indice);
}
}
}
}
std::size_t TabelaDeAnalise::producaoPara(const std::string& naoTerminal,
const std::string& terminal) const {
const auto encontrada = celulas_.find(chaveDeCelula(naoTerminal, terminal));
return encontrada == celulas_.end() ? kSemProducao : encontrada->second;
}
const std::vector<ConflitoLL1>& TabelaDeAnalise::conflitos() const { return conflitos_; }
bool TabelaDeAnalise::ehLL1() const { return conflitos_.empty(); }
const std::vector<std::string>& TabelaDeAnalise::terminais() const { return terminais_; }
// --- o reconhecedor dirigido por tabela --------------------------------------
AnaliseDirigidaPorTabela analisarComTabela(const Gramatica& gramatica,
const TabelaDeAnalise& tabela,
const std::vector<std::string>& entrada,
const std::size_t maximoDePassosRegistrados) {
AnaliseDirigidaPorTabela resultado;
// A pilha guarda os símbolos AINDA POR CASAR, com o topo no fim do vetor. O
// fundo é o marcador de fim de entrada, e é ele que faz o aceite ser uma
// condição só: pilha e entrada terminam juntas.
std::vector<std::string> pilha{kFimDeEntrada, gramatica.inicial()};
std::size_t posicao = 0;
const auto formatarPilha = [&pilha]() {
std::string texto;
for (std::size_t i = pilha.size(); i > 0; --i) {
if (!texto.empty()) {
texto += ' ';
}
texto += pilha[i - 1];
}
return texto;
};
const auto formatarEntrada = [&entrada, &posicao]() {
std::string texto;
for (std::size_t i = posicao; i < entrada.size(); ++i) {
if (!texto.empty()) {
texto += ' ';
}
texto += entrada[i];
if (texto.size() > 40) {
texto += " ...";
break;
}
}
return texto.empty() ? std::string{kFimDeEntrada} : texto;
};
const auto registrar = [&](const std::string& acao) {
++resultado.passosTotais;
if (resultado.passos.size() < maximoDePassosRegistrados) {
resultado.passos.push_back(PassoDaPilha{formatarPilha(), formatarEntrada(), acao});
}
};
while (!pilha.empty()) {
const std::string topo = pilha.back();
const std::string adiante = posicao < entrada.size() ? entrada[posicao] : kFimDeEntrada;
if (topo == kFimDeEntrada && adiante == kFimDeEntrada) {
registrar("aceita");
resultado.aceita = true;
return resultado;
}
if (!gramatica.ehNaoTerminal(topo)) {
if (topo != adiante) {
registrar("erro");
resultado.erro = "esperava " + topo + " e encontrou " + adiante;
return resultado;
}
registrar("casa " + topo);
pilha.pop_back();
++posicao;
continue;
}
const std::size_t indice = tabela.producaoPara(topo, adiante);
if (indice == TabelaDeAnalise::kSemProducao) {
registrar("erro");
resultado.erro = "nenhuma producao de " + topo + " comeca por " + adiante;
return resultado;
}
registrar("aplica " + producaoFormatada(gramatica, indice));
pilha.pop_back();
const FormaSentencial& corpo = gramatica.producoes()[indice].corpo;
for (std::size_t i = corpo.size(); i > 0; --i) {
pilha.push_back(corpo[i - 1]);
}
}
resultado.erro = "a pilha esvaziou antes do fim da entrada";
return resultado;
}
// --- impressão ---------------------------------------------------------------
namespace {
std::string conjuntoFormatado(const ConjuntoDeSimbolos& conjunto) {
std::string texto = "{ ";
for (const std::string& terminal : conjunto.terminais) {
texto += terminal + ' ';
}
if (conjunto.derivaVazio) {
texto += "<vazio> ";
}
texto += '}';
return texto;
}
} // namespace
std::string formatarConjuntos(const Gramatica& gramatica, const ConjuntosDeAnalise& conjuntos) {
std::ostringstream saida;
for (const std::string& naoTerminal : gramatica.naoTerminais()) {
saida << naoTerminal << '\n';
saida << " primeiros: " << conjuntoFormatado(conjuntos.primeirosDe(naoTerminal)) << '\n';
saida << " seguidores: " << conjuntoFormatado(conjuntos.seguidoresDe(naoTerminal)) << '\n';
}
return saida.str();
}
std::string formatarConflitos(const Gramatica& gramatica,
const std::vector<ConflitoLL1>& conflitos) {
if (conflitos.empty()) {
return "nenhum conflito: a gramatica decide com um simbolo de antecipacao.\n";
}
std::ostringstream saida;
saida << conflitos.size() << " conflito(s):\n";
for (const ConflitoLL1& conflito : conflitos) {
saida << " [" << conflito.naoTerminal << ", " << conflito.simbolo << "] — "
<< conflito.origem << '\n';
for (const std::size_t indice : conflito.producoes) {
saida << " " << producaoFormatada(gramatica, indice) << '\n';
}
}
return saida.str();
}
std::string formatarTabela(const Gramatica& gramatica, const TabelaDeAnalise& tabela) {
std::ostringstream saida;
for (const std::string& naoTerminal : gramatica.naoTerminais()) {
for (const std::string& terminal : tabela.terminais()) {
const std::size_t indice = tabela.producaoPara(naoTerminal, terminal);
if (indice == TabelaDeAnalise::kSemProducao) {
continue;
}
saida << " [" << naoTerminal << ", " << terminal
<< "] = " << producaoFormatada(gramatica, indice) << '\n';
}
}
return saida.str();
}
std::string formatarTraco(const AnaliseDirigidaPorTabela& analise) {
std::ostringstream saida;
for (const PassoDaPilha& passo : analise.passos) {
saida << " pilha: " << passo.pilha << '\n';
saida << " vendo: " << passo.entrada << '\n';
saida << " acao: " << passo.acao << "\n\n";
}
if (analise.passos.size() < analise.passosTotais) {
saida << " ... mais " << analise.passosTotais - analise.passos.size()
<< " passos omitidos do traco.\n";
}
return saida.str();
}
} // namespace peneiraA decisão central deste arquivo é a mesma do capítulo anterior, levada um passo adiante: os conjuntos são calculados a partir da gramática como dado, e não escritos à mão ao lado do analisador. Escritos à mão, eles são uma promessa sobre a gramática, e a promessa se desfaz na primeira regra alterada, em silêncio. Sendo calculados, alterar a gramática recalcula os conjuntos, e a condição de analisabilidade é reverificada sem que ninguém precise lembrar de fazê-lo.
O cálculo é por ponto fixo: repete-se a varredura inteira enquanto alguma coisa mudar. Existe forma mais rápida, com ordenação topológica, e ela foi recusada por uma razão concreta — a forma rápida depende da ordem em que as produções foram escritas, e a ordem das produções é justamente o que muda toda vez que alguém edita a gramática. Aqui a lentidão é irrelevante e a robustez não é.
Duas armadilhas de implementação estão marcadas no código, porque as duas produzem resultado plausível e errado. A primeira é tratar o vazio como se fosse um terminal do conjunto: ele não é, e guardá-lo junto produz o analisador que tenta casar o vazio na entrada e trava. Por isso a marca de que a forma pode derivar o vazio fica separada da lista. A segunda é usar os primeiros do não terminal para preencher a tabela, quando o correto são os primeiros da alternativa: com o erro, a tabela sai preenchida, cada alternativa reivindica tudo o que a cabeça pode começar, e todas as células viram conflito. É o tipo de defeito que se manifesta como “minha gramática inteira está errada” e não é isso.
O que a solução faz com os conjuntos é a verificação da condição, e ela é apresentada como comparação porque só assim ela ensina alguma coisa. A demonstração monta a tabela duas vezes: sobre a gramática escrita por extenso, antes das transformações, e sobre a gramática preparada. A primeira acusa dezenove células disputadas, e o relatório separa as duas famílias, porque elas se corrigem de maneiras diferentes — primeiros contra primeiros pede fatoração, primeiros contra seguidores pede rever a produção vazia. A segunda não acusa nenhuma. A bateria de testes reprova se a preparada deixar de decidir com um símbolo de antecipação, o que fecha o ciclo aberto no capítulo anterior: lá se transformou a gramática, aqui se prova que a transformação bastou.
1.6 A variante dirigida por tabela, e o que ela expõe
O analisador que o sistema usa é o recursivo. A variante dirigida por tabela existe na solução mesmo assim, e por duas razões que justificam o código que ela custa.
A primeira é que ela torna visível o que o analisador recursivo esconde na forma dos procedimentos. No recursivo, a decisão está distribuída por dezenas de comandos condicionais; na tabela, ela está em células, e uma célula com duas produções é um conflito que salta aos olhos — enquanto o mesmo conflito, numa cadeia de condicionais, aparece como um ramo que nunca é tomado, que é a definição de defeito silencioso. A tabela é, nesse sentido, o instrumento de diagnóstico do analisador que não a usa.
A segunda é que ela é o autômato de pilha do capítulo anterior, agora concreto. O modelo abstrato — pilha, símbolo de antecipação, tabela de transição — vira aqui um laço de vinte linhas, e a solução guarda o traço de cada passo para que ele possa ser lido: a pilha de um lado, a entrada restante do outro, e a ação tomada. Sobre a descrição de referência, o reconhecimento fecha em oitenta e nove passos, sem um único retrocesso. O contraste com o capítulo anterior é o argumento inteiro do módulo em um número: lá, a busca com retrocesso tentava milhares de expansões para encontrar a mesma derivação. A diferença está na gramática que o capítulo anterior preparou, e não na esperteza do reconhecedor.
O traço impresso é truncado nos primeiros passos, e o corte é do relatório, nunca da análise: o reconhecimento vai até o fim, e o que se limita é o volume de saída. Confundir as duas coisas produziria um reconhecedor que aceita o que não deveria por ter parado cedo, que é o pior defeito possível numa peça de verificação.
1.7 O que este capítulo entrega ao arco seguinte
O produto do módulo é a árvore. O analisador é o meio pelo qual ela é construída, e a partir daqui ele desaparece de vista: nenhuma fase seguinte volta a olhar para símbolos, e é isso que significa uma fase estar fechada. A análise semântica recebe a árvore e a percorre; o gerador de código percorre a mesma estrutura; a máquina de execução consome o que o gerador produziu. A cadeia inteira que resta depende da qualidade da estrutura projetada na primeira tarefa, e é por isso que ela é a primeira.
Duas dívidas ficam explicitamente registradas para o módulo seguinte, e as duas são de natureza semântica, não sintática. A árvore atual aceita uma ação que cita um padrão nunca declarado, e aceita um nome ligado que não é usado em lugar nenhum — as duas coisas são sintaticamente perfeitas, e recusá-las aqui seria misturar as fases. O lugar delas é a tabela de símbolos, e a posição guardada em cada nó existe justamente para que essas recusas tenham onde apontar quando chegarem.