1 Ambientes de execução — 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 máquina que o seu grupo definir é a que a linguagem de vocês pede, e o formato que vocês escreverem é o contrato do sistema de vocês. O que se copia daqui é o método — decidir o mundo de execução antes de emitir para dentro dele, escrever o formato de modo que outra pessoa consiga preenchê-lo, e tratar as restrições como parte do contrato e não como detalhe do gerador.
1.1 Visão Geral
Este é o capítulo em que quase não se escreve código e quase tudo se decide. As três tarefas produzem um documento, um formato e uma máquina; nenhuma delas produz uma fase nova do compilador. É por essa proporção invertida — pouca escrita, muita consequência — que ele é o capítulo mais fácil de adiar, e é por isso que o preço de adiá-lo é sempre pago pelo capítulo seguinte, quando o gerador precisa emitir contra um contrato que ninguém escreveu.
A decisão que organiza tudo o que vem a seguir é uma só: a máquina existe antes do gerador que a alveja. Não se emite código contra um alvo que ainda não se decidiu como é, e a maneira de provar que o alvo está decidido é preencher um objeto à mão, sem gerador nenhum, e executá-lo. Foi o que fiz, e o arquivo resultante é o critério de conclusão deste módulo: ele roda hoje, produzindo sobre a entrada de referência exatamente as duas saídas esperadas, e nenhuma linha dele foi escrita por um programa.
Três números organizam o módulo, e cada seção adiante volta a um deles. A máquina reserva 3.317 bytes para executar a descrição de referência, distribuídos por quatro regiões cujos tamanhos são todos conhecidos antes da primeira ativação, exceto o da última. Dos 34 bytes reconhecidos na entrada, 25 foram copiados — e os copiados são exatamente os que atravessaram a fronteira de uma ativação. O objeto defeituoso de referência viola nove restrições, todas apontadas numa única passagem, e nenhuma delas quebraria o carregamento se não estivesse escrita. As três medidas dizem a mesma coisa por três ângulos: o que se decide aqui só é verificável porque foi escrito antes.
Uma observação sobre o que este capítulo deliberadamente não faz. Ele não gera código — o gerador é o capítulo seguinte. A tentação de antecipá-lo é forte, porque escrever o tradutor parece mais produtivo do que escrever o formato para o qual ele traduz, e o resultado dessa antecipação é sempre o mesmo: um formato que existe apenas na cabeça de quem escreveu o gerador, descoberto por quem escreve a máquina, e ajustado por ambos até que os dois programas concordem sem que nada esteja escrito em lugar nenhum. Foi essa forma de acordo tácito que a primeira tarefa existe para impedir.
1.2 Tarefa 1: Definir e justificar o modelo de execução
O que a tarefa pede
Definir o mundo em que o resultado produzido pelo sistema vai rodar: como o objeto emitido é executado, o que existe durante essa execução e o que se mantém entre um trecho de entrada e o seguinte. Justificar a escolha contra a alternativa descartada. É uma etapa com pouco código e muita consequência, e essa proporção é o que a torna fácil de adiar.
O objeto que este compilador produz não é um executável nativo. Ele é carregado e executado por uma máquina de pilha própria, que varre um texto de entrada e ativa uma ação a cada trecho reconhecido. A alternativa descartada foi emitir código de máquina diretamente, e a razão da escolha é o que a linguagem faz.
Uma descrição desta linguagem declara padrões, e o produto natural de reconhecer um padrão é um autômato. Com máquina própria, a tabela de transição é o código-alvo — o autômato não é uma estrutura auxiliar guardada dentro do programa objeto, ele é o programa objeto. Emitir código nativo obrigaria a traduzir a tabela em instruções de processador antes de ela poder rodar, e a propriedade mais incomum do artefato desapareceria justamente na travessia: o aluno veria um laço de comparações onde havia uma máquina de estados. O que se ganha em velocidade se perde em ver.
O preço da escolha fica declarado, e declará-lo é parte da justificativa. Cada símbolo da entrada custa uma consulta de tabela mais uma volta do laço da máquina, e não uma instrução de processador. Quem quiser código nativo percorre a mesma representação com um segundo emissor — e é precisamente aí que a representação intermediária deixa de ser uma afirmação de manual e vira um fato observável: o mesmo objeto, dois destinos. Enquanto houver um alvo só, “a representação separa a frente do fundo” é uma frase que o leitor aceita por confiança.
Duas perguntas da tarefa exigem resposta explícita, e as duas foram respondidas contra o hábito de deixá-las implícitas. O que existe durante a execução são quatro regiões de memória, e nada além delas — a seção adiante as detalha. O que se mantém de um trecho reconhecido para o seguinte são apenas as emissões já produzidas: não há estado do usuário entre ativações, nem contadores, nem variável global, nem lembrança do casamento anterior. Cada ativação começa igual à primeira.
Essa segunda decisão parece uma limitação e é uma escolha de projeto de linguagem, com consequência forte e fácil de enunciar: sem estado entre ativações, a saída de uma descrição depende só da entrada, e duas execuções sobre o mesmo texto são necessariamente iguais. Uma linguagem que permitisse “conte quantos endereços apareceram” seria mais expressiva e passaria a ter, no momento seguinte, todas as perguntas que estado carrega — quando o contador zera, o que acontece se duas regras o tocarem, o que significa executar a mesma descrição duas vezes. Recusei o estado porque a linguagem não precisa dele para o que ela serve, e não porque a máquina não o comportaria. É a diferença entre uma restrição decidida e uma restrição sofrida.
1.3 Tarefa 2: Fixar por extenso o formato do objeto produzido
O que a tarefa pede
Escrever por extenso o formato do que será produzido, com um exemplo preenchido à mão para uma descrição mínima. Este formato é o contrato entre as duas metades do sistema — a que analisa e a que executa — e é a única peça que as liga. Registrar também as restrições que o gerador terá de respeitar ao emitir contra esse formato, porque é a ausência delas, e não a ausência do formato, que costuma aparecer tarde demais.
O critério de conclusão é operacional e não admite autoavaliação: alguém que não participou da escrita precisa conseguir preencher um exemplo lendo apenas a especificação, sem perguntar nada ao autor.
13_objeto.h
// 13_objeto.h — O formato do objeto produzido, e o contrato que ele institui.
//
// ESTE ARQUIVO NÃO PRODUZ NADA. Ele descreve o que será produzido, e essa
// diferença é a razão de o capítulo ter pouco código e muita consequência. A
// geração de código, que vem depois, emite CONTRA este formato; a máquina, que
// vem ao lado, executa o que este formato descreve. As duas metades do sistema
// não se conhecem — a única coisa que as liga é o que está declarado aqui.
//
// POR QUE O FORMATO É TEXTO, E LEGÍVEL. Um formato binário seria menor e mais
// rápido de carregar, e ninguém conseguiria preencher um exemplo à mão. O
// critério de conclusão da especificação é operacional: alguém que não a
// escreveu precisa conseguir preencher um objeto lendo apenas o documento
// `docs/13_formato_objeto.md`. Um formato que só o próprio gerador consegue
// escrever não é um contrato — é um acoplamento com nome de contrato, e ele só
// cobra quando o gerador muda e a máquina continua lendo o que mudou.
//
// POR QUE OS ÍNDICES SÃO REDUNDANTES. Cada linha carrega o índice do item que
// declara, embora a posição na sequência já o determine. A redundância é
// verificada: o carregador recusa o arquivo quando o índice não casa com a
// posição. É o que transforma um erro de digitação de quem preenche à mão — a
// linha esquecida, a linha duplicada — em recusa imediata e localizada, em vez
// de um objeto silenciosamente deslocado que só produz saída errada muito
// adiante.
//
// AS RESTRIÇÕES SÃO PARTE DO FORMATO. Um formato que apenas descreve a forma
// dos dados deixa ao gerador a liberdade de emitir sequências que a máquina não
// consegue executar. As restrições declaradas em `Violacao` são a metade do
// contrato que costuma ficar por escrever, e são as que aparecem tarde: salto
// para fora do código, pilha desequilibrada, código sem retorno. Verificá-las no
// carregamento é caro uma vez e barato para sempre.
#ifndef PENEIRA_13_OBJETO_H
#define PENEIRA_13_OBJETO_H
#include <cstddef>
#include <string>
#include <vector>
#include "03_afd.h"
namespace peneira {
// O repertório da máquina alvo. É fixo, e é fixado AQUI: o gerador do capítulo
// seguinte escolhe como traduzir, mas não escolhe para o quê — a existência ou
// ausência de uma instrução é restrição da máquina, não do gerador.
//
// `Conjuncao` e `Disjuncao` permanecem no repertório de propósito, embora o
// salto condicional já permita compilar a mesma condição por curto-circuito. Ter
// as duas formas disponíveis é o que torna MENSURÁVEL uma decisão de tradução —
// quantas instruções cada forma emite, quantas avaliações cada uma executa — e a
// medida é assunto do capítulo seguinte.
enum class Opcode {
EmpilharConstante, // PUSH_CONST i — lê a área estática
EmpilharCasamento, // PUSH_MATCH — lê o quadro de ativação
Valor, // VALUE — converte o casamento no número que ele representa
CompararMenor, // CMP_LT
CompararMaior, // CMP_GT
CompararIgual, // CMP_EQ
CompararDiferente, // CMP_NE
CompararMenorIgual, // CMP_LE
CompararMaiorIgual, // CMP_GE
Conjuncao, // AND
Disjuncao, // OR
Emitir, // EMIT — desempilha valor e rótulo, produz saída
Saltar, // JMP alvo
SaltarSeFalso, // JMP_IF_FALSE alvo
Retornar, // RET — encerra a ativação
};
std::string mnemonico(Opcode opcode);
bool opcodeDeMnemonico(const std::string& texto, Opcode& destino);
bool temOperando(Opcode opcode);
// Quantos valores a instrução consome e quantos deixa. É o que permite decidir,
// sem executar, se a pilha fica equilibrada — e qual profundidade a máquina
// precisa reservar antes de começar.
void efeitoNaPilha(Opcode opcode, std::size_t& consome, std::size_t& produz);
enum class EspecieDeConstante {
Numero,
Texto,
};
// A área estática do programa objeto: o que existe antes de a execução começar e
// não muda enquanto ela dura. Um literal do texto-fonte vira uma entrada aqui, e
// a instrução carrega o índice — nunca o valor. É a separação entre código e
// dado, e ela não é estética: o código passa a ser do mesmo tamanho
// independentemente do tamanho do literal, e duas ocorrências do mesmo literal
// passam a poder compartilhar uma entrada.
struct Constante {
EspecieDeConstante especie = EspecieDeConstante::Texto;
double numero = 0.0;
std::string texto;
};
struct Instrucao {
Opcode opcode = Opcode::Retornar;
std::size_t operando = 0; // índice de constante ou alvo de salto; 0 quando não há
};
// Um autômato determinístico como ele viaja no objeto: tabela de transição
// declarada por faixas de símbolos, e não célula a célula. A escolha é pelo
// humano que preenche à mão — `trans 0 "0123456789" 1` cabe numa linha e dez
// linhas idênticas não caberiam numa cabeça. O carregador expande.
struct AutomatoObjeto {
struct Transicao {
std::size_t origem = 0;
std::string simbolos;
std::size_t destino = 0;
};
std::string nome;
std::string alfabeto;
std::size_t estados = 0;
std::size_t inicial = 0;
std::vector<std::size_t> aceitacao;
std::vector<Transicao> transicoes;
};
// Uma regra: o autômato que a dispara, o nome que a ligação recebe e o código
// que roda quando o casamento acontece. `profundidade` é declarada e conferida —
// a máquina reserva a pilha antes de executar, e por isso precisa saber de
// quanto ela precisa sem simular.
struct RegraObjeto {
std::size_t automato = 0;
std::string ligacao;
std::size_t profundidade = 0;
std::vector<Instrucao> codigo;
};
struct ProgramaObjeto {
std::size_t versao = 1;
std::vector<Constante> constantes;
std::vector<AutomatoObjeto> automatos;
std::vector<RegraObjeto> regras;
};
// As restrições que o gerador tem de respeitar. Cada uma existe porque a máquina
// não tem como se defender dela em tempo de execução sem pagar o custo a cada
// instrução executada — verificar uma vez no carregamento é o que permite que o
// laço de execução não pergunte nada.
enum class Violacao {
VersaoDesconhecida,
SemAutomatos,
SemRegras,
AutomatoInexistente,
EstadoInexistente,
SimboloForaDoAlfabeto,
SemEstadoDeAceitacao,
ConstanteInexistente,
RotuloDeEmissaoNaoTextual,
AlvoDeSaltoForaDoCodigo,
SaltoParaTras,
CodigoSemRetornoFinal,
PilhaInsuficiente,
PilhaDesequilibradaNoRetorno,
ProfundidadeIncoerenteNoDestino,
ProfundidadeDeclaradaErrada,
};
std::string nomeDaViolacao(Violacao violacao);
struct Reprovacao {
Violacao violacao = Violacao::SemRegras;
bool sobreAutomato = false; // quando verdadeiro, `indice` é o do autômato, não o da regra
std::size_t indice = 0;
std::size_t posicao = 0; // índice da instrução, quando a violação é de código
std::string detalhe; // o que se esperava e o que se encontrou
};
struct ErroDeLeitura {
std::size_t linha = 0;
std::string mensagem;
};
// Lê o formato textual. Devolve falso quando o arquivo não é um objeto válido —
// e nesse caso `erros` diz em que linha e por quê, porque quem preenche à mão
// erra e precisa saber onde.
bool lerObjeto(const std::string& texto, ProgramaObjeto& destino, std::vector<ErroDeLeitura>& erros);
// Escreve o formato textual. A ida e a volta têm de coincidir byte a byte: é o
// teste mais barato de que o formato está de fato especificado, e não apenas
// implementado numa direção.
std::string escreverObjeto(const ProgramaObjeto& programa);
// As restrições, conferidas. Lista vazia significa objeto executável.
std::vector<Reprovacao> validar(const ProgramaObjeto& programa);
// A profundidade de pilha que o código de uma regra exige. Devolve `false`
// quando o código não é analisável — salto para trás, alvo fora do código,
// consumo maior do que a pilha corrente —, e é a mesma travessia que a validação
// usa. Existe separada porque o gerador do capítulo seguinte precisa dela para
// PREENCHER o campo que a validação depois confere.
bool profundidadeExigida(const std::vector<Instrucao>& codigo, std::size_t& destino);
// Reconstrói a máquina de estados a partir da tabela declarada, reusando o mesmo
// autômato determinístico dos primeiros capítulos. Não há um segundo AFD no
// sistema: o objeto transporta a tabela, e a tabela volta a ser o mesmo tipo.
Afd montarAfd(const AutomatoObjeto& automato);
std::string formatarReprovacoes(const std::vector<Reprovacao>& reprovacoes);
std::string formatarCodigo(const RegraObjeto& regra);
} // namespace peneira
#endif // PENEIRA_13_OBJETO_H13_objeto.cpp
// 13_objeto.cpp — leitura, escrita e verificação do formato do objeto.
#include "13_objeto.h"
#include <algorithm>
#include <cstdlib>
#include <iomanip>
#include <sstream>
namespace peneira {
namespace {
struct Linha {
std::size_t numero = 0;
std::vector<std::string> campos;
};
// Separa a linha em campos, respeitando cadeias entre aspas. O comentário começa
// em `#` e vale até o fim da linha, mas não dentro de aspas — um rótulo pode
// conter o caractere, e uma varredura ingênua o truncaria.
bool separar(const std::string& linha, std::vector<std::string>& campos, std::string& erro) {
campos.clear();
std::size_t i = 0;
while (i < linha.size()) {
const char atual = linha[i];
if (atual == ' ' || atual == '\t' || atual == '\r') {
++i;
continue;
}
if (atual == '#') {
break;
}
if (atual == '"') {
std::string valor;
++i;
bool fechou = false;
while (i < linha.size()) {
const char c = linha[i];
if (c == '\\' && i + 1 < linha.size()) {
valor.push_back(linha[i + 1]);
i += 2;
continue;
}
if (c == '"') {
fechou = true;
++i;
break;
}
valor.push_back(c);
++i;
}
if (!fechou) {
erro = "cadeia entre aspas nao foi fechada";
return false;
}
campos.push_back(valor);
continue;
}
std::string valor;
while (i < linha.size() && linha[i] != ' ' && linha[i] != '\t' && linha[i] != '\r' &&
linha[i] != '#') {
valor.push_back(linha[i]);
++i;
}
campos.push_back(valor);
}
return true;
}
bool inteiroDe(const std::string& campo, std::size_t& destino) {
if (campo.empty()) {
return false;
}
for (const char c : campo) {
if (c < '0' || c > '9') {
return false;
}
}
destino = static_cast<std::size_t>(std::strtoull(campo.c_str(), nullptr, 10));
return true;
}
bool numeroDe(const std::string& campo, double& destino) {
if (campo.empty()) {
return false;
}
char* fim = nullptr;
destino = std::strtod(campo.c_str(), &fim);
return fim != nullptr && *fim == '\0';
}
// A forma canônica de um número no arquivo. A ida e a volta precisam coincidir
// byte a byte, então a precisão sobe até que o valor lido de volta seja o mesmo.
std::string formatarNumero(double valor) {
for (int precisao = 15; precisao <= 17; ++precisao) {
std::ostringstream fluxo;
fluxo << std::defaultfloat << std::setprecision(precisao) << valor;
const std::string texto = fluxo.str();
double devolta = 0.0;
if (numeroDe(texto, devolta) && devolta == valor) {
return texto;
}
}
std::ostringstream fluxo;
fluxo << std::setprecision(17) << valor;
return fluxo.str();
}
std::string entreAspas(const std::string& texto) {
std::string saida;
saida.push_back('"');
for (const char c : texto) {
if (c == '"' || c == '\\') {
saida.push_back('\\');
}
saida.push_back(c);
}
saida.push_back('"');
return saida;
}
void reprovar(std::vector<Reprovacao>& saida, Violacao violacao, std::size_t indice,
std::size_t posicao, std::string detalhe, bool sobreAutomato = false) {
Reprovacao reprovacao;
reprovacao.violacao = violacao;
reprovacao.sobreAutomato = sobreAutomato;
reprovacao.indice = indice;
reprovacao.posicao = posicao;
reprovacao.detalhe = std::move(detalhe);
saida.push_back(reprovacao);
}
constexpr std::size_t kSemProfundidade = static_cast<std::size_t>(-1);
} // namespace
std::string mnemonico(Opcode opcode) {
switch (opcode) {
case Opcode::EmpilharConstante: return "PUSH_CONST";
case Opcode::EmpilharCasamento: return "PUSH_MATCH";
case Opcode::Valor: return "VALUE";
case Opcode::CompararMenor: return "CMP_LT";
case Opcode::CompararMaior: return "CMP_GT";
case Opcode::CompararIgual: return "CMP_EQ";
case Opcode::CompararDiferente: return "CMP_NE";
case Opcode::CompararMenorIgual: return "CMP_LE";
case Opcode::CompararMaiorIgual: return "CMP_GE";
case Opcode::Conjuncao: return "AND";
case Opcode::Disjuncao: return "OR";
case Opcode::Emitir: return "EMIT";
case Opcode::Saltar: return "JMP";
case Opcode::SaltarSeFalso: return "JMP_IF_FALSE";
case Opcode::Retornar: return "RET";
}
return "?";
}
bool opcodeDeMnemonico(const std::string& texto, Opcode& destino) {
static const Opcode todos[] = {
Opcode::EmpilharConstante, Opcode::EmpilharCasamento, Opcode::Valor,
Opcode::CompararMenor, Opcode::CompararMaior, Opcode::CompararIgual,
Opcode::CompararDiferente, Opcode::CompararMenorIgual, Opcode::CompararMaiorIgual,
Opcode::Conjuncao, Opcode::Disjuncao, Opcode::Emitir,
Opcode::Saltar, Opcode::SaltarSeFalso, Opcode::Retornar,
};
for (const Opcode candidato : todos) {
if (mnemonico(candidato) == texto) {
destino = candidato;
return true;
}
}
return false;
}
bool temOperando(Opcode opcode) {
return opcode == Opcode::EmpilharConstante || opcode == Opcode::Saltar ||
opcode == Opcode::SaltarSeFalso;
}
void efeitoNaPilha(Opcode opcode, std::size_t& consome, std::size_t& produz) {
switch (opcode) {
case Opcode::EmpilharConstante:
case Opcode::EmpilharCasamento:
consome = 0;
produz = 1;
return;
case Opcode::Valor:
consome = 1;
produz = 1;
return;
case Opcode::CompararMenor:
case Opcode::CompararMaior:
case Opcode::CompararIgual:
case Opcode::CompararDiferente:
case Opcode::CompararMenorIgual:
case Opcode::CompararMaiorIgual:
case Opcode::Conjuncao:
case Opcode::Disjuncao:
consome = 2;
produz = 1;
return;
case Opcode::Emitir:
consome = 2;
produz = 0;
return;
case Opcode::SaltarSeFalso:
consome = 1;
produz = 0;
return;
case Opcode::Saltar:
case Opcode::Retornar:
consome = 0;
produz = 0;
return;
}
consome = 0;
produz = 0;
}
std::string nomeDaViolacao(Violacao violacao) {
switch (violacao) {
case Violacao::VersaoDesconhecida: return "versao desconhecida";
case Violacao::SemAutomatos: return "objeto sem automatos";
case Violacao::SemRegras: return "objeto sem regras";
case Violacao::AutomatoInexistente: return "automato inexistente";
case Violacao::EstadoInexistente: return "estado inexistente";
case Violacao::SimboloForaDoAlfabeto: return "simbolo fora do alfabeto";
case Violacao::SemEstadoDeAceitacao: return "automato sem estado de aceitacao";
case Violacao::ConstanteInexistente: return "constante inexistente";
case Violacao::RotuloDeEmissaoNaoTextual: return "rotulo de emissao nao textual";
case Violacao::AlvoDeSaltoForaDoCodigo: return "alvo de salto fora do codigo";
case Violacao::SaltoParaTras: return "salto para tras";
case Violacao::CodigoSemRetornoFinal: return "codigo sem retorno final";
case Violacao::PilhaInsuficiente: return "pilha insuficiente";
case Violacao::PilhaDesequilibradaNoRetorno: return "pilha desequilibrada no retorno";
case Violacao::ProfundidadeIncoerenteNoDestino: return "profundidade incoerente no destino";
case Violacao::ProfundidadeDeclaradaErrada: return "profundidade declarada errada";
}
return "?";
}
bool lerObjeto(const std::string& texto, ProgramaObjeto& destino,
std::vector<ErroDeLeitura>& erros) {
destino = ProgramaObjeto{};
erros.clear();
std::vector<Linha> linhas;
{
std::istringstream fluxo{texto};
std::string bruta;
std::size_t numero = 0;
while (std::getline(fluxo, bruta)) {
++numero;
Linha linha;
linha.numero = numero;
std::string erro;
if (!separar(bruta, linha.campos, erro)) {
erros.push_back(ErroDeLeitura{numero, erro});
return false;
}
if (!linha.campos.empty()) {
linhas.push_back(linha);
}
}
}
if (linhas.empty()) {
erros.push_back(ErroDeLeitura{0, "arquivo vazio"});
return false;
}
const auto falhar = [&erros](std::size_t numero, const std::string& mensagem) {
erros.push_back(ErroDeLeitura{numero, mensagem});
return false;
};
const Linha& cabecalho = linhas.front();
if (cabecalho.campos.size() != 2 || cabecalho.campos[0] != "peneira-objeto") {
return falhar(cabecalho.numero, "a primeira linha util deve ser: peneira-objeto <versao>");
}
if (!inteiroDe(cabecalho.campos[1], destino.versao)) {
return falhar(cabecalho.numero, "versao nao numerica");
}
for (std::size_t i = 1; i < linhas.size(); ++i) {
const Linha& linha = linhas[i];
const std::vector<std::string>& c = linha.campos;
const std::string& chave = c[0];
if (chave == "constante") {
if (c.size() != 4) {
return falhar(linha.numero, "uso: constante <i> <texto|numero> <valor>");
}
std::size_t indice = 0;
if (!inteiroDe(c[1], indice) || indice != destino.constantes.size()) {
return falhar(linha.numero, "o indice da constante tem de ser o proximo da sequencia");
}
Constante constante;
if (c[2] == "texto") {
constante.especie = EspecieDeConstante::Texto;
constante.texto = c[3];
} else if (c[2] == "numero") {
constante.especie = EspecieDeConstante::Numero;
if (!numeroDe(c[3], constante.numero)) {
return falhar(linha.numero, "valor numerico invalido");
}
} else {
return falhar(linha.numero, "especie de constante desconhecida: " + c[2]);
}
destino.constantes.push_back(constante);
continue;
}
if (chave == "automato") {
if (c.size() != 10 || c[2] != "nome" || c[4] != "estados" || c[6] != "inicial" ||
c[8] != "alfabeto") {
return falhar(linha.numero,
"uso: automato <i> nome \"<n>\" estados <q> inicial <e> alfabeto \"<a>\"");
}
std::size_t indice = 0;
if (!inteiroDe(c[1], indice) || indice != destino.automatos.size()) {
return falhar(linha.numero, "o indice do automato tem de ser o proximo da sequencia");
}
AutomatoObjeto automato;
automato.nome = c[3];
if (!inteiroDe(c[5], automato.estados) || !inteiroDe(c[7], automato.inicial)) {
return falhar(linha.numero, "quantidade de estados ou estado inicial nao numerico");
}
automato.alfabeto = c[9];
destino.automatos.push_back(automato);
continue;
}
if (chave == "aceita") {
if (c.size() < 3) {
return falhar(linha.numero, "uso: aceita <automato> <estado> [<estado> ...]");
}
std::size_t indice = 0;
if (!inteiroDe(c[1], indice) || indice >= destino.automatos.size()) {
return falhar(linha.numero, "aceita refere automato ainda nao declarado");
}
for (std::size_t k = 2; k < c.size(); ++k) {
std::size_t estado = 0;
if (!inteiroDe(c[k], estado)) {
return falhar(linha.numero, "estado nao numerico");
}
destino.automatos[indice].aceitacao.push_back(estado);
}
continue;
}
if (chave == "trans") {
if (c.size() != 5) {
return falhar(linha.numero, "uso: trans <automato> <origem> \"<simbolos>\" <destino>");
}
std::size_t indice = 0;
if (!inteiroDe(c[1], indice) || indice >= destino.automatos.size()) {
return falhar(linha.numero, "trans refere automato ainda nao declarado");
}
AutomatoObjeto::Transicao transicao;
if (!inteiroDe(c[2], transicao.origem) || !inteiroDe(c[4], transicao.destino)) {
return falhar(linha.numero, "origem ou destino nao numerico");
}
transicao.simbolos = c[3];
if (transicao.simbolos.empty()) {
return falhar(linha.numero, "conjunto de simbolos vazio");
}
destino.automatos[indice].transicoes.push_back(transicao);
continue;
}
if (chave == "regra") {
if (c.size() != 8 || c[2] != "automato" || c[4] != "ligacao" || c[6] != "pilha") {
return falhar(linha.numero,
"uso: regra <i> automato <a> ligacao \"<n>\" pilha <profundidade>");
}
std::size_t indice = 0;
if (!inteiroDe(c[1], indice) || indice != destino.regras.size()) {
return falhar(linha.numero, "o indice da regra tem de ser o proximo da sequencia");
}
RegraObjeto regra;
if (!inteiroDe(c[3], regra.automato) || !inteiroDe(c[7], regra.profundidade)) {
return falhar(linha.numero, "automato ou profundidade nao numerico");
}
regra.ligacao = c[5];
destino.regras.push_back(regra);
continue;
}
if (chave == "codigo") {
if (c.size() != 4 && c.size() != 5) {
return falhar(linha.numero, "uso: codigo <regra> <posicao> <MNEMONICO> [operando]");
}
std::size_t indice = 0;
if (!inteiroDe(c[1], indice) || indice >= destino.regras.size()) {
return falhar(linha.numero, "codigo refere regra ainda nao declarada");
}
RegraObjeto& regra = destino.regras[indice];
std::size_t posicao = 0;
if (!inteiroDe(c[2], posicao) || posicao != regra.codigo.size()) {
return falhar(linha.numero, "a posicao da instrucao tem de ser a proxima da sequencia");
}
Instrucao instrucao;
if (!opcodeDeMnemonico(c[3], instrucao.opcode)) {
return falhar(linha.numero, "instrucao desconhecida: " + c[3]);
}
const bool esperaOperando = temOperando(instrucao.opcode);
if (esperaOperando && c.size() != 5) {
return falhar(linha.numero, c[3] + " exige um operando");
}
if (!esperaOperando && c.size() != 4) {
return falhar(linha.numero, c[3] + " nao aceita operando");
}
if (esperaOperando && !inteiroDe(c[4], instrucao.operando)) {
return falhar(linha.numero, "operando nao numerico");
}
regra.codigo.push_back(instrucao);
continue;
}
return falhar(linha.numero, "linha desconhecida: " + chave);
}
return true;
}
std::string escreverObjeto(const ProgramaObjeto& programa) {
std::ostringstream saida;
saida << "peneira-objeto " << programa.versao << "\n";
saida << "\n";
for (std::size_t i = 0; i < programa.constantes.size(); ++i) {
const Constante& constante = programa.constantes[i];
saida << "constante " << i << ' ';
if (constante.especie == EspecieDeConstante::Texto) {
saida << "texto " << entreAspas(constante.texto);
} else {
saida << "numero " << formatarNumero(constante.numero);
}
saida << "\n";
}
for (std::size_t i = 0; i < programa.automatos.size(); ++i) {
const AutomatoObjeto& automato = programa.automatos[i];
saida << "\n";
saida << "automato " << i << " nome " << entreAspas(automato.nome) << " estados "
<< automato.estados << " inicial " << automato.inicial << " alfabeto "
<< entreAspas(automato.alfabeto) << "\n";
if (!automato.aceitacao.empty()) {
saida << "aceita " << i;
for (const std::size_t estado : automato.aceitacao) {
saida << ' ' << estado;
}
saida << "\n";
}
for (const AutomatoObjeto::Transicao& transicao : automato.transicoes) {
saida << "trans " << i << ' ' << transicao.origem << ' '
<< entreAspas(transicao.simbolos) << ' ' << transicao.destino << "\n";
}
}
for (std::size_t i = 0; i < programa.regras.size(); ++i) {
const RegraObjeto& regra = programa.regras[i];
saida << "\n";
saida << "regra " << i << " automato " << regra.automato << " ligacao "
<< entreAspas(regra.ligacao) << " pilha " << regra.profundidade << "\n";
for (std::size_t k = 0; k < regra.codigo.size(); ++k) {
const Instrucao& instrucao = regra.codigo[k];
saida << "codigo " << i << ' ' << k << ' ' << mnemonico(instrucao.opcode);
if (temOperando(instrucao.opcode)) {
saida << ' ' << instrucao.operando;
}
saida << "\n";
}
}
return saida.str();
}
bool profundidadeExigida(const std::vector<Instrucao>& codigo, std::size_t& destino) {
destino = 0;
if (codigo.empty()) {
return false;
}
// Uma única passada basta porque o salto é sempre para a frente: quando se
// chega a uma instrução, todas as que podiam saltar para ela já foram vistas.
// Com salto para trás, isto viraria um ponto fixo — e é essa, e não a
// dificuldade de implementar, a razão pela qual a restrição existe.
std::vector<std::size_t> profundidade(codigo.size(), kSemProfundidade);
profundidade[0] = 0;
std::size_t maxima = 0;
for (std::size_t i = 0; i < codigo.size(); ++i) {
if (profundidade[i] == kSemProfundidade) {
return false; // instrução inalcançável
}
std::size_t consome = 0;
std::size_t produz = 0;
efeitoNaPilha(codigo[i].opcode, consome, produz);
if (profundidade[i] < consome) {
return false;
}
const std::size_t depois = profundidade[i] - consome + produz;
maxima = std::max(maxima, std::max(profundidade[i], depois));
if (codigo[i].opcode == Opcode::Retornar) {
if (depois != 0) {
return false;
}
continue;
}
if (codigo[i].opcode == Opcode::Saltar || codigo[i].opcode == Opcode::SaltarSeFalso) {
const std::size_t alvo = codigo[i].operando;
if (alvo <= i || alvo >= codigo.size()) {
return false;
}
if (profundidade[alvo] != kSemProfundidade && profundidade[alvo] != depois) {
return false;
}
profundidade[alvo] = depois;
}
if (codigo[i].opcode == Opcode::Saltar) {
continue; // não cai na seguinte
}
if (i + 1 < codigo.size()) {
if (profundidade[i + 1] != kSemProfundidade && profundidade[i + 1] != depois) {
return false;
}
profundidade[i + 1] = depois;
}
}
destino = maxima;
return true;
}
std::vector<Reprovacao> validar(const ProgramaObjeto& programa) {
std::vector<Reprovacao> saida;
if (programa.versao != 1) {
reprovar(saida, Violacao::VersaoDesconhecida, 0, 0,
"esta maquina executa a versao 1 do formato");
return saida;
}
if (programa.automatos.empty()) {
reprovar(saida, Violacao::SemAutomatos, 0, 0, "nenhum automato declarado");
}
if (programa.regras.empty()) {
reprovar(saida, Violacao::SemRegras, 0, 0, "nenhuma regra declarada");
}
for (std::size_t a = 0; a < programa.automatos.size(); ++a) {
const AutomatoObjeto& automato = programa.automatos[a];
if (automato.estados == 0 || automato.inicial >= automato.estados) {
reprovar(saida, Violacao::EstadoInexistente, a, 0,
"estado inicial " + std::to_string(automato.inicial) + " fora de 0.." +
std::to_string(automato.estados), true);
}
if (automato.aceitacao.empty()) {
reprovar(saida, Violacao::SemEstadoDeAceitacao, a, 0,
"o automato \"" + automato.nome + "\" nunca aceita, logo nunca dispara", true);
}
for (const std::size_t estado : automato.aceitacao) {
if (estado >= automato.estados) {
reprovar(saida, Violacao::EstadoInexistente, a, 0,
"estado de aceitacao " + std::to_string(estado) + " inexistente", true);
}
}
for (const AutomatoObjeto::Transicao& transicao : automato.transicoes) {
if (transicao.origem >= automato.estados || transicao.destino >= automato.estados) {
reprovar(saida, Violacao::EstadoInexistente, a, 0,
"transicao entre estados inexistentes", true);
}
for (const char simbolo : transicao.simbolos) {
if (automato.alfabeto.find(simbolo) == std::string::npos) {
reprovar(saida, Violacao::SimboloForaDoAlfabeto, a, 0,
std::string{"o simbolo '"} + simbolo +
"' nao esta no alfabeto declarado", true);
}
}
}
}
for (std::size_t r = 0; r < programa.regras.size(); ++r) {
const RegraObjeto& regra = programa.regras[r];
if (regra.automato >= programa.automatos.size()) {
reprovar(saida, Violacao::AutomatoInexistente, r, 0,
"a regra dispara com o automato " + std::to_string(regra.automato) +
", que nao existe");
}
if (regra.codigo.empty() || regra.codigo.back().opcode != Opcode::Retornar) {
reprovar(saida, Violacao::CodigoSemRetornoFinal, r, regra.codigo.size(),
"toda ativacao termina, e quem a termina e RET");
}
for (std::size_t i = 0; i < regra.codigo.size(); ++i) {
const Instrucao& instrucao = regra.codigo[i];
if (instrucao.opcode == Opcode::EmpilharConstante &&
instrucao.operando >= programa.constantes.size()) {
reprovar(saida, Violacao::ConstanteInexistente, r, i,
"constante " + std::to_string(instrucao.operando) + " inexistente");
}
if (instrucao.opcode == Opcode::Saltar || instrucao.opcode == Opcode::SaltarSeFalso) {
if (instrucao.operando >= regra.codigo.size()) {
reprovar(saida, Violacao::AlvoDeSaltoForaDoCodigo, r, i,
"alvo " + std::to_string(instrucao.operando) + " fora do codigo");
} else if (instrucao.operando <= i) {
reprovar(saida, Violacao::SaltoParaTras, r, i,
"esta linguagem nao tem repeticao, e um salto para tras aqui e um laco "
"que a varredura nao sabe interromper");
}
}
}
// O rótulo da emissão é textual, e a verificação é estática porque a
// sequência que alimenta o EMIT é conhecida: a constante empilhada duas
// instruções antes, quando ela é uma constante.
for (std::size_t i = 0; i < regra.codigo.size(); ++i) {
if (regra.codigo[i].opcode != Opcode::Emitir || i < 2) {
continue;
}
const Instrucao& candidato = regra.codigo[i - 2];
if (candidato.opcode != Opcode::EmpilharConstante) {
continue;
}
if (candidato.operando < programa.constantes.size() &&
programa.constantes[candidato.operando].especie != EspecieDeConstante::Texto) {
reprovar(saida, Violacao::RotuloDeEmissaoNaoTextual, r, i,
"o rotulo de uma emissao e texto, e a constante " +
std::to_string(candidato.operando) + " e numerica");
}
}
std::size_t exigida = 0;
if (!profundidadeExigida(regra.codigo, exigida)) {
// A travessia recusou. Refaz-se o passo a passo apenas para dizer
// POR QUE — uma recusa sem causa nomeada obriga quem preencheu o
// objeto a adivinhar, que é exatamente o que este formato existe
// para evitar.
std::vector<std::size_t> profundidade(regra.codigo.size(), kSemProfundidade);
if (!regra.codigo.empty()) {
profundidade[0] = 0;
}
for (std::size_t i = 0; i < regra.codigo.size(); ++i) {
if (profundidade[i] == kSemProfundidade) {
break;
}
std::size_t consome = 0;
std::size_t produz = 0;
efeitoNaPilha(regra.codigo[i].opcode, consome, produz);
if (profundidade[i] < consome) {
reprovar(saida, Violacao::PilhaInsuficiente, r, i,
mnemonico(regra.codigo[i].opcode) + " consome " +
std::to_string(consome) + " valores e a pilha tem " +
std::to_string(profundidade[i]));
break;
}
const std::size_t depois = profundidade[i] - consome + produz;
if (regra.codigo[i].opcode == Opcode::Retornar && depois != 0) {
reprovar(saida, Violacao::PilhaDesequilibradaNoRetorno, r, i,
"sobram " + std::to_string(depois) + " valores na pilha no retorno");
break;
}
const bool salta = regra.codigo[i].opcode == Opcode::Saltar ||
regra.codigo[i].opcode == Opcode::SaltarSeFalso;
if (salta) {
const std::size_t alvo = regra.codigo[i].operando;
if (alvo <= i || alvo >= regra.codigo.size()) {
break; // já reprovado acima
}
if (profundidade[alvo] != kSemProfundidade && profundidade[alvo] != depois) {
reprovar(saida, Violacao::ProfundidadeIncoerenteNoDestino, r, i,
"os dois caminhos chegam a " + std::to_string(alvo) +
" com pilhas de tamanhos diferentes");
break;
}
profundidade[alvo] = depois;
}
if (regra.codigo[i].opcode == Opcode::Saltar) {
continue;
}
if (i + 1 < regra.codigo.size()) {
if (profundidade[i + 1] != kSemProfundidade && profundidade[i + 1] != depois) {
reprovar(saida, Violacao::ProfundidadeIncoerenteNoDestino, r, i,
"os dois caminhos chegam a " + std::to_string(i + 1) +
" com pilhas de tamanhos diferentes");
break;
}
profundidade[i + 1] = depois;
}
}
} else if (exigida != regra.profundidade) {
reprovar(saida, Violacao::ProfundidadeDeclaradaErrada, r, 0,
"declarada " + std::to_string(regra.profundidade) + ", exigida " +
std::to_string(exigida));
}
}
return saida;
}
Afd montarAfd(const AutomatoObjeto& automato) {
Afd afd{automato.alfabeto, automato.estados, automato.inicial};
for (const AutomatoObjeto::Transicao& transicao : automato.transicoes) {
afd.definirTransicoes(transicao.origem, transicao.simbolos, transicao.destino);
}
for (const std::size_t estado : automato.aceitacao) {
afd.marcarAceitacao(estado);
}
afd.nomearEstado(automato.inicial, automato.nome);
return afd;
}
std::string formatarReprovacoes(const std::vector<Reprovacao>& reprovacoes) {
std::ostringstream saida;
for (const Reprovacao& reprovacao : reprovacoes) {
saida << "objeto recusado: " << nomeDaViolacao(reprovacao.violacao) << ' ';
if (reprovacao.sobreAutomato) {
saida << "(automato " << reprovacao.indice << ")";
} else {
saida << "(regra " << reprovacao.indice << ", instrucao " << reprovacao.posicao << ")";
}
saida << "\n " << reprovacao.detalhe << "\n";
}
return saida.str();
}
std::string formatarCodigo(const RegraObjeto& regra) {
std::ostringstream saida;
for (std::size_t i = 0; i < regra.codigo.size(); ++i) {
const Instrucao& instrucao = regra.codigo[i];
saida << " " << std::setw(3) << i << ": " << mnemonico(instrucao.opcode);
if (temOperando(instrucao.opcode)) {
saida << ' ' << instrucao.operando;
}
saida << "\n";
}
return saida.str();
}
} // namespace peneiraA primeira decisão foi que o formato é texto legível, e ela custou tamanho e velocidade de carregamento. Um formato binário seria menor, carregaria mais rápido e — este é o ponto — ninguém conseguiria preencher um exemplo à mão. O critério de conclusão da tarefa é operacional, e um formato que só o próprio gerador consegue escrever é um acoplamento com nome de contrato, que só cobra no dia em que o gerador muda e a máquina continua lendo a versão antiga sem reclamar.
A segunda decisão é a que mais surpreende quem lê o formato pela primeira vez: cada linha carrega o índice do item que declara, e o índice é redundante. A posição na sequência já determina o índice; declará-lo de novo parece cerimônia. A redundância existe porque é verificada — o carregador recusa o arquivo quando o índice não casa com a posição —, e o que ela transforma é o erro típico de quem preenche à mão: a linha esquecida, a linha duplicada, o bloco copiado e não renumerado. Sem a conferência, esses três erros produzem um objeto silenciosamente deslocado, que carrega, roda e emite a coisa errada. Com ela, produzem uma recusa que aponta a linha.
A terceira decisão é sobre a tabela de transição, e ela também foi tomada pelo humano que preenche. Uma transição é declarada por conjunto de símbolos, não célula a célula: uma linha diz que dez dígitos levam do estado 0 ao 2, e o carregador expande para a tabela densa. Dez linhas idênticas cabem num arquivo e não cabem numa cabeça, e a primeira delas que fosse escrita errada seria invisível no meio das outras nove.
13_objeto.pobj
# 13_objeto.pobj — o objeto da descricao de referencia, PREENCHIDO A MAO.
#
# Este arquivo e o criterio de conclusao da especificacao do formato, e nao um
# artefato de conveniencia: ele foi escrito lendo `docs/13_formato_objeto.md`, sem
# gerador nenhum, porque uma especificacao que so o proprio autor consegue
# preencher equivale a especificacao inexistente. O gerador de codigo do capitulo
# seguinte tera de produzir exatamente isto a partir de `exemplos/exemplo01.pen`.
#
# Sobre `exemplos/entrada01.txt`, a execucao deve produzir:
# contato ana.silva@exemplo.com
# grande 1500
#
# Os dois casos que NAO produzem saida sao a parte que prova que a condicao esta
# sendo avaliada: 42 casa o pattern e falha por magnitude; -240.75 casa o pattern
# e falha por sinal.
peneira-objeto 1
# --- area estatica: as constantes -------------------------------------------
constante 0 texto "contato"
constante 1 texto "grande"
constante 2 numero 100
# --- automato 0: o pattern `email` ------------------------------------------
# Regex de origem: [a-z0-9._]+@[a-z]+\.[a-z]+
# Estados: 0 inicio | 1 parte local | 2 apos o arroba | 3 dominio | 4 apos o ponto
# 5 sufixo (aceitacao)
automato 0 nome "email" estados 6 inicial 0 alfabeto "abcdefghijklmnopqrstuvwxyz0123456789._@"
aceita 0 5
trans 0 0 "abcdefghijklmnopqrstuvwxyz0123456789._" 1
trans 0 1 "abcdefghijklmnopqrstuvwxyz0123456789._" 1
trans 0 1 "@" 2
trans 0 2 "abcdefghijklmnopqrstuvwxyz" 3
trans 0 3 "abcdefghijklmnopqrstuvwxyz" 3
trans 0 3 "." 4
trans 0 4 "abcdefghijklmnopqrstuvwxyz" 5
trans 0 5 "abcdefghijklmnopqrstuvwxyz" 5
# --- automato 1: o pattern `numero` -----------------------------------------
# Regex de origem: -?[0-9]+(\.[0-9]+)?
# Estados: 0 inicio | 1 apos o sinal | 2 parte inteira (aceitacao) | 3 apos o ponto
# 4 parte fracionaria (aceitacao)
automato 1 nome "numero" estados 5 inicial 0 alfabeto "0123456789-."
aceita 1 2 4
trans 1 0 "-" 1
trans 1 0 "0123456789" 2
trans 1 1 "0123456789" 2
trans 1 2 "0123456789" 2
trans 1 2 "." 3
trans 1 3 "0123456789" 4
trans 1 4 "0123456789" 4
# --- regra 0: on email(e) => emit("contato", e); ----------------------------
regra 0 automato 0 ligacao "e" pilha 2
codigo 0 0 PUSH_CONST 0
codigo 0 1 PUSH_MATCH
codigo 0 2 EMIT
codigo 0 3 RET
# --- regra 1: on numero(n) where value(n) > 100 => emit("grande", n); -------
# A condicao e compilada por FLUXO: o salto pula a emissao quando ela e falsa.
# A forma alternativa — avaliar por valor e decidir depois — e assunto do
# gerador, nao da maquina; as duas cabem neste mesmo repertorio.
regra 1 automato 1 ligacao "n" pilha 2
codigo 1 0 PUSH_MATCH
codigo 1 1 VALUE
codigo 1 2 PUSH_CONST 2
codigo 1 3 CMP_GT
codigo 1 4 JMP_IF_FALSE 8
codigo 1 5 PUSH_CONST 1
codigo 1 6 PUSH_MATCH
codigo 1 7 EMIT
codigo 1 8 RET13_invalido.pobj
# 13_invalido.pobj — um objeto BEM FORMADO que a maquina recusa.
#
# Todas as linhas deste arquivo obedecem a forma do formato: o carregador o le
# inteiro, sem uma queixa. O que ele viola sao as RESTRICOES — a metade do
# contrato que costuma ficar por escrever, e a que so cobra em tempo de execucao
# quando nao esta escrita. Cada regra abaixo carrega um defeito diferente, e a
# bateria de testes exige que todos sejam apontados numa unica passagem.
peneira-objeto 1
constante 0 texto "ok"
constante 1 numero 7
# Automato util, so para que as regras tenham do que disparar.
automato 0 nome "letra" estados 2 inicial 0 alfabeto "ab"
aceita 0 1
trans 0 0 "a" 1
trans 0 1 "a" 1
# Automato que nunca aceita: a regra que dependesse dele nunca dispararia, e o
# silencio resultante seria indistinguivel de "a entrada nao tinha o padrao".
automato 1 nome "morto" estados 2 inicial 0 alfabeto "ab"
trans 1 0 "c" 1
# Rotulo de emissao numerico: a saida tem duas colunas, e a primeira e um nome.
regra 0 automato 0 ligacao "x" pilha 2
codigo 0 0 PUSH_CONST 1
codigo 0 1 PUSH_MATCH
codigo 0 2 EMIT
codigo 0 3 RET
# Pilha desequilibrada: sobra um valor no retorno. Duas ativacoes seguidas e a
# pilha cresce sem limite, contra uma reserva feita no carregamento.
regra 1 automato 0 ligacao "x" pilha 1
codigo 1 0 PUSH_CONST 0
codigo 1 1 RET
# Salto para tras: um laco numa linguagem que nao tem repeticao, e que a
# varredura nao saberia interromper.
regra 2 automato 0 ligacao "x" pilha 1
codigo 2 0 PUSH_MATCH
codigo 2 1 JMP_IF_FALSE 1
codigo 2 2 RET
# Automato inexistente e constante inexistente na mesma regra.
regra 3 automato 5 ligacao "x" pilha 1
codigo 3 0 PUSH_CONST 9
codigo 3 1 RET
# Codigo correto, profundidade declarada errada: a maquina reservaria mais do que
# precisa — e, no sentido contrario, reservaria menos e escreveria fora.
regra 4 automato 0 ligacao "x" pilha 5
codigo 4 0 PUSH_CONST 0
codigo 4 1 PUSH_MATCH
codigo 4 2 EMIT
codigo 4 3 RET
# Codigo que nao termina em RET: a ativacao nao tem quem a encerre.
regra 5 automato 0 ligacao "x" pilha 1
codigo 5 0 PUSH_MATCHO exemplo preenchido à mão é o entregável, e não a ilustração do entregável. Ele contém os dois autômatos da descrição de referência, escritos estado a estado a partir das expressões regulares, mais o código das duas ações; roda sobre a entrada de referência e produz as duas linhas esperadas. Preenchê-lo levou menos tempo do que escrever esta seção, e mudou o formato em dois pontos — a declaração de transição por conjunto de símbolos nasceu ali, e o campo que declara a profundidade da pilha mudou de posição, porque quem preenche precisa saber o valor antes de escrever o código e não depois. É o efeito que o critério operacional produz e que a autoavaliação não produz: o formato foi corrigido por quem o usou, não por quem o admirou.
O que essa tarefa tem de mais fácil de subestimar são as restrições. Um formato descreve a forma dos dados e deixa ao gerador a liberdade de emitir sequências bem formadas que a máquina não consegue executar — código que não termina, salto para fora, pilha que sobra. São nove, todas escritas no documento de formato, e vale enunciar as três de que mais me sirvo: todo salto é para a frente, a pilha está vazia no retorno, e dois caminhos que chegam à mesma instrução chegam com pilhas de mesmo tamanho.
Essas três não são higiene: elas são o que torna a profundidade máxima da pilha calculável sem executar, numa única passada sobre o código. E é essa calculabilidade que permite à máquina reservar a pilha no carregamento, em vez de descobrir o tamanho por crescimento. Derrube qualquer uma delas e a reserva antecipada cai junto — o salto para trás transforma a conta num ponto fixo, e caminhos com pilhas divergentes tornam a resposta dependente do caminho tomado. É o exemplo mais limpo que conheço de uma restrição da máquina alvo pagando por si mesma: proíbe-se uma liberdade que a linguagem não usa, e ganha-se em troca uma propriedade que vale para sempre.
O segundo arquivo do bloco acima é a contraparte da bateria de testes. Ele é bem formado: o carregador o lê inteiro, sem uma queixa, porque nenhuma linha dele viola a forma. O que ele viola são nove restrições, uma por regra, e todas as nove são apontadas numa única passagem, cada uma dizendo o que se esperava e o que se encontrou. Nenhuma delas quebraria o carregamento — são todas condições que apareceriam durante a execução, e tarde.
Onde é fácil errar. Escrever a especificação depois do gerador, olhando o que ele já emite. O documento resultante parece uma especificação e não especifica nada: descreve. A diferença aparece no primeiro desacordo, quando não há a quem recorrer, porque o documento apenas repete o que um dos dois lados faz. Como verificar que está correta: entregue a especificação a alguém que não a escreveu e peça um objeto preenchido. Se a pessoa precisar perguntar qualquer coisa, o que faltou é exatamente o que ela perguntou — anote e escreva.
1.4 Tarefa 3: Tornar disponíveis os dados reconhecidos
O que a tarefa pede
Definir como os dados reconhecidos durante a execução ficam disponíveis a quem consome o resultado — o que se guarda, sob que forma e por quanto tempo. É a parte da especificação que parece detalhe de implementação e não é: ela decide o que o sistema consegue produzir como saída, e portanto o que ele serve para fazer.
13_maquina.h
// 13_maquina.h — O mundo em que o objeto roda.
//
// A MÁQUINA EXISTE ANTES DO GERADOR QUE A ALVEJA, e a ordem não é acidente de
// cronograma: não se emite código contra uma máquina que ainda não se decidiu
// como é. O que este arquivo fixa — quantas regiões de memória há, o que vive em
// cada uma, o que acontece quando um casamento dispara uma regra, o que
// sobrevive ao fim da ativação — é a lista de restrições que o gerador do
// capítulo seguinte terá de respeitar. Um objeto preenchido à mão roda aqui hoje;
// é essa a prova de que a máquina está pronta, e ela não depende de existir
// compilador algum.
//
// AS QUATRO REGIÕES, e por que elas são quatro e não uma:
//
// CÓDIGO as instruções das regras. Imutável durante a execução, e por
// isso compartilhável e conferível uma única vez, no carregamento.
// ESTÁTICA constantes e tabelas de transição. Existe antes da primeira
// ativação, dura até o fim, tem tamanho conhecido no carregamento.
// PILHA operandos e registros de ativação. Cresce e encolhe com as
// ativações, e o tamanho MÁXIMO é conhecido antes de a execução
// começar porque o objeto o declara — é a razão de o campo
// `pilha` existir no formato.
// DINÂMICA o que sobrevive à ativação que o produziu. Aqui, só isso: as
// emissões.
//
// A REGIÃO DINÂMICA É PEQUENA DE PROPÓSITO, e a decisão que a mantém pequena é a
// terceira tarefa do capítulo. Um casamento NÃO É COPIADO: o que circula é um
// descritor de três inteiros — qual autômato, onde começou, quanto durou —, e o
// texto continua onde já estava, no tampão da entrada. Copiar cada casamento
// seria mais simples de escrever e transformaria a área dinâmica no maior gasto
// do sistema, proporcional ao tamanho da entrada em vez de proporcional ao que
// a descrição de fato emite. O que se copia é só o que atravessa a fronteira da
// ativação — o valor emitido —, e é essa fronteira, e não o gosto do
// implementador, que decide o tempo de vida.
//
// O "ENDEREÇO DE RETORNO" AQUI É UMA POSIÇÃO DA ENTRADA, e vale dizer por quê em
// vez de fingir que é um endereço de código. Quem chama a regra é a varredura, e
// a varredura não é código do objeto: é a máquina. Não há, portanto, instrução à
// qual voltar. O que o quadro guarda é o ponto do texto em que a leitura
// recomeça quando a ativação termina, que é o papel que o endereço de retorno
// cumpre numa chamada comum — dizer onde continuar. A estrutura é a mesma; o que
// muda é de que espaço é o endereço.
#ifndef PENEIRA_13_MAQUINA_H
#define PENEIRA_13_MAQUINA_H
#include <cstddef>
#include <string>
#include <vector>
#include "03_afd.h"
#include "13_objeto.h"
namespace peneira {
// O descritor de um casamento. Três inteiros, nenhuma cópia. É o que o quadro de
// ativação recebe como parâmetro, e é a resposta da terceira tarefa à pergunta
// "sob que forma os dados reconhecidos ficam disponíveis".
struct Casamento {
std::size_t automato = 0;
std::size_t deslocamento = 0;
std::size_t comprimento = 0;
};
enum class EspecieDeValor {
Numero,
Logico,
TextoConstante, // índice na área estática — o texto não sobe para a pilha
Casamento,
};
// recorte:inicio pilha-nao-carrega-texto
// Uma posição da pilha de operandos. Nenhuma variante carrega texto: o texto de
// uma constante vive na área estática e o de um casamento vive no tampão da
// entrada, e as duas coisas sobrevivem à execução inteira. Se a pilha carregasse
// cadeias, cada empilhamento seria uma alocação.
struct Valor {
EspecieDeValor especie = EspecieDeValor::Numero;
double numero = 0.0;
bool logico = false;
std::size_t constante = 0;
Casamento casamento;
};
// recorte:fim pilha-nao-carrega-texto
// recorte:inicio registro-de-ativacao
// O registro de ativação. Um por casamento que dispara uma regra.
struct Quadro {
std::size_t regra = 0;
std::size_t baseDaPilha = 0; // onde os operandos desta ativação começam
Casamento parametro; // o único parâmetro, passado por descritor
std::size_t retornoNaEntrada = 0; // onde a varredura recomeça quando esta ativação terminar
std::size_t nivel = 1; // 1: a ação; 0 é a área estática, que é o não local
};
// recorte:fim registro-de-ativacao
struct Emissao {
std::size_t rotulo = 0; // índice da constante textual
std::size_t inicioNaArena = 0; // o valor foi COPIADO: ele sobrevive à ativação
std::size_t comprimento = 0;
std::size_t deslocamentoNaEntrada = 0;
};
struct ErroDeExecucao {
std::size_t regra = 0;
std::size_t posicao = 0;
std::size_t deslocamentoNaEntrada = 0;
std::string mensagem;
};
struct MapaDeMemoria {
std::size_t codigo = 0;
std::size_t estatica = 0;
std::size_t pilhaReservada = 0;
std::size_t dinamica = 0;
};
struct Estatisticas {
std::size_t simbolosLidos = 0;
std::size_t tentativasDeCasamento = 0;
std::size_t casamentos = 0;
std::size_t ativacoes = 0;
std::size_t instrucoes = 0;
// Quantas vezes o texto casado foi convertido em numero. É a medida que
// torna o curto-circuito OBSERVAVEL: a forma que desvia cedo converte menos
// do que a forma que avalia os dois lados, e a diferenca aparece aqui em vez
// de ser afirmada.
std::size_t conversoes = 0;
std::size_t profundidadeObservada = 0;
std::size_t bytesCasados = 0; // o que NÃO foi copiado, porque virou descritor
std::size_t bytesCopiados = 0; // o que atravessou a fronteira da ativação
};
struct ResultadoDeExecucao {
std::vector<Emissao> emissoes;
std::vector<char> arena;
std::vector<ErroDeExecucao> erros;
std::vector<std::string> traco;
// Os primeiros registros de ativação, guardados como estavam no momento da
// chamada. Existem para que a estrutura possa ser MOSTRADA em vez de
// descrita: um quadro que ninguém vê é uma afirmação sobre o código.
std::vector<Quadro> quadros;
MapaDeMemoria mapa;
Estatisticas estatisticas;
bool ok() const { return erros.empty(); }
};
// Carrega um objeto já validado e o executa sobre um texto. A máquina não
// verifica nada em tempo de execução que o carregamento já tenha verificado —
// essa é a contrapartida das restrições do formato, e é o que mantém o laço de
// execução com um `switch` e nada mais.
class Maquina {
public:
explicit Maquina(const ProgramaObjeto& programa);
// `limiteDoTraco` registra as primeiras instruções executadas, para que o
// passo a passo possa ser mostrado sem inundar a saída de uma entrada real.
ResultadoDeExecucao executar(const std::string& entrada, std::size_t limiteDoTraco = 0);
const MapaDeMemoria& mapa() const;
private:
// O casamento mais longo a partir de uma posição, entre todos os autômatos.
// Empate resolve-se pela ordem de declaração das regras — o mesmo critério
// que o reconhecedor de símbolos da própria linguagem já usa.
bool casarMaisLongo(const std::string& entrada, std::size_t posicao, std::size_t& regra,
std::size_t& comprimento, Estatisticas& estatisticas) const;
const ProgramaObjeto& programa_;
std::vector<Afd> automatos_;
MapaDeMemoria mapa_;
std::size_t profundidadeMaxima_ = 0;
};
std::string formatarMapa(const MapaDeMemoria& mapa);
std::string formatarEstatisticas(const Estatisticas& estatisticas);
std::string formatarEmissoes(const ProgramaObjeto& programa, const ResultadoDeExecucao& resultado);
std::string formatarQuadro(const ProgramaObjeto& programa, const Quadro& quadro,
const std::string& entrada);
} // namespace peneira
#endif // PENEIRA_13_MAQUINA_H13_maquina.cpp
// 13_maquina.cpp — a execução do objeto: varredura, ativação e emissão.
#include "13_maquina.h"
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <sstream>
namespace peneira {
namespace {
std::string formatarNumeroDeSaida(double valor) {
if (std::floor(valor) == valor && std::fabs(valor) < 1e15) {
std::ostringstream fluxo;
fluxo << static_cast<long long>(valor);
return fluxo.str();
}
std::ostringstream fluxo;
fluxo << std::defaultfloat << std::setprecision(15) << valor;
return fluxo.str();
}
std::string lexemaDe(const std::string& entrada, const Casamento& casamento) {
if (casamento.deslocamento >= entrada.size()) {
return std::string{};
}
const std::size_t disponivel = entrada.size() - casamento.deslocamento;
return entrada.substr(casamento.deslocamento, std::min(casamento.comprimento, disponivel));
}
bool ehComparacao(Opcode opcode) {
return opcode == Opcode::CompararMenor || opcode == Opcode::CompararMaior ||
opcode == Opcode::CompararIgual || opcode == Opcode::CompararDiferente ||
opcode == Opcode::CompararMenorIgual || opcode == Opcode::CompararMaiorIgual;
}
bool compararNumeros(Opcode opcode, double esquerda, double direita) {
switch (opcode) {
case Opcode::CompararMenor: return esquerda < direita;
case Opcode::CompararMaior: return esquerda > direita;
case Opcode::CompararIgual: return esquerda == direita;
case Opcode::CompararDiferente: return esquerda != direita;
case Opcode::CompararMenorIgual: return esquerda <= direita;
case Opcode::CompararMaiorIgual: return esquerda >= direita;
default: return false;
}
}
} // namespace
Maquina::Maquina(const ProgramaObjeto& programa) : programa_{programa} {
automatos_.reserve(programa_.automatos.size());
for (const AutomatoObjeto& automato : programa_.automatos) {
automatos_.push_back(montarAfd(automato));
}
// recorte:inicio mapa-de-memoria-antes-da-execucao
// O mapa de memória é conhecido AGORA, antes de a primeira ativação existir,
// e é isso que o formato compra com o campo `pilha`: a máquina reserva de uma
// vez o que a execução pode exigir, em vez de descobrir por crescimento.
for (const RegraObjeto& regra : programa_.regras) {
mapa_.codigo += regra.codigo.size() * sizeof(Instrucao);
profundidadeMaxima_ = std::max(profundidadeMaxima_, regra.profundidade);
}
for (const Constante& constante : programa_.constantes) {
mapa_.estatica += sizeof(Constante) + constante.texto.size();
}
for (const Afd& afd : automatos_) {
mapa_.estatica += afd.bytesDaTabela();
}
mapa_.pilhaReservada = profundidadeMaxima_ * sizeof(Valor) + sizeof(Quadro);
// recorte:fim mapa-de-memoria-antes-da-execucao
}
const MapaDeMemoria& Maquina::mapa() const {
return mapa_;
}
bool Maquina::casarMaisLongo(const std::string& entrada, std::size_t posicao, std::size_t& regra,
std::size_t& comprimento, Estatisticas& estatisticas) const {
std::size_t melhorRegra = 0;
std::size_t melhorComprimento = 0;
for (std::size_t r = 0; r < programa_.regras.size(); ++r) {
++estatisticas.tentativasDeCasamento;
const Afd& afd = automatos_[programa_.regras[r].automato];
Estado estado = afd.estadoInicial();
std::size_t aceitouAte = 0;
// recorte:inicio casamento-mais-longo-na-vm
// A varredura do casamento mais longo guarda o último ponto de aceitação
// e continua andando: parar na primeira aceitação daria `1` sobre `1500`,
// e a descrição passaria a falar de outra coisa.
for (std::size_t i = posicao; i < entrada.size(); ++i) {
estado = afd.transicao(estado, entrada[i]);
if (estado == afd.estadoDeErro()) {
break;
}
if (afd.ehDeAceitacao(estado)) {
aceitouAte = i - posicao + 1;
}
// recorte:fim casamento-mais-longo-na-vm
}
// Empate resolve-se pela ordem de declaração: só substitui quem veio
// antes um casamento ESTRITAMENTE maior.
if (aceitouAte > melhorComprimento) {
melhorComprimento = aceitouAte;
melhorRegra = r;
}
}
if (melhorComprimento == 0) {
return false;
}
regra = melhorRegra;
comprimento = melhorComprimento;
return true;
}
ResultadoDeExecucao Maquina::executar(const std::string& entrada, std::size_t limiteDoTraco) {
ResultadoDeExecucao resultado;
resultado.mapa = mapa_;
std::vector<Valor> pilha;
pilha.reserve(profundidadeMaxima_);
std::vector<Quadro> quadros;
std::size_t posicao = 0;
while (posicao < entrada.size()) {
std::size_t regraCasada = 0;
std::size_t comprimento = 0;
if (!casarMaisLongo(entrada, posicao, regraCasada, comprimento,
resultado.estatisticas)) {
++posicao;
++resultado.estatisticas.simbolosLidos;
continue;
}
resultado.estatisticas.simbolosLidos += comprimento;
++resultado.estatisticas.casamentos;
resultado.estatisticas.bytesCasados += comprimento;
// A ATIVAÇÃO. O parâmetro é o descritor do casamento — três inteiros —, e
// o endereço de retorno é a posição da entrada em que a varredura
// recomeça. Nada do texto casado é copiado para dentro do quadro.
Quadro quadro;
quadro.regra = regraCasada;
quadro.baseDaPilha = pilha.size();
quadro.parametro = Casamento{programa_.regras[regraCasada].automato, posicao, comprimento};
quadro.retornoNaEntrada = posicao + comprimento;
quadro.nivel = 1;
quadros.push_back(quadro);
++resultado.estatisticas.ativacoes;
if (limiteDoTraco > 0 && resultado.quadros.size() < 2) {
resultado.quadros.push_back(quadro);
}
const RegraObjeto& regra = programa_.regras[regraCasada];
bool abortou = false;
std::size_t pc = 0;
while (pc < regra.codigo.size()) {
const Instrucao& instrucao = regra.codigo[pc];
++resultado.estatisticas.instrucoes;
const bool registrouLinha = resultado.traco.size() < limiteDoTraco;
if (registrouLinha) {
std::ostringstream linha;
linha << " " << std::setw(3) << pc << ": " << std::setw(12) << std::left
<< mnemonico(instrucao.opcode) << std::right;
if (temOperando(instrucao.opcode)) {
linha << std::setw(4) << instrucao.operando;
} else {
linha << std::setw(4) << ' ';
}
linha << " | pilha " << (pilha.size() - quadro.baseDaPilha) << " -> ";
resultado.traco.push_back(linha.str());
}
const auto falhar = [&](const std::string& mensagem) {
ErroDeExecucao erro;
erro.regra = regraCasada;
erro.posicao = pc;
erro.deslocamentoNaEntrada = posicao;
erro.mensagem = mensagem;
resultado.erros.push_back(erro);
abortou = true;
};
switch (instrucao.opcode) {
case Opcode::EmpilharConstante: {
const Constante& constante = programa_.constantes[instrucao.operando];
Valor valor;
if (constante.especie == EspecieDeConstante::Numero) {
valor.especie = EspecieDeValor::Numero;
valor.numero = constante.numero;
} else {
valor.especie = EspecieDeValor::TextoConstante;
valor.constante = instrucao.operando;
}
pilha.push_back(valor);
++pc;
break;
}
case Opcode::EmpilharCasamento: {
// O ACESSO LOCAL: o parâmetro vem do quadro corrente, nível 1.
Valor valor;
valor.especie = EspecieDeValor::Casamento;
valor.casamento = quadros.back().parametro;
pilha.push_back(valor);
++pc;
break;
}
case Opcode::Valor: {
++resultado.estatisticas.conversoes;
Valor topo = pilha.back();
pilha.pop_back();
if (topo.especie != EspecieDeValor::Casamento) {
falhar("VALUE espera um casamento no topo da pilha");
break;
}
const std::string lexema = lexemaDe(entrada, topo.casamento);
char* fim = nullptr;
const double numero = std::strtod(lexema.c_str(), &fim);
if (fim == nullptr || *fim != '\0' || lexema.empty()) {
falhar("VALUE sobre um casamento que nao e numerico: \"" + lexema + "\"");
break;
}
Valor convertido;
convertido.especie = EspecieDeValor::Numero;
convertido.numero = numero;
pilha.push_back(convertido);
++pc;
break;
}
case Opcode::CompararMenor:
case Opcode::CompararMaior:
case Opcode::CompararIgual:
case Opcode::CompararDiferente:
case Opcode::CompararMenorIgual:
case Opcode::CompararMaiorIgual: {
const Valor direita = pilha.back();
pilha.pop_back();
const Valor esquerda = pilha.back();
pilha.pop_back();
Valor saida;
saida.especie = EspecieDeValor::Logico;
if (esquerda.especie == EspecieDeValor::Numero &&
direita.especie == EspecieDeValor::Numero) {
saida.logico =
compararNumeros(instrucao.opcode, esquerda.numero, direita.numero);
} else if (esquerda.especie == EspecieDeValor::Logico ||
direita.especie == EspecieDeValor::Logico) {
falhar("comparacao entre condicoes");
break;
} else {
// A única promoção implícita da linguagem: casamento vira
// texto. Ordem sobre texto exigiria uma regra de colação
// que esta linguagem não tem, e escolher uma em silencio
// produziria resultado que varia com a maquina.
if (instrucao.opcode != Opcode::CompararIgual &&
instrucao.opcode != Opcode::CompararDiferente) {
falhar("esta maquina nao ordena texto");
break;
}
const auto comoTexto = [&](const Valor& valor) {
if (valor.especie == EspecieDeValor::TextoConstante) {
return programa_.constantes[valor.constante].texto;
}
if (valor.especie == EspecieDeValor::Casamento) {
return lexemaDe(entrada, valor.casamento);
}
return formatarNumeroDeSaida(valor.numero);
};
const bool iguais = comoTexto(esquerda) == comoTexto(direita);
saida.logico =
instrucao.opcode == Opcode::CompararIgual ? iguais : !iguais;
}
pilha.push_back(saida);
++pc;
break;
}
case Opcode::Conjuncao:
case Opcode::Disjuncao: {
const Valor direita = pilha.back();
pilha.pop_back();
const Valor esquerda = pilha.back();
pilha.pop_back();
if (esquerda.especie != EspecieDeValor::Logico ||
direita.especie != EspecieDeValor::Logico) {
falhar("operador logico sobre algo que nao e condicao");
break;
}
Valor saida;
saida.especie = EspecieDeValor::Logico;
saida.logico = instrucao.opcode == Opcode::Conjuncao
? (esquerda.logico && direita.logico)
: (esquerda.logico || direita.logico);
pilha.push_back(saida);
++pc;
break;
}
case Opcode::Emitir: {
const Valor valor = pilha.back();
pilha.pop_back();
const Valor rotulo = pilha.back();
pilha.pop_back();
if (rotulo.especie != EspecieDeValor::TextoConstante) {
falhar("o rotulo de uma emissao e uma constante textual");
break;
}
std::string texto;
if (valor.especie == EspecieDeValor::Casamento) {
texto = lexemaDe(entrada, valor.casamento);
} else if (valor.especie == EspecieDeValor::TextoConstante) {
texto = programa_.constantes[valor.constante].texto;
} else if (valor.especie == EspecieDeValor::Numero) {
texto = formatarNumeroDeSaida(valor.numero);
} else {
falhar("nao se emite uma condicao");
break;
}
// AQUI, E SÓ AQUI, ALGO É COPIADO. O valor emitido atravessa
// a fronteira da ativação: ele precisa existir depois que o
// quadro tiver ido embora, e por isso vai para a área
// dinâmica em vez de continuar sendo um descritor.
Emissao emissao;
emissao.rotulo = rotulo.constante;
emissao.inicioNaArena = resultado.arena.size();
emissao.comprimento = texto.size();
emissao.deslocamentoNaEntrada = quadros.back().parametro.deslocamento;
resultado.arena.insert(resultado.arena.end(), texto.begin(), texto.end());
resultado.emissoes.push_back(emissao);
resultado.estatisticas.bytesCopiados += texto.size();
++pc;
break;
}
case Opcode::Saltar: {
pc = instrucao.operando;
break;
}
case Opcode::SaltarSeFalso: {
const Valor topo = pilha.back();
pilha.pop_back();
if (topo.especie != EspecieDeValor::Logico) {
falhar("salto condicional sobre algo que nao e condicao");
break;
}
pc = topo.logico ? pc + 1 : instrucao.operando;
break;
}
case Opcode::Retornar: {
pc = regra.codigo.size();
break;
}
}
resultado.estatisticas.profundidadeObservada =
std::max(resultado.estatisticas.profundidadeObservada,
pilha.size() - quadro.baseDaPilha);
if (registrouLinha) {
resultado.traco.back() += std::to_string(pilha.size() - quadro.baseDaPilha);
}
if (abortou) {
break;
}
}
// O DESCARTE DO QUADRO. A pilha volta à base, o descritor do casamento
// deixa de existir, e nada precisa ser recuperado: o que sobrevive já
// está na área dinâmica, e o que não sobrevive nunca chegou a ocupar
// espaço próprio.
pilha.resize(quadro.baseDaPilha);
quadros.pop_back();
posicao = quadro.retornoNaEntrada;
if (abortou) {
break;
}
}
resultado.mapa.dinamica = resultado.arena.size();
return resultado;
}
std::string formatarMapa(const MapaDeMemoria& mapa) {
std::ostringstream saida;
const std::size_t total = mapa.codigo + mapa.estatica + mapa.pilhaReservada + mapa.dinamica;
saida << " regiao bytes conteudo\n";
saida << " codigo " << std::setw(7) << mapa.codigo
<< " as instrucoes das regras; imutavel durante a execucao\n";
saida << " estatica " << std::setw(7) << mapa.estatica
<< " constantes e tabelas de transicao; existe antes da 1a ativacao\n";
saida << " pilha " << std::setw(7) << mapa.pilhaReservada
<< " operandos e quadros; RESERVADA no carregamento, nao por crescimento\n";
saida << " dinamica " << std::setw(7) << mapa.dinamica
<< " o que sobrevive a ativacao que o produziu: as emissoes\n";
saida << " total " << std::setw(7) << total << "\n";
return saida.str();
}
std::string formatarEstatisticas(const Estatisticas& estatisticas) {
std::ostringstream saida;
saida << " simbolos lidos ............ " << estatisticas.simbolosLidos << "\n";
saida << " tentativas de casamento ... " << estatisticas.tentativasDeCasamento << "\n";
saida << " casamentos ................ " << estatisticas.casamentos << "\n";
saida << " ativacoes ................. " << estatisticas.ativacoes << "\n";
saida << " instrucoes executadas ..... " << estatisticas.instrucoes << "\n";
saida << " profundidade observada .... " << estatisticas.profundidadeObservada << "\n";
saida << " bytes casados (descritor) . " << estatisticas.bytesCasados << "\n";
saida << " bytes copiados (arena) .... " << estatisticas.bytesCopiados << "\n";
return saida.str();
}
std::string formatarEmissoes(const ProgramaObjeto& programa,
const ResultadoDeExecucao& resultado) {
std::ostringstream saida;
for (const Emissao& emissao : resultado.emissoes) {
const std::string valor{resultado.arena.begin() + static_cast<std::ptrdiff_t>(emissao.inicioNaArena),
resultado.arena.begin() +
static_cast<std::ptrdiff_t>(emissao.inicioNaArena + emissao.comprimento)};
saida << " " << std::setw(10) << std::left << programa.constantes[emissao.rotulo].texto
<< std::right << valor << "\n";
}
return saida.str();
}
std::string formatarQuadro(const ProgramaObjeto& programa, const Quadro& quadro,
const std::string& entrada) {
std::ostringstream saida;
const RegraObjeto& regra = programa.regras[quadro.regra];
saida << " regra ................. " << quadro.regra << " (automato \""
<< programa.automatos[regra.automato].nome << "\")\n";
saida << " ligacao ............... " << regra.ligacao << "\n";
saida << " parametro (descritor) . automato " << quadro.parametro.automato << ", inicio "
<< quadro.parametro.deslocamento << ", comprimento " << quadro.parametro.comprimento
<< "\n";
saida << " o texto que ele designa \"" << lexemaDe(entrada, quadro.parametro) << "\"\n";
saida << " base da pilha ......... " << quadro.baseDaPilha << "\n";
saida << " retorno (na entrada) .. " << quadro.retornoNaEntrada << "\n";
saida << " nivel ................. " << quadro.nivel
<< " (0 e a area estatica: o nome nao local)\n";
return saida.str();
}
} // namespace peneiraA resposta às três perguntas da tarefa cabe numa regra, e a regra é literal: copia-se o que sobrevive; referencia-se o que não sobrevive.
O que se guarda de um trecho reconhecido é um descritor de três inteiros — qual autômato o reconheceu, onde ele começou, quanto ele durou. O texto continua onde já estava, no tampão da entrada, que dura a execução inteira. Copiar cada trecho reconhecido para dentro da ativação seria mais simples de escrever e teria uma consequência mensurável: a região dinâmica passaria a crescer proporcionalmente ao tamanho da entrada, e não ao que a descrição de fato emite. Sobre a entrada de referência, a diferença é entre 34 e 25 bytes e não impressiona ninguém; sobre um arquivo de log de alguns megabytes com uma regra seletiva, é a diferença entre um sistema que roda e um que não.
Por quanto tempo o descritor existe é a pergunta cuja resposta a estrutura já dá: ele vive no registro de ativação e morre com ele. O que atravessa a fronteira da ativação é apenas o valor emitido — porque a saída precisa existir depois que o quadro tiver ido embora — e é por isso que ele, e só ele, é copiado para a região dinâmica. É o critério aplicado uma vez, no único ponto do código em que algo é copiado, com o comentário que diz por quê.
A parte da tarefa que parece detalhe de implementação e decide o que o sistema serve para fazer é a terceira. Como o que se guarda é o deslocamento na entrada, e não uma cópia, o sistema sabe de graça onde cada casamento estava — e uma saída que informe a posição, ou que ordene as emissões por ocorrência, ou que devolva o contexto em volta do trecho, é acrescentável sem tocar em nada. A alternativa que copia o lexema teria descartado essa informação no ato da cópia, e recuperá-la depois exigiria procurar o trecho na entrada, o que é reabrir uma fase fechada — e, pior, procurar o trecho errado quando ele aparece duas vezes.
Onde é fácil errar. Guardar no descritor um ponteiro para dentro do tampão da entrada em vez de um deslocamento. Funciona, é mais rápido, e para de funcionar no dia em que a entrada passar a ser lida por partes: o ponteiro aponta para memória reaproveitada, e a saída fica plausível e errada. Como verificar que está correta: compare, ao final de uma execução, os bytes reconhecidos com os bytes copiados. Se os dois números forem iguais, alguma cópia está acontecendo onde deveria haver referência; se o segundo for zero havendo emissões, alguma referência está sobrevivendo a quem a criou, e o defeito só vai aparecer quando a memória for reaproveitada.
1.5 As quatro regiões, e o que decide o tamanho de cada uma
A organização da memória de um programa em execução é o assunto teórico deste módulo, e a máquina o materializa em quatro regiões, que são as mesmas quatro de qualquer programa em execução, com nomes que aqui significam coisas concretas.
O código são as instruções das regras. É imutável durante a execução, e é essa imutabilidade que permite conferir tudo uma única vez, no carregamento, e nunca mais. A área estática guarda as constantes e as tabelas de transição — existe antes da primeira ativação, dura até o fim, e tem tamanho conhecido no carregamento. A pilha guarda os operandos e os registros de ativação, e é a única cujo conteúdo varia com a execução; o máximo dela, no entanto, é conhecido antes de a execução começar, porque o objeto declara a profundidade que cada regra exige. A região dinâmica guarda o que sobrevive à ativação que o produziu, e aqui só isso: as emissões.
O mapa de memória impresso pela demonstração é intencionalmente exibido antes da primeira ativação, e ele mostra três das quatro linhas já preenchidas. É a diferença que o formato compra com um campo de uma palavra: a máquina reserva de uma vez o máximo que a execução pode exigir, em vez de descobrir o tamanho por crescimento. Um sistema que descobre por crescimento funciona igualmente bem na demonstração e falha de modo diferente sob carga — realoca no meio de uma ativação, invalida os ponteiros que alguém guardou, e o defeito aparece longe da causa.
Vale notar qual das quatro é a maior aqui, porque a proporção é característica desta linguagem e contraria a intuição de quem vem de linguagens de propósito geral. A área estática ocupa quase nove décimos do total, e ela é quase inteiramente tabela de transição. O programa objeto desta linguagem é, em massa, um autômato — o código das regras é um vigésimo dele. É a mesma afirmação da primeira tarefa, agora em bytes.
1.6 O registro de ativação, e um endereço de retorno que não é de código
Cada casamento dispara uma ativação, e o registro de ativação contém exatamente o que a teoria prevê: o índice da regra que se ativou, a base da pilha de operandos, o parâmetro e o endereço de retorno. A demonstração imprime o primeiro registro tal como ele estava no momento da chamada, e vale olhar duas linhas dele com atenção.
A primeira é o parâmetro. A passagem de parâmetro aqui é por descritor: três inteiros, e nenhum byte do texto reconhecido. A ligação criada pelo on é esse parâmetro, e é a única coisa que a ação recebe de fora — o que resolve, de um jeito quase anticlimático, a pergunta sobre como o valor casado chega ao código que o usa.
A segunda é o endereço de retorno, e ele merece uma correção honesta em vez de uma analogia frouxa. Aqui o endereço de retorno é uma posição da entrada, e não uma posição de código. A razão é que quem chama a regra é a varredura, e a varredura é a máquina, e não código do objeto. Não existe instrução à qual voltar. O que o quadro guarda é o ponto do texto em que a leitura recomeça quando a ativação terminar — que é exatamente o papel que o endereço de retorno cumpre numa chamada comum, dizer onde continuar. A estrutura é a mesma; o que muda é de que espaço é o endereço. Fingir que é um endereço de código, para que o exemplo casasse melhor com o desenho do livro, seria ensinar a estrutura certa pela razão errada.
O valor de retorno é o terceiro elemento clássico, e nesta máquina ele é ausente por decisão: uma ação não devolve valor, ela emite. A distinção decide uma região de memória — quem devolve valor tem um chamador esperando por ele, e o chamador aqui é uma varredura que não tem o que fazer com um resultado. O que a ação produz vai para a saída, que é a única coisa que sobrevive a ela.
O escopo em tempo de execução completa o quadro, e a máquina o resolve por níveis. Uma ação enxerga dois: o seu próprio, onde vive a ligação, e o global, que é a área estática. A instrução que empilha o casamento lê o nível da ativação; a que empilha uma constante lê o global. Não há cadeia estática nem display, e a ausência é registrada em vez de silenciada: ela vale porque esta linguagem não aninha ações. No dia em que aninhar, um dos dois passa a ser necessário — e o parágrafo que registra isso é o lugar onde o próximo a mexer no assunto vai descobri-lo, em vez de descobrir pelo defeito.
1.7 Alocação dinâmica, e o que aqui não precisa ser recuperado
A região dinâmica desta máquina cresce e nunca é recuperada durante a execução, e a afirmação, sozinha, soa como confissão de preguiça. Ela é o contrário: é a consequência de olhar o padrão de vida dos objetos antes de escolher a estratégia.
Tudo o que entra na região dinâmica sobrevive até o fim, porque é a saída do programa — não há valor emitido que possa morrer antes do término. Um alocador que sabe disso é uma arena: aloca por incremento de um índice, não mantém metadado por objeto, não tem fragmentação e libera tudo de uma vez. As estratégias mais elaboradas resolvem um problema que aqui não existe, e cada uma tem um preço que aqui seria pago sem contrapartida. A lista de livres com liberação explícita cobra o metadado por bloco e a disciplina de quem libera. A contagem de referências cobra a atualização do contador em toda cópia e não recupera ciclos. A varredura de alcançáveis a partir das raízes cobra a identificação das raízes e a pausa, e recupera exatamente o que aqui nunca fica inalcançável.
O que a decisão custa está escrito junto: se a linguagem ganhar um dia uma construção em que valores emitidos possam ser descartados — uma emissão condicionada a um estado posterior, um agrupamento que substitua saídas anteriores —, a arena deixa de ser adequada no mesmo instante, e a estratégia a escolher será decidida pelo novo padrão de vida, não por gosto. É o formato de conclusão que este módulo cobra em todas as suas partes: a escolha, a razão dela, e a condição em que ela deixa de valer.
1.8 O que este capítulo entrega ao arco seguinte
O sistema sai daqui com três coisas que não tinha ao entrar, e as três existem para serem consumidas pelo gerador de código.
A primeira é o alvo. Existe uma máquina, com repertório fixo, regiões definidas e comportamento observável, e ela roda um objeto preenchido à mão. O gerador do capítulo seguinte não vai inventar o alvo enquanto escreve o tradutor — ele vai produzir automaticamente o que já se sabe produzir manualmente, que é a única ordem em que a tarefa é verificável a cada passo: cada trecho gerado pode ser comparado com o trecho equivalente do objeto escrito à mão.
A segunda é o contrato com as restrições dentro dele. O gerador não precisará descobrir por experimentação o que a máquina aceita, e — o que importa mais — não conseguirá emitir em silêncio algo que ela não execute: o carregamento recusa antes de rodar, nomeando a restrição violada. A verificação que um gerador imaturo mais precisa é justamente essa, e ela existe antes de o gerador existir.
A terceira é uma pergunta com resposta contável, que a demonstração deste capítulo já exibe. A mesma condição composta cabe no repertório de duas formas — por fluxo, com saltos que dispensam avaliar o que já se decidiu, e por valor, avaliando os dois lados e combinando —, e as duas emitem o mesmo resultado com o mesmo número de instruções no código, mas com 57 e 72 instruções executadas sobre a mesma entrada, e com profundidades de pilha diferentes. Qual delas emitir é decisão do gerador; o que este capítulo fez foi construir a máquina que torna a decisão possível, e a medida que a torna defensável em vez de opinativa.