1 Módulo 13: Projeto do Professor — Decidir o Formato Antes de Escrevê-lo
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 13
Este é o módulo de projeto no sentido mais literal do termo: quase todo o trabalho é decidir e documentar, e o código que resulta é consequência dessas decisões. O entregável principal não é um programa — é uma especificação, e o critério de qualidade dela é literal e será aplicado literalmente: outra pessoa consegue escrever um executor compatível lendo apenas ela?
A atividade tem três partes. Definir a representação intermediária que fica entre a análise e a síntese, com a justificativa da escolha. Especificar o formato do programa objeto e o modelo de execução que o interpreta. E implementar a tradução da árvore verificada para a representação escolhida.
Resolvi a atividade e vou começar pela parte incômoda, porque ela define o tom do módulo. O argumento clássico a favor de uma camada intermediária é combinatório: para m origens e n destinos, a tradução direta custa m \times n tradutores e a intermediária custa m + n. Calculei isso para o nosso caso e o resultado é constrangedor — temos uma origem e um destino, então direto custaria um tradutor e com a camada intermediária custa dois. O argumento que a literatura usa para justificar a camada, aplicado honestamente a este projeto, a condena.
A camada existe assim mesmo, e por outro motivo, que é o que este módulo descobriu: o curto-circuito dos conectivos lógicos exige desvio, desvio exige rótulo, e rótulo exige um endereço que só se conhece depois de gerar o que vem adiante. Misturar essa dificuldade com a emissão do objeto torna as duas difíceis. Separá-las é o que as torna tratáveis. A camada se paga em clareza, não em reaproveitamento — e dizer isso é mais útil ao grupo do que repetir o argumento combinatório onde ele não se aplica.
A segunda coisa que este módulo me obrigou a enfrentar foi uma divergência entre o design do artefato e o que o módulo seguinte exige. Está registrada na tarefa 3, com a decisão que tomei.
1.2 Tarefa 1: Justificar a camada, com números honestos
A atividade — justificar a existência de uma representação intermediária à luz das alternativas e das características da linguagem.
13_ri.h
#ifndef PENEIRA_13_RI_H
#define PENEIRA_13_RI_H
#include <cstddef>
#include <cstdint>
#include <string>
#include <vector>
#include "10_ast.h"
namespace peneira {
// Representação intermediária da Peneira: código de três endereços.
//
// Por que existe uma camada aqui, em vez de a árvore verificada ir direto para
// o objeto. O argumento é combinatório e vale escrever com números: para
// suportar $m$ linguagens de origem e $n$ destinos, a tradução direta custa
// $m \times n$ tradutores; com uma representação intermediária no meio, custa
// $m + n$. Cinco por cinco: vinte e cinco contra dez.
//
// Nesta disciplina $m = n = 1$, e o argumento combinatório sozinho NÃO
// justificaria a camada — seria uma indireção paga sem retorno. O que a
// justifica aqui é outra coisa, e é honesto dizer qual: o curto-circuito dos
// conectivos lógicos exige desvios, e desvios exigem rótulos cujo destino só
// se conhece depois. Fazer isso direto sobre a árvore, durante a emissão do
// objeto, mistura duas dificuldades; separá-las é o que torna as duas
// tratáveis. A camada se paga em clareza, não em reaproveitamento.
enum class OpRI : std::uint8_t {
Rotulo, // marca um ponto do código; alvo de desvio
CasamentoDe, // t := o texto casado pela variável de ligação
Valor, // t := valor numérico de um casamento (o `value` da fonte)
Constante, // t := literal
Comparacao, // t := arg1 <op> arg2
DesvioSeFalso, // se arg1 for falso, desvia
Desvio, // desvia incondicionalmente
Emite, // emite (rotulo, arg1)
};
const char* nomeDaOpRI(OpRI op) noexcept;
// Uma instrução de três endereços: um resultado e até dois operandos.
//
// `destino` é o índice da instrução alvo, para os desvios. Ele nasce com
// kDestinoPendente e é preenchido depois — é o campo que a técnica de
// preenchimento retroativo manipula.
inline constexpr std::size_t kDestinoPendente = static_cast<std::size_t>(-1);
struct InstrucaoRI {
OpRI op = OpRI::Rotulo;
std::string resultado; // nome do temporário, ou do rótulo
std::string arg1;
std::string arg2;
std::string operador; // só para Comparacao
std::size_t destino = kDestinoPendente;
};
// O código de uma regra: a condição (com desvios) seguida da emissão.
struct CodigoRI {
std::vector<InstrucaoRI> instrucoes;
std::string padrao; // padrão que dispara a regra
std::string ligacao; // variável de ligação
};
std::string formatarRI(const CodigoRI& c);
// Tradutor de árvore verificada para código de três endereços.
//
// A técnica central é o **preenchimento retroativo**: ao traduzir uma condição,
// o desvio que sai quando ela é falsa precisa apontar para o fim da regra, e o
// fim da regra ainda não foi gerado. Em vez de fazer um segundo percurso para
// descobrir o endereço, a tradução guarda a lista das instruções incompletas e
// as preenche quando o endereço fica conhecido.
//
// É a mesma ideia do módulo 10 em outro disfarce: lá, a decisão sobre qual
// produção usar era adiada até haver informação; aqui, a decisão sobre para
// onde desviar.
class TradutorRI {
public:
// Traduz uma ação verificada (nó Acao) para código de três endereços.
CodigoRI traduzirAcao(const NoAst& acao);
std::size_t temporariosUsados() const noexcept;
private:
// Traduz uma expressão de valor e devolve o nome do temporário que a
// contém.
std::string traduzirValor(const NoAst& expr);
// Traduz uma condição. Devolve as listas de instruções de desvio que ainda
// precisam de destino: as que saem quando a condição é verdadeira e as que
// saem quando é falsa.
struct ListasDeDesvio {
std::vector<std::size_t> verdadeiro;
std::vector<std::size_t> falso;
};
ListasDeDesvio traduzirCondicao(const NoAst& cond);
// Preenche o destino de todas as instruções da lista.
void preencher(const std::vector<std::size_t>& lista, std::size_t destino);
std::size_t emitir(InstrucaoRI instrucao);
std::string novoTemporario();
std::vector<InstrucaoRI> instrucoes_;
std::size_t proximoTemporario_ = 0;
};
// Notação pós-fixada da mesma expressão.
//
// Está aqui porque é a forma intermediária mais simples que existe e serve de
// contraste: ela dispensa temporários e rótulos, porque a ordem de avaliação
// está na própria sequência. O preço é que ela não exprime desvio — e é
// exatamente por isso que ela não serve para o curto-circuito, o que fecha o
// argumento a favor do código de três endereços nesta linguagem.
std::string emPosFixada(const NoAst& expr);
// O argumento combinatório, calculado.
struct CustoDeTraducao {
std::size_t origens = 0;
std::size_t destinos = 0;
std::size_t tradutoresDiretos = 0; // origens * destinos
std::size_t tradutoresComIntermediaria = 0; // origens + destinos
};
CustoDeTraducao custoDeTraducao(std::size_t origens, std::size_t destinos) noexcept;
} // namespace peneira
#endif // PENEIRA_13_RI_HA demonstração --porqueri calcula o argumento clássico em vez de enunciá-lo:
origens | destinos | tradutores diretos | com intermediaria
--------+----------+--------------------+------------------
1 | 1 | 1 | 2
2 | 2 | 4 | 4
3 | 3 | 9 | 6
5 | 5 | 25 | 10
10 | 10 | 100 | 20O ponto de virada está em três por três, e abaixo dele a camada custa mais do que economiza. Nosso caso é a primeira linha.
Escrevi a tabela inteira, e não só a linha de cinco por cinco que a literatura costuma citar, justamente porque a primeira linha é a nossa e omiti-la seria vender um argumento que não se aplica. O grupo que copiar o argumento combinatório para justificar a camada num compilador de origem única e destino único está repetindo uma frase, não fazendo engenharia.
A justificativa real, nesta linguagem, é a separação de dificuldades. A tradução da árvore para o objeto tem duas partes independentes: decidir a ordem de avaliação com desvios e decidir a codificação das instruções. Feitas juntas, cada erro de uma parece defeito da outra. A representação intermediária é a fronteira que permite testar a primeira sem a segunda existir — e é exatamente o que este módulo faz, já que a emissão do objeto só vem no módulo seguinte.
Onde é fácil errar aqui. Justificar a camada pelo argumento que não se aplica ao próprio projeto, porque é o argumento que está no livro. A justificativa tem de sair das características da linguagem do grupo, e se ela não existir, a conclusão honesta é que o grupo não precisa da camada — o que também é uma resposta defensável.
Como verificar. A pergunta que uso: se eu apagar a camada e traduzir direto, o que fica mais difícil? Se a resposta for “nada”, a camada é peso morto.
1.3 Tarefa 2: A representação, e por que não a mais simples
A atividade — comparar as formas usuais quanto ao que facilitam e implementar a tradução da árvore verificada.
Comparei três formas sobre a mesma condição, o que é a única comparação que vale — comparar formas sobre exemplos diferentes só mostra que os exemplos são diferentes. O programa de referência tem condições compostas, que é o que separa as formas:
pattern numero = /-?[0-9]+(\.[0-9]+)?/;
rule {
on numero(n) where value(n) > 100 and value(n) < 500
=> emit("faixa", n);
on numero(n) where value(n) < 0 or value(n) > 1000
=> emit("extremo", n);
}A árvore sintática abstrata é a forma que já temos, saída do módulo 10:
E
Comparacao ">"
ValorDe "n"
LiteralNumero "100"
Comparacao "<"
ValorDe "n"
LiteralNumero "500"Ela é a mais informativa e a menos executável: a ordem de avaliação está implícita na estrutura, e quem executa precisa reconstruí-la percorrendo.
A notação pós-fixada é a mais curta das três:
n valor 100 > n valor 500 < andEla resolve a ordem de avaliação de graça — a sequência é a ordem — e dispensa temporários e rótulos. E não serve, por uma razão que é o argumento central deste módulo: ela não exprime desvio. Sem desvio não há curto-circuito, e sem curto-circuito o and avalia os dois lados sempre. Numa linguagem em que avaliar não custa nada isso seria só ineficiência; aqui, o módulo seguinte exige curto-circuito explicitamente.
Sobra o código de três endereços, que é o que implementei:
13_ri.cpp
#include "13_ri.h"
#include <sstream>
#include <utility>
namespace peneira {
const char* nomeDaOpRI(OpRI op) noexcept {
switch (op) {
case OpRI::Rotulo: return "rotulo";
case OpRI::CasamentoDe: return "casamento";
case OpRI::Valor: return "valor";
case OpRI::Constante: return "const";
case OpRI::Comparacao: return "cmp";
case OpRI::DesvioSeFalso: return "se_falso";
case OpRI::Desvio: return "desvia";
case OpRI::Emite: return "emite";
}
return "<desconhecida>";
}
std::size_t TradutorRI::emitir(InstrucaoRI instrucao) {
instrucoes_.push_back(std::move(instrucao));
return instrucoes_.size() - 1;
}
std::string TradutorRI::novoTemporario() {
return "t" + std::to_string(proximoTemporario_++);
}
std::size_t TradutorRI::temporariosUsados() const noexcept {
return proximoTemporario_;
}
void TradutorRI::preencher(const std::vector<std::size_t>& lista,
std::size_t destino) {
for (const std::size_t i : lista) {
instrucoes_[i].destino = destino;
}
}
std::string TradutorRI::traduzirValor(const NoAst& expr) {
switch (expr.tipo) {
case TipoAst::LiteralNumero: {
const std::string t = novoTemporario();
InstrucaoRI ins;
ins.op = OpRI::Constante;
ins.resultado = t;
// O lexema, e não o valor reconvertido: preserva a forma escrita
// pelo autor no relatório, e a conversão já foi feita e validada no
// módulo 7.
ins.arg1 = expr.texto;
emitir(std::move(ins));
return t;
}
case TipoAst::LiteralTexto: {
const std::string t = novoTemporario();
InstrucaoRI ins;
ins.op = OpRI::Constante;
ins.resultado = t;
ins.arg1 = "\"" + expr.texto + "\"";
emitir(std::move(ins));
return t;
}
case TipoAst::Referencia: {
const std::string t = novoTemporario();
InstrucaoRI ins;
ins.op = OpRI::CasamentoDe;
ins.resultado = t;
ins.arg1 = expr.texto;
emitir(std::move(ins));
return t;
}
case TipoAst::ValorDe: {
// Duas instruções, e não uma: primeiro o casamento, depois a
// conversão. Separá-las é o que torna a conversão visível na
// representação — e a conversão é justamente o que a fase semântica
// exigiu que fosse explícita no programa fonte.
const std::string casamento = novoTemporario();
InstrucaoRI busca;
busca.op = OpRI::CasamentoDe;
busca.resultado = casamento;
busca.arg1 = expr.texto;
emitir(std::move(busca));
const std::string t = novoTemporario();
InstrucaoRI conversao;
conversao.op = OpRI::Valor;
conversao.resultado = t;
conversao.arg1 = casamento;
emitir(std::move(conversao));
return t;
}
default:
return "<indefinido>";
}
}
TradutorRI::ListasDeDesvio TradutorRI::traduzirCondicao(const NoAst& cond) {
ListasDeDesvio listas;
switch (cond.tipo) {
case TipoAst::Comparacao: {
const std::string esquerda =
cond.filhos.size() > 0 && cond.filhos[0]
? traduzirValor(*cond.filhos[0])
: "<indefinido>";
const std::string direita =
cond.filhos.size() > 1 && cond.filhos[1]
? traduzirValor(*cond.filhos[1])
: "<indefinido>";
const std::string t = novoTemporario();
InstrucaoRI comparacao;
comparacao.op = OpRI::Comparacao;
comparacao.resultado = t;
comparacao.arg1 = esquerda;
comparacao.arg2 = direita;
comparacao.operador = cond.texto;
emitir(std::move(comparacao));
InstrucaoRI desvio;
desvio.op = OpRI::DesvioSeFalso;
desvio.arg1 = t;
const std::size_t indice = emitir(std::move(desvio));
// Quando a comparação é falsa, desvia — destino a preencher.
// Quando é verdadeira, cai para a instrução seguinte, e essa
// "queda" é o caminho verdadeiro. Não emitir desvio para o caso
// verdadeiro é o que mantém o código curto.
listas.falso.push_back(indice);
return listas;
}
case TipoAst::E: {
// Curto-circuito do E: se o lado esquerdo falha, a expressão
// inteira falha e o direito NÃO é avaliado. O caminho verdadeiro do
// esquerdo cai no início do direito; as saídas falsas dos dois se
// juntam.
if (cond.filhos.size() < 2 || !cond.filhos[0] || !cond.filhos[1]) {
return listas;
}
ListasDeDesvio esquerda = traduzirCondicao(*cond.filhos[0]);
// O verdadeiro do esquerdo aponta para onde o direito começa, que é
// a próxima instrução a ser emitida.
preencher(esquerda.verdadeiro, instrucoes_.size());
ListasDeDesvio direita = traduzirCondicao(*cond.filhos[1]);
listas.verdadeiro = std::move(direita.verdadeiro);
listas.falso = std::move(esquerda.falso);
for (const std::size_t i : direita.falso) {
listas.falso.push_back(i);
}
return listas;
}
case TipoAst::Ou: {
// Curto-circuito do OU, simétrico: se o esquerdo é verdadeiro, a
// expressão inteira é verdadeira. O caminho FALSO do esquerdo cai
// no direito.
if (cond.filhos.size() < 2 || !cond.filhos[0] || !cond.filhos[1]) {
return listas;
}
ListasDeDesvio esquerda = traduzirCondicao(*cond.filhos[0]);
// O verdadeiro do esquerdo tem de pular o lado direito inteiro, e
// esse destino ainda não existe. Um desvio incondicional carrega a
// pendência adiante.
InstrucaoRI salto;
salto.op = OpRI::Desvio;
const std::size_t indiceSalto = emitir(std::move(salto));
preencher(esquerda.verdadeiro, indiceSalto);
preencher(esquerda.falso, instrucoes_.size());
ListasDeDesvio direita = traduzirCondicao(*cond.filhos[1]);
listas.verdadeiro.push_back(indiceSalto);
for (const std::size_t i : direita.verdadeiro) {
listas.verdadeiro.push_back(i);
}
listas.falso = std::move(direita.falso);
return listas;
}
default:
return listas;
}
}
CodigoRI TradutorRI::traduzirAcao(const NoAst& acao) {
instrucoes_.clear();
proximoTemporario_ = 0;
CodigoRI codigo;
codigo.padrao = acao.texto;
codigo.ligacao = acao.conteudo;
ListasDeDesvio listas;
const bool temCondicao = !acao.filhos.empty() && acao.filhos[0] != nullptr;
if (temCondicao) {
listas = traduzirCondicao(*acao.filhos[0]);
// O caminho verdadeiro segue para a emissão, que é a próxima
// instrução.
preencher(listas.verdadeiro, instrucoes_.size());
}
// A emissão.
if (!acao.filhos.empty() && acao.filhos.back() &&
acao.filhos.back()->tipo == TipoAst::Emissao) {
const NoAst& emissao = *acao.filhos.back();
std::string valor = "<indefinido>";
if (!emissao.filhos.empty() && emissao.filhos[0]) {
valor = traduzirValor(*emissao.filhos[0]);
}
InstrucaoRI ins;
ins.op = OpRI::Emite;
ins.arg1 = "\"" + emissao.texto + "\"";
ins.arg2 = valor;
emitir(std::move(ins));
}
// Fim da regra. Todo desvio de condição falsa termina aqui, e este é o
// momento em que o endereço finalmente se conhece: é o índice logo após a
// última instrução.
preencher(listas.falso, instrucoes_.size());
codigo.instrucoes = std::move(instrucoes_);
return codigo;
}
std::string formatarRI(const CodigoRI& c) {
std::ostringstream out;
out << " regra: on " << c.padrao << "(" << c.ligacao << ")\n";
for (std::size_t i = 0; i < c.instrucoes.size(); ++i) {
const InstrucaoRI& ins = c.instrucoes[i];
out << " " << i << ": ";
switch (ins.op) {
case OpRI::Constante:
out << ins.resultado << " := " << ins.arg1;
break;
case OpRI::CasamentoDe:
out << ins.resultado << " := casamento " << ins.arg1;
break;
case OpRI::Valor:
out << ins.resultado << " := valor " << ins.arg1;
break;
case OpRI::Comparacao:
out << ins.resultado << " := " << ins.arg1 << " "
<< ins.operador << " " << ins.arg2;
break;
case OpRI::DesvioSeFalso:
out << "se_falso " << ins.arg1 << " desvia para "
<< ins.destino;
break;
case OpRI::Desvio:
out << "desvia para " << ins.destino;
break;
case OpRI::Emite:
out << "emite " << ins.arg1 << ", " << ins.arg2;
break;
case OpRI::Rotulo:
out << "rotulo " << ins.resultado;
break;
}
out << '\n';
}
out << " " << c.instrucoes.size() << ": (fim da regra)\n";
return out.str();
}
std::string emPosFixada(const NoAst& expr) {
switch (expr.tipo) {
case TipoAst::LiteralNumero:
case TipoAst::LiteralTexto:
return expr.texto;
case TipoAst::Referencia:
return expr.texto;
case TipoAst::ValorDe:
return expr.texto + " valor";
case TipoAst::Comparacao: {
const std::string e = expr.filhos.size() > 0 && expr.filhos[0]
? emPosFixada(*expr.filhos[0])
: "";
const std::string d = expr.filhos.size() > 1 && expr.filhos[1]
? emPosFixada(*expr.filhos[1])
: "";
return e + " " + d + " " + expr.texto;
}
case TipoAst::E:
case TipoAst::Ou: {
const std::string e = expr.filhos.size() > 0 && expr.filhos[0]
? emPosFixada(*expr.filhos[0])
: "";
const std::string d = expr.filhos.size() > 1 && expr.filhos[1]
? emPosFixada(*expr.filhos[1])
: "";
return e + " " + d + (expr.tipo == TipoAst::E ? " and" : " or");
}
default:
return "";
}
}
CustoDeTraducao custoDeTraducao(std::size_t origens,
std::size_t destinos) noexcept {
CustoDeTraducao c;
c.origens = origens;
c.destinos = destinos;
c.tradutoresDiretos = origens * destinos;
c.tradutoresComIntermediaria = origens + destinos;
return c;
}
} // namespace peneiraUma decisão de tradução merece destaque porque não é óbvia. A construção value(n) vira duas instruções, e não uma: primeiro o casamento é buscado, depois convertido.
0: t0 := casamento n
1: t1 := valor t0Poderia ser uma instrução só, e seria mais curto. Separei porque a conversão é justamente o que a análise semântica do módulo 12 exigiu que fosse explícita no programa fonte — foi a razão de recusar conversão implícita. Colapsá-la aqui esconderia na representação intermediária a distinção que a fase anterior lutou para tornar visível.
Sobre a forma de atribuição única estática, que a ementa menciona: ela não foi implementada, e o motivo é que ela existe para viabilizar otimizações sobre fluxo de dados que este compilador não faz. Registro a ausência em vez de fingir cobertura.
Registro também um limite do artefato, porque ele afeta o que este módulo consegue demonstrar. A tradução de condicionais está exercitada — a condição where é um condicional, e é dela que saem os desvios acima. A de laços não está, porque a Peneira não tem laço nenhum no nível do usuário: a repetição da linguagem é o laço de varredura do executor, que é parte do modelo de execução e não uma construção que o programador escreva. O mecanismo é o mesmo e a diferença é uma só: um laço precisa de desvio para trás, para uma instrução já emitida, e por isso o seu destino é conhecido no momento em que o desvio é gerado — é o caso fácil, não o difícil. Tudo que aparece aqui é desvio para a frente, que é justamente o que exige o preenchimento retroativo. Um grupo cuja linguagem tenha laços encontra as duas situações; o nosso só encontra a pior delas.
Onde é fácil errar aqui. Escolher a representação pela elegância e descobrir depois que ela não exprime o que a linguagem precisa. A pós-fixada é claramente a mais bonita das três aqui, e é a errada. O teste tem de ser feito contra a construção mais difícil da linguagem — no nosso caso, a condição composta —, não contra a mais fácil.
Como verificar. Cada instrução gerada tem de ter destino definido e cada temporário tem de ser escrito antes de lido. A demonstração --formasri imprime as três formas lado a lado, e a contagem de temporários fecha com o número de subexpressões da condição.
1.4 Tarefa 3: O formato do objeto, e a divergência que precisei resolver
A atividade — especificar o formato do programa objeto, completo o bastante para permitir implementação independente.
Este é o entregável principal, e escrevi a especificação antes do código, que é a ordem que a atividade exige e a que os grupos costumam inverter. O arquivo de cabeçalho é a especificação — os campos vêm com semântica declarada, não apenas com nome:
13_objeto.h
#ifndef PENEIRA_13_OBJETO_H
#define PENEIRA_13_OBJETO_H
#include <cstddef>
#include <cstdint>
#include <string>
#include <vector>
#include "03_afd.h"
namespace peneira {
// O FORMATO DO PROGRAMA OBJETO DA PENEIRA.
//
// Este cabeçalho é a especificação. O critério de qualidade anunciado para o
// módulo é literal: outra pessoa tem de conseguir escrever um executor
// compatível lendo apenas isto. Por isso os campos vêm com semântica declarada,
// e não apenas com nome.
//
// O objeto tem duas seções, conforme o design do artefato:
//
// 1. A TABELA DE PADRÕES — um autômato finito determinístico por `pattern`,
// serializado como tabela de transição.
// 2. O CÓDIGO DAS REGRAS — para cada ação, uma sequência de instruções de uma
// máquina de pilha.
//
// A escolha de máquina de pilha, e não de registradores, tem motivo: as
// expressões da Peneira são rasas (uma comparação, no máximo alguns conectivos)
// e a máquina de pilha dispensa alocação de registradores por completo. Numa
// linguagem com expressões profundas a conta se inverteria.
// ---------------------------------------------------------------------------
// Conjunto de instruções
// ---------------------------------------------------------------------------
//
// As sete primeiras vêm do design do artefato. As duas de desvio são
// ACRÉSCIMO DELIBERADO, e registro o porquê em vez de silenciá-lo: o design
// lista `AND` e `OR` como instruções, o que implica avaliação ansiosa dos dois
// lados; o curto-circuito exigido na geração de código do módulo seguinte não
// é exprimível sem desvio. Mantive `AND` e `OR` no conjunto — elas continuam
// válidas e são o que um gerador ansiado emitiria — e acrescentei os desvios,
// que são o que o nosso gerador vai usar. Um executor compatível precisa
// implementar as nove.
enum class OpCode : std::uint8_t {
PUSH_CONST = 0, // empilha a constante de índice `argumento`
PUSH_MATCH = 1, // empilha o texto casado pela ligação de índice `argumento`
VALUE = 2, // desempilha texto, empilha o número correspondente
CMP_GT = 3, // desempilha b, a; empilha (a > b)
CMP_LT = 4,
CMP_GE = 5,
CMP_LE = 6,
CMP_EQ = 7,
CMP_NE = 8,
AND = 9, // desempilha b, a; empilha (a e b) — avaliação ansiosa
OR = 10, // desempilha b, a; empilha (a ou b) — avaliação ansiosa
JUMP_IF_FALSE = 11, // desempilha; se falso, desvia para `argumento`
JUMP = 12, // desvia para `argumento`
EMIT = 13, // desempilha valor; emite com o rótulo de índice `argumento`
HALT = 14, // encerra a execução desta regra
};
const char* nomeDoOpCode(OpCode op) noexcept;
// Toda instrução ocupa dois campos: o código e um argumento inteiro. As que não
// usam argumento gravam zero. O tamanho fixo é decisão consciente — dispensa
// decodificação de comprimento variável no executor, ao custo de alguns bytes
// que não importam nesta escala.
struct Instrucao {
OpCode op = OpCode::HALT;
std::uint32_t argumento = 0;
};
// ---------------------------------------------------------------------------
// Seções do objeto
// ---------------------------------------------------------------------------
// Um padrão compilado, serializado como tabela de transição.
//
// `transicoes` é a matriz achatada: a transição do estado `e` pelo símbolo `s`
// está em `transicoes[e * 256 + s]`. O valor kSemTransicao marca ausência, que
// o executor trata como falha de casamento.
//
// A matriz densa é escolha de FORMATO, e diverge da representação esparsa que o
// compilador usa internamente desde o módulo 3. O motivo é que os papéis são
// diferentes: dentro do compilador, o autômato é construído e transformado, e a
// esparsa economiza memória num alfabeto de 256 símbolos; no objeto, ele só é
// consultado, e a densa dá consulta em tempo constante sem busca. Trocar de
// representação na fronteira entre as duas fases é a decisão certa, e é o tipo
// de coisa que só fica evidente quando a especificação é escrita antes do
// código.
inline constexpr std::uint32_t kSemTransicao = 0xFFFFFFFFu;
inline constexpr std::size_t kTamanhoDoAlfabeto = 256;
struct PadraoObjeto {
std::string nome;
std::uint32_t quantidadeDeEstados = 0;
std::uint32_t estadoInicial = 0;
std::vector<std::uint8_t> finais; // 1 por estado
std::vector<std::uint32_t> transicoes; // achatada, 256 por estado
bool casaSomenteNumeros = false; // do verificador de tipos
};
// O código de uma regra.
struct RegraObjeto {
std::uint32_t indiceDoPadrao = 0; // qual padrão dispara esta regra
std::string ligacao; // nome da variável, para diagnóstico
std::vector<Instrucao> codigo;
};
// O programa objeto completo.
struct ProgramaObjeto {
// Constantes agrupadas numa área única, referenciadas por índice. Textos e
// números moram no mesmo vetor, na forma textual: a distinção de tipo já
// foi resolvida na análise semântica, e o executor sabe qual instrução lê o
// quê.
std::vector<std::string> constantes;
std::vector<PadraoObjeto> padroes;
std::vector<RegraObjeto> regras;
// Registra a constante e devolve o índice, reaproveitando se já existir.
std::uint32_t adicionarConstante(const std::string& valor);
};
// Converte o autômato interno para a forma do objeto.
PadraoObjeto serializarPadrao(const Afd& afd, const std::string& nome,
bool casaSomenteNumeros);
// Forma textual do objeto, legível e suficiente para conferência manual.
std::string formatarObjeto(const ProgramaObjeto& p);
// O MODELO DE EXECUÇÃO, em texto, para acompanhar a especificação dos campos.
// Está em código, e não só no material, porque a especificação e o
// implementador precisam ler a mesma coisa.
std::string modeloDeExecucao();
} // namespace peneira
#endif // PENEIRA_13_OBJETO_HO objeto tem duas seções, conforme o design do artefato: uma tabela com um autômato determinístico por padrão, e o código das regras para uma máquina de pilha. A escolha de máquina de pilha em vez de registradores se justifica porque as expressões da Peneira são rasas — uma comparação, no máximo alguns conectivos — e a pilha dispensa alocação de registradores por completo. Numa linguagem com expressões profundas a conta se inverteria.
1.4.1 A divergência, e como a resolvi
Ao escrever o conjunto de instruções encontrei um conflito entre dois documentos que eu mesmo tinha produzido, e prefiro registrá-lo a silenciá-lo.
O design do artefato lista sete instruções, entre elas AND e OR. Ter AND e OR como instruções significa avaliação ansiosa: os dois operandos são calculados e empilhados, e a instrução combina. Só que a especificação do projeto integrador exige, para o módulo seguinte, que a avaliação com curto-circuito seja tratada — e curto-circuito não é exprimível sem desvio.
Resolvi acrescentando duas instruções de desvio ao conjunto e mantendo AND e OR, e registrando a decisão no próprio cabeçalho. As sete originais continuam válidas e são o que um gerador ansioso emitiria; os desvios são o que o nosso gerador vai usar. Acrescentei também as demais comparações, já que o design nomeia CMP_GT como representante de uma família e não como uma instrução isolada. O conjunto fica, portanto, com quinze códigos de operação: as sete do design original, as duas de desvio que acabo de justificar, e as seis da família de comparação — e é essa a conta que um executor compatível precisa implementar. Quando o texto fala em nove instruções, refere-se ao núcleo do design com CMP_GT valendo pela família inteira; o cabeçalho expande a família, e é ele que vale.
O que não fiz foi mudar o design em silêncio nem torcer o conjunto de instruções para caber na lista original. Divergência entre documentos de projeto acontece; o que não pode acontecer é ela ser resolvida sem ficar escrita.
1.4.2 A decisão de formato que a especificação revelou
Escrever a especificação antes fez aparecer uma decisão que eu teria tomado errado por inércia. Dentro do compilador, a função de transição é um mapa esparso por estado — decisão do módulo 3, tomada porque o alfabeto tem 256 símbolos e a maior parte não é usada. No objeto, gravei uma matriz densa.
A troca é deliberada, porque os papéis são diferentes: dentro do compilador o autômato é construído e transformado, e a esparsa economiza; no objeto ele só é consultado, e a densa dá consulta em tempo constante sem busca.
E aqui a medição desmente a intuição confortável. A demonstração --objeto imprime a densidade real:
[0] numero: 5 estados, inicial 0, 2 final(is)
celulas: 1280, preenchidas: 52Quatro por cento. A matriz densa desperdiça noventa e seis por cento do espaço que ocupa, e não adianta esconder isso. A defesa da escolha tem de ser feita com o número na mesa: são 5120 bytes por padrão, o laço interno do executor consulta essa tabela uma vez por byte da entrada, e nessa posição a consulta em tempo constante vale mais que os kilobytes. A defesa tem prazo de validade — se o número de padrões crescer a ponto de as tabelas não caberem em cache, a decisão precisa ser revista, e é esse número impresso que vai permitir notar.
1.4.3 O modelo de execução
A especificação dos campos não basta: quem for escrever o executor precisa saber o que a máquina faz com eles. O modelo está no código, e não só neste texto, porque a especificação e o implementador precisam ler a mesma coisa:
13_objeto.cpp
#include "13_objeto.h"
#include <sstream>
namespace peneira {
const char* nomeDoOpCode(OpCode op) noexcept {
switch (op) {
case OpCode::PUSH_CONST: return "PUSH_CONST";
case OpCode::PUSH_MATCH: return "PUSH_MATCH";
case OpCode::VALUE: return "VALUE";
case OpCode::CMP_GT: return "CMP_GT";
case OpCode::CMP_LT: return "CMP_LT";
case OpCode::CMP_GE: return "CMP_GE";
case OpCode::CMP_LE: return "CMP_LE";
case OpCode::CMP_EQ: return "CMP_EQ";
case OpCode::CMP_NE: return "CMP_NE";
case OpCode::AND: return "AND";
case OpCode::OR: return "OR";
case OpCode::JUMP_IF_FALSE: return "JUMP_IF_FALSE";
case OpCode::JUMP: return "JUMP";
case OpCode::EMIT: return "EMIT";
case OpCode::HALT: return "HALT";
}
return "<desconhecido>";
}
std::uint32_t ProgramaObjeto::adicionarConstante(const std::string& valor) {
for (std::size_t i = 0; i < constantes.size(); ++i) {
if (constantes[i] == valor) {
return static_cast<std::uint32_t>(i);
}
}
constantes.push_back(valor);
return static_cast<std::uint32_t>(constantes.size() - 1);
}
PadraoObjeto serializarPadrao(const Afd& afd, const std::string& nome,
bool casaSomenteNumeros) {
PadraoObjeto p;
p.nome = nome;
p.quantidadeDeEstados = static_cast<std::uint32_t>(afd.quantidadeDeEstados());
p.estadoInicial = static_cast<std::uint32_t>(afd.inicial());
p.casaSomenteNumeros = casaSomenteNumeros;
p.finais.resize(afd.quantidadeDeEstados(), 0);
p.transicoes.assign(afd.quantidadeDeEstados() * kTamanhoDoAlfabeto,
kSemTransicao);
for (std::size_t e = 0; e < afd.quantidadeDeEstados(); ++e) {
p.finais[e] = afd.ehFinal(e) ? std::uint8_t{1} : std::uint8_t{0};
for (std::size_t s = 0; s < kTamanhoDoAlfabeto; ++s) {
const Estado destino =
afd.transicao(e, static_cast<Simbolo>(s));
if (destino != kSemEstado) {
p.transicoes[e * kTamanhoDoAlfabeto + s] =
static_cast<std::uint32_t>(destino);
}
}
}
return p;
}
std::string formatarObjeto(const ProgramaObjeto& p) {
std::ostringstream out;
out << " area de constantes (" << p.constantes.size() << "):\n";
for (std::size_t i = 0; i < p.constantes.size(); ++i) {
out << " [" << i << "] " << p.constantes[i] << '\n';
}
out << "\n tabela de padroes (" << p.padroes.size() << "):\n";
for (std::size_t i = 0; i < p.padroes.size(); ++i) {
const PadraoObjeto& pd = p.padroes[i];
// Conta as transições preenchidas para mostrar a densidade real da
// matriz — o número que justifica ou condena a escolha de formato.
std::size_t preenchidas = 0;
for (const std::uint32_t t : pd.transicoes) {
if (t != kSemTransicao) {
++preenchidas;
}
}
std::size_t finais = 0;
for (const std::uint8_t f : pd.finais) {
finais += f;
}
out << " [" << i << "] " << pd.nome << ": "
<< pd.quantidadeDeEstados << " estados, inicial "
<< pd.estadoInicial << ", " << finais << " final(is)\n"
<< " celulas: " << pd.transicoes.size() << ", preenchidas: "
<< preenchidas << '\n'
<< " casa somente numeros: "
<< (pd.casaSomenteNumeros ? "sim" : "nao") << '\n';
}
out << "\n codigo das regras (" << p.regras.size() << "):\n";
for (std::size_t i = 0; i < p.regras.size(); ++i) {
const RegraObjeto& r = p.regras[i];
out << " regra [" << i << "] padrao ["
<< r.indiceDoPadrao << "] ligacao '" << r.ligacao << "'\n";
for (std::size_t k = 0; k < r.codigo.size(); ++k) {
const Instrucao& ins = r.codigo[k];
out << " " << k << ": " << nomeDoOpCode(ins.op);
switch (ins.op) {
case OpCode::PUSH_CONST:
case OpCode::EMIT:
out << " " << ins.argumento << " ; "
<< (ins.argumento < p.constantes.size()
? p.constantes[ins.argumento]
: std::string("<fora de faixa>"));
break;
case OpCode::PUSH_MATCH:
case OpCode::JUMP:
case OpCode::JUMP_IF_FALSE:
out << " " << ins.argumento;
break;
default:
break;
}
out << '\n';
}
}
return out.str();
}
std::string modeloDeExecucao() {
// Escrito como contrato para quem for implementar o executor, e não como
// descrição do que o nosso executor faz — ainda não existe executor. A
// diferença importa: um descreve o que se pode assumir, o outro descreve o
// que aconteceu de ser implementado.
return
" ESTADO DA MAQUINA\n"
" - a entrada, lida como sequencia de bytes\n"
" - uma posicao de leitura, que so avanca\n"
" - uma pilha de valores, vazia no inicio de cada regra\n"
" - o ambiente de casamento: o texto casado e o padrao que casou\n\n"
" LACO PRINCIPAL\n"
" Na posicao corrente, o executor tenta TODOS os padroes em\n"
" paralelo, avancando enquanto algum automato ainda tem transicao.\n"
" Registra a ultima posicao em que algum automato esteve em estado\n"
" final, e qual padrao. Ao travar, retrocede ate essa posicao: e a\n"
" regra do CASAMENTO MAIS LONGO, a mesma do analisador lexico.\n"
" Empate entre padroes no mesmo comprimento resolve-se pela ORDEM DE\n"
" DECLARACAO no programa fonte — o primeiro declarado vence.\n"
" Sem casamento nenhum, a posicao avanca um byte e o laco recomeca.\n\n"
" DISPARO DA REGRA\n"
" Com um casamento, o executor liga o texto casado a variavel da\n"
" regra correspondente e executa o codigo daquela regra desde a\n"
" instrucao 0, com a pilha vazia. A execucao termina em HALT ou ao\n"
" passar da ultima instrucao.\n"
" Terminada a regra, a posicao de leitura avanca para o fim do\n"
" casamento e o laco principal recomeca.\n\n"
" SEMANTICA DAS INSTRUCOES\n"
" PUSH_CONST k empilha constantes[k]\n"
" PUSH_MATCH k empilha o texto casado (k identifica a ligacao)\n"
" VALUE desempilha texto, empilha o numero que ele denota\n"
" CMP_* desempilha b, depois a; empilha o resultado de a<op>b\n"
" AND / OR desempilha b, depois a; empilha a combinacao\n"
" JUMP_IF_FALSE k desempilha; se falso, a proxima instrucao e k\n"
" JUMP k a proxima instrucao e k\n"
" EMIT k desempilha o valor e emite o par (constantes[k], valor)\n"
" HALT encerra esta regra\n\n"
" CONDICOES DE ERRO QUE O EXECUTOR PRECISA TRATAR\n"
" - VALUE sobre texto que nao denota numero: nao pode ocorrer, porque\n"
" a analise semantica provou por inclusao de linguagens que o\n"
" padrao so casa numeros. Um executor defensivo aborta com\n"
" diagnostico em vez de produzir valor arbitrario.\n"
" - desvio para fora da faixa de instrucoes: objeto malformado.\n"
" - pilha vazia numa instrucao que desempilha: objeto malformado.\n";
}
} // namespace peneiraTrês pontos do modelo mereceram decisão explícita, e são justamente os que faltariam numa especificação apressada. O casamento mais longo é a mesma regra do analisador léxico do módulo 7, e reusá-la é o que mantém a linguagem coerente consigo mesma. O empate entre padrões de mesmo comprimento resolve-se pela ordem de declaração no fonte — precisa estar escrito, porque sem isso dois executores corretos produziriam saídas diferentes para o mesmo programa. E as condições de erro estão listadas, inclusive uma que não pode ocorrer: VALUE sobre texto não numérico é impossível porque a análise semântica provou por inclusão de linguagens que o padrão só casa números — e mesmo assim o executor defensivo deve abortar com diagnóstico, em vez de produzir valor arbitrário se o objeto tiver sido adulterado.
A seção de regras sai vazia nesta demonstração, e de propósito: preenchê-la é geração de código, que é o módulo seguinte. Este módulo entrega o formato e a representação intermediária; o próximo traduz uma na outra.
Onde é fácil errar aqui. Especificar depois de implementar. A especificação escrita a partir do código já existente documenta as decisões acidentais junto com as deliberadas, e não tem como distinguir umas das outras — quem lê não sabe o que pode assumir. As duas decisões acima, a matriz densa e o desempate por ordem de declaração, só apareceram como decisões porque a especificação veio antes.
Como verificar. O critério literal: entregar apenas a especificação a alguém e pedir que descreva o que o executor faz com uma entrada dada. Onde a pessoa precisar perguntar, falta texto. Foi assim que descobri que o desempate entre padrões não estava especificado.
1.5 Tarefa 4: O ambiente de execução
A atividade — descrever a organização da memória em execução e o que o compilador precisa emitir para sustentá-la.
13_ambiente.h
#ifndef PENEIRA_13_AMBIENTE_H
#define PENEIRA_13_AMBIENTE_H
#include <cstddef>
#include <cstdint>
#include <string>
#include <vector>
namespace peneira {
// AMBIENTES DE EXECUÇÃO.
//
// Duas coisas moram neste arquivo, e é preciso separá-las com clareza porque
// só a primeira é o nosso artefato:
//
// 1. O ambiente de execução DA PENEIRA — a divisão de memória que o programa
// objeto exige e o registro de ativação de uma regra. Isso é o sistema.
//
// 2. Um EXEMPLO MÍNIMO ISOLADO de registro de ativação com procedimentos
// aninhados, cadeia de controle e cadeia de acesso. Isso NÃO faz parte do
// compilador da Peneira, e não faria sentido embutir: a linguagem não tem
// procedimentos definidos pelo usuário, e inventar uns só para exercitar
// o mecanismo distorceria o artefato. Fica aqui como exemplo separado,
// pelo mesmo padrão do exemplo de tradução do módulo 1.
//
// O motivo de não omitir o segundo é que ele é o repertório necessário para ler
// qualquer linguagem real, e a conexão com a organização de memória vista em
// arquitetura de computadores é direta.
// ---------------------------------------------------------------------------
// 1. O ambiente de execução da Peneira
// ---------------------------------------------------------------------------
// As quatro áreas em que a memória de um programa em execução se divide, com o
// que cada uma guarda no caso da Peneira. Tamanho zero significa "cresce em
// execução".
enum class AreaDeMemoria : std::uint8_t {
Codigo, // o código das regras; imutável, tamanho conhecido na compilação
Estatica, // constantes e tabelas de transição; tamanho conhecido também
Pilha, // a pilha de avaliação da regra corrente
Monte, // o texto casado, cujo tamanho só se conhece em execução
};
const char* nomeDaArea(AreaDeMemoria a) noexcept;
struct DescricaoDeArea {
AreaDeMemoria area;
std::string conteudo;
bool tamanhoConhecidoNaCompilacao = false;
std::size_t bytesNesteObjeto = 0; // 0 quando cresce em execução
};
// Descreve o mapa de memória do objeto dado, com os tamanhos reais das áreas
// estáticas. É o que permite dizer, com número, quanto do programa é decidido
// na compilação e quanto sobra para a execução.
struct ProgramaObjeto; // declarado em 13_objeto.h
std::vector<DescricaoDeArea> mapaDeMemoria(const ProgramaObjeto& objeto);
// O registro de ativação de uma regra da Peneira.
//
// A Peneira não tem chamada de procedimento, e mesmo assim tem registro de
// ativação — porque disparar uma regra É uma ativação: há um ponto de entrada,
// um conjunto de valores ligados na entrada, um espaço de trabalho próprio e um
// retorno. O registro é pequeno porque a linguagem é pequena, e mostrar que ele
// existe é o que liga o conceito ao artefato em vez de deixá-lo abstrato.
struct AtivacaoDeRegra {
std::uint32_t regra = 0;
std::size_t posicaoNaEntrada = 0; // onde o casamento começou
std::string textoCasado; // o parâmetro, em essência
std::size_t topoDaPilha = 0; // espaço de trabalho
std::size_t enderecoDeRetorno = 0; // para onde o laço principal volta
};
std::string descreverAtivacao(const AtivacaoDeRegra& a);
// Por que NÃO há cadeia de controle nem de acesso na Peneira: as ativações não
// se aninham. Uma regra dispara, executa e termina antes de a próxima começar,
// então a "pilha" de ativações tem no máximo um elemento. É o que torna o
// registro acima um registro só, e não uma pilha deles.
std::size_t profundidadeMaximaDeAtivacao() noexcept;
// ---------------------------------------------------------------------------
// 2. Exemplo mínimo isolado: aninhamento, cadeia de controle e de acesso
// ---------------------------------------------------------------------------
//
// NÃO faz parte do compilador da Peneira. Existe para exercitar o mecanismo que
// a linguagem não tem, sobre um programa hipotético com procedimentos
// aninhados.
// Um procedimento do exemplo: nome, nível de aninhamento léxico e quem o
// contém.
struct ProcedimentoExemplo {
std::string nome;
std::size_t nivelLexico = 0;
std::size_t contidoEm = 0; // índice do procedimento envolvente
};
// Um quadro na pilha de execução do exemplo.
struct Quadro {
std::size_t procedimento = 0;
// Cadeia de CONTROLE: quem me chamou. Segue a ordem de EXECUÇÃO.
std::size_t eloDeControle = 0;
// Cadeia de ACESSO: o quadro do procedimento que me CONTÉM no texto do
// programa. Segue a ordem LÉXICA. As duas coincidem em muitos casos e
// divergem exatamente quando a recursão ou a chamada cruzada entram —
// e é essa divergência que justifica manter as duas.
std::size_t eloDeAcesso = 0;
bool temElo = false;
};
// Os procedimentos do exemplo: um programa principal contendo `externo`, que
// contém `interno`.
const std::vector<ProcedimentoExemplo>& procedimentosDoExemplo();
// Simula a sequência de chamadas dada (por índice de procedimento) e devolve a
// pilha de quadros resultante, com as duas cadeias montadas.
std::vector<Quadro> simularChamadas(const std::vector<std::size_t>& chamadas);
std::string desenharPilha(const std::vector<Quadro>& pilha);
// Resolve o acesso a uma variável declarada no nível léxico dado, a partir do
// topo da pilha, seguindo a cadeia de ACESSO. Devolve o índice do quadro que a
// contém, ou o tamanho da pilha se não achar.
//
// É este percurso que torna a cadeia de acesso necessária: seguir a de controle
// aqui daria a variável do chamador, que pode não ser o mesmo procedimento que
// envolve este no texto.
std::size_t resolverAcesso(const std::vector<Quadro>& pilha,
std::size_t nivelLexicoAlvo);
} // namespace peneira
#endif // PENEIRA_13_AMBIENTE_HA memória de um programa Peneira em execução divide-se em quatro áreas, e a divisão útil não é a nominal — é a que separa o que o compilador sabe do que só a execução descobre:
area | tamanho conhecido na compilacao | bytes
---------+--------------------------------+-------
codigo | sim | 0
estatica | sim | 5137
pilha | nao | cresce
monte | nao | cresceO código das regras e a área estática — tabelas de transição e constantes — têm tamanho fixado na compilação. A pilha de avaliação cresce em execução, mas com um detalhe que vale registrar: a profundidade máxima dela é conhecida na compilação, porque é a da expressão mais aninhada do programa. É informação que o compilador poderia emitir no objeto para o executor pré-alocar, e anoto como possibilidade não implementada em vez de deixar implícito. Só o texto casado é genuinamente dinâmico, porque o comprimento do casamento só se conhece ao casar.
A área de código aparece com zero bytes porque o módulo 14 ainda não emitiu nada. Essa linha da tabela custou uma correção: na primeira versão, tamanho zero e tamanho dinâmico apareciam iguais, e a área de código — que é a mais estática de todas — parecia crescer em execução. Distinguir “zero” de “cresce” é o tipo de detalhe que só aparece rodando.
1.5.1 O registro de ativação de uma regra
A Peneira não tem chamada de procedimento e mesmo assim tem registro de ativação, porque disparar uma regra é uma ativação: há entrada, valores ligados na entrada, espaço de trabalho próprio e retorno.
registro de ativacao da regra 0:
posicao na entrada ... 42
texto casado ......... "250" (3 bytes)
topo da pilha ........ 0
endereco de retorno .. 45O texto casado é, em essência, o parâmetro; o endereço de retorno é para onde o laço principal volta. Mostrar que o registro existe neste artefato é o que liga o conceito ao projeto, em vez de deixá-lo abstrato.
E há um resultado que decide o resto: a profundidade máxima da pilha de ativações é um. Uma regra termina antes de a próxima começar, então as ativações não se aninham. É por isso que a Peneira não precisa de cadeia de controle nem de cadeia de acesso — e é por isso que esse mecanismo, que a ementa pede, não cabe no sistema principal.
Onde é fácil errar aqui. Descrever a divisão de memória copiando a divisão clássica de uma linguagem com procedimentos, sem verificar quais áreas a linguagem do grupo realmente usa. Uma linguagem sem alocação dinâmica não tem monte, e listá-lo mesmo assim é preencher formulário.
Como verificar. Some os bytes das áreas estáticas e compare com o tamanho do objeto gravado. Se não bater, alguma coisa está sendo emitida sem estar no mapa.
1.6 Tarefa 5: O mecanismo que a linguagem dispensa
A atividade — explicar o protocolo de chamada e retorno, o escopo em tempo de execução e as cadeias de acesso e de controle.
A ementa pede este conteúdo e a Peneira não o exercita. Tinha duas saídas ruins e escolhi uma terceira.
A primeira saída ruim seria omitir, alegando que o artefato não usa. É o repertório necessário para ler qualquer linguagem real, e a conexão com a organização de memória vista em arquitetura de computadores é direta demais para ser desperdiçada.
A segunda seria inventar procedimentos na Peneira só para exercitar o mecanismo. Distorceria o artefato: a linguagem não precisa deles, e acrescentá-los por razão didática produziria uma característica que nenhuma outra parte do sistema usa — exatamente o que os módulos 9 e 11 recusaram fazer com o autômato de pilha e o gerador ascendente.
A terceira, que é a que tomei, é manter um exemplo mínimo isolado dentro do projeto, claramente separado do sistema principal — o mesmo padrão do exemplo de interpretação contra compilação do módulo 1:
13_ambiente.cpp
#include "13_ambiente.h"
#include <sstream>
#include "13_objeto.h"
namespace peneira {
const char* nomeDaArea(AreaDeMemoria a) noexcept {
switch (a) {
case AreaDeMemoria::Codigo: return "codigo";
case AreaDeMemoria::Estatica: return "estatica";
case AreaDeMemoria::Pilha: return "pilha";
case AreaDeMemoria::Monte: return "monte";
}
return "<desconhecida>";
}
std::vector<DescricaoDeArea> mapaDeMemoria(const ProgramaObjeto& objeto) {
std::vector<DescricaoDeArea> areas;
std::size_t bytesDeCodigo = 0;
for (const RegraObjeto& r : objeto.regras) {
bytesDeCodigo += r.codigo.size() * sizeof(Instrucao);
}
std::size_t bytesEstaticos = 0;
for (const PadraoObjeto& p : objeto.padroes) {
bytesEstaticos += p.transicoes.size() * sizeof(std::uint32_t);
bytesEstaticos += p.finais.size() * sizeof(std::uint8_t);
}
for (const std::string& c : objeto.constantes) {
bytesEstaticos += c.size();
}
areas.push_back(DescricaoDeArea{
AreaDeMemoria::Codigo,
"o codigo das regras; imutavel e nunca realocado", true,
bytesDeCodigo});
areas.push_back(DescricaoDeArea{
AreaDeMemoria::Estatica,
"tabelas de transicao dos padroes e area de constantes", true,
bytesEstaticos});
areas.push_back(DescricaoDeArea{
AreaDeMemoria::Pilha,
"pilha de avaliacao da regra corrente; profundidade limitada pela "
"expressao mais aninhada, conhecida na compilacao",
false, 0});
areas.push_back(DescricaoDeArea{
AreaDeMemoria::Monte,
"o texto casado, cujo comprimento so se conhece ao casar", false, 0});
return areas;
}
std::string descreverAtivacao(const AtivacaoDeRegra& a) {
std::ostringstream out;
out << " registro de ativacao da regra " << a.regra << ":\n"
<< " posicao na entrada ... " << a.posicaoNaEntrada << '\n'
<< " texto casado ......... \"" << a.textoCasado << "\" ("
<< a.textoCasado.size() << " bytes)\n"
<< " topo da pilha ........ " << a.topoDaPilha << '\n'
<< " endereco de retorno .. " << a.enderecoDeRetorno << '\n';
return out.str();
}
std::size_t profundidadeMaximaDeAtivacao() noexcept { return 1; }
// ---------------------------------------------------------------------------
// Exemplo mínimo isolado
// ---------------------------------------------------------------------------
const std::vector<ProcedimentoExemplo>& procedimentosDoExemplo() {
// principal contem externo, que contem interno. Tres niveis, que e o
// minimo para a cadeia de acesso divergir da de controle.
static const std::vector<ProcedimentoExemplo> procs = {
ProcedimentoExemplo{"principal", 0, 0},
ProcedimentoExemplo{"externo", 1, 0},
ProcedimentoExemplo{"interno", 2, 1},
};
return procs;
}
std::vector<Quadro> simularChamadas(const std::vector<std::size_t>& chamadas) {
const std::vector<ProcedimentoExemplo>& procs = procedimentosDoExemplo();
std::vector<Quadro> pilha;
for (const std::size_t proc : chamadas) {
if (proc >= procs.size()) {
continue;
}
Quadro q;
q.procedimento = proc;
if (!pilha.empty()) {
q.temElo = true;
// Cadeia de CONTROLE: sempre o quadro imediatamente abaixo, isto é,
// quem chamou. Não depende de onde o procedimento foi escrito.
q.eloDeControle = pilha.size() - 1;
// Cadeia de ACESSO: o quadro mais recente cujo procedimento é o que
// CONTÉM este no texto. Procura de cima para baixo — o mais
// recente é o correto, e é isso que faz a recursão funcionar.
const std::size_t envolvente = procs[proc].contidoEm;
q.eloDeAcesso = pilha.size() - 1;
for (std::size_t i = pilha.size(); i > 0; --i) {
if (pilha[i - 1].procedimento == envolvente) {
q.eloDeAcesso = i - 1;
break;
}
}
}
pilha.push_back(q);
}
return pilha;
}
std::string desenharPilha(const std::vector<Quadro>& pilha) {
const std::vector<ProcedimentoExemplo>& procs = procedimentosDoExemplo();
std::ostringstream out;
out << " quadro | procedimento | nivel | controle | acesso\n";
out << " -------+--------------+-------+----------+-------\n";
for (std::size_t i = 0; i < pilha.size(); ++i) {
const Quadro& q = pilha[i];
const ProcedimentoExemplo& p = procs[q.procedimento];
out << " " << i << " | " << p.nome;
for (std::size_t k = p.nome.size(); k < 12; ++k) {
out << ' ';
}
out << " | " << p.nivelLexico << " | ";
if (q.temElo) {
out << q.eloDeControle << " | " << q.eloDeAcesso;
} else {
out << "- | -";
}
out << '\n';
}
return out.str();
}
std::size_t resolverAcesso(const std::vector<Quadro>& pilha,
std::size_t nivelLexicoAlvo) {
if (pilha.empty()) {
return 0;
}
const std::vector<ProcedimentoExemplo>& procs = procedimentosDoExemplo();
std::size_t atual = pilha.size() - 1;
// Sobe pela cadeia de ACESSO até chegar ao nível léxico procurado. O número
// de saltos é a diferença de níveis, conhecida na compilação — é por isso
// que este percurso não custa busca em tempo de execução num compilador de
// verdade.
while (procs[pilha[atual].procedimento].nivelLexico > nivelLexicoAlvo) {
if (!pilha[atual].temElo) {
return pilha.size();
}
const std::size_t proximo = pilha[atual].eloDeAcesso;
if (proximo == atual) {
return pilha.size();
}
atual = proximo;
}
if (procs[pilha[atual].procedimento].nivelLexico == nivelLexicoAlvo) {
return atual;
}
return pilha.size();
}
} // namespace peneiraO exemplo tem três procedimentos aninhados: principal contém externo, que contém interno. Três níveis são o mínimo para as duas cadeias divergirem, e a divergência é o assunto inteiro. A demonstração --ativacoes simula a sequência principal chama externo, que chama interno, que chama externo de novo:
quadro | procedimento | nivel | controle | acesso
-------+--------------+-------+----------+-------
0 | principal | 0 | - | -
1 | externo | 1 | 0 | 0
2 | interno | 2 | 1 | 1
3 | externo | 1 | 2 | 0O quadro 3 é onde tudo se decide. A cadeia de controle aponta para o quadro 2, porque foi interno quem chamou — ela segue a ordem de execução. A cadeia de acesso aponta para o quadro 0, porque é principal que contém externo no texto do programa. As duas divergem, e é essa divergência que obriga a manter as duas: uma responde “para onde volto”, a outra responde “onde estão as variáveis que enxergo”.
A resolução de acesso a partir do topo confirma:
variavel de nivel lexico 0 -> quadro 0 (principal)
variavel de nivel lexico 1 -> quadro 3 (externo)
variavel de nivel lexico 2 -> nao visivel daquiO nível 2 não é visível do quadro 3, e está certo: interno está na pilha, mas não envolve externo no texto, então suas variáveis não são acessíveis dali. Confundir “está na pilha” com “é visível” é o erro que a cadeia de acesso existe para impedir.
Sobre gerência de memória, que a ementa também menciona: o objeto da Peneira aloca explicitamente e libera por escopo — o texto casado vive enquanto a regra executa e some ao terminar, o que é o padrão de região, o mais simples que existe. A coleta automática não foi implementada e não caberia: coletar exige rastrear referências que sobrevivem à ativação, e nesta linguagem nada sobrevive.
Onde é fácil errar aqui. Montar a cadeia de acesso apontando para o quadro do procedimento envolvente mais antigo em vez do mais recente. Com recursão, os dois diferem, e a versão errada acessa a variável da ativação errada — silenciosamente, porque a variável existe nos dois quadros.
Como verificar. O número de saltos na cadeia de acesso tem de ser igual à diferença de níveis léxicos entre quem acessa e quem declara. Essa diferença é conhecida na compilação, e é por isso que num compilador de verdade este percurso não custa busca em tempo de execução.
1.7 Verificação da entrega
| Item | Como conferir | Estado nesta referência |
|---|---|---|
| Justificativa da representação | Argumento aplicado ao caso, não copiado | Combinatório calculado e descartado; justificativa real é a separação de dificuldades |
| Comparação das formas | Mesma expressão nas três formas | Árvore, pós-fixada e três endereços |
| Tradução implementada | Árvore verificada vira código intermediário | Duas ações traduzidas, 9 temporários |
| Rótulos e desvios | Curto-circuito de and e de or |
Ambos, com traçado |
| Endereços desconhecidos | Preenchimento retroativo | 0 desvios pendentes ao fim, verificado |
| Especificação do formato | Campos com semântica, não só nome | Duas seções, quinze instruções |
| Modelo de execução | Suficiente para implementação independente | Laço, disparo, semântica das instruções, erros |
| Desempate especificado | Comportamento definido quando dois padrões casam igual | Ordem de declaração |
| Organização da memória | Quatro áreas, com o que é fixo e o que cresce | Medido: 5137 bytes estáticos |
| Registro de ativação | Composição e protocolo de retorno | Cinco campos, profundidade máxima 1 |
| Cadeias de controle e acesso | Divergência exibida, não afirmada | Exemplo isolado, quadro 3 diverge |
| Especificação antes do código | Ordem de trabalho registrada | Cabeçalho escrito primeiro; revelou duas decisões |
| Compilação limpa | Modo estrito, aviso como erro | Sem nenhum diagnóstico |
O que quero deixar registrado sobre esta entrega é o que a escrita da especificação produziu que a implementação não teria produzido. Duas decisões só existem porque o documento veio antes: a troca de representação da tabela de transição na fronteira entre compilador e objeto, e o desempate entre padrões de mesmo comprimento. A segunda é a mais reveladora — ela não é uma otimização nem um detalhe, é uma escolha que muda a saída do programa, e ela estava ausente de tudo que eu tinha escrito até aqui. Dois executores corretos, lidos os documentos anteriores, produziriam resultados diferentes para o mesmo programa. Foi o critério de completude, aplicado literalmente à minha própria especificação, que a fez aparecer.
E fica um número desconfortável de propósito. A tabela de transição do objeto usa quatro por cento do espaço que ocupa. A decisão continua sendo a certa pela razão que está escrita, mas ela agora tem um número medido ao lado, e não uma justificativa genérica — que é a diferença entre uma decisão de engenharia e uma preferência.