1 Módulo 07: Projeto do Professor — A Primeira Fase do Compilador
Este é o projeto de referência resolvido pelo professor: a mesma atividade que cada grupo vai executar neste módulo, feita por inteiro, com as decisões justificadas uma a uma. É a entrega consolidada do primeiro bloco — o modelo do que o seu grupo entrega no marco, não algo a copiar.
1.1 Visão Geral do Módulo 07
Cinco módulos construíram um motor: expressão regular entra, autômato mínimo sai. Este módulo o embrulha numa peça com nome próprio e o conecta ao resto do compilador. Nenhum algoritmo novo é escrito aqui. O que se acrescenta é tudo aquilo que a teoria não menciona e que responde pela maior parte do esforço de um analisador léxico real: a interface com a fase seguinte, o desempate entre padrões que casam a mesma entrada, o descarte de espaço e comentário, e o erro léxico que diz onde está o problema.
É também o primeiro marco de consolidação, o que muda a natureza da entrega. Além do incremento, revisa-se tudo que foi produzido desde o módulo 1 — e essa revisão não é formalidade. Ao ligar o analisador aos autômatos das seis categorias, descobri um defeito que atravessou cinco módulos sem ser notado, e que só apareceu porque este é o primeiro momento em que todos eles são usados de verdade. Trato dele na primeira tarefa, antes de qualquer outra coisa.
1.2 Tarefa 1: A revisão do acumulado, e o que ela encontrou
A atividade — revisar o que foi produzido do módulo 1 ao 7 e apresentar o conjunto como unidade coerente.
Comecei pelo que parecia burocrático: rodar os autômatos das seis categorias contra os corpora escritos no módulo 2. No módulo 3 só duas categorias tinham autômato, porque construí-las à mão teria sido trabalho jogado fora. Agora as seis existem, geradas a partir da notação.
Quatro passaram de primeira. PONTUACAO falhou, e a causa era antiga.
A notação daquela categoria, escrita no módulo 2, estava assim:
= | ; | ( | ) | { | } | , | => | > | < | >= | <= | == | !=Isso é prosa legível, não a mini-notação. Os espaços entre as alternativas são símbolos literais, e os parênteses são operadores de agrupamento, não os caracteres de pontuação que eu queria descrever. A expressão foi analisada sem erro, produziu um autômato bem formado de cento e doze estados, atravessou a determinização e a minimização, e apareceu em duas tabelas publicadas — reconhecendo a linguagem errada o tempo inteiro.
A versão correta escapa os parênteses e dispensa os espaços:
\(|\)|\{|\}|;|,|=>|==|!=|>=|<=|=|>|<Por que o defeito sobreviveu a cinco módulos. Ele nunca foi executado. O módulo 3 verificou duas categorias; os módulos 4 e 5 usaram PONTUACAO apenas para contar estados, e contagem de estados de um autômato errado é um número perfeitamente plausível. Só quando o analisador léxico passou a reconhecer texto de verdade é que a diferença apareceu.
Isso tem uma consequência que vale registrar: medir não é verificar. As tabelas dos módulos 4 e 5 mediram um artefato que não fazia o que dizia fazer, e nenhuma das duas tinha como perceber. A verificação que pega esse tipo de erro é a que confronta comportamento contra expectativa escrita antes — que é exatamente o papel dos corpora, e é por isso que eles foram escritos no módulo 2, antes de existir implementação.
A correção mudou números já publicados. PONTUACAO caiu de 112 para 64 estados após Thompson, de 29 para 16 após determinização, e de 7 para 5 após minimização. Os totais das seis categorias passaram de 1344 para 1296 após Thompson, de 345 para 332 após determinização, e de 22 para 20 no mínimo. Atualizei as tabelas dos módulos 4 e 5, porque número publicado errado é pior que número ausente.
Com a correção, as seis categorias passam:
categoria estados aceitas rejeitadas veredicto
IDENTIFICADOR 2 6/6 5/5 confere
NUMERO 5 6/6 7/7 confere
TEXTO 3 3/3 3/3 confere
PADRAO 3 3/3 3/3 confere
PONTUACAO 5 6/6 4/4 confere
ESPACO 2 3/3 2/2 confereTrinta e três casos de aceitação e vinte e quatro de rejeição, todos corretos. O corpus escrito no módulo 2, quando nada existia, fecha a conta aqui.
Onde é fácil errar aqui. Tratar a revisão do marco como conferência de documentação. A parte que encontra defeito é a que executa o que nunca foi executado — e num projeto cumulativo sempre há algo nessa condição, porque cada módulo usa apenas o que precisa.
1.3 Tarefa 2: O analisador léxico
A atividade — construir o analisador léxico completo da linguagem, reutilizando o motor de autômatos já pronto.
Primeiro o que o analisador produz. Os quatro conceitos que o módulo distingue — padrão, lexema, símbolo e atributo — se confundem com facilidade, e resolvi separá-los na própria estrutura de dados.
07_token.h
#ifndef PENEIRA_07_TOKEN_H
#define PENEIRA_07_TOKEN_H
#include <cstdint>
#include <string>
#include "01_source.h"
namespace peneira {
// As quatro noções que o módulo distingue e que se confundem com facilidade:
//
// padrão — a descrição de uma classe de cadeias (a expressão regular)
// lexema — o trecho concreto do texto que casou com o padrão
// símbolo — a categoria produzida, que é o que a fase seguinte consome
// atributo— a informação adicional que o símbolo carrega além da categoria
//
// O padrão vive na especificação léxica; os outros três vivem aqui.
enum class Categoria : std::uint8_t {
Identificador,
PalavraReservada,
Numero,
Texto,
Padrao,
Pontuacao,
FimDeArquivo,
Invalido,
};
const char* nomeDaCategoria(Categoria c) noexcept;
// Um símbolo léxico. Guarda a posição de propósito: sem ela, o analisador
// sintático do módulo 10 não teria como reportar erro em lugar nenhum, e a
// infraestrutura de diagnóstico do módulo 1 ficaria sem uso.
struct SimboloLexico {
Categoria categoria = Categoria::Invalido;
std::string lexema;
Position posicao{0, 0, 0};
// Atributo. Só um dos dois é significativo, conforme a categoria:
// `valor` para número, `conteudo` para texto e padrão (o miolo, já sem os
// delimitadores). Manter os dois num par de campos em vez de uma união
// discriminada é escolha de simplicidade: são poucos bytes e o código que
// lê fica direto.
double valor = 0.0;
std::string conteudo;
std::string emTexto() const;
};
} // namespace peneira
#endif // PENEIRA_07_TOKEN_HO padrão vive na especificação léxica e não aparece aqui; ele é a descrição da classe. O lexema é o trecho concreto do texto. O símbolo é a categoria que a fase seguinte consome. E o atributo é a informação adicional — o valor numérico de um número, o conteúdo de um texto já sem as aspas. Guardar o conteúdo sem os delimitadores é decisão pequena e que se paga: quem consome não deveria precisar lembrar de tirá-las.
A posição está em todo símbolo, e é o que finalmente dá uso real à infraestrutura de diagnóstico escrita no módulo 1. Até aqui ela só tinha sido exercitada com “arquivo vazio”.
07_lexer.h
#ifndef PENEIRA_07_LEXER_H
#define PENEIRA_07_LEXER_H
#include <cstddef>
#include <string>
#include <vector>
#include "01_diagnostico.h"
#include "01_source.h"
#include "03_afd.h"
#include "07_token.h"
namespace peneira {
// Analisador léxico da Peneira.
//
// Não há motor novo aqui: os autômatos vêm da especificação do módulo 2,
// passada pelo analisador de notação do módulo 4 e pelo pipeline do módulo 5.
// O que este módulo acrescenta é tudo o que a teoria não menciona — a
// interface sob demanda, o desempate entre padrões, o descarte de espaço e
// comentário, e o erro léxico que informa onde está o problema.
//
// A interface é SOB DEMANDA: o analisador sintático pede o próximo símbolo e
// recebe um. Não produzimos a lista inteira de antemão, porque a fase seguinte
// consome um de cada vez e porque, num arquivo grande, materializar tudo
// custaria memória sem ganho. O método que devolve a lista existe só para as
// demonstrações e para os testes.
class AnalisadorLexico {
public:
AnalisadorLexico(const SourceFile& fonte, DiagnosticBag& diagnosticos);
SimboloLexico proximo();
bool terminou() const noexcept;
std::vector<SimboloLexico> todos();
// Instrumentação do retrocesso. `examinados` conta cada caractere que
// algum autômato leu durante a busca pelo casamento mais longo;
// `consumidos` conta os que viraram lexema. A diferença é o custo do
// retrocesso, e ela é medível em vez de teórica.
std::size_t caracteresExaminados() const noexcept;
std::size_t caracteresConsumidos() const noexcept;
private:
struct Regra {
Categoria categoria;
std::string nome;
Afd automato;
};
void pularIgnoraveis();
bool ehPalavraReservada(const std::string& lexema) const;
SimboloLexico montar(Categoria categoria, const std::string& lexema,
Position posicao) const;
void reportarInvalido();
const SourceFile& fonte_;
DiagnosticBag& diagnosticos_;
std::vector<Regra> regras_;
std::size_t posicao_ = 0;
std::size_t examinados_ = 0;
std::size_t consumidos_ = 0;
bool entregouFim_ = false;
};
// Monta as regras a partir da especificação léxica, na ordem de prioridade.
// Exposta para que as demonstrações possam inspecionar os autômatos.
std::vector<std::string> categoriasEmPrioridade();
} // namespace peneira
#endif // PENEIRA_07_LEXER_H07_lexer.cpp
#include "07_lexer.h"
#include <algorithm>
#include <cstdlib>
#include <map>
#include <utility>
#include "02_lexico.h"
#include "04_notacao.h"
#include "04_thompson.h"
#include "05_determinizacao.h"
#include "05_minimizacao.h"
namespace peneira {
namespace {
// Ordem de prioridade das categorias. É ela que desempata quando dois padrões
// casam a MESMA quantidade de caracteres — situação diferente do casamento
// mais longo, que desempata por comprimento.
//
// ESPACO fica de fora: espaço em branco é descartado pelo laço de varredura e
// nunca vira símbolo. Precisa existir na especificação mesmo assim, porque é
// ele que delimita onde um identificador termina.
const std::vector<std::pair<std::string, Categoria>>& ordemDasRegras() {
static const std::vector<std::pair<std::string, Categoria>> ordem{
{"NUMERO", Categoria::Numero},
{"IDENTIFICADOR", Categoria::Identificador},
{"TEXTO", Categoria::Texto},
{"PADRAO", Categoria::Padrao},
{"PONTUACAO", Categoria::Pontuacao},
};
return ordem;
}
// Comentário de linha: inicia em '#' e vai até o fim da linha.
//
// A escolha por comentário de LINHA, e não de bloco, tem uma razão que vem
// direto do módulo 6. Comentário de bloco aninhavel — em que um comentário
// pode conter outro — exige contar profundidade, e contar profundidade é
// exatamente o que um autômato finito nao faz. Um analisador léxico que os
// suporte precisa de um contador escrito à mão, fora do modelo. Comentário de
// linha é regular, cabe no modelo, e resolve o problema do usuário.
constexpr char kInicioDeComentario = '#';
bool ehEspacoEmBranco(char c) {
return c == ' ' || c == '\t' || c == '\r' || c == '\n';
}
} // namespace
std::vector<std::string> categoriasEmPrioridade() {
std::vector<std::string> nomes;
for (const auto& par : ordemDasRegras()) {
nomes.push_back(par.first);
}
return nomes;
}
AnalisadorLexico::AnalisadorLexico(const SourceFile& fonte,
DiagnosticBag& diagnosticos)
: fonte_(fonte), diagnosticos_(diagnosticos) {
// Constrói um autômato mínimo por categoria, uma vez só, no início.
// Poderíamos combinar tudo num autômato único, com os estados finais
// marcados por categoria — é o que um gerador de analisadores faz, e é
// mais rápido. Mantive separados porque assim o desempate por prioridade
// fica explícito no laço, em vez de escondido na marcação dos estados.
std::map<std::string, std::string> notacaoPorNome;
for (const CategoriaLexica& c : especificacaoLexica()) {
notacaoPorNome[c.nome] = c.notacao;
}
for (const auto& par : ordemDasRegras()) {
const auto it = notacaoPorNome.find(par.first);
if (it == notacaoPorNome.end()) {
continue;
}
const ResultadoNotacao r = analisarNotacao(it->second);
if (!r.ok) {
continue;
}
const Afn afn = thompson(*r.expressao, par.first);
Afd minimo = minimizar(determinizar(afn, par.first), par.first);
regras_.push_back(Regra{par.second, par.first, std::move(minimo)});
}
}
bool AnalisadorLexico::terminou() const noexcept {
return entregouFim_;
}
std::size_t AnalisadorLexico::caracteresExaminados() const noexcept {
return examinados_;
}
std::size_t AnalisadorLexico::caracteresConsumidos() const noexcept {
return consumidos_;
}
void AnalisadorLexico::pularIgnoraveis() {
const std::string& texto = fonte_.text();
for (;;) {
while (posicao_ < texto.size() && ehEspacoEmBranco(texto[posicao_])) {
++posicao_;
}
if (posicao_ < texto.size() && texto[posicao_] == kInicioDeComentario) {
while (posicao_ < texto.size() && texto[posicao_] != '\n') {
++posicao_;
}
continue; // pode haver mais espaço ou outro comentário adiante
}
return;
}
}
bool AnalisadorLexico::ehPalavraReservada(const std::string& lexema) const {
const std::vector<std::string>& lista = palavrasReservadas();
return std::find(lista.begin(), lista.end(), lexema) != lista.end();
}
SimboloLexico AnalisadorLexico::montar(Categoria categoria,
const std::string& lexema,
Position posicao) const {
SimboloLexico s;
s.categoria = categoria;
s.lexema = lexema;
s.posicao = posicao;
if (categoria == Categoria::Numero) {
s.valor = std::strtod(lexema.c_str(), nullptr);
} else if (categoria == Categoria::Texto || categoria == Categoria::Padrao) {
// O atributo do texto e do padrão é o miolo, sem os delimitadores.
// Quem consome não deveria precisar lembrar de tirar as aspas.
s.conteudo = lexema.size() >= 2 ? lexema.substr(1, lexema.size() - 2)
: std::string();
}
return s;
}
void AnalisadorLexico::reportarInvalido() {
const std::string& texto = fonte_.text();
const std::size_t inicio = posicao_;
// Consome a corrida inteira de caracteres que não podem iniciar símbolo
// algum e reporta UMA vez. Reportar por caractere transformaria uma
// sequência estranha de dez bytes em dez erros, e o critério de qualidade
// deste módulo é o oposto disso: um erro real vale mais que dez derivados.
while (posicao_ < texto.size()) {
if (ehEspacoEmBranco(texto[posicao_]) ||
texto[posicao_] == kInicioDeComentario) {
break;
}
bool algumInicia = false;
for (const Regra& regra : regras_) {
if (regra.automato.transicao(regra.automato.inicial(),
static_cast<Simbolo>(texto[posicao_])) !=
kSemEstado) {
algumInicia = true;
break;
}
}
if (algumInicia && posicao_ > inicio) {
break;
}
++posicao_;
if (algumInicia) {
break;
}
}
const std::size_t tamanho = posicao_ - inicio;
const std::string trecho = texto.substr(inicio, tamanho);
diagnosticos_.error(fonte_.positionAt(inicio),
"caractere inesperado: \"" + trecho + "\"");
}
SimboloLexico AnalisadorLexico::proximo() {
const std::string& texto = fonte_.text();
for (;;) {
pularIgnoraveis();
if (posicao_ >= texto.size()) {
entregouFim_ = true;
SimboloLexico fim;
fim.categoria = Categoria::FimDeArquivo;
fim.posicao = fonte_.positionAt(texto.size());
return fim;
}
const std::size_t inicio = posicao_;
// Casamento mais longo: cada autômato avança enquanto puder, e
// registra a última posição em que passou por estado final. Vence o
// que chegar mais longe; empate resolve pela ordem de prioridade, que
// é a ordem em que as regras estão no vetor.
std::size_t melhorFim = inicio;
Categoria melhorCategoria = Categoria::Invalido;
for (const Regra& regra : regras_) {
Estado atual = regra.automato.inicial();
std::size_t ultimoAceite = inicio;
bool aceitou = false;
for (std::size_t i = inicio; i < texto.size(); ++i) {
atual = regra.automato.transicao(atual,
static_cast<Simbolo>(texto[i]));
++examinados_;
if (atual == kSemEstado) {
break;
}
if (regra.automato.ehFinal(atual)) {
ultimoAceite = i + 1;
aceitou = true;
}
}
if (aceitou && ultimoAceite > melhorFim) {
melhorFim = ultimoAceite;
melhorCategoria = regra.categoria;
}
}
if (melhorCategoria == Categoria::Invalido) {
reportarInvalido();
continue; // recupera e segue: erro léxico não aborta a análise
}
const std::string lexema = texto.substr(inicio, melhorFim - inicio);
const Position posicao = fonte_.positionAt(inicio);
posicao_ = melhorFim;
consumidos_ += lexema.size();
// Prioridade entre padrões que casam a MESMA cadeia: toda palavra
// reservada é um identificador válido segundo a expressão. A escolha
// aqui é a segunda das duas estratégias usuais — reconhecer como
// identificador e reclassificar por consulta a uma lista, em vez de
// dar a cada palavra reservada seu próprio padrão. Custa uma busca por
// símbolo e evita oito autômatos a mais.
Categoria categoria = melhorCategoria;
if (categoria == Categoria::Identificador && ehPalavraReservada(lexema)) {
categoria = Categoria::PalavraReservada;
}
return montar(categoria, lexema, posicao);
}
}
std::vector<SimboloLexico> AnalisadorLexico::todos() {
std::vector<SimboloLexico> lista;
for (;;) {
SimboloLexico s = proximo();
const bool fim = s.categoria == Categoria::FimDeArquivo;
lista.push_back(std::move(s));
if (fim) {
return lista;
}
}
}
} // namespace peneiraQuatro decisões de projeto sustentam a implementação.
A interface é sob demanda. O analisador sintático pede o próximo símbolo e recebe um. Não produzo a lista inteira de antemão porque a fase seguinte consome um de cada vez, e porque materializar tudo custaria memória sem ganho num arquivo grande. O método que devolve a lista existe, e existe apenas para as demonstrações e os testes — deixei isso escrito no cabeçalho para que ninguém o adote como caminho principal.
Cinco autômatos separados, não um combinado. Poderia fundir as cinco regras num autômato único com os estados finais marcados por categoria. É o que um gerador de analisadores faz, e é mais rápido. Mantive separados porque assim o desempate por prioridade fica explícito no laço, em vez de escondido na marcação dos estados. A troca é deliberada, tem custo medido — que a última tarefa quantifica — e está comentada no código.
Comentário é de linha, e a escolha vem do módulo 6. Comentário de bloco aninhável, em que um comentário pode conter outro, exige contar profundidade — e contar profundidade é exatamente o que um autômato finito não faz, pelo resultado demonstrado no módulo anterior. Um analisador que os suporte precisa de um contador escrito à mão, fora do modelo. Comentário de linha é regular, cabe no motor, e resolve o problema do usuário. É a primeira vez no projeto em que um resultado de impossibilidade decide uma característica da linguagem.
Espaço e comentário são descartados pelo laço de varredura, não emitidos como símbolos. A categoria ESPACO existe na especificação e nunca vira símbolo. Precisa existir mesmo assim, porque é ela que delimita onde um identificador termina — sem espaço declarado, on email seria um identificador só.
Rodando sobre o programa de exemplo, com o comentário na primeira linha:
2:1 PALAVRA_RESERVADA "pattern"
2:9 IDENTIFICADOR "email"
2:16 PONTUACAO "="
2:18 PADRAO "/[a-z0-9._]+@[a-z]+\.[a-z]+/" conteudo="[a-z0-9._]+@[a-z]+\.[a-z]+"
2:46 PONTUACAO ";"
...
6:48 TEXTO ""contato"" conteudo="contato"Quarenta e sete símbolos para duzentos e cinquenta e sete caracteres em nove linhas, zero erros. Repare que a numeração de linha começa em 2: a linha 1 é o comentário, e ela não produziu símbolo algum. E repare no atributo do padrão, que traz o miolo sem as barras — é ele que o módulo 4 vai receber para construir o autômato do usuário.
Onde é fácil errar aqui. Aplicar o desempate por palavra reservada antes do casamento mais longo. Se você consultar a lista assim que os primeiros caracteres formarem on, a entrada onibus vira a palavra reservada on seguida de ibus. A ordem correta é deixar o casamento mais longo decidir onde o identificador termina e só então comparar a cadeia inteira contra a lista.
1.4 Tarefa 3: As duas regras de desempate
O tópico — casamento mais longo e prioridade entre padrões, que resolvem conflitos de naturezas diferentes.
As duas regras são frequentemente confundidas, e vale separá-las com precisão. O casamento mais longo resolve o conflito entre padrões que casam quantidades diferentes de caracteres: vence o que chegar mais longe. A prioridade resolve o conflito entre padrões que casam a mesma cadeia: vence o de maior precedência na especificação.
O caso que justifica a primeira regra:
">=" -> PONTUACAO ">="
"=>" -> PONTUACAO "=>"
"-5" -> NUMERO "-5"Sem ela, >= sairia como > seguido de =, e a condição where value(n) >= 100 seria analisada como uma comparação estrita seguida de um sinal de igual solto. O analisador sintático reclamaria de algo estranho três símbolos adiante, com uma mensagem que não apontaria a causa. O -5 é o mesmo fenômeno com outra cara: sem casamento mais longo, viraria pontuação seguida de número.
O caso que justifica a segunda:
"pattern" -> PALAVRA_RESERVADA
"where" -> PALAVRA_RESERVADA
"patterns" -> IDENTIFICADOR
"emitir" -> IDENTIFICADORToda palavra reservada é um identificador válido segundo a expressão [a-z][a-z0-9_]* — o fato foi registrado na observação da categoria lá no módulo 2, e é aqui que ele cobra tratamento.
Das duas estratégias usuais, escolhi a segunda: reconhecer como identificador e reclassificar por consulta a uma lista, em vez de dar a cada palavra reservada seu próprio padrão. A alternativa exigiria oito autômatos a mais e, pior, faria a prioridade entre eles e o identificador depender da ordem das regras — acoplamento frágil. A consulta custa uma busca por símbolo reconhecido e mantém a lista de reservadas num lugar só.
As duas últimas linhas da saída são o teste que importa: patterns e emitir não são reclassificadas, apesar de conterem uma palavra reservada. A comparação é da cadeia inteira, depois que o casamento mais longo já decidiu onde o identificador termina.
Onde é fácil errar aqui. Implementar a prioridade comparando prefixos em vez da cadeia inteira. É um erro que passa em todos os testes com palavras reservadas isoladas e falha na primeira variável que o usuário chamar de ruleta.
1.5 Tarefa 4: Erro léxico e recuperação
O tópico — detectar erro léxico, reportar de forma útil e continuar a análise.
A partir deste módulo, a qualidade do relato de erro é critério explícito de avaliação. Convém ser preciso sobre o que isso significa, porque “boa mensagem” é vago.
Uma entrada com dois trechos inválidos produz:
com_erros.pen:2:9: erro: caractere inesperado: "$$$"
pattern $$$ = /x/;
^
com_erros.pen:4:9: erro: caractere inesperado: "~~~~~"
pattern ~~~~~ = /y/;
^
2 erro(s) para 30 simbolos reconhecidos.Três propriedades, em ordem crescente de importância.
A mensagem tem posição, linha ofensora e cursor, no formato que editores sabem interpretar e transformar em navegação clicável. Isso vem de graça da infraestrutura do módulo 1, que finalmente tem uso.
A análise não parou no primeiro erro. Trinta símbolos foram reconhecidos, incluindo os das linhas seguintes ao problema. O usuário vê os dois defeitos numa passada em vez de corrigir, recompilar e descobrir o próximo. Isso só é possível porque o DiagnosticBag foi projetado no módulo 1 para coletar em vez de lançar — decisão que na época pareceu exagero num módulo sem fase alguma.
E a corrida de cinco tis virou um erro, não cinco. Essa é a parte que exigiu trabalho: a recuperação consome a corrida inteira de caracteres que não podem iniciar símbolo algum e reporta uma vez. Reportar por caractere transformaria um engano de digitação numa parede de mensagens, e o critério discutido no módulo 10 — um erro real vale mais que dez derivados — já vale aqui.
Onde é fácil errar aqui. Recuperar avançando um caractere e tentando de novo, sem coalescer. Funciona, no sentido de que a análise prossegue, e produz uma mensagem por caractere inválido. O grupo só percebe o problema quando alguém cola um trecho de texto errado no arquivo e recebe quarenta erros idênticos.
Como verificar. Uma entrada com uma corrida longa de caracteres inválidos precisa produzir um diagnóstico, e a contagem de símbolos reconhecidos precisa ser maior que zero — provando que a análise continuou.
1.6 Referência teórica: buffers de entrada e o custo do retrocesso
O módulo trata de buffers de entrada e do efeito do retrocesso sobre o desempenho. Nossa situação é particular e vale declará-la: o arquivo inteiro é carregado na memória desde o módulo 1, então não há buffer a gerenciar nem fronteira de bloco a tratar. A decisão foi tomada lá e continua adequada — programas Peneira são pequenos.
O retrocesso, porém, existe e é medível. O casamento mais longo obriga cada autômato a avançar enquanto puder, mesmo quando outro vai vencer, e os caracteres lidos e descartados são o custo. Instrumentei o analisador para contá-los:
simbolos produzidos: 47
caracteres do arquivo: 257
caracteres consumidos: 161 (viraram lexema)
caracteres examinados: 391 (lidos por algum automato)
fator de releitura: 2.43xCada caractere que vira lexema foi lido, em média, duas vezes e meia. O fator vem de rodar as cinco regras em paralelo a cada posição — decisão da tarefa 2, agora com preço na tela em vez de na intuição.
Um gerador de analisadores combinaria as cinco num autômato só, com os estados finais marcados por categoria, e o fator cairia para perto de um. Mantive separado por clareza do desempate, e a conta fecha: num arquivo de programa Peneira, duas vezes e meia quase nada continua sendo quase nada. Se o alvo fosse arquivos de megabytes, a decisão seria outra — e agora há o número para embasá-la.
1.7 Referência teórica: geradores automáticos de analisadores léxicos
O módulo apresenta os geradores ao final, e a ordem é deliberada. Um gerador recebe a lista de padrões com as ações associadas e produz o código do analisador; internamente ele faz exatamente o que este projeto fez à mão — converte cada padrão em autômato, funde tudo num determinístico, minimiza, e gera uma tabela de transição junto com o laço de casamento mais longo.
Apresentá-los no módulo 2 teria esvaziado os cinco módulos seguintes. Apresentá-los agora tem efeito oposto: quem implementou a construção de subconjuntos olha para a saída de um gerador e reconhece a tabela. A diferença entre saber usar e saber por quê é exatamente esta.
Não há código de referência para este tópico, e a razão é a decisão travada do projeto: o ferramental é tudo à mão, sem geradores. Demonstrá-los exigiria adicionar uma dependência que o resto do semestre não usa, para produzir um analisador que já temos. O que o projeto oferece no lugar é a comparação honesta — nosso analisador tem fator de releitura de 2,43; o de um gerador teria perto de 1; e a diferença é o preço da legibilidade que escolhemos.
1.8 Verificação da entrega consolidada
| Item | Como conferir | Estado nesta referência |
|---|---|---|
| Seis categorias verificadas | Corpora do módulo 2, aceitas e rejeitadas | 33 e 24 casos, todos corretos |
| Analisador léxico completo | Programa de exemplo reconhecido de ponta a ponta | 47 símbolos, 0 erros |
| Interface sob demanda | Um símbolo por chamada, sem materializar a lista | Atende |
| Casamento mais longo | >=, =>, -5 reconhecidos inteiros |
Atende |
| Prioridade de reservadas | pattern reclassificada, patterns não |
Atende |
| Espaço e comentário | Descartados, não emitidos | Atende |
| Erro posicionado | Arquivo, linha, coluna, linha ofensora e cursor | Atende |
| Recuperação sem cascata | Corrida inválida vira um diagnóstico | 2 erros, 30 símbolos reconhecidos |
| Retrocesso medido | Contador de examinados contra consumidos | Fator 2,43 |
| Documentação revisada | Números dos módulos 4 e 5 corrigidos | Atende |
| Código compila limpo | Nenhum aviso sob o modo estrito | Atende, verificado por compilação e execução |
O que quero deixar registrado sobre este marco é o que a revisão custou e rendeu. Ela encontrou um defeito de cinco módulos de idade, obrigou a corrigir duas tabelas publicadas, e mostrou que medir não é verificar. Nenhum grupo gosta de descobrir isso no marco; todos preferem descobrir no marco a descobrir na entrega final. O front-end léxico está pronto, e o que vem a seguir — a estrutura aninhada que o módulo 6 provou estar fora do alcance deste modelo — precisa de outra fase.