1 Análise léxica — 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 especificação dos símbolos é da sua linguagem, e o que ela declara depende do recorte que você fixou no primeiro capítulo. O que se copia daqui é a exigência de que nenhuma linha de reconhecimento nova apareça, e a de que a posição no texto entre no sistema agora, e não depois.
1.1 Visão Geral
Este é o módulo em que a máquina teórica vira componente de software, e o que se pede dele é interface, não capacidade nova. As três tarefas descrevem o mesmo movimento visto de três ângulos: o reconhecedor construído nos cinco módulos anteriores passa a ser instanciado sobre uma segunda especificação, a que descreve os símbolos da própria linguagem; o texto que quem usa o sistema escreve passa a ser percorrido por essa instância; e o caractere que não pertence a nenhum padrão passa a produzir uma resposta endereçada a quem escreveu o texto.
A afirmação mais importante da solução cabe numa medida, e ela está impressa na saída do programa: a especificação léxica inteira da linguagem tem vinte e oito regras, e o arquivo que a implementa não contém nenhuma linha de reconhecimento. Cada uma das vinte e oito passou pelas mesmas quatro peças de sempre — leitura da expressão, construção de Thompson, determinização, minimização —, e o que o módulo acrescenta é a especificação, o critério de desempate entre padrões que disputam a mesma posição do texto, e o transporte da posição.
Vale enunciar de saída por que essa economia é o coração do artefato e não uma elegância opcional. O sistema tem dois níveis em que padrões são compilados: os que quem usa a linguagem declara, e os que a linguagem usa para se descrever. Se este módulo tivesse escrito um reconhecedor próprio ao lado do que já funcionava, o sistema teria dois reconhecedores — e a afirmação que a obra faz sobre autômatos seria falsa dentro do seu próprio artefato. É a diferença entre demonstrar uma teoria e ilustrá-la.
O módulo cobre a teoria inteira do capítulo: a distinção entre token, lexema e padrão fica materializada na estrutura de dados que atravessa a fronteira entre as duas fases; a especificação por expressões regulares é a lista de regras compiladas; o casamento mais longo e o desempate entre padrões concorrentes são o laço de decisão do reconhecedor, e a demonstração os exibe falhando quando invertidos; espaços e comentários entram como regras de descarte em pé de igualdade com as demais; a posição no texto é dado transportado desde o primeiro símbolo; e a tabela de símbolos aparece na forma mínima que esta fase comporta.
1.2 Tarefa 1: Reaproveitar o reconhecedor como componente com interface
O que a tarefa pede
Transformar o reconhecedor construído até aqui em um componente com interface definida, e fazer o sistema ler a própria descrição escrita pelo usuário instanciando esse mesmo componente sobre outra especificação. Não há reconhecimento novo a escrever: o que muda é a especificação alimentada ao que já existe. Código de reconhecimento novo, escrito em paralelo ao que já funciona, é defeito de projeto e não avanço — e aqui o defeito é especialmente caro, porque destrói justamente a economia estrutural que sustenta o sistema inteiro. Se a interface do componente não permite reaproveitá-lo, o que precisa mudar é a interface, não a decisão de reaproveitar.
07_lexer.h
// 07_lexer.h — O reconhecedor de símbolos da própria Peneira.
//
// Este é o arco em que a máquina teórica vira componente de software, e o que se
// pede dele não é capacidade nova: é INTERFACE. Não há nenhuma linha de
// reconhecimento aqui. O reconhecimento é o mesmo dos arcos anteriores —
// leitura da expressão, construção de Thompson, determinização, minimização —,
// instanciado sobre outra especificação. O que este arquivo acrescenta é a
// especificação, o desempate entre padrões que concorrem pela mesma posição, e o
// transporte da posição no texto.
//
// A ECONOMIA ESTRUTURAL DO SISTEMA ESTÁ AQUI, e vale enunciá-la antes do código:
// o mesmo componente que compila os `pattern` escritos por quem usa a Peneira
// compila os símbolos da linguagem em que esses `pattern` são escritos. Uma peça,
// dois níveis. Se este arquivo tivesse um reconhecedor próprio, escrito à mão ao
// lado do que já funciona, o sistema teria dois — e a afirmação que a obra faz
// sobre autômatos seria falsa no seu próprio artefato.
//
// TRÊS CONCEITOS QUE O CÓDIGO SEPARA DE PROPÓSITO. O *padrão* é a expressão que
// descreve uma classe de trechos (`[a-zA-Z_][a-zA-Z0-9_]*`); o *lexema* é o
// trecho concreto que apareceu no texto (`email`); o *token* é o que se entrega à
// fase seguinte — a categoria mais o lexema mais a posição. Confundir lexema com
// token é o que produz um analisador sintático que precisa reexaminar caracteres,
// e a fronteira entre as duas fases deixa de existir.
#ifndef PENEIRA_07_LEXER_H
#define PENEIRA_07_LEXER_H
#include <cstddef>
#include <string>
#include <vector>
#include "03_afd.h"
namespace peneira {
// As categorias que a fase entrega ao analisador sintático. `Descartado` não é
// categoria de token: é a marca das regras cujo casamento não produz símbolo
// algum — espaço e comentário. Elas participam do reconhecimento em pé de
// igualdade com as demais, e é isso que impede o descarte de virar um laço
// separado que come caracteres antes do reconhecimento começar.
enum class TipoDeToken {
PalavraPattern,
PalavraRule,
PalavraOn,
PalavraWhere,
PalavraEmit,
PalavraValue,
OperadorAnd,
OperadorOr,
Identificador,
Numero,
Texto,
ExpressaoDePadrao,
AbreParenteses,
FechaParenteses,
AbreChaves,
FechaChaves,
PontoEVirgula,
Virgula,
Igual,
Seta,
Menor,
Maior,
MenorOuIgual,
MaiorOuIgual,
IgualIgual,
Diferente,
FimDeArquivo,
Descartado,
};
// A posição de origem, transportada com cada símbolo. São três números e não um
// porque servem a leitores diferentes: o deslocamento em bytes é o que o
// programa usa para recortar o texto, e o par linha/coluna é o que a pessoa usa
// para achar o lugar no editor.
//
// A coluna conta CARACTERES, não bytes: um byte de continuação de UTF-8 não
// avança a coluna. Sem isso, um travessão num comentário deslocaria em duas
// colunas todas as mensagens de erro daquela linha — e o defeito só apareceria
// em arquivo com acento, que é a pior forma de um defeito aparecer.
struct Posicao {
std::size_t deslocamento = 0;
std::size_t linha = 1;
std::size_t coluna = 1;
};
// Índice ausente na tabela de símbolos: vale para todo token que não é nome.
inline constexpr std::size_t kSemEntrada = static_cast<std::size_t>(-1);
struct Token {
TipoDeToken tipo = TipoDeToken::FimDeArquivo;
std::string lexema;
Posicao posicao;
// Preenchido apenas em `Identificador`. É a interação mínima com a tabela de
// símbolos: o léxico não sabe o que o nome significa — sabe apenas que é o
// mesmo nome de antes, e diz onde ele está registrado.
std::size_t entradaNaTabela = kSemEntrada;
};
// A recusa dirigida a quem escreveu a descrição, e não a quem escreveu o
// sistema. É a primeira do percurso, e a forma decidida aqui é herdada por todas
// as famílias de recusa dos arcos seguintes.
struct ErroLexico {
Posicao posicao;
std::string trecho; // o caractere ofensor, inteiro, mesmo em UTF-8
std::string mensagem;
};
// Uma entrada da tabela de símbolos em sua forma mínima. Ainda não há tipo nem
// escopo — os dois entram no arco de análise semântica. O que existe já é o
// suficiente para o propósito desta fase: um nome ocorre uma vez na tabela, por
// mais vezes que ocorra no texto.
struct EntradaDeSimbolo {
std::string nome;
Posicao primeiraOcorrencia;
std::size_t ocorrencias = 0;
};
class TabelaDeSimbolos {
public:
// Devolve o índice da entrada, criando-a se for a primeira ocorrência.
std::size_t registrar(const std::string& nome, const Posicao& posicao);
const std::vector<EntradaDeSimbolo>& entradas() const;
private:
std::vector<EntradaDeSimbolo> entradas_;
};
// Uma regra léxica: o nome pelo qual a demonstração se refere a ela, a expressão
// que a descreve na mesma notação que quem usa a Peneira escreve, e a categoria
// que o casamento produz. A ORDEM da lista é significativa — ela é o critério de
// desempate quando dois padrões casam trechos de mesmo comprimento.
struct RegraLexica {
std::string nome;
std::string expressao;
TipoDeToken tipo = TipoDeToken::Descartado;
};
// A especificação dos símbolos da Peneira, na ordem de prioridade.
std::vector<RegraLexica> regrasDaPeneira();
// O alfabeto declarado da linguagem: tabulação, quebra de linha, retorno, os
// imprimíveis de ASCII e todos os bytes altos. Os bytes altos entram porque
// comentário e literal de texto são transparentes à codificação — o reconhecedor
// trabalha byte a byte e não precisa saber o que é um travessão, só que não é
// delimitador. Fechar o alfabeto é o que permite distinguir, na recusa, o
// símbolo que não pertence à linguagem do símbolo que está no lugar errado.
std::string alfabetoDaPeneira();
// Constrói a expressão que casa qualquer símbolo do alfabeto menos os excluídos.
// O recorte do primeiro arco não tem classe negada, então o complemento é
// ENUMERADO — e quem o enumera é esta função, não a mão. É o primeiro ponto do
// percurso em que uma decisão de recorte cobra preço concreto, e o preço é
// medível: aparece na contagem de nós da árvore, e desaparece na minimização.
std::string qualquerSimboloExceto(const std::string& excluidos);
// O que sobrou de cada regra depois de compilada, com as medidas que a
// demonstração usa para mostrar que nada foi reconhecido por código novo.
struct PadraoCompilado {
std::string nome;
TipoDeToken tipo = TipoDeToken::Descartado;
std::size_t nosDaArvore = 0;
std::size_t estadosDoAfn = 0;
std::size_t estadosDoAfd = 0;
std::size_t estadosMinimos = 0;
Afd afd;
};
struct ResultadoLexico {
std::vector<Token> tokens;
std::vector<ErroLexico> erros;
TabelaDeSimbolos tabela;
std::size_t descartados = 0; // espaços e comentários consumidos
bool ok() const;
};
class AnalisadorLexico {
public:
// Compila cada regra pelo caminho já construído: expressão em árvore, árvore
// em máquina não determinística, máquina em determinística, determinística em
// mínima. Se alguma expressão da especificação estiver malformada, o nome dela
// fica em `regrasInvalidas` — é defeito de quem escreveu a especificação, e
// não de quem escreve na linguagem.
explicit AnalisadorLexico(const std::vector<RegraLexica>& regras);
ResultadoLexico analisar(const std::string& texto) const;
const std::vector<PadraoCompilado>& padroes() const;
const std::vector<std::string>& regrasInvalidas() const;
private:
std::vector<PadraoCompilado> padroes_;
std::vector<std::string> regrasInvalidas_;
std::string alfabeto_;
};
// O maior prefixo de `texto`, a partir de `inicio`, que a máquina aceita. Zero
// quer dizer que nenhum prefixo foi aceito — e não que o vazio foi aceito, que é
// a confusão que faz o reconhecedor entrar em laço infinito na primeira posição
// que não casa.
std::size_t maiorPrefixoAceito(const Afd& afd, const std::string& texto, std::size_t inicio);
std::string nomeDoTipo(TipoDeToken tipo);
std::string formatarTokens(const std::vector<Token>& tokens);
std::string formatarEspecificacao(const std::vector<PadraoCompilado>& padroes);
std::string formatarTabelaDeSimbolos(const TabelaDeSimbolos& tabela);
// A mensagem de recusa com a linha de origem e o cursor sob a coluna.
std::string formatarErroLexico(const std::string& texto, const ErroLexico& erro);
// Lê o arquivo inteiro em memória. Devolve falso se não abriu — e o chamador
// precisa distinguir isso de arquivo vazio, que é entrada legítima.
bool lerArquivo(const std::string& caminho, std::string& conteudo);
} // namespace peneira
#endif // PENEIRA_07_LEXER_H07_lexer.cpp
#include "07_lexer.h"
#include <algorithm>
#include <fstream>
#include <sstream>
#include "02_regex.h"
#include "04_afn.h"
#include "05_determinizacao.h"
namespace peneira {
namespace {
// Um byte de continuação de UTF-8 tem os dois bits mais altos em 10. Não é um
// caractere: é a segunda, terceira ou quarta parte de um. Contá-lo como coluna é
// o que faz a seta da mensagem de erro apontar para o lugar errado.
bool ehContinuacaoUtf8(const char byte) {
return (static_cast<unsigned char>(byte) & 0xC0U) == 0x80U;
}
// Avança a posição pelo trecho consumido. É a única função do arquivo que mexe
// em linha e coluna, e essa concentração é deliberada: posição atualizada em
// mais de um lugar é posição que diverge no primeiro caso de borda.
// recorte:inicio posicao-tres-numeros
void avancar(Posicao& posicao, const std::string& trecho) {
for (const char simbolo : trecho) {
++posicao.deslocamento;
if (simbolo == '\n') {
++posicao.linha;
posicao.coluna = 1;
} else if (simbolo == '\r' || ehContinuacaoUtf8(simbolo)) {
// Nem um nem outro ocupa coluna própria.
} else {
++posicao.coluna;
// recorte:fim posicao-tres-numeros
}
}
}
// O caractere completo que começa em `inicio` — o byte inicial mais os bytes de
// continuação que o acompanham. A recusa precisa dele inteiro: apontar um byte
// solto de um travessão diria "simbolo 0xE2", que não ajuda ninguém.
std::string caractereEm(const std::string& texto, const std::size_t inicio) {
std::string caractere(1, texto[inicio]);
std::size_t i = inicio + 1;
while (i < texto.size() && ehContinuacaoUtf8(texto[i])) {
caractere += texto[i];
++i;
}
return caractere;
}
std::string escapadoParaExibicao(const std::string& trecho) {
std::string saida;
for (const char simbolo : trecho) {
if (simbolo == '\n') {
saida += "\\n";
} else if (simbolo == '\t') {
saida += "\\t";
} else if (simbolo == '\r') {
saida += "\\r";
} else {
saida += simbolo;
}
}
return saida;
}
std::string preencher(const std::string& texto, const std::size_t largura) {
std::string saida = texto;
while (saida.size() < largura) {
saida += ' ';
}
return saida;
}
std::string emNumero(const std::size_t valor) {
std::ostringstream fluxo;
fluxo << valor;
return fluxo.str();
}
// A linha de `texto` que contém o deslocamento dado, sem a quebra final.
std::string linhaDe(const std::string& texto, const std::size_t deslocamento) {
std::size_t inicio = deslocamento;
while (inicio > 0 && texto[inicio - 1] != '\n') {
--inicio;
}
std::size_t fim = deslocamento;
while (fim < texto.size() && texto[fim] != '\n') {
++fim;
}
std::string linha = texto.substr(inicio, fim - inicio);
if (!linha.empty() && linha.back() == '\r') {
linha.pop_back();
}
return linha;
}
} // namespace
std::string alfabetoDaPeneira() {
std::string alfabeto;
alfabeto += '\t';
alfabeto += '\n';
alfabeto += '\r';
for (int codigo = 32; codigo <= 126; ++codigo) {
alfabeto += static_cast<char>(codigo);
}
// Os bytes altos: comentário e literal de texto são transparentes à
// codificação, e o reconhecedor não precisa saber o que eles formam.
for (int codigo = 128; codigo <= 255; ++codigo) {
alfabeto += static_cast<char>(codigo);
}
return alfabeto;
}
std::string qualquerSimboloExceto(const std::string& excluidos) {
std::vector<bool> presente(256, false);
for (const char simbolo : alfabetoDaPeneira()) {
presente[static_cast<unsigned char>(simbolo)] = true;
}
for (const char simbolo : excluidos) {
presente[static_cast<unsigned char>(simbolo)] = false;
}
// Dois símbolos não podem entrar na classe porque a notação de classe os usa
// como pontuação: o fecha-colchetes a terminaria, e o hífen viraria faixa.
// Saem para uma alternância à parte, onde a barra invertida os torna literais.
std::string avulsos;
for (const char especial : std::string("-]")) {
const std::size_t indice = static_cast<unsigned char>(especial);
if (presente[indice]) {
avulsos += '\\';
avulsos += especial;
avulsos += '|';
presente[indice] = false;
}
}
std::string classe = "[";
int codigo = 0;
while (codigo < 256) {
if (!presente[static_cast<std::size_t>(codigo)]) {
++codigo;
continue;
}
const int inicio = codigo;
while (codigo < 256 && presente[static_cast<std::size_t>(codigo)]) {
++codigo;
}
const int fim = codigo - 1;
if (fim - inicio >= 2) {
classe += static_cast<char>(inicio);
classe += '-';
classe += static_cast<char>(fim);
} else {
for (int k = inicio; k <= fim; ++k) {
classe += static_cast<char>(k);
}
}
}
classe += ']';
return "(" + avulsos + classe + ")";
}
std::vector<RegraLexica> regrasDaPeneira() {
// recorte:inicio complemento-gerado-nao-digitado
// Os três complementos que a linguagem precisa. Note que nenhum deles é
// digitado: são gerados, e por isso não há como esquecer um símbolo.
const std::string corpoDeComentario = qualquerSimboloExceto("\n\r");
const std::string corpoDeTexto = qualquerSimboloExceto("\"\n\r");
const std::string corpoDePadrao = qualquerSimboloExceto("/\n\r");
// recorte:fim complemento-gerado-nao-digitado
// recorte:inicio ordem-das-regras-e-o-desempate
// A ordem é o critério de desempate, e ela codifica duas decisões. Descarte
// vem primeiro por clareza, não por necessidade. Palavra reservada vem antes
// de identificador porque as duas casam o mesmo trecho com o mesmo
// comprimento — e sem a ordem, `rule` seria um nome de variável.
return {
{"comentario", "//" + corpoDeComentario + "*", TipoDeToken::Descartado},
{"espaco", "( |\t|\n|\r)+", TipoDeToken::Descartado},
{"pattern", "pattern", TipoDeToken::PalavraPattern},
{"rule", "rule", TipoDeToken::PalavraRule},
{"on", "on", TipoDeToken::PalavraOn},
{"where", "where", TipoDeToken::PalavraWhere},
{"emit", "emit", TipoDeToken::PalavraEmit},
{"value", "value", TipoDeToken::PalavraValue},
{"and", "and", TipoDeToken::OperadorAnd},
{"or", "or", TipoDeToken::OperadorOr},
// recorte:fim ordem-das-regras-e-o-desempate
{"identificador", "[a-zA-Z_][a-zA-Z0-9_]*", TipoDeToken::Identificador},
{"numero", "-?[0-9]+(\\.[0-9]+)?", TipoDeToken::Numero},
{"texto", "\"" + corpoDeTexto + "*\"", TipoDeToken::Texto},
{"padrao", "/" + corpoDePadrao + "+/", TipoDeToken::ExpressaoDePadrao},
{"seta", "=>", TipoDeToken::Seta},
{"igual_igual", "==", TipoDeToken::IgualIgual},
{"diferente", "!=", TipoDeToken::Diferente},
{"menor_ou_igual", "<=", TipoDeToken::MenorOuIgual},
{"maior_ou_igual", ">=", TipoDeToken::MaiorOuIgual},
{"igual", "=", TipoDeToken::Igual},
{"menor", "<", TipoDeToken::Menor},
{"maior", ">", TipoDeToken::Maior},
{"abre_parenteses", "\\(", TipoDeToken::AbreParenteses},
{"fecha_parenteses", "\\)", TipoDeToken::FechaParenteses},
{"abre_chaves", "{", TipoDeToken::AbreChaves},
{"fecha_chaves", "}", TipoDeToken::FechaChaves},
{"ponto_e_virgula", ";", TipoDeToken::PontoEVirgula},
{"virgula", ",", TipoDeToken::Virgula},
};
}
std::size_t TabelaDeSimbolos::registrar(const std::string& nome, const Posicao& posicao) {
for (std::size_t i = 0; i < entradas_.size(); ++i) {
if (entradas_[i].nome == nome) {
++entradas_[i].ocorrencias;
return i;
}
}
entradas_.push_back(EntradaDeSimbolo{nome, posicao, 1});
return entradas_.size() - 1;
}
const std::vector<EntradaDeSimbolo>& TabelaDeSimbolos::entradas() const { return entradas_; }
bool ResultadoLexico::ok() const { return erros.empty(); }
AnalisadorLexico::AnalisadorLexico(const std::vector<RegraLexica>& regras)
: alfabeto_(alfabetoDaPeneira()) {
for (const RegraLexica& regra : regras) {
// recorte:inicio quatro-pecas-viram-uma-fase
// Este bloco é a tarefa inteira do arco. Não há nada aqui que reconheça
// coisa alguma: há quatro chamadas às peças que já existiam, na ordem em
// que foram construídas, alimentadas por outra especificação.
const Resultado leitura = analisarExpressao(regra.expressao);
if (!leitura.ok) {
regrasInvalidas_.push_back(regra.nome);
continue;
}
const Afn afn = construirThompson(leitura.arvore);
const ResultadoDaDeterminizacao determinizado = determinizar(afn, alfabeto_);
const ResultadoDaMinimizacao minimo = minimizar(determinizado.afd);
// recorte:fim quatro-pecas-viram-uma-fase
PadraoCompilado padrao;
padrao.nome = regra.nome;
padrao.tipo = regra.tipo;
padrao.nosDaArvore = tamanho(leitura.arvore);
padrao.estadosDoAfn = afn.quantidadeDeEstados();
padrao.estadosDoAfd = determinizado.estadosDoAfd;
padrao.estadosMinimos = minimo.estadosDepois;
padrao.afd = minimo.afd;
padroes_.push_back(padrao);
}
}
const std::vector<PadraoCompilado>& AnalisadorLexico::padroes() const { return padroes_; }
const std::vector<std::string>& AnalisadorLexico::regrasInvalidas() const {
return regrasInvalidas_;
}
std::size_t maiorPrefixoAceito(const Afd& afd, const std::string& texto,
const std::size_t inicio) {
Estado atual = afd.estadoInicial();
const Estado erro = afd.estadoDeErro();
std::size_t melhor = 0;
for (std::size_t i = inicio; i < texto.size(); ++i) {
atual = afd.transicao(atual, texto[i]);
if (atual == erro) {
break;
}
if (afd.ehDeAceitacao(atual)) {
melhor = i - inicio + 1;
}
}
return melhor;
}
ResultadoLexico AnalisadorLexico::analisar(const std::string& texto) const {
ResultadoLexico resultado;
Posicao posicao;
std::size_t i = 0;
while (i < texto.size()) {
// recorte:inicio casamento-mais-longo
// Casamento mais longo: percorremos TODOS os padrões e ficamos com o
// maior. Parar no primeiro que casa é o defeito clássico da fase, e ele
// não se manifesta na maioria dos programas — só naquele em que um nome
// começa por palavra reservada.
std::size_t melhorComprimento = 0;
const PadraoCompilado* vencedor = nullptr;
for (const PadraoCompilado& padrao : padroes_) {
const std::size_t comprimento = maiorPrefixoAceito(padrao.afd, texto, i);
// A comparação é estritamente maior, e é isso — e só isso — que faz
// a ordem de declaração ser o desempate entre comprimentos iguais.
if (comprimento > melhorComprimento) {
melhorComprimento = comprimento;
vencedor = &padrao;
}
}
// recorte:fim casamento-mais-longo
if (vencedor == nullptr) {
const std::string ofensor = caractereEm(texto, i);
const bool noAlfabeto =
ofensor.size() == 1 &&
alfabeto_.find(ofensor[0]) != std::string::npos;
ErroLexico erro;
erro.posicao = posicao;
erro.trecho = ofensor;
// recorte:inicio recusar-sem-parar-a-leitura
erro.mensagem = noAlfabeto
? "simbolo '" + escapadoParaExibicao(ofensor) +
"' nao inicia nenhum simbolo da linguagem"
: "caractere '" + ofensor +
"' nao pertence ao alfabeto da linguagem";
resultado.erros.push_back(erro);
// Recuperação: consome o caractere ofensor inteiro e continua. Parar
// no primeiro erro entregaria uma recusa por execução, e quem escreve
// a descrição corrigiria um caractere de cada vez.
avancar(posicao, ofensor);
i += ofensor.size();
// recorte:fim recusar-sem-parar-a-leitura
continue;
}
const std::string lexema = texto.substr(i, melhorComprimento);
if (vencedor->tipo == TipoDeToken::Descartado) {
++resultado.descartados;
} else {
Token token;
token.tipo = vencedor->tipo;
token.lexema = lexema;
token.posicao = posicao;
if (token.tipo == TipoDeToken::Identificador) {
token.entradaNaTabela = resultado.tabela.registrar(lexema, posicao);
}
resultado.tokens.push_back(token);
}
// O descarte acontece DEPOIS de avançar a posição, e nunca antes: é aqui
// que se perde a posição dos símbolos seguintes quando o espaço é comido
// por um laço à parte que não atualiza linha e coluna.
avancar(posicao, lexema);
i += melhorComprimento;
}
Token fim;
fim.tipo = TipoDeToken::FimDeArquivo;
fim.posicao = posicao;
resultado.tokens.push_back(fim);
return resultado;
}
std::string nomeDoTipo(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::OperadorAnd: return "AND";
case TipoDeToken::OperadorOr: return "OR";
case TipoDeToken::Identificador: return "ID";
case TipoDeToken::Numero: return "NUMERO";
case TipoDeToken::Texto: return "TEXTO";
case TipoDeToken::ExpressaoDePadrao: return "REGEX";
case TipoDeToken::AbreParenteses: return "ABRE_PAR";
case TipoDeToken::FechaParenteses: return "FECHA_PAR";
case TipoDeToken::AbreChaves: return "ABRE_CHAVE";
case TipoDeToken::FechaChaves: return "FECHA_CHAVE";
case TipoDeToken::PontoEVirgula: return "PONTO_VIRGULA";
case TipoDeToken::Virgula: return "VIRGULA";
case TipoDeToken::Igual: return "IGUAL";
case TipoDeToken::Seta: return "SETA";
case TipoDeToken::Menor: return "MENOR";
case TipoDeToken::Maior: return "MAIOR";
case TipoDeToken::MenorOuIgual: return "MENOR_IGUAL";
case TipoDeToken::MaiorOuIgual: return "MAIOR_IGUAL";
case TipoDeToken::IgualIgual: return "IGUAL_IGUAL";
case TipoDeToken::Diferente: return "DIFERENTE";
case TipoDeToken::FimDeArquivo: return "FIM";
case TipoDeToken::Descartado: return "DESCARTADO";
}
return "?";
}
std::string formatarTokens(const std::vector<Token>& tokens) {
std::ostringstream saida;
saida << preencher("linha:coluna", 14) << preencher("token", 16) << "lexema\n";
saida << std::string(60, '-') << '\n';
for (const Token& token : tokens) {
const std::string local = emNumero(token.posicao.linha) + ":" +
emNumero(token.posicao.coluna);
saida << preencher(local, 14) << preencher(nomeDoTipo(token.tipo), 16)
<< escapadoParaExibicao(token.lexema);
if (token.entradaNaTabela != kSemEntrada) {
saida << " [simbolo #" << token.entradaNaTabela << "]";
}
saida << '\n';
}
return saida.str();
}
std::string formatarEspecificacao(const std::vector<PadraoCompilado>& padroes) {
std::ostringstream saida;
saida << preencher("regra", 18) << preencher("nos", 8) << preencher("AFN", 8)
<< preencher("AFD", 8) << "minimo\n";
saida << std::string(50, '-') << '\n';
std::size_t nos = 0;
std::size_t minimos = 0;
for (const PadraoCompilado& padrao : padroes) {
saida << preencher(padrao.nome, 18) << preencher(emNumero(padrao.nosDaArvore), 8)
<< preencher(emNumero(padrao.estadosDoAfn), 8)
<< preencher(emNumero(padrao.estadosDoAfd), 8)
<< padrao.estadosMinimos << '\n';
nos += padrao.nosDaArvore;
minimos += padrao.estadosMinimos;
}
saida << std::string(50, '-') << '\n';
saida << preencher("total", 18) << preencher(emNumero(nos), 8) << preencher("", 8)
<< preencher("", 8) << minimos << '\n';
return saida.str();
}
std::string formatarTabelaDeSimbolos(const TabelaDeSimbolos& tabela) {
std::ostringstream saida;
saida << preencher("#", 4) << preencher("nome", 16) << preencher("1a ocorrencia", 16)
<< "ocorrencias\n";
saida << std::string(50, '-') << '\n';
const std::vector<EntradaDeSimbolo>& entradas = tabela.entradas();
for (std::size_t i = 0; i < entradas.size(); ++i) {
const EntradaDeSimbolo& entrada = entradas[i];
const std::string local = emNumero(entrada.primeiraOcorrencia.linha) + ":" +
emNumero(entrada.primeiraOcorrencia.coluna);
saida << preencher(emNumero(i), 4) << preencher(entrada.nome, 16)
<< preencher(local, 16) << entrada.ocorrencias << '\n';
}
return saida.str();
}
std::string formatarErroLexico(const std::string& texto, const ErroLexico& erro) {
std::ostringstream saida;
saida << "erro lexico 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();
}
bool lerArquivo(const std::string& caminho, std::string& conteudo) {
std::ifstream arquivo(caminho, std::ios::binary);
if (!arquivo) {
return false;
}
std::ostringstream fluxo;
fluxo << arquivo.rdbuf();
conteudo = fluxo.str();
return true;
}
} // namespace peneiraA resolução da tarefa está concentrada em oito linhas do construtor do analisador, e vale lê-las antes de qualquer outra coisa do arquivo: para cada regra da especificação, lê-se a expressão, constrói-se a máquina não determinística, determiniza-se, minimiza-se. São quatro chamadas a funções que já existiam, na ordem em que foram construídas. Não há um caso especial, não há uma segunda implementação de leitura de expressões, não há um reconhecedor de identificadores escrito à mão porque identificador é fácil.
A especificação, essa sim, é nova — e ela é escrita na mesma notação que quem usa o sistema escreve. O padrão de identificador é a expressão de classe de símbolos seguida de um fecho; o de número é o mesmo que aparece no exemplo do primeiro capítulo, sinal opcional e parte fracionária opcional. Quem lê a especificação lê patterns, e não código. Foi essa a promessa do primeiro capítulo, e é aqui que ela se paga.
Duas decisões de interface merecem ser justificadas, porque a tarefa avisa que é a interface, e não o reaproveitamento, o que deve ceder quando os dois não cabem juntos.
A primeira é que a ordem da lista de regras é significativa. Ela é o critério de desempate quando dois padrões casam trechos de mesmo comprimento, e por isso está declarada no comentário da estrutura, e não escondida no laço que a consome. Uma interface que aceitasse as regras num conjunto sem ordem tornaria o desempate indefinido, e o comportamento do sistema dependeria da ordem de iteração de uma estrutura de dados — que é o tipo de dependência que funciona por anos e quebra numa troca de biblioteca padrão.
A segunda é que a categoria de descarte é uma categoria de regra, e não um laço à parte. Espaço e comentário entram na especificação como qualquer outro padrão, competem pela posição como qualquer outro, e o que os distingue é apenas o que se faz com o casamento. A alternativa — consumir espaços num laço antes de tentar reconhecer — parece mais simples e é a origem do defeito mais comum da fase, tratado na tarefa seguinte.
Há um preço concreto que a especificação cobra do recorte fixado no primeiro capítulo, e ele é medível. A notação decidida lá não tem classe negada: não há como escrever “qualquer símbolo exceto aspas”. Ora, é exatamente disso que um literal de texto precisa, e um comentário, e o corpo de um pattern. A saída resolve isso enumerando o complemento — e quem enumera é uma função, não a mão, porque uma enumeração digitada esquece um símbolo e o esquecimento só aparece no dia em que aquele símbolo é usado.
O custo aparece na coluna de nós da árvore, e é grande: a regra de comentário tem quatrocentos e cinquenta e dois nós contra três da regra de palavra reservada. E some inteiramente na coluna seguinte: depois de determinizada e minimizada, a regra de comentário tem quatro estados. É a demonstração mais econômica que o módulo oferece de que o custo de um recorte pobre é de construção, e não de execução — o reconhecimento roda sobre a máquina mínima, e a máquina mínima não guarda memória do caminho que a produziu.
Onde é fácil errar. Achar que reaproveitar o componente significa chamá-lo uma vez e guardar o resultado. Não: são vinte e oito instâncias independentes, uma por regra, e é essa multiplicidade que cria o problema de desempate que a tarefa seguinte resolve. Quem tenta compilar a especificação inteira numa máquina só perde a informação de qual padrão casou, que é justamente o que a fase precisa entregar. Como verificar que está correta: conte as linhas de código do módulo que decidem se um caractere pertence a um símbolo. Se houver alguma, o reaproveitamento não aconteceu — apenas foi anunciado.
1.3 Tarefa 2: Quebrar a descrição em símbolos com posição
O que a tarefa pede
Fazer o sistema percorrer a descrição de exemplo e produzir a sequência de símbolos que a representa, com cada símbolo carregando a sua posição no texto de origem. Espaços e comentários são descartados, mas descartá-los não pode custar a posição dos símbolos que vêm depois — é o erro mais comum desta etapa, e ele só se manifesta bem adiante, quando uma mensagem de erro aponta para o lugar errado e a suspeita recai sobre a peça errada. A tarefa se cumpre quando a descrição escrita à mão no primeiro capítulo é reconhecida por inteiro, sem sobra e sem símbolo desconhecido.
A condição de saída da tarefa é verificável, e por isso ela virou teste, e não afirmação. A demonstração lê a descrição escrita à mão no primeiro capítulo, tokeniza-a e devolve código de saída não-zero se restar qualquer recusa. Quarenta e seis símbolos entregues, cinquenta e três trechos descartados, nenhuma recusa — e o dia em que uma peça anterior mudar de comportamento e a descrição de referência deixar de ser reconhecida, a reconstrução acusa.
O ponto delicado da tarefa é o que ela nomeia: descartar sem perder posição. A solução o trata por construção, e a construção é pequena a ponto de caber numa frase — existe uma única função no arquivo que altera linha e coluna, e ela é chamada com o trecho consumido, seja ele símbolo entregue ou trecho descartado. Não há dois caminhos de avanço a manter em acordo, porque quando existem dois, eles divergem no primeiro caso de borda e a divergência é silenciosa.
O caso de borda que a solução encontrou não estava previsto, e é do tipo que aparece uma vez e ensina para sempre. A descrição escrita no primeiro capítulo tem comentários em português, e um deles usa travessão. Em UTF-8, o travessão ocupa 3 bytes. Contar bytes como colunas deslocaria em duas posições todas as mensagens de erro daquela linha — e o defeito só apareceria em arquivo com acento, que é a pior forma de um defeito aparecer, porque a máquina de quem escreveu o sistema costuma não ter nenhum.
A saída trata isso reconhecendo, no avanço de posição, os bytes de continuação da codificação e não os contando como coluna. São duas linhas, e elas resolvem a coluna. Resolvem também uma segunda coisa, menos óbvia: o alfabeto declarado da linguagem inclui os bytes altos, de modo que comentário e literal de texto são transparentes à codificação. O reconhecedor trabalha byte a byte e não precisa saber o que um travessão significa — só que não é delimitador de comentário. Essa é a decisão que um analisador léxico real toma, e tomá-la aqui evitou a alternativa constrangedora, que seria voltar ao arquivo escrito dois capítulos antes e apagar os travessões dele para que o reconhecedor coubesse.
Uma observação sobre o que a posição custa e quando ela se paga. Ela não serve a nada neste módulo: o programa imprime uma tabela, e a tabela ficaria igualmente legível sem linha e coluna. O valor dela é inteiramente futuro — cada família de recusa dos módulos seguintes, sintática, semântica e de geração, vai apontar para um lugar do texto, e nenhuma delas tem como recuperar esse lugar se o símbolo não o trouxer. Deixar a posição “para depois” é a decisão que nunca se desfaz, porque desfazê-la depois significa tocar em toda a cadeia.
Onde é fácil errar. Consumir espaços e comentários num laço próprio antes de tentar o reconhecimento. Funciona, é mais curto, e é onde a posição se perde: o laço avança o índice do texto e esquece de avançar linha e coluna, e a partir do primeiro comentário todas as posições ficam adiantadas. Como verificar que está correta: tokenize um arquivo cuja primeira declaração venha depois de dez linhas de comentário e confira que ela é reportada na linha onze. Na saída da demonstração, a primeira declaração da descrição de referência aparece na linha dezesseis, que é onde ela de fato está.
1.4 Tarefa 3: Responder ao caractere inválido
O que a tarefa pede
Fazer um caractere que não pertence à linguagem produzir uma mensagem que diga onde ele está. É a primeira vez que o sistema responde a quem escreveu a descrição, e não a quem escreveu o sistema; daqui em diante, cada capítulo acrescenta uma família nova de recusas, e todas herdam a forma decidida agora.
A tarefa é curta e a decisão que ela contém é longa, porque “a forma decidida agora” será herdada por tudo o que vem depois. A solução decide três coisas, e cada uma tem uma alternativa plausível que foi descartada.
A primeira é que a recusa distingue duas famílias. Um caractere pode não iniciar símbolo algum embora pertença ao alfabeto da linguagem — é o caso do cerquilha, que é um símbolo perfeitamente escrevível e não abre nenhum padrão —, ou pode não pertencer ao alfabeto, como uma letra acentuada fora de comentário. As duas mensagens são diferentes porque as duas correções são diferentes: a primeira pede que se remova ou substitua o símbolo, e a segunda avisa que a linguagem não aceita aquele caractere em posição alguma de código. Emitir a mesma frase para os dois casos custa uma rodada de tentativa e erro a quem escreve.
A segunda é que a recusa não interrompe a leitura. O reconhecedor consome o caractere ofensor inteiro — inclusive os bytes de continuação, para que a mensagem mostre o caractere e não um byte solto — e continua. A demonstração exibe as duas recusas do arquivo defeituoso numa única execução, e é isso que se quer: parar no primeiro erro obriga quem escreve a corrigir um caractere por vez, e cada correção custa uma execução inteira. A recuperação por consumo de um caractere é a mais simples que existe e é a certa aqui, porque nesta fase não há estrutura a recuperar — o que vem depois do caractere ruim é texto normal.
A terceira é a forma da mensagem: a posição, a frase, a linha de origem reproduzida e um cursor sob a coluna. Reproduzir a linha parece redundante quando se tem a posição, e não é: quem lê a mensagem no terminal não tem o editor aberto no ponto certo, e a linha reproduzida elimina a ida e volta. O cursor sob a coluna é o que torna a posição legível sem contar caracteres — e é também o que exige que a coluna esteja correta, o que fecha o ciclo com a decisão da tarefa anterior.
O arquivo de descrição defeituosa que a demonstração usa foi escrito para ser recusado, e o comentário no topo dele diz isso, pela mesma razão registrada no capítulo anterior a respeito do caso que falha de propósito: um arquivo cuja função é falhar é o tipo de coisa que se apaga por engano numa limpeza de repositório. Ele traz também, no próprio comentário, um travessão que não é recusado — o que documenta, no lugar em que a dúvida aparece, que a transparência à codificação dentro de comentário é decisão e não descuido.
Onde é fácil errar. Escrever a mensagem na voz de quem programou o sistema. “Estado de erro alcançado na posição 214” é verdadeiro, é útil para depurar o reconhecedor e é inútil para quem escreveu a descrição, que não sabe o que é um estado. A recusa é dirigida a quem escreve na linguagem, e o vocabulário dela é o da linguagem. Como verificar que está correta: entregue a mensagem a alguém que nunca viu o código do sistema e peça que conserte o arquivo. Se a pessoa conseguir, a mensagem serve.
1.5 Token, lexema e padrão, e o que a fase entrega à seguinte
Os três termos são confundidos com frequência e a solução os separa em código, porque separá-los em prosa e juntá-los na estrutura de dados não sustenta a distinção.
O padrão é a expressão que descreve uma classe de trechos, e vive na especificação. O lexema é o trecho concreto que apareceu no texto, e é uma cadeia de caracteres. O token é o que atravessa a fronteira entre as duas fases: a categoria, mais o lexema, mais a posição, mais — quando é nome — o índice na tabela de símbolos.
A pergunta que importa é o que a fase entrega à seguinte, e a resposta se lê na estrutura do token. Ela entrega categoria, porque é sobre categorias que a gramática do próximo capítulo é escrita, e não sobre caracteres. Entrega o lexema, porque a categoria sozinha perde a informação de qual identificador é este. E entrega a posição, porque a fase seguinte não tem como recuperá-la.
O que ela deliberadamente não entrega é tão informativo quanto: não entrega espaços, não entrega comentários, e não entrega estrutura. A ausência de estrutura é o que define a fronteira — o reconhecedor de símbolos não sabe que um parêntese que abre pede um que feche, e é precisamente essa ignorância, demonstrada no capítulo anterior como limite de classe, que obriga a existir uma fase seguinte com pilha.
Confundir lexema com token tem uma consequência concreta e observável: o analisador sintático passa a reexaminar caracteres para descobrir o que recebeu, e a fronteira entre as fases deixa de existir de fato, embora continue existindo no diagrama. O sinal de que isso aconteceu é o analisador sintático precisando de uma função que compare cadeias de caracteres para decidir um desvio.
1.6 O casamento mais longo, e por que o desempate é a ordem
Vinte e oito padrões disputando a mesma posição do texto criam dois problemas diferentes, e a solução usa duas regras diferentes, uma para cada.
O primeiro é a disputa entre casamentos de comprimentos diferentes, e a regra é o casamento mais longo. Sobre o texto que começa com a palavra onda, o padrão de palavra reservada on casa dois caracteres e o de identificador casa quatro; vence o de quatro. A regra parece óbvia enunciada assim, e a implementação ingênua a viola sem perceber: quem para no primeiro padrão que casa produz um reconhecedor que quebra onda em duas partes, e o defeito não aparece em programa nenhum até que alguém use um nome que começa por palavra reservada.
O segundo é a disputa entre casamentos de mesmo comprimento, e a regra é a ordem de declaração. Sobre o texto que começa com a palavra on isolada, os dois padrões casam dois caracteres, e é a posição na lista que decide. A implementação inteira dessa regra é o operador de comparação do laço: a comparação é estritamente maior, e não maior ou igual. Um caractere de diferença no código, e a consequência é toda a linguagem: com maior ou igual, o último padrão declarado venceria os empates, toda palavra reservada viraria nome de variável, e a linguagem deixaria de ter palavras reservadas — sem que nenhum teste dos capítulos anteriores acusasse coisa alguma.
Vale registrar um conflito que a especificação resolve por construção, e não por regra de desempate, porque a diferença entre as duas soluções é instrutiva. O comentário começa por duas barras e o corpo de um pattern começa por uma; os dois disputam a mesma posição. A saída não precisou arbitrar isso, porque o corpo de um pattern exige ao menos um símbolo que não seja barra antes do fechamento — de modo que, diante de duas barras seguidas, o padrão de pattern simplesmente não casa. Ambiguidade resolvida na especificação custa menos e falha menos do que ambiguidade resolvida na regra de desempate, e procurar essa resolução antes de recorrer à ordem é um bom hábito de projeto de linguagem.
Uma restrição declarada, para não passar por descuido: como o corpo de um pattern exclui a barra, não há como escrever uma barra dentro de um pattern, nem escapada. É limitação real, conhecida, e a solução escolheu declará-la em vez de resolvê-la com um segundo modo de leitura — que é como um gerador de analisadores a resolveria, e que introduziria no sistema exatamente o tipo de estado fora do autômato que este capítulo existe para evitar.
1.7 A tabela de símbolos, e o pouco que ela pode saber agora
A tabela de símbolos aparece aqui na forma mínima que a fase comporta, e a palavra mínima é a que importa: ela registra o nome, a primeira ocorrência e a contagem de ocorrências. Não registra tipo, não registra escopo, não registra se o nome foi declarado antes de usado. Nada disso é acessível a quem só reconhece símbolos — e escrever esses campos agora, deixando-os vazios para preencher adiante, seria construir a estrutura antes de ter o que pôr nela.
O que a forma mínima já sustenta é a única coisa que a fase sabe de fato: que este nome é o mesmo nome de antes. Na saída da demonstração isso vira quatro entradas para uma descrição em que nomes aparecem nove vezes, e cada token de identificador carrega o índice da sua entrada. É pouco, e é exatamente o que se pede: a fase seguinte recebe, junto com o símbolo, a informação de que ele e um símbolo anterior se referem à mesma coisa, sem precisar comparar cadeias de caracteres para descobrir.
A escolha de estrutura merece uma nota, porque ela contradiz o que se esperaria. A busca é linear sobre um vetor, e não uma tabela de espalhamento. É a escolha certa aqui por duas razões, e nenhuma delas é preguiça: a quantidade de nomes distintos numa descrição da linguagem é pequena, e a busca linear preserva a ordem de inserção, que é a ordem em que os nomes aparecem no texto e a única que torna a saída da demonstração reproduzível e comparável entre execuções. Quando a estrutura ganhar escopos aninhados, a decisão volta à mesa — e voltará documentada, com a medida que a justificou.
1.8 O que este módulo entrega ao resto do percurso
Vale fechar dizendo o que muda no sistema depois deste capítulo, porque a resposta não é “ele reconhece símbolos”.
O que muda é que a fronteira entre duas fases passa a existir materialmente, e não só no diagrama do primeiro capítulo. Há uma estrutura de dados que uma fase produz e outra consome, e a partir daqui as duas podem ser mudadas independentemente enquanto essa estrutura não mudar. É a primeira vez no percurso em que a palavra interface tem consequência prática, e é por isso que a primeira tarefa insiste tanto nela.
Muda também o endereçamento das mensagens. Até aqui, tudo o que o sistema dizia era dirigido a quem o estava construindo; a partir daqui existe uma segunda audiência, que é quem escreve na linguagem, e ela não conhece nem quer conhecer as máquinas por dentro. Cada capítulo seguinte acrescenta uma família de recusas a essa segunda audiência, e todas herdam a forma decidida aqui — a posição, a linha reproduzida, o cursor, o vocabulário da linguagem e não o do sistema.
E muda, por fim, o estatuto da maquinaria dos cinco capítulos anteriores. Ela deixou de ser assunto e virou ferramenta: ninguém mais vai olhar para uma construção de Thompson pelo que ela é, e sim pelo que ela entrega. O sinal de que essa passagem se completou está na saída da demonstração — a especificação inteira da linguagem cabe em vinte e oito linhas de patterns, e o que as compila é código que já estava escrito. Quem chega aqui com o próprio projeto e precisa escrever reconhecimento novo não chegou ainda; chegou a um sistema com duas peças que fazem a mesma coisa, e o trabalho que falta é apagar uma delas.