1 Módulo 14: Projeto do Professor — Os Autômatos Dentro do Arquivo Gerado
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. É o modelo do que o seu grupo entrega, não algo a copiar.
1.1 Visão Geral do Módulo 14
A partir deste módulo existe um artefato que não é mais estrutura interna: é um arquivo. O compilador da Peneira passa a produzir saída, e a saída executa.
A atividade tem três partes. Implementar o gerador que percorre a representação intermediária do módulo 13 e emite o objeto no formato especificado lá, tratando a avaliação com curto-circuito. Implementar um executor mínimo capaz de rodar o objeto sobre uma entrada e produzir o efeito observável. E demonstrar pelo menos três programas compilados e executados, com entrada e saída registradas, e o objeto salvo para inspeção.
Resolvi a atividade e há um resultado que vale antecipar, porque é o fechamento conceitual mais forte do semestre. A primeira seção do arquivo que este compilador gera é uma tabela de transição — os autômatos finitos determinísticos que construímos no primeiro bloco, saídos de expressão regular por Thompson, determinização e minimização, serializados. Os autômatos estudados em fevereiro estão literalmente dentro do arquivo que o compilador produz. Não é analogia nem paralelo pedagógico: é o mesmo objeto, gravado.
O segundo resultado é menos agradável e mais instrutivo. Escrevi a rotina que calcula quantos registradores uma máquina de registradores precisaria para estas mesmas regras, confrontei o número com a profundidade da pilha, e os dois não bateram. A rotina estava errada. Está registrado na tarefa 3, porque o modo como o erro apareceu é mais útil que o erro.
1.2 Tarefa 1: A seleção de instruções, e os dois subproblemas que somem
A atividade — implementar o gerador que percorre a representação intermediária e emite o objeto no formato especificado.
A geração de código tem três subproblemas clássicos, e eles são interdependentes: a melhor seleção de instruções depende de quantos registradores sobraram, que depende da ordem de avaliação escolhida, que depende de quais instruções foram selecionadas. Resolver os três juntos é intratável, e a prática é decompor e aceitar um resultado subótimo.
Nesta máquina de destino, dois dos três desaparecem, e o motivo é a decisão de projeto tomada no módulo 13. A ordenação já está resolvida: o código de três endereços é linear, e a ordem de avaliação está na sequência. A alocação de registradores não existe: a máquina é de pilha e não tem registradores — o operando fica no topo, e o topo é implícito.
Sobra a seleção, que aqui é quase uma tabela:
14_codegen.h
#ifndef PENEIRA_14_CODEGEN_H
#define PENEIRA_14_CODEGEN_H
#include <cstddef>
#include <string>
#include <vector>
#include "10_ast.h"
#include "12_sema.h"
#include "13_objeto.h"
#include "13_ri.h"
namespace peneira {
// GERAÇÃO DE CÓDIGO: da representação intermediária para o programa objeto.
//
// Os três subproblemas clássicos da geração de código são seleção de
// instruções, alocação de registradores e ordenação da avaliação, e eles são
// interdependentes — a melhor seleção depende de quantos registradores
// sobraram, que depende da ordem escolhida, que depende de quais instruções
// foram selecionadas. Resolver os três juntos é intratável; a prática é
// decompor e aceitar o resultado subótimo.
//
// Nesta máquina de destino, dois dos três **desaparecem**, e vale saber por
// quê antes de ler o código:
//
// - A ORDENAÇÃO já foi decidida no módulo 13. O código de três endereços é
// linear: a ordem de avaliação está na sequência das instruções.
// - A ALOCAÇÃO DE REGISTRADORES não existe, porque a máquina é de pilha e
// não tem registradores. O operando fica no topo, e o topo é implícito.
//
// Sobra a SELEÇÃO, que aqui é quase uma tabela: cada operação da representação
// intermediária tem uma instrução correspondente. Essa simplicidade é o que se
// compra ao escolher máquina de pilha, e o preço está pago no módulo 13 — o
// preço é que o objeto executa mais instruções do que executaria numa máquina
// de registradores.
//
// Para não deixar a alocação de registradores como assunto puramente verbal,
// este módulo CALCULA o que ela custaria: monta o grafo de interferência dos
// temporários da representação intermediária e o colore. O número de cores é o
// número de registradores que uma máquina de registradores precisaria.
// ---------------------------------------------------------------------------
// Geração
// ---------------------------------------------------------------------------
struct RelatorioDeGeracao {
std::size_t regrasGeradas = 0;
std::size_t instrucoesEmitidas = 0;
std::size_t referenciasResolvidas = 0;
// Profundidade máxima da pilha de avaliação, calculada por simulação
// estática. O executor pode pré-alocar exatamente isto.
std::size_t profundidadeMaximaDaPilha = 0;
// Falha dura: um temporário lido mais de uma vez quebraria a disciplina de
// pilha (o valor é consumido ao ser lido). Ver `verificarUsoUnico`.
std::vector<std::string> violacoesDeUsoUnico;
};
// Gera o programa objeto completo a partir do resultado da análise semântica e
// da árvore verificada.
ProgramaObjeto gerarObjeto(const ResultadoSemantico& semantico,
const NoAst& raiz, RelatorioDeGeracao& relatorio);
// Traduz o código de uma regra. Exposta separadamente porque é o miolo do
// módulo e a demonstração a exercita isolada.
std::vector<Instrucao> gerarCodigoDaRegra(const CodigoRI& ri,
ProgramaObjeto& objeto,
RelatorioDeGeracao& relatorio);
// A disciplina de pilha só funciona se cada temporário for lido EXATAMENTE uma
// vez: ler é desempilhar, e um segundo leitor encontraria a pilha já consumida.
// A representação intermediária do módulo 13 satisfaz isso por construção — ela
// reemite o casamento a cada uso em vez de reaproveitar o temporário —, mas
// "por construção" é exatamente o tipo de garantia que se perde numa alteração
// futura. A verificação custa um percurso e transforma um defeito silencioso de
// execução em erro de compilação.
std::vector<std::string> verificarUsoUnico(const CodigoRI& ri);
// ---------------------------------------------------------------------------
// Alocação de registradores, calculada (tratamento conceitual, número real)
// ---------------------------------------------------------------------------
// A faixa de vida de um temporário: da instrução que o define à última que o
// lê. Dois temporários INTERFEREM quando as faixas se sobrepõem — eles não
// podem compartilhar registrador.
struct FaixaDeVida {
std::string temporario;
std::size_t definicao = 0;
std::size_t ultimoUso = 0;
};
struct GrafoDeInterferencia {
std::vector<FaixaDeVida> faixas;
// Matriz de adjacência achatada: interfere[i * n + j].
std::vector<std::uint8_t> interfere;
std::size_t n = 0;
bool haAresta(std::size_t i, std::size_t j) const;
};
GrafoDeInterferencia construirInterferencia(const CodigoRI& ri);
// Coloração gulosa: percorre os temporários e dá a cada um a menor cor que
// nenhum vizinho usa. Não é ótima em geral — colorir com o número mínimo de
// cores é problema difícil, e é por isso que compiladores reais usam heurística
// —, mas em grafos de intervalo como estes ela encontra o mínimo.
struct Coloracao {
std::vector<std::size_t> corDoTemporario;
std::size_t cores = 0;
};
Coloracao colorir(const GrafoDeInterferencia& g);
// Grava o objeto em disco, para inspeção. Devolve false e preenche `erro` em
// caso de falha.
bool gravarObjeto(const ProgramaObjeto& objeto, const std::string& caminho,
std::string& erro);
} // namespace peneira
#endif // PENEIRA_14_CODEGEN_HEssa simplicidade foi comprada, e o preço está pago no módulo anterior: o objeto executa mais instruções do que executaria numa máquina de registradores, porque empilhar e desempilhar são trabalho que o registrador nomeado dispensa. A demonstração --selecao põe as duas formas lado a lado:
tres enderecos (maquina de registradores infinitos) pilha
---------------------------------------------------- --------------------
0: t0 := casamento n 0: PUSH_MATCH 0
1: t1 := valor t0 1: VALUE
2: t2 := 100 2: PUSH_CONST 0
3: t3 := t1 > t2 3: CMP_GT
4: se_falso t3 desvia para 12 4: JUMP_IF_FALSE 12
5: t4 := casamento n 5: PUSH_MATCH 0
6: t5 := valor t4 6: VALUE
7: t6 := 500 7: PUSH_CONST 1
8: t7 := t5 < t6 8: CMP_LT
9: se_falso t7 desvia para 12 9: JUMP_IF_FALSE 12
10: t8 := casamento n 10: PUSH_MATCH 0
11: emite "faixa", t8 11: EMIT 2Repare no que a coluna da direita não tem: nomes. O código de três endereços é, na prática, código para uma máquina de registradores infinitos, e cada t é um registrador virtual. A máquina de pilha apaga todos eles e deixa a posição fazer o trabalho do nome.
1.2.1 A invariante que torna isso válido
A disciplina de pilha só funciona se cada temporário for lido exatamente uma vez: ler é desempilhar, e um segundo leitor encontraria a pilha já consumida. A representação intermediária do módulo 13 satisfaz isso por construção, porque ela reemite o casamento a cada uso em vez de reaproveitar o temporário — é por isso que value(n) aparece duas vezes na condição e gera PUSH_MATCH duas vezes.
“Por construção” é exatamente o tipo de garantia que se perde numa alteração futura, então a verifiquei em código. verificarUsoUnico percorre a representação contando leituras por temporário, e uma violação vira erro de compilação em vez de defeito silencioso de execução. O gerador do módulo principal encerra com código de erro se a lista não estiver vazia.
Onde é fácil errar aqui. Contar como leitura de temporário todo campo de operando. O campo arg1 de uma constante é um literal, não um temporário, e contá-lo produz nomes fantasmas na tabela de leituras. Por isso a verificação despacha por operação em vez de varrer os campos.
Como verificar. Em qualquer programa correto, a contagem de violações tem de ser zero e a profundidade da pilha calculada estaticamente tem de fechar com o que a execução usa.
1.3 Tarefa 2: As referências pendentes, do numerador da representação para o do objeto
A atividade — resolver as referências pendentes, tratando a avaliação com curto-circuito.
O curto-circuito já estava resolvido no módulo 13 — as listas de desvio foram preenchidas lá, e chegam aqui com destino definido. O que não estava resolvido é que aqueles destinos são índices da representação intermediária, e o objeto precisa de índices do objeto.
14_codegen.cpp
#include "14_codegen.h"
#include <fstream>
#include <unordered_map>
namespace peneira {
namespace {
// Seleção de instruções: a tabela que mapeia operador de comparação da fonte
// para o código da máquina. É literalmente a "seleção de instruções" do
// módulo, e ela cabe numa função porque a máquina foi projetada para isso.
OpCode selecionarComparacao(const std::string& operador) noexcept {
if (operador == ">") return OpCode::CMP_GT;
if (operador == "<") return OpCode::CMP_LT;
if (operador == ">=") return OpCode::CMP_GE;
if (operador == "<=") return OpCode::CMP_LE;
if (operador == "==") return OpCode::CMP_EQ;
if (operador == "!=") return OpCode::CMP_NE;
return OpCode::CMP_EQ;
}
// Efeito de cada instrução sobre a altura da pilha. Serve para calcular a
// profundidade máxima por simulação estática, sem executar.
int efeitoNaPilha(OpCode op) noexcept {
switch (op) {
case OpCode::PUSH_CONST:
case OpCode::PUSH_MATCH:
return +1;
case OpCode::VALUE:
return 0; // desempilha um, empilha um
case OpCode::CMP_GT:
case OpCode::CMP_LT:
case OpCode::CMP_GE:
case OpCode::CMP_LE:
case OpCode::CMP_EQ:
case OpCode::CMP_NE:
case OpCode::AND:
case OpCode::OR:
return -1; // desempilha dois, empilha um
case OpCode::JUMP_IF_FALSE:
case OpCode::EMIT:
return -1;
case OpCode::JUMP:
case OpCode::HALT:
return 0;
}
return 0;
}
void colherAcoes(const NoAst& no, std::vector<const NoAst*>& saida) {
if (no.tipo == TipoAst::Acao) {
saida.push_back(&no);
return;
}
for (const AstPtr& filho : no.filhos) {
if (filho) {
colherAcoes(*filho, saida);
}
}
}
} // namespace
std::vector<std::string> verificarUsoUnico(const CodigoRI& ri) {
std::unordered_map<std::string, std::size_t> leituras;
for (const InstrucaoRI& ins : ri.instrucoes) {
// Os campos que CONTÊM leitura de temporário variam por operação, e
// listá-los explicitamente é mais seguro que varrer todos os campos:
// `arg1` de uma constante é um literal, não um temporário.
switch (ins.op) {
case OpRI::Valor:
++leituras[ins.arg1];
break;
case OpRI::Comparacao:
++leituras[ins.arg1];
++leituras[ins.arg2];
break;
case OpRI::DesvioSeFalso:
++leituras[ins.arg1];
break;
case OpRI::Emite:
++leituras[ins.arg2];
break;
default:
break;
}
}
std::vector<std::string> violacoes;
for (const InstrucaoRI& ins : ri.instrucoes) {
const bool define = ins.op == OpRI::Constante ||
ins.op == OpRI::CasamentoDe ||
ins.op == OpRI::Valor ||
ins.op == OpRI::Comparacao;
if (!define) {
continue;
}
const auto it = leituras.find(ins.resultado);
const std::size_t vezes = it == leituras.end() ? 0 : it->second;
if (vezes > 1) {
violacoes.push_back(ins.resultado + " lido " +
std::to_string(vezes) + " vezes");
}
}
return violacoes;
}
std::vector<Instrucao> gerarCodigoDaRegra(const CodigoRI& ri,
ProgramaObjeto& objeto,
RelatorioDeGeracao& relatorio) {
std::vector<Instrucao> codigo;
// O mapa de endereços. A representação intermediária desvia para ÍNDICES
// DELA MESMA, e o objeto precisa desviar para índices DO OBJETO. Como uma
// instrução intermediária pode virar zero, uma ou várias instruções de
// máquina, os dois numeradores não coincidem em geral, e supor que
// coincidem é o erro que produz desvio para o meio de outra instrução.
//
// O mapa tem um elemento A MAIS que o número de instruções: o índice
// "logo depois da última" é destino legítimo — é para lá que apontam os
// desvios de condição falsa.
std::vector<std::size_t> enderecoDe(ri.instrucoes.size() + 1, 0);
for (std::size_t i = 0; i < ri.instrucoes.size(); ++i) {
enderecoDe[i] = codigo.size();
const InstrucaoRI& ins = ri.instrucoes[i];
switch (ins.op) {
case OpRI::Constante: {
// O literal vai para a área de constantes; a instrução carrega
// o índice. Reaproveitamento é automático: constante repetida
// ocupa uma entrada só.
std::string valor = ins.arg1;
if (valor.size() >= 2 && valor.front() == '"' &&
valor.back() == '"') {
valor = valor.substr(1, valor.size() - 2);
}
codigo.push_back(Instrucao{OpCode::PUSH_CONST,
objeto.adicionarConstante(valor)});
break;
}
case OpRI::CasamentoDe:
// Argumento 0: cada regra tem exatamente uma ligação nesta
// linguagem. O campo existe para o dia em que houver mais.
codigo.push_back(Instrucao{OpCode::PUSH_MATCH, 0});
break;
case OpRI::Valor:
codigo.push_back(Instrucao{OpCode::VALUE, 0});
break;
case OpRI::Comparacao:
codigo.push_back(
Instrucao{selecionarComparacao(ins.operador), 0});
break;
case OpRI::DesvioSeFalso:
// Destino ainda desconhecido em endereços de objeto: fica zero
// e é corrigido na passagem seguinte.
codigo.push_back(Instrucao{OpCode::JUMP_IF_FALSE, 0});
break;
case OpRI::Desvio:
codigo.push_back(Instrucao{OpCode::JUMP, 0});
break;
case OpRI::Emite: {
std::string rotulo = ins.arg1;
if (rotulo.size() >= 2 && rotulo.front() == '"' &&
rotulo.back() == '"') {
rotulo = rotulo.substr(1, rotulo.size() - 2);
}
codigo.push_back(Instrucao{OpCode::EMIT,
objeto.adicionarConstante(rotulo)});
break;
}
case OpRI::Rotulo:
// Não emite instrução nenhuma: o rótulo é posição, e a posição
// já está registrada no mapa. É o caso que torna o mapa
// necessário — aqui o numerador do objeto NÃO avança.
break;
}
}
enderecoDe[ri.instrucoes.size()] = codigo.size();
// Toda regra termina em HALT explícito. Poderia ser implícito — passar da
// última instrução encerra —, e deixar explícito custa um byte e elimina
// um caso especial do executor.
codigo.push_back(Instrucao{OpCode::HALT, 0});
// Segunda passagem: resolver as referências pendentes. Agora os dois
// numeradores são conhecidos, e a tradução de um para o outro é o mapa.
std::size_t resolvidas = 0;
for (std::size_t i = 0; i < ri.instrucoes.size(); ++i) {
const InstrucaoRI& ins = ri.instrucoes[i];
const bool ehDesvio =
ins.op == OpRI::Desvio || ins.op == OpRI::DesvioSeFalso;
if (!ehDesvio) {
continue;
}
if (ins.destino == kDestinoPendente ||
ins.destino > ri.instrucoes.size()) {
// Desvio sem destino chegou até aqui: é defeito do módulo 13, e
// gerar código a partir dele produziria objeto malformado.
continue;
}
codigo[enderecoDe[i]].argumento =
static_cast<std::uint32_t>(enderecoDe[ins.destino]);
++resolvidas;
}
relatorio.referenciasResolvidas += resolvidas;
// Profundidade máxima da pilha, por simulação estática. Percorrer
// linearmente é aproximação segura aqui porque todo desvio salta para a
// frente e os dois caminhos chegam com a mesma altura — propriedade que a
// tradução do módulo 13 garante e que uma tradução futura poderia quebrar.
int altura = 0;
int maximo = 0;
for (const Instrucao& ins : codigo) {
altura += efeitoNaPilha(ins.op);
if (altura > maximo) {
maximo = altura;
}
}
if (static_cast<std::size_t>(maximo) > relatorio.profundidadeMaximaDaPilha) {
relatorio.profundidadeMaximaDaPilha = static_cast<std::size_t>(maximo);
}
relatorio.instrucoesEmitidas += codigo.size();
return codigo;
}
ProgramaObjeto gerarObjeto(const ResultadoSemantico& semantico,
const NoAst& raiz, RelatorioDeGeracao& relatorio) {
ProgramaObjeto objeto;
// Seção 1: os autômatos. É aqui que o conteúdo do primeiro bloco do
// semestre entra, literalmente, dentro do arquivo gerado.
std::unordered_map<std::string, std::uint32_t> indiceDoPadrao;
for (const PadraoCompilado& p : semantico.padroes) {
indiceDoPadrao.emplace(
p.nome, static_cast<std::uint32_t>(objeto.padroes.size()));
objeto.padroes.push_back(serializarPadrao(
p.automato, p.nome, p.tipoDoCasamento == Tipo::Numero));
}
// Seção 2: o código das regras.
std::vector<const NoAst*> acoes;
colherAcoes(raiz, acoes);
for (const NoAst* acao : acoes) {
TradutorRI tradutor;
const CodigoRI ri = tradutor.traduzirAcao(*acao);
const std::vector<std::string> violacoes = verificarUsoUnico(ri);
for (const std::string& v : violacoes) {
relatorio.violacoesDeUsoUnico.push_back(acao->texto + ": " + v);
}
RegraObjeto regra;
const auto it = indiceDoPadrao.find(acao->texto);
if (it == indiceDoPadrao.end()) {
// Padrão inexistente já foi reportado pela análise semântica; aqui
// a ação é simplesmente pulada, para não emitir objeto que
// referencia padrão que não existe.
continue;
}
regra.indiceDoPadrao = it->second;
regra.ligacao = acao->conteudo;
regra.codigo = gerarCodigoDaRegra(ri, objeto, relatorio);
objeto.regras.push_back(std::move(regra));
++relatorio.regrasGeradas;
}
return objeto;
}
// ---------------------------------------------------------------------------
// Interferência e coloração
// ---------------------------------------------------------------------------
bool GrafoDeInterferencia::haAresta(std::size_t i, std::size_t j) const {
if (i >= n || j >= n) {
return false;
}
return interfere[i * n + j] != 0;
}
GrafoDeInterferencia construirInterferencia(const CodigoRI& ri) {
GrafoDeInterferencia g;
std::unordered_map<std::string, std::size_t> indice;
// Faixa de vida: da definição ao último uso.
for (std::size_t i = 0; i < ri.instrucoes.size(); ++i) {
const InstrucaoRI& ins = ri.instrucoes[i];
const bool define = ins.op == OpRI::Constante ||
ins.op == OpRI::CasamentoDe ||
ins.op == OpRI::Valor ||
ins.op == OpRI::Comparacao;
if (define && !ins.resultado.empty()) {
indice.emplace(ins.resultado, g.faixas.size());
g.faixas.push_back(FaixaDeVida{ins.resultado, i, i});
}
auto registrarUso = [&](const std::string& nome) {
const auto it = indice.find(nome);
if (it != indice.end()) {
g.faixas[it->second].ultimoUso = i;
}
};
switch (ins.op) {
case OpRI::Valor:
case OpRI::DesvioSeFalso:
registrarUso(ins.arg1);
break;
case OpRI::Comparacao:
registrarUso(ins.arg1);
registrarUso(ins.arg2);
break;
case OpRI::Emite:
registrarUso(ins.arg2);
break;
default:
break;
}
}
g.n = g.faixas.size();
g.interfere.assign(g.n * g.n, 0);
for (std::size_t i = 0; i < g.n; ++i) {
for (std::size_t j = i + 1; j < g.n; ++j) {
// Sobreposição em intervalo SEMIABERTO, e a diferença em relação ao
// fechado não é detalhe: um valor MORRE na instrução que o lê pela
// última vez, e o valor que essa mesma instrução produz pode ocupar
// o registrador que acabou de vagar.
//
// Com intervalo fechado, `t3 := t1 > t2` faria t3 interferir com t1
// e t2, e a conta pediria um registrador a mais do que o necessário.
// Foi exatamente o que a primeira versão desta função respondeu — 3
// registradores para uma expressão de profundidade 2 —, e o erro só
// apareceu porque o número foi confrontado com a altura da pilha.
const bool sobrepoe = g.faixas[i].definicao < g.faixas[j].ultimoUso &&
g.faixas[j].definicao < g.faixas[i].ultimoUso;
if (sobrepoe) {
g.interfere[i * g.n + j] = 1;
g.interfere[j * g.n + i] = 1;
}
}
}
return g;
}
Coloracao colorir(const GrafoDeInterferencia& g) {
Coloracao c;
c.corDoTemporario.assign(g.n, 0);
for (std::size_t i = 0; i < g.n; ++i) {
std::vector<bool> usada(g.n + 1, false);
for (std::size_t j = 0; j < g.n; ++j) {
if (j != i && g.haAresta(i, j) && j < i) {
usada[c.corDoTemporario[j]] = true;
}
}
std::size_t cor = 0;
while (cor < usada.size() && usada[cor]) {
++cor;
}
c.corDoTemporario[i] = cor;
if (cor + 1 > c.cores) {
c.cores = cor + 1;
}
}
return c;
}
bool gravarObjeto(const ProgramaObjeto& objeto, const std::string& caminho,
std::string& erro) {
std::ofstream saida(caminho, std::ios::binary);
if (!saida) {
erro = "nao foi possivel abrir para escrita";
return false;
}
// Forma textual, e não binária. A decisão é didática e assumida: o objeto
// deste compilador é para ser LIDO na correção e na aula. Um formato
// binário seria menor e ilegível, e a economia não tem valor aqui.
saida << formatarObjeto(objeto);
if (!saida) {
erro = "falha ao escrever";
return false;
}
return true;
}
} // namespace peneiraA solução é um mapa construído durante a emissão e consultado numa segunda passagem. Cada instrução intermediária registra, antes de ser traduzida, em que endereço de objeto ela começou; ao final, cada desvio troca o destino intermediário pelo endereço correspondente.
Dois detalhes do mapa não são óbvios. Ele tem um elemento a mais que o número de instruções, porque “logo depois da última” é destino legítimo — é para lá que apontam os desvios de condição falsa, e sem essa entrada extra o preenchimento leria fora do vetor. E a operação de rótulo não emite instrução nenhuma: o rótulo é posição, e ali o numerador do objeto não avança enquanto o da representação avança.
A demonstração --referencias confere o resultado nos três programas, e o resultado é honesto de um jeito que vale registrar:
faixa.pen, regra on numero(n):
instrucoes intermediarias: 12, de maquina: 13
referencias resolvidas: 2
RI 4 desvia para RI 12 -> objeto 4 desvia para 12
RI 9 desvia para RI 12 -> objeto 9 desvia para 12A correspondência saiu um para um neste artefato, porque toda instrução intermediária virou exatamente uma de máquina. Poderia ter concluído dali que o mapa é desnecessário e escrito o gerador supondo identidade. Seria errado: a coincidência é propriedade deste conjunto de instruções, não garantia. A operação de rótulo já quebraria a identidade se fosse usada, e qualquer instrução futura que precise de duas de máquina também. Supor identidade produz desvio para o meio de outra instrução — defeito que não aparece em teste algum até a entrada certa aparecer.
Onde é fácil errar aqui. Corrigir os destinos na mesma passagem que emite. No momento em que o desvio é emitido, o endereço do alvo ainda não existe, e a única saída seria voltar atrás — que é a segunda passagem, escrita de forma pior. Duas passagens explícitas custam um vetor e são corretas por construção.
Como verificar. Todo argumento de desvio no objeto tem de ser um índice válido de instrução daquela regra, e todo desvio tem de apontar para um endereço que consta do mapa. Um desvio para o meio de uma instrução é impossível aqui porque as instruções têm tamanho fixo, mas num formato de tamanho variável essa checagem seria obrigatória.
1.4 Tarefa 3: A alocação de registradores, calculada — e o erro que o cálculo revelou
A atividade — explicar a alocação de registradores pelo modelo de coloração de grafo de interferência.
Esta máquina não tem registradores, então o assunto poderia ficar no verbal. Preferi calcular o que ele custaria: montar o grafo de interferência dos temporários da representação intermediária e colori-lo. O número de cores é o número de registradores que uma máquina de registradores precisaria para a mesma regra.
Dois temporários interferem quando suas faixas de vida se sobrepõem — não podem compartilhar registrador. A coloração gulosa dá a cada um a menor cor que nenhum vizinho usa. Ela não é ótima em geral, e vale saber por quê: colorir um grafo com o número mínimo de cores é problema difícil, e é exatamente por isso que compiladores reais usam heurística em vez de solução exata. Em grafos de intervalo como estes, porém, a gulosa encontra o mínimo.
O resultado, de --registradores:
temporario | definido em | ultimo uso | cor
-----------+-------------+------------+----
t0 | 0 | 1 | 0
t1 | 1 | 3 | 0
t2 | 2 | 3 | 1
t3 | 3 | 4 | 0
...
temporarios: 9, arestas de interferencia: 2
registradores necessarios (cores): 2
profundidade maxima da pilha: 2Dois registradores, e profundidade de pilha dois. Os números coincidem, e não por acaso: com cada temporário lido uma única vez, o número de valores vivos ao mesmo tempo é a altura da pilha naquele ponto. A máquina de pilha e a de registradores precisam da mesma quantidade de espaço de trabalho; a diferença está em quem o endereça — a pilha implicitamente, o registrador por nome na instrução.
1.4.1 O erro, e como ele apareceu
A primeira versão desta rotina respondeu três registradores contra pilha de dois. Os números não bateram, e isso é o que denunciou o defeito.
A causa é sutil e é o erro clássico deste cálculo. Eu tratava as faixas de vida como intervalos fechados, de modo que em t3 := t1 > t2 o temporário t3 interferia com t1 e com t2. Só que um valor morre na instrução que o lê pela última vez, e o valor que essa mesma instrução produz pode ocupar o registrador que acabou de vagar. A sobreposição correta é em intervalo semiaberto, e a correção é trocar duas comparações de <= para <.
O que quero registrar não é o erro, é o mecanismo que o pegou. Três registradores para uma expressão de profundidade dois é um número perfeitamente plausível — não tem cara de defeito, e nenhum teste de compilação o acusaria. Ele só caiu porque havia um segundo caminho para chegar à mesma grandeza, a simulação da pilha, e os dois foram confrontados. É o mesmo padrão do módulo 4, quando o autômato gerado foi confrontado com o desenhado à mão, e do módulo 5, quando o mínimo por duas vias foi testado por isomorfismo. Calcular a mesma coisa de dois jeitos independentes é a técnica de verificação mais barata que existe neste projeto, e é a que mais defeitos encontrou.
Onde é fácil errar aqui. Aceitar o primeiro número plausível. Se eu tivesse escrito apenas a coloração, sem a simulação da pilha ao lado, a resposta errada teria entrado no material como resultado.
Como verificar. O confronto entre as duas grandezas, que é o que está impresso na demonstração. Divergência entre elas significa que uma das duas está errada, e nunca que “ambas estão certas de pontos de vista diferentes”.
1.5 Tarefa 4: O executor mínimo
A atividade — implementar um executor mínimo, capaz de rodar o objeto e produzir o efeito observável.
Mínimo tem significado preciso: suficiente para demonstrar que o objeto está correto. O tratamento completo de erro e de casos de fronteira é do módulo 15, e superdimensionar o executor agora atrasaria a única coisa que ele precisa provar.
14_vm.h
#ifndef PENEIRA_14_VM_H
#define PENEIRA_14_VM_H
#include <cstddef>
#include <string>
#include <vector>
#include "13_objeto.h"
namespace peneira {
// EXECUTOR MÍNIMO do programa objeto.
//
// Mínimo tem significado preciso aqui: suficiente para demonstrar que o objeto
// gerado está correto. O tratamento completo de erro e de casos de fronteira é
// do módulo 15, e superdimensionar este executor agora atrasaria a única coisa
// que ele precisa provar — que o que o gerador emitiu executa e produz o efeito
// esperado.
//
// Ele é escrito contra a ESPECIFICAÇÃO do módulo 13, e não contra o gerador do
// módulo 14. A diferença importa: escrito contra o gerador, ele concordaria com
// os defeitos do gerador. Escrito contra a especificação, uma divergência entre
// os dois acusa que um dos dois está errado — que é justamente o teste que o
// critério de completude da especificação queria permitir.
// Um valor na pilha de avaliação. A linguagem tem dois tipos, e o executor
// carrega os dois numa estrutura só porque a análise semântica já garantiu que
// nenhuma instrução vai receber o tipo errado.
struct Valor {
bool ehNumero = false;
double numero = 0.0;
std::string texto;
};
// Uma emissão produzida pela execução: o par (rótulo, valor) que `emit` gera.
struct Emissao {
std::string rotulo;
std::string valor;
std::size_t posicao = 0; // onde na entrada o casamento começou
};
struct ResultadoExecucao {
std::vector<Emissao> emissoes;
std::size_t casamentos = 0;
std::size_t bytesLidos = 0;
std::size_t instrucoesExecutadas = 0;
std::vector<std::string> erros;
};
// Executa o programa objeto sobre a entrada.
//
// O laço principal implementa o casamento mais longo especificado no módulo 13:
// na posição corrente, avança todos os autômatos em paralelo enquanto algum
// tiver transição, lembrando a última posição em que algum esteve em estado
// final. Empate no mesmo comprimento resolve-se pela ordem de declaração — o
// primeiro padrão declarado vence, exatamente como está escrito na
// especificação.
ResultadoExecucao executar(const ProgramaObjeto& objeto,
const std::string& entrada);
} // namespace peneira
#endif // PENEIRA_14_VM_HUma decisão de método vale mais que o código, e é a que recomendo a qualquer grupo: escrevi o executor contra a especificação do módulo 13, e não contra o gerador do módulo 14. A diferença não é retórica. Escrito contra o gerador, o executor concordaria com os defeitos do gerador — os dois estariam errados juntos e os testes passariam. Escrito contra a especificação, uma divergência entre gerador e executor acusa que um dos dois está errado. É exatamente o teste que o critério de completude da especificação existia para tornar possível, e é a razão de a especificação ter vindo antes.
14_vm.cpp
#include "14_vm.h"
#include <cstdlib>
namespace peneira {
namespace {
// Consulta a tabela de transição densa. É a operação do laço interno — roda uma
// vez por byte da entrada e por padrão —, e é ela que justifica a matriz densa
// escolhida no módulo 13.
std::uint32_t transicaoDe(const PadraoObjeto& p, std::uint32_t estado,
unsigned char simbolo) noexcept {
const std::size_t indice =
static_cast<std::size_t>(estado) * kTamanhoDoAlfabeto +
static_cast<std::size_t>(simbolo);
if (indice >= p.transicoes.size()) {
return kSemTransicao;
}
return p.transicoes[indice];
}
// Verdade nesta linguagem: número diferente de zero, ou texto não vazio. A
// definição precisa estar num lugar só, porque JUMP_IF_FALSE e os conectivos a
// consultam.
bool ehVerdadeiro(const Valor& v) noexcept {
return v.ehNumero ? v.numero != 0.0 : !v.texto.empty();
}
std::string comoTexto(const Valor& v) {
if (!v.ehNumero) {
return v.texto;
}
// Sem casas decimais quando o número é inteiro: 250 e não 250.000000. É
// cosmético e afeta a saída observável, então está aqui e não no chamador.
const double arredondado = static_cast<double>(static_cast<long long>(v.numero));
if (v.numero == arredondado) {
return std::to_string(static_cast<long long>(v.numero));
}
return std::to_string(v.numero);
}
// Executa o código de uma regra sobre um casamento. Devolve false se o objeto
// estiver malformado — pilha vazia numa instrução que desempilha, ou desvio
// fora de faixa. As duas são as condições de erro listadas na especificação.
bool executarRegra(const ProgramaObjeto& objeto, const RegraObjeto& regra,
const std::string& casamento, std::size_t posicao,
ResultadoExecucao& resultado) {
std::vector<Valor> pilha;
std::size_t pc = 0;
auto desempilhar = [&](Valor& destino) -> bool {
if (pilha.empty()) {
resultado.erros.push_back(
"objeto malformado: pilha vazia em instrucao que desempilha");
return false;
}
destino = pilha.back();
pilha.pop_back();
return true;
};
while (pc < regra.codigo.size()) {
const Instrucao& ins = regra.codigo[pc];
++resultado.instrucoesExecutadas;
switch (ins.op) {
case OpCode::PUSH_CONST: {
if (ins.argumento >= objeto.constantes.size()) {
resultado.erros.push_back(
"objeto malformado: constante fora de faixa");
return false;
}
Valor v;
// A constante é guardada como texto; se ela denota um número,
// entra como número. A análise semântica já garantiu a
// coerência de tipos, então esta conversão não pode
// surpreender.
const std::string& bruto = objeto.constantes[ins.argumento];
char* fim = nullptr;
const double numero = std::strtod(bruto.c_str(), &fim);
if (fim != nullptr && *fim == '\0' && !bruto.empty()) {
v.ehNumero = true;
v.numero = numero;
} else {
v.texto = bruto;
}
pilha.push_back(v);
break;
}
case OpCode::PUSH_MATCH: {
Valor v;
v.texto = casamento;
pilha.push_back(v);
break;
}
case OpCode::VALUE: {
Valor v;
if (!desempilhar(v)) {
return false;
}
Valor n;
n.ehNumero = true;
n.numero = v.ehNumero ? v.numero : std::strtod(v.texto.c_str(), nullptr);
pilha.push_back(n);
break;
}
case OpCode::CMP_GT:
case OpCode::CMP_LT:
case OpCode::CMP_GE:
case OpCode::CMP_LE:
case OpCode::CMP_EQ:
case OpCode::CMP_NE: {
// A ordem importa: o segundo operando foi empilhado por
// último, então sai primeiro. Inverter aqui produz comparações
// trocadas que passam despercebidas nos casos simétricos.
Valor b;
Valor a;
if (!desempilhar(b) || !desempilhar(a)) {
return false;
}
bool r = false;
if (a.ehNumero && b.ehNumero) {
switch (ins.op) {
case OpCode::CMP_GT: r = a.numero > b.numero; break;
case OpCode::CMP_LT: r = a.numero < b.numero; break;
case OpCode::CMP_GE: r = a.numero >= b.numero; break;
case OpCode::CMP_LE: r = a.numero <= b.numero; break;
case OpCode::CMP_EQ: r = a.numero == b.numero; break;
default: r = a.numero != b.numero; break;
}
} else {
const std::string ta = comoTexto(a);
const std::string tb = comoTexto(b);
switch (ins.op) {
case OpCode::CMP_EQ: r = ta == tb; break;
case OpCode::CMP_NE: r = ta != tb; break;
default:
// Ordem sobre texto foi recusada na analise
// semantica, entao chegar aqui e objeto adulterado.
resultado.erros.push_back(
"objeto malformado: operador de ordem sobre texto");
return false;
}
}
Valor v;
v.ehNumero = true;
v.numero = r ? 1.0 : 0.0;
pilha.push_back(v);
break;
}
case OpCode::AND:
case OpCode::OR: {
Valor b;
Valor a;
if (!desempilhar(b) || !desempilhar(a)) {
return false;
}
Valor v;
v.ehNumero = true;
const bool r = ins.op == OpCode::AND
? (ehVerdadeiro(a) && ehVerdadeiro(b))
: (ehVerdadeiro(a) || ehVerdadeiro(b));
v.numero = r ? 1.0 : 0.0;
pilha.push_back(v);
break;
}
case OpCode::JUMP_IF_FALSE: {
Valor v;
if (!desempilhar(v)) {
return false;
}
if (!ehVerdadeiro(v)) {
if (ins.argumento > regra.codigo.size()) {
resultado.erros.push_back(
"objeto malformado: desvio fora de faixa");
return false;
}
pc = ins.argumento;
continue;
}
break;
}
case OpCode::JUMP: {
if (ins.argumento > regra.codigo.size()) {
resultado.erros.push_back(
"objeto malformado: desvio fora de faixa");
return false;
}
pc = ins.argumento;
continue;
}
case OpCode::EMIT: {
Valor v;
if (!desempilhar(v)) {
return false;
}
if (ins.argumento >= objeto.constantes.size()) {
resultado.erros.push_back(
"objeto malformado: rotulo fora de faixa");
return false;
}
resultado.emissoes.push_back(Emissao{
objeto.constantes[ins.argumento], comoTexto(v), posicao});
break;
}
case OpCode::HALT:
return true;
}
++pc;
}
return true;
}
} // namespace
ResultadoExecucao executar(const ProgramaObjeto& objeto,
const std::string& entrada) {
ResultadoExecucao resultado;
resultado.bytesLidos = entrada.size();
std::size_t posicao = 0;
while (posicao < entrada.size()) {
// Casamento mais longo: avança todos os autômatos em paralelo.
std::vector<std::uint32_t> estados(objeto.padroes.size());
std::vector<bool> vivo(objeto.padroes.size(), true);
for (std::size_t p = 0; p < objeto.padroes.size(); ++p) {
estados[p] = objeto.padroes[p].estadoInicial;
if (objeto.padroes[p].quantidadeDeEstados == 0) {
vivo[p] = false;
}
}
std::size_t melhorFim = posicao;
std::size_t melhorPadrao = objeto.padroes.size();
bool houveCasamento = false;
// Um padrão pode aceitar a cadeia vazia; conferir o estado inicial
// antes de consumir byte nenhum evita perder esse caso — e evita
// também o laço infinito que ele causaria se fosse aceito com
// comprimento zero, tratado adiante.
for (std::size_t p = 0; p < objeto.padroes.size(); ++p) {
if (vivo[p] && objeto.padroes[p].finais[estados[p]] != 0) {
houveCasamento = true;
melhorFim = posicao;
melhorPadrao = p;
break;
}
}
std::size_t i = posicao;
while (i < entrada.size()) {
const unsigned char simbolo = static_cast<unsigned char>(entrada[i]);
bool algumVivo = false;
for (std::size_t p = 0; p < objeto.padroes.size(); ++p) {
if (!vivo[p]) {
continue;
}
const std::uint32_t proximo =
transicaoDe(objeto.padroes[p], estados[p], simbolo);
if (proximo == kSemTransicao) {
vivo[p] = false;
continue;
}
estados[p] = proximo;
algumVivo = true;
}
if (!algumVivo) {
break;
}
++i;
// Registra o casamento mais longo visto até agora. A varredura é
// da esquerda para a direita, e o desempate por ORDEM DE
// DECLARAÇÃO sai de graça: o laço testa os padrões na ordem do
// vetor e o `>` estrito impede que um padrão posterior substitua
// um anterior de mesmo comprimento.
for (std::size_t p = 0; p < objeto.padroes.size(); ++p) {
if (vivo[p] && objeto.padroes[p].finais[estados[p]] != 0) {
if (!houveCasamento || i > melhorFim) {
houveCasamento = true;
melhorFim = i;
melhorPadrao = p;
}
break;
}
}
}
// Casamento de comprimento zero não faz progresso e travaria o laço.
// Tratar como ausência de casamento é o que garante terminação.
if (!houveCasamento || melhorFim == posicao ||
melhorPadrao >= objeto.padroes.size()) {
++posicao;
continue;
}
const std::string casado =
entrada.substr(posicao, melhorFim - posicao);
++resultado.casamentos;
// Todas as regras daquele padrão disparam, na ordem de declaração.
for (const RegraObjeto& regra : objeto.regras) {
if (regra.indiceDoPadrao != melhorPadrao) {
continue;
}
if (!executarRegra(objeto, regra, casado, posicao, resultado)) {
return resultado;
}
}
posicao = melhorFim;
}
return resultado;
}
} // namespace peneiraTrês pontos do laço principal mereceram cuidado.
O casamento mais longo avança todos os autômatos em paralelo enquanto algum tiver transição, lembrando a última posição em que algum esteve em estado final. É a mesma regra do analisador léxico do módulo 7, e reusá-la é o que mantém a linguagem coerente consigo mesma.
O desempate por ordem de declaração — a decisão que só apareceu quando escrevi a especificação — sai praticamente de graça: o laço testa os padrões na ordem do vetor e a comparação estrita impede que um padrão posterior substitua um anterior de mesmo comprimento. Uma decisão que custou uma linha de código e teria custado dias de confusão se não estivesse especificada.
O casamento de comprimento zero é a armadilha do laço. Um padrão que aceita a cadeia vazia casaria sem consumir nada, e a posição de leitura nunca avançaria: o executor trava sem erro, sem mensagem, sem consumir processador de forma visível. Tratar comprimento zero como ausência de casamento é o que garante terminação, e está no código com comentário porque não é dedutível de olhar.
A ordem dos operandos nas comparações também é ponto de erro: o segundo operando foi empilhado por último e sai primeiro. Inverter aqui produz comparações trocadas que passam despercebidas em todos os casos simétricos — == e != continuam certos, e só > e < denunciam.
Onde é fácil errar aqui. Implementar o executor lendo o código do gerador em vez da especificação. É mais rápido e destrói o valor do teste.
Como verificar. Programas cuja saída se conhece por inspeção, o que é a tarefa seguinte.
1.6 Tarefa 5: Os três programas, compilados e executados
A atividade — demonstrar pelo menos três programas compilados e executados, com entrada e saída registradas, e o objeto salvo para inspeção.
Escolhi três programas que exercitam coisas diferentes, porque três programas parecidos demonstram uma coisa só. A saída literal de --executar:
faixa.pen — curto-circuito do 'and' e desvios para a frente
entrada: valores: 7 250 1200 480 -3 99 101
saida:
faixa = 250 (posicao 11)
faixa = 480 (posicao 20)
faixa = 101 (posicao 30)
casamentos: 7, instrucoes executadas: 68, bytes: 33
extremo.pen — curto-circuito do 'or', com desvio incondicional
entrada: leituras 5 -12 1500 800 -1 2000
saida:
extremo = -12 (posicao 11)
extremo = 1500 (posicao 15)
extremo = -1 (posicao 24)
extremo = 2000 (posicao 27)
casamentos: 6, instrucoes executadas: 66, bytes: 31
contatos.pen — dois padroes competindo, casamento mais longo
entrada: ana@teste.com 42 bruno@x.org 350
saida:
contato = ana@teste.com (posicao 0)
contato = bruno@x.org (posicao 17)
grande = 350 (posicao 29)
casamentos: 4, instrucoes executadas: 20, bytes: 32Conferi as três à mão, e a conferência é o que dá valor à demonstração. No primeiro, dos sete números da entrada, apenas 250, 480 e 101 estão estritamente entre 100 e 500 — os outros quatro falham por um dos dois lados, e três deles falham já na primeira comparação, com o segundo value nunca avaliado. É o curto-circuito funcionando, e ele é observável na contagem de instruções: 68 para sete casamentos dá menos de dez por casamento, quando o caminho completo tem doze.
No segundo, a condição é disjuntiva e os quatro extremos saem: dois negativos e dois acima de mil. Repare que -12 casa com o sinal, porque a expressão regular do padrão o inclui — se o padrão fosse só de dígitos, o executor casaria 12 e a condição daria falso, e o defeito pareceria da condição quando seria do padrão.
No terceiro, os dois padrões competem na mesma entrada e o casamento mais longo decide: ana@teste.com casa inteiro como endereço, e não como uma sequência de pedaços. E 42 casa e não emite, porque a regra tem condição; 350 casa e emite. As duas regras convivem sobre padrões diferentes.
O comando principal do compilador agora faz o ciclo completo, na forma prevista para a interface da ferramenta:
> peneira exemplos/contatos.pen < exemplos/entrada.txt
fases do compilador:
analise lexica pronta (modulo 7)
analise sintatica pronta (modulo 10)
analise semantica pronta (modulo 12)
geracao de codigo pronta (modulo 14)
execucao minima (modulo 14; completa no 15)
padroes compilados: 2, regras: 2, instrucoes: 11
objeto gravado em: exemplos/contatos.pen.obj.txt
execucao sobre 33 bytes de entrada:
contato ana@teste.com
contato bruno@x.org
grande 350
3 emissao(oes) em 4 casamento(s)O objeto é gravado em forma textual, e a decisão é didática e assumida: o objeto deste compilador é para ser lido na correção e na aula. Um formato binário seria menor e ilegível, e a economia não tem valor aqui.
Onde é fácil errar aqui. Escolher entradas em que a saída é a mesma com e sem a característica testada. Uma entrada só com números dentro da faixa não distingue curto-circuito de avaliação completa, e uma sem endereços não testa a competição entre padrões. Cada entrada foi montada com casos que passam e casos que falham por cada motivo possível.
Como verificar. A saída esperada tem de ser escrita antes de rodar. Conferir depois é confirmar o que o programa fez, não o que ele deveria fazer.
1.7 O reencontro com o primeiro bloco
Vale olhar a primeira seção do objeto gerado, porque é o fechamento conceitual da disciplina:
tabela de padroes (2):
[0] email: 6 estados, inicial 0, 1 final(is)
celulas: 1536, preenchidas: 182
casa somente numeros: nao
[1] numero: 5 estados, inicial 0, 2 final(is)
celulas: 1280, preenchidas: 52
casa somente numeros: simEsses dois autômatos não são estruturas auxiliares do compilador. São o produto: a maior parte do arquivo gerado, em bytes, é tabela de transição. E cada um deles percorreu o caminho inteiro do primeiro bloco — a notação foi analisada no módulo 4, virou autômato não determinístico por Thompson no mesmo módulo, foi determinizada por subconjuntos e minimizada por refinamento de partições no módulo 5.
A linha casa somente numeros também vem de longe: é o resultado da inclusão de linguagens decidida no módulo 12, que por sua vez usou a diferença de autômatos do módulo 6. Uma informação de sistema de tipos, gravada no programa objeto, calculada por operações sobre autômatos.
O compilador tem seis fases e todas cabem numa tabela:
| Fase | Módulo | Resultado neste programa |
|---|---|---|
| Análise léxica | 07 | símbolos reconhecidos por AFD |
| Análise sintática | 10 | 13 nós na árvore |
| Análise semântica | 12 | 2 padrões, 0 erros |
| Representação intermediária | 13 | três endereços com desvios |
| Geração de código | 14 | 11 instruções, 2816 células de transição |
| Execução | 14 | 3 emissões em 4 casamentos |
1.8 Verificação da entrega
| Item | Como conferir | Estado nesta referência |
|---|---|---|
| Gerador funcionando | Objeto produzido no formato do módulo 13 | 2 seções, 11 instruções |
| Curto-circuito tratado | and e or com desvios, não com operações |
Ambos, verificados na execução |
| Referências resolvidas | Destino intermediário virou endereço de objeto | 2 por regra, via mapa |
| Executor mínimo | Roda o objeto e produz o efeito observável | Três programas |
| Três programas demonstrados | Entrada e saída registradas | Três, conferidos à mão |
| Objeto salvo | Gravado para inspeção | Forma textual, ao lado do fonte |
| Três subproblemas | Enunciados e situados nesta máquina | Dois somem, e está explicado por quê |
| Pilha × registradores | Comparação com número, não com opinião | 2 cores contra pilha 2 |
| Alocação por coloração | Grafo de interferência colorido | Calculado; achou um defeito |
| Autômatos no objeto | Evidência da unidade da disciplina | 2816 células, a maior parte do arquivo |
| Compilação limpa | Modo estrito, aviso como erro | Sem nenhum diagnóstico |
| Regressão | Demonstrações dos módulos 2 a 13 | Verificadas |
O que quero deixar registrado sobre esta entrega tem duas partes.
A primeira é o que o módulo prova sobre o método de trabalho. A especificação escrita no módulo 13 permitiu que o executor fosse escrito contra ela em vez de contra o gerador, e é isso que torna um confronto entre os dois informativo. Grupos cuja especificação ficou incompleta descobrem aqui, e o custo é alto porque a descoberta vem junto com dois componentes a depurar ao mesmo tempo.
A segunda é sobre verificação. O único defeito real deste módulo — a interferência calculada com intervalo fechado — não foi encontrado por teste, por revisão nem pelo compilador. Foi encontrado porque a mesma grandeza tinha dois caminhos independentes de cálculo e os dois foram impressos lado a lado. Três registradores para uma expressão de profundidade dois é um número plausível, e número plausível não levanta suspeita. Só o segundo caminho levanta.