1 Geração de código — 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: o alvo é o que o seu grupo definiu, e as duas decisões que vocês vão medir são as de vocês. O que se copia daqui é o método — pôr uma representação entre a árvore e a máquina, tratar as otimizações como decisões com critério de aplicabilidade, e fechar o percurso com número em vez de adjetivo.
1.1 Visão Geral
Este é o capítulo em que tudo cobra. As três tarefas produzem o gerador de código, a execução ponta a ponta e a medida que sustenta um julgamento — e as três dependem de decisões tomadas lá atrás: a forma da árvore, a representação da tabela de transição, o núcleo de operadores da linguagem, o repertório da máquina. Nenhuma delas se conserta aqui. O que se faz aqui é descobrir quanto elas custaram ou economizaram.
A decisão que organiza o módulo é pôr uma representação intermediária entre a árvore e a máquina, em vez de traduzir direto. A tradução direta é mais curta de escrever, e tem duas consequências que só aparecem depois. A primeira é que cada alvo novo custa um tradutor novo, com as regras de tradução duplicadas. A segunda, mais cara, é que não sobra onde otimizar: a árvore ainda fala da forma do texto — precedência, agrupamento — e o código de máquina já fala de pilha e de saltos, e nenhuma das duas é a linguagem em que se enuncia “isto foi calculado duas vezes”.
O percurso deste capítulo, então, tem três passos e não um: a árvore verificada vira código de três endereços, o código de três endereços é otimizado, e só então ele é traduzido para o repertório fixo da máquina do capítulo anterior. O terceiro passo é feito duas vezes, para dois alvos diferentes, e é essa repetição que transforma “a representação separa a frente do fundo” de frase em fato observável.
Vale registrar de saída os números que o capítulo persegue. O objeto gerado automaticamente para a descrição de referência produz exatamente a mesma saída do objeto que preenchi à mão no capítulo anterior — e produz também as mesmas quatro instruções na primeira regra e as mesmas nove na segunda, o que é mais do que eu esperava e explico adiante. Sobre a descrição de medida, as duas estratégias de tradução emitem 33 e 32 instruções e executam 51 e 61, com 8 e 10 conversões do texto casado em número. E o mesmo código intermediário, emitido para um segundo alvo, compila e produz saída idêntica byte a byte à da máquina de pilha.
Uma observação sobre o que este capítulo não faz, e que é a decisão de escopo mais difícil de sustentar. Ele não otimiza a varredura. A demonstração conta as tentativas de casamento e mostra que são duas por posição do texto, uma por padrão declarado — e que fundir os autômatos num só reduziria isso a uma. Não fundi, de propósito: a fusão é exatamente o que um gerador automático de analisador léxico faz por baixo, e ela esconderia o que este percurso inteiro existe para mostrar. A otimização fica registrada como caminho conhecido e não tomado, que é diferente de caminho não visto.
1.2 Tarefa 1: Emitir o objeto a partir da árvore verificada
O que a tarefa pede
Implementar a produção do objeto no formato especificado, a partir da árvore que passou pela verificação. É o fecho do caminho que começou no primeiro capítulo, e o ponto em que decisões tomadas lá atrás cobram ou economizam: a forma da árvore, a representação da tabela de transição e o núcleo de operadores escolhido determinam, os três, quanto trabalho existe aqui.
14_ir.h
// 14_ir.h — A representação intermediária: código de três endereços.
//
// POR QUE EXISTE UMA CAMADA INTERMEDIÁRIA, e por que ela não é cerimônia. A
// tradução direta da árvore para a máquina alvo é mais curta de escrever e tem
// duas consequências que só aparecem depois. A primeira é que cada alvo novo
// custa um tradutor novo, escrito contra a árvore, com as regras de tradução
// duplicadas. A segunda, mais cara, é que não há onde otimizar: a árvore ainda
// fala da forma do texto — precedência, agrupamento — e o código de máquina já
// fala de pilha e de saltos, e nenhuma das duas é a linguagem em que se enuncia
// "isto foi calculado duas vezes".
//
// O CÓDIGO DE TRÊS ENDEREÇOS é essa linguagem. Cada quádrupla nomeia uma
// operação, dois operandos e um destino, e o destino é um temporário. É plana —
// não há aninhamento —, é independente de máquina — não há pilha nem registrador
// — e é sequencial, com rótulos e desvios explícitos. As três propriedades juntas
// são o que torna as otimizações deste arquivo escrevíveis em algumas dezenas de
// linhas cada.
//
// A FORMA BASEADA EM PILHA é o outro modelo de representação intermediária, e
// neste sistema ela também existe: é o próprio programa objeto do capítulo
// anterior. A diferença entre as duas é instrutiva e este projeto a exibe lado a
// lado, porque as duas são geradas a partir da mesma árvore: a forma de pilha
// não nomeia resultados intermediários (a pilha os guarda implicitamente), o que
// a torna mais compacta e menos analisável — para saber o que uma instrução
// consome é preciso simular a pilha desde o início do bloco. A tradução de três
// endereços para pilha é mecânica; o contrário, não.
//
// DUAS ESTRATÉGIAS PARA A MESMA CONDIÇÃO. `gerarIr` produz o `where` composto por
// avaliação gulosa (calcula os dois lados e combina) ou por curto-circuito
// (desvia assim que a resposta está decidida). As duas são geradas da mesma
// árvore e chegam ao mesmo resultado com custos diferentes, e é essa diferença
// que a medição do módulo transforma em número.
//
// O `ifTrue` EXISTE AQUI E NÃO EXISTE NA MÁQUINA, de propósito. Ele nasce do
// curto-circuito do `or` e é a operação que a seleção de instruções terá de
// EXPANDIR ao emitir para a máquina de pilha, que só tem desvio por falso. É o
// caso concreto, dentro deste projeto, de uma operação ausente do repertório do
// alvo — e a razão pela qual a representação intermediária não deve ser
// desenhada com o repertório de um alvo específico em mente.
#ifndef PENEIRA_14_IR_H
#define PENEIRA_14_IR_H
#include <cstddef>
#include <string>
#include <vector>
#include "07_lexer.h"
#include "10_ast.h"
#include "13_objeto.h"
namespace peneira {
enum class OpIr {
Rotulo, // L<n>:
CarregarConstante, // t := k<i>
CarregarCasamento, // t := casamento
Converter, // t := value(a)
Comparar, // t := a <op> b
Conjuncao, // t := a and b
Disjuncao, // t := a or b
SeFalso, // ifFalse a goto L<n>
SeVerdadeiro, // ifTrue a goto L<n>
Saltar, // goto L<n>
Emitir, // emit k<i>, a
};
struct OperandoIr {
enum class Especie {
Nenhum,
Temporario,
Constante,
Casamento,
Logico, // só aparece depois da dobra de constantes: não vem do texto-fonte
};
Especie especie = Especie::Nenhum;
std::size_t indice = 0;
bool logico = false;
};
struct Quadrupla {
OpIr op = OpIr::Rotulo;
TipoDeToken operador = TipoDeToken::FimDeArquivo; // significativo em `Comparar`
OperandoIr a;
OperandoIr b;
std::size_t destino = 0; // temporário definido, quando a operação define um
std::size_t rotulo = 0; // alvo do desvio, ou o número do próprio rótulo
bool morta = false; // marcada pela eliminação de código inalcançável
};
struct AcaoIr {
std::size_t padrao = 0;
std::string ligacao;
std::size_t rotuloDaEmissao = 0; // índice da constante textual
std::vector<Quadrupla> codigo;
std::size_t temporarios = 0;
std::size_t rotulos = 0;
};
struct PadraoIr {
std::string nome;
std::string expressao;
};
struct ProgramaIr {
std::vector<Constante> constantes;
std::vector<PadraoIr> padroes;
std::vector<AcaoIr> acoes;
bool curtoCircuito = true;
};
// Traduz a árvore verificada para três endereços. `curtoCircuito` escolhe a
// estratégia de tradução do `where` composto; nada mais muda entre as duas.
ProgramaIr gerarIr(const Programa& arvore, bool curtoCircuito);
// As três otimizações elementares, cada uma devolvendo quantas quádruplas
// alterou. Nenhuma delas depende da máquina alvo — é por isso que moram aqui, e
// não no gerador de código.
//
// DOBRA DE CONSTANTES. Aplicável quando os dois operandos são constantes E a
// operação é total sobre eles: comparação de ordem entre textos não é dobrável
// porque a máquina não a executa, e dobrá-la seria decidir em tempo de compilação
// algo que a linguagem recusa em tempo de execução.
std::size_t dobrarConstantes(ProgramaIr& programa);
// ELIMINAÇÃO DE SUBEXPRESSÃO COMUM. Aplicável dentro de um mesmo bloco básico —
// entre dois rótulos ou desvios — e apenas sobre operações puras. As duas
// condições valem aqui por razões diferentes: puras porque a linguagem não tem
// atribuição nem efeito colateral, e no mesmo bloco porque, atravessando um
// desvio, a segunda ocorrência pode não ser alcançada pelo caminho que calculou
// a primeira. A consequência é mensurável e aparece na demonstração: a
// otimização se aplica à forma gulosa e NÃO se aplica à forma por
// curto-circuito, onde as duas ocorrências caem em blocos diferentes.
std::size_t eliminarSubexpressoesComuns(ProgramaIr& programa);
// ELIMINAÇÃO DE CÓDIGO INALCANÇÁVEL. Aplicável quando um desvio condicional
// passou a ter condição estaticamente conhecida — o que só acontece depois da
// dobra. Sem a dobra antes, não encontra nada; é o exemplo mais simples de
// otimização que habilita outra.
std::size_t eliminarCodigoInalcancavel(ProgramaIr& programa);
struct MedidaIr {
std::size_t quadruplas = 0;
std::size_t temporarios = 0;
std::size_t desvios = 0;
std::size_t conversoes = 0; // quantos `value` sobraram no código
};
MedidaIr medir(const ProgramaIr& programa);
std::string formatarIr(const ProgramaIr& programa);
} // namespace peneira
#endif // PENEIRA_14_IR_H14_ir.cpp
// 14_ir.cpp — geração do código de três endereços e as otimizações elementares.
#include "14_ir.h"
#include "12_tipos.h"
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <sstream>
namespace peneira {
namespace {
bool mesmoOperando(const OperandoIr& primeiro, const OperandoIr& segundo) {
if (primeiro.especie != segundo.especie) {
return false;
}
if (primeiro.especie == OperandoIr::Especie::Logico) {
return primeiro.logico == segundo.logico;
}
return primeiro.indice == segundo.indice;
}
OperandoIr temporario(std::size_t indice) {
OperandoIr operando;
operando.especie = OperandoIr::Especie::Temporario;
operando.indice = indice;
return operando;
}
OperandoIr constante(std::size_t indice) {
OperandoIr operando;
operando.especie = OperandoIr::Especie::Constante;
operando.indice = indice;
return operando;
}
OperandoIr casamento() {
OperandoIr operando;
operando.especie = OperandoIr::Especie::Casamento;
return operando;
}
OperandoIr logico(bool valor) {
OperandoIr operando;
operando.especie = OperandoIr::Especie::Logico;
operando.logico = valor;
return operando;
}
// O construtor do código de uma ação. Existe como classe porque a geração é
// recursiva e precisa de estado — contador de temporários, contador de rótulos,
// a lista sendo montada —, e passar os três por parâmetro em cada chamada
// esconderia a estrutura da tradução atrás da mecânica dela.
class Tradutor {
public:
Tradutor(std::vector<Constante>& constantes, AcaoIr& acao, bool curtoCircuito)
: constantes_{constantes}, acao_{acao}, curtoCircuito_{curtoCircuito} {}
void traduzir(const Acao& fonte) {
const std::size_t fim = novoRotulo();
if (fonte.condicao != nullptr) {
if (curtoCircuito_) {
condicaoFalso(*fonte.condicao, fim);
} else {
const OperandoIr valor = expressao(*fonte.condicao);
Quadrupla desvio;
desvio.op = OpIr::SeFalso;
desvio.a = valor;
desvio.rotulo = fim;
acao_.codigo.push_back(desvio);
}
}
Quadrupla emissao;
emissao.op = OpIr::Emitir;
emissao.a = expressao(*fonte.valor);
emissao.b = constante(acao_.rotuloDaEmissao);
acao_.codigo.push_back(emissao);
Quadrupla marca;
marca.op = OpIr::Rotulo;
marca.rotulo = fim;
acao_.codigo.push_back(marca);
}
std::size_t indiceDeTexto(const std::string& texto) {
for (std::size_t i = 0; i < constantes_.size(); ++i) {
if (constantes_[i].especie == EspecieDeConstante::Texto &&
constantes_[i].texto == texto) {
return i;
}
}
Constante nova;
nova.especie = EspecieDeConstante::Texto;
nova.texto = texto;
constantes_.push_back(nova);
return constantes_.size() - 1;
}
private:
std::size_t novoTemporario() { return acao_.temporarios++; }
std::size_t novoRotulo() { return acao_.rotulos++; }
std::size_t indiceDeNumero(double valor) {
for (std::size_t i = 0; i < constantes_.size(); ++i) {
if (constantes_[i].especie == EspecieDeConstante::Numero &&
constantes_[i].numero == valor) {
return i;
}
}
Constante nova;
nova.especie = EspecieDeConstante::Numero;
nova.numero = valor;
constantes_.push_back(nova);
return constantes_.size() - 1;
}
// Uma expressão vira uma sequência de quádruplas e devolve o operando que
// guarda o resultado. Folhas não geram quádrupla nenhuma: o operando já as
// representa, e criar um temporário para copiar uma constante seria trabalho
// que a otimização teria de desfazer depois.
OperandoIr expressao(const Expressao& no) {
switch (no.tipo) {
case TipoDeExpressao::Nome:
return casamento();
case TipoDeExpressao::Numero:
return constante(indiceDeNumero(std::strtod(no.lexema.c_str(), nullptr)));
case TipoDeExpressao::Texto:
// O lexema do parser vem com as aspas: elas sao delimitador do token, e
// nao parte do valor. `corpoDaExpressao` retira o primeiro e o ultimo
// simbolo, que e o que separa o dado do delimitador nos dois casos.
return constante(indiceDeTexto(corpoDaExpressao(no.lexema)));
case TipoDeExpressao::ValorDe: {
Quadrupla quadrupla;
quadrupla.op = OpIr::Converter;
quadrupla.a = casamento();
quadrupla.destino = novoTemporario();
acao_.codigo.push_back(quadrupla);
return temporario(quadrupla.destino);
}
case TipoDeExpressao::Comparacao:
case TipoDeExpressao::Conjuncao:
case TipoDeExpressao::Disjuncao: {
const OperandoIr esquerda = expressao(*no.esquerda);
const OperandoIr direita = expressao(*no.direita);
Quadrupla quadrupla;
quadrupla.op = no.tipo == TipoDeExpressao::Comparacao ? OpIr::Comparar
: no.tipo == TipoDeExpressao::Conjuncao ? OpIr::Conjuncao
: OpIr::Disjuncao;
quadrupla.operador = no.operador;
quadrupla.a = esquerda;
quadrupla.b = direita;
quadrupla.destino = novoTemporario();
acao_.codigo.push_back(quadrupla);
return temporario(quadrupla.destino);
}
}
return casamento();
}
// O esquema clássico de tradução por fluxo de controle: a condição não
// produz valor, produz DESVIO. `and` encadeia as duas saídas falsas para o
// mesmo destino; `or` precisa de um rótulo próprio para o caso verdadeiro,
// e é dele que nasce o `ifTrue` que a máquina não tem.
void condicaoFalso(const Expressao& no, std::size_t rotuloFalso) {
if (no.tipo == TipoDeExpressao::Conjuncao) {
condicaoFalso(*no.esquerda, rotuloFalso);
condicaoFalso(*no.direita, rotuloFalso);
return;
}
if (no.tipo == TipoDeExpressao::Disjuncao) {
const std::size_t verdadeiro = novoRotulo();
condicaoVerdadeiro(*no.esquerda, verdadeiro);
condicaoFalso(*no.direita, rotuloFalso);
Quadrupla marca;
marca.op = OpIr::Rotulo;
marca.rotulo = verdadeiro;
acao_.codigo.push_back(marca);
return;
}
Quadrupla desvio;
desvio.op = OpIr::SeFalso;
desvio.a = expressao(no);
desvio.rotulo = rotuloFalso;
acao_.codigo.push_back(desvio);
}
void condicaoVerdadeiro(const Expressao& no, std::size_t rotuloVerdadeiro) {
if (no.tipo == TipoDeExpressao::Disjuncao) {
condicaoVerdadeiro(*no.esquerda, rotuloVerdadeiro);
condicaoVerdadeiro(*no.direita, rotuloVerdadeiro);
return;
}
if (no.tipo == TipoDeExpressao::Conjuncao) {
const std::size_t falso = novoRotulo();
condicaoFalso(*no.esquerda, falso);
condicaoVerdadeiro(*no.direita, rotuloVerdadeiro);
Quadrupla marca;
marca.op = OpIr::Rotulo;
marca.rotulo = falso;
acao_.codigo.push_back(marca);
return;
}
Quadrupla desvio;
desvio.op = OpIr::SeVerdadeiro;
desvio.a = expressao(no);
desvio.rotulo = rotuloVerdadeiro;
acao_.codigo.push_back(desvio);
}
std::vector<Constante>& constantes_;
AcaoIr& acao_;
bool curtoCircuito_ = true;
};
bool comparacaoNumerica(TipoDeToken operador, double esquerda, double direita, bool& resultado) {
switch (operador) {
case TipoDeToken::Menor: resultado = esquerda < direita; return true;
case TipoDeToken::Maior: resultado = esquerda > direita; return true;
case TipoDeToken::MenorOuIgual: resultado = esquerda <= direita; return true;
case TipoDeToken::MaiorOuIgual: resultado = esquerda >= direita; return true;
case TipoDeToken::IgualIgual: resultado = esquerda == direita; return true;
case TipoDeToken::Diferente: resultado = esquerda != direita; return true;
default: return false;
}
}
// recorte:inicio compactar-o-morto
void compactar(AcaoIr& acao) {
acao.codigo.erase(std::remove_if(acao.codigo.begin(), acao.codigo.end(),
[](const Quadrupla& q) { return q.morta; }),
acao.codigo.end());
}
// recorte:fim compactar-o-morto
// recorte:inicio fronteira-de-bloco-basico
bool abreBloco(const Quadrupla& quadrupla) {
return quadrupla.op == OpIr::Rotulo;
}
bool fechaBloco(const Quadrupla& quadrupla) {
return quadrupla.op == OpIr::SeFalso || quadrupla.op == OpIr::SeVerdadeiro ||
quadrupla.op == OpIr::Saltar;
}
// recorte:fim fronteira-de-bloco-basico
std::string formatarNumeroIr(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 simboloDoOperador(TipoDeToken operador) {
switch (operador) {
case TipoDeToken::Menor: return "<";
case TipoDeToken::Maior: return ">";
case TipoDeToken::MenorOuIgual: return "<=";
case TipoDeToken::MaiorOuIgual: return ">=";
case TipoDeToken::IgualIgual: return "==";
case TipoDeToken::Diferente: return "!=";
default: return "?";
}
}
std::string formatarOperando(const ProgramaIr& programa, const OperandoIr& operando) {
switch (operando.especie) {
case OperandoIr::Especie::Temporario: return "t" + std::to_string(operando.indice);
case OperandoIr::Especie::Casamento: return "casamento";
case OperandoIr::Especie::Logico: return operando.logico ? "verdadeiro" : "falso";
case OperandoIr::Especie::Constante: {
const Constante& valor = programa.constantes[operando.indice];
if (valor.especie == EspecieDeConstante::Numero) {
return "k" + std::to_string(operando.indice) + "(" +
formatarNumeroIr(valor.numero) + ")";
}
return "k" + std::to_string(operando.indice) + "(\"" + valor.texto + "\")";
}
case OperandoIr::Especie::Nenhum: return "-";
}
return "-";
}
} // namespace
ProgramaIr gerarIr(const Programa& arvore, bool curtoCircuito) {
ProgramaIr programa;
programa.curtoCircuito = curtoCircuito;
for (const DeclaracaoDePadrao& padrao : arvore.padroes) {
programa.padroes.push_back(PadraoIr{padrao.nome, corpoDaExpressao(padrao.expressao)});
}
for (const Acao& fonte : arvore.acoes) {
AcaoIr acao;
acao.ligacao = fonte.ligacao;
for (std::size_t i = 0; i < programa.padroes.size(); ++i) {
if (programa.padroes[i].nome == fonte.padrao) {
acao.padrao = i;
break;
}
}
Tradutor tradutor{programa.constantes, acao, curtoCircuito};
acao.rotuloDaEmissao = tradutor.indiceDeTexto(corpoDaExpressao(fonte.rotulo));
tradutor.traduzir(fonte);
programa.acoes.push_back(std::move(acao));
}
return programa;
}
std::size_t dobrarConstantes(ProgramaIr& programa) {
std::size_t dobradas = 0;
for (AcaoIr& acao : programa.acoes) {
// recorte:inicio propagacao-sem-segundo-passe
// Temporário -> valor lógico já conhecido. A substituição é aplicada nas
// quádruplas seguintes, e é ela que faz a dobra se propagar por uma
// condição composta inteira sem um segundo passe.
std::vector<OperandoIr> conhecido(acao.temporarios);
std::vector<bool> temValor(acao.temporarios, false);
const auto resolver = [&](OperandoIr& operando) {
if (operando.especie == OperandoIr::Especie::Temporario &&
operando.indice < temValor.size() && temValor[operando.indice]) {
operando = conhecido[operando.indice];
}
};
// recorte:fim propagacao-sem-segundo-passe
for (Quadrupla& quadrupla : acao.codigo) {
resolver(quadrupla.a);
resolver(quadrupla.b);
if (quadrupla.op == OpIr::Comparar &&
quadrupla.a.especie == OperandoIr::Especie::Constante &&
quadrupla.b.especie == OperandoIr::Especie::Constante) {
const Constante& esquerda = programa.constantes[quadrupla.a.indice];
const Constante& direita = programa.constantes[quadrupla.b.indice];
bool resultado = false;
// recorte:inicio dobra-so-quando-executavel
// A aplicabilidade tem duas condições, e a segunda é a que se
// esquece: além de os dois lados serem constantes, a operação
// tem de ser executável sobre eles. Ordem entre textos não é —
// a máquina a recusa —, e dobrá-la aqui decidiria em tempo de
// compilação algo que a linguagem recusa em tempo de execução.
const bool ambosNumericos = esquerda.especie == EspecieDeConstante::Numero &&
direita.especie == EspecieDeConstante::Numero;
const bool igualdadeDeTexto = esquerda.especie == EspecieDeConstante::Texto &&
direita.especie == EspecieDeConstante::Texto &&
(quadrupla.operador == TipoDeToken::IgualIgual ||
quadrupla.operador == TipoDeToken::Diferente);
// recorte:fim dobra-so-quando-executavel
bool dobrou = false;
if (ambosNumericos) {
dobrou = comparacaoNumerica(quadrupla.operador, esquerda.numero,
direita.numero, resultado);
} else if (igualdadeDeTexto) {
const bool iguais = esquerda.texto == direita.texto;
resultado = quadrupla.operador == TipoDeToken::IgualIgual ? iguais : !iguais;
dobrou = true;
}
if (dobrou) {
conhecido[quadrupla.destino] = logico(resultado);
temValor[quadrupla.destino] = true;
quadrupla.morta = true;
++dobradas;
continue;
}
}
if ((quadrupla.op == OpIr::Conjuncao || quadrupla.op == OpIr::Disjuncao) &&
quadrupla.a.especie == OperandoIr::Especie::Logico &&
quadrupla.b.especie == OperandoIr::Especie::Logico) {
const bool resultado = quadrupla.op == OpIr::Conjuncao
? (quadrupla.a.logico && quadrupla.b.logico)
: (quadrupla.a.logico || quadrupla.b.logico);
conhecido[quadrupla.destino] = logico(resultado);
temValor[quadrupla.destino] = true;
quadrupla.morta = true;
++dobradas;
}
}
compactar(acao);
}
return dobradas;
}
std::size_t eliminarSubexpressoesComuns(ProgramaIr& programa) {
std::size_t eliminadas = 0;
for (AcaoIr& acao : programa.acoes) {
std::vector<std::size_t> substituto(acao.temporarios);
std::vector<bool> temSubstituto(acao.temporarios, false);
std::vector<const Quadrupla*> disponiveis; // as do bloco básico corrente
const auto resolver = [&](OperandoIr& operando) {
if (operando.especie == OperandoIr::Especie::Temporario &&
operando.indice < temSubstituto.size() && temSubstituto[operando.indice]) {
operando.indice = substituto[operando.indice];
}
};
for (Quadrupla& quadrupla : acao.codigo) {
resolver(quadrupla.a);
resolver(quadrupla.b);
if (abreBloco(quadrupla) || fechaBloco(quadrupla)) {
// recorte:inicio bloco-basico-apaga-o-disponivel
// A fronteira do bloco básico apaga o que estava disponível. É
// conservador de propósito: atravessando um desvio, a segunda
// ocorrência pode ser alcançada por um caminho que não calculou
// a primeira, e o temporário reusado estaria indefinido.
disponiveis.clear();
// recorte:fim bloco-basico-apaga-o-disponivel
continue;
}
const bool pura = quadrupla.op == OpIr::Converter || quadrupla.op == OpIr::Comparar ||
quadrupla.op == OpIr::Conjuncao || quadrupla.op == OpIr::Disjuncao;
if (!pura) {
continue;
}
bool reusou = false;
for (const Quadrupla* anterior : disponiveis) {
if (anterior->op == quadrupla.op && anterior->operador == quadrupla.operador &&
mesmoOperando(anterior->a, quadrupla.a) &&
mesmoOperando(anterior->b, quadrupla.b)) {
substituto[quadrupla.destino] = anterior->destino;
temSubstituto[quadrupla.destino] = true;
quadrupla.morta = true;
++eliminadas;
reusou = true;
break;
}
}
if (!reusou) {
disponiveis.push_back(&quadrupla);
}
}
compactar(acao);
}
return eliminadas;
}
std::size_t eliminarCodigoInalcancavel(ProgramaIr& programa) {
std::size_t removidas = 0;
for (AcaoIr& acao : programa.acoes) {
for (std::size_t i = 0; i < acao.codigo.size(); ++i) {
Quadrupla& quadrupla = acao.codigo[i];
const bool condicional =
quadrupla.op == OpIr::SeFalso || quadrupla.op == OpIr::SeVerdadeiro;
if (!condicional || quadrupla.a.especie != OperandoIr::Especie::Logico) {
continue;
}
const bool desvia = quadrupla.op == OpIr::SeFalso ? !quadrupla.a.logico
: quadrupla.a.logico;
if (!desvia) {
// O desvio nunca acontece: some, e nada mais muda.
quadrupla.morta = true;
++removidas;
continue;
}
// O desvio sempre acontece: vira incondicional, e o que está entre
// ele e o rótulo de destino deixa de ser alcançável.
const std::size_t alvo = quadrupla.rotulo;
quadrupla.op = OpIr::Saltar;
quadrupla.a = OperandoIr{};
for (std::size_t k = i + 1; k < acao.codigo.size(); ++k) {
if (acao.codigo[k].op == OpIr::Rotulo && acao.codigo[k].rotulo == alvo) {
break;
}
if (!acao.codigo[k].morta) {
acao.codigo[k].morta = true;
++removidas;
}
}
}
compactar(acao);
}
return removidas;
}
MedidaIr medir(const ProgramaIr& programa) {
MedidaIr medida;
for (const AcaoIr& acao : programa.acoes) {
std::vector<bool> usado(acao.temporarios, false);
for (const Quadrupla& quadrupla : acao.codigo) {
if (quadrupla.op == OpIr::Rotulo) {
continue; // rótulo não é instrução: é posição
}
++medida.quadruplas;
if (quadrupla.op == OpIr::SeFalso || quadrupla.op == OpIr::SeVerdadeiro ||
quadrupla.op == OpIr::Saltar) {
++medida.desvios;
}
if (quadrupla.op == OpIr::Converter) {
++medida.conversoes;
if (quadrupla.destino < usado.size()) {
usado[quadrupla.destino] = true;
}
} else if (quadrupla.op == OpIr::Comparar || quadrupla.op == OpIr::Conjuncao ||
quadrupla.op == OpIr::Disjuncao) {
if (quadrupla.destino < usado.size()) {
usado[quadrupla.destino] = true;
}
}
}
medida.temporarios += static_cast<std::size_t>(std::count(usado.begin(), usado.end(), true));
}
return medida;
}
std::string formatarIr(const ProgramaIr& programa) {
std::ostringstream saida;
for (std::size_t a = 0; a < programa.acoes.size(); ++a) {
const AcaoIr& acao = programa.acoes[a];
saida << " acao " << a << " (pattern \"" << programa.padroes[acao.padrao].nome
<< "\", ligacao " << acao.ligacao << ")\n";
for (const Quadrupla& quadrupla : acao.codigo) {
switch (quadrupla.op) {
case OpIr::Rotulo:
saida << " L" << quadrupla.rotulo << ":\n";
break;
case OpIr::Converter:
saida << " t" << quadrupla.destino << " := value("
<< formatarOperando(programa, quadrupla.a) << ")\n";
break;
case OpIr::Comparar:
saida << " t" << quadrupla.destino << " := "
<< formatarOperando(programa, quadrupla.a) << ' '
<< simboloDoOperador(quadrupla.operador) << ' '
<< formatarOperando(programa, quadrupla.b) << "\n";
break;
case OpIr::Conjuncao:
case OpIr::Disjuncao:
saida << " t" << quadrupla.destino << " := "
<< formatarOperando(programa, quadrupla.a)
<< (quadrupla.op == OpIr::Conjuncao ? " and " : " or ")
<< formatarOperando(programa, quadrupla.b) << "\n";
break;
case OpIr::SeFalso:
saida << " ifFalse " << formatarOperando(programa, quadrupla.a)
<< " goto L" << quadrupla.rotulo << "\n";
break;
case OpIr::SeVerdadeiro:
saida << " ifTrue " << formatarOperando(programa, quadrupla.a)
<< " goto L" << quadrupla.rotulo << "\n";
break;
case OpIr::Saltar:
saida << " goto L" << quadrupla.rotulo << "\n";
break;
case OpIr::Emitir:
saida << " emit " << formatarOperando(programa, quadrupla.b) << ", "
<< formatarOperando(programa, quadrupla.a) << "\n";
break;
case OpIr::CarregarConstante:
case OpIr::CarregarCasamento:
saida << " t" << quadrupla.destino << " := "
<< formatarOperando(programa, quadrupla.a) << "\n";
break;
}
}
}
return saida.str();
}
} // namespace peneiraO código de três endereços é a linguagem em que as decisões independentes de máquina cabem. Cada quádrupla nomeia uma operação, dois operandos e um destino, e o destino é um temporário; a forma é plana, sem aninhamento, e sequencial, com rótulos e desvios explícitos. As três propriedades juntas são o que faz cada otimização deste projeto caber em algumas dezenas de linhas.
A tradução da árvore para essa forma tem uma decisão que vale explicar porque ela é contraintuitiva: folhas não geram quádrupla. Um literal ou o casamento ligado já são representáveis como operando, e criar um temporário para copiá-los seria produzir trabalho que a otimização teria de desfazer em seguida. Quem gera uma quádrupla por nó da árvore acaba com um código intermediário duas vezes maior e uma primeira otimização cuja única função é reparar a geração.
A segunda decisão é que a condição composta é traduzida por duas estratégias, e as duas ficam disponíveis. Por valor, calculam-se os dois lados e combinam-se com uma operação lógica. Por fluxo, desvia-se assim que a resposta está decidida. A tradução por fluxo é a clássica de esquema dirigido pela sintaxe: a condição não produz valor, produz desvio; o and encadeia as duas saídas falsas para o mesmo destino, e o or precisa de um rótulo próprio para o caso verdadeiro. Os destinos são gerados antes de se saber onde ficam, e preenchidos quando o ponto se torna conhecido — e o defeito clássico dessa técnica é justamente o destino que fica por preencher, silencioso enquanto a condição for simples. Foi contra ele que a descrição de medida ganhou uma condição composta e uma disjunção: sem elas, o preenchimento nunca é exercitado.
14_codegen.h
// 14_codegen.h — a seleção de instruções: da representação intermediária para a
// máquina de pilha do capítulo anterior.
//
// O QUE ESTE ARQUIVO FAZ, e o que ele deliberadamente não faz. Ele traduz a
// representação intermediária para o repertório fixo da máquina alvo, e para
// mais nada: as decisões que valem para qualquer alvo — dobrar constantes,
// eliminar subexpressão comum, descartar código inalcançável — ficaram do outro
// lado, na representação. A fronteira é o que permite dizer que trocar de alvo
// custa este arquivo, e só ele.
//
// A EXPANSÃO DA OPERAÇÃO AUSENTE. A representação tem desvio por verdadeiro; a
// máquina não. Um `ifTrue t goto L` é emitido como um desvio por falso para a
// instrução seguinte, seguido de um salto incondicional para L — duas
// instruções e um destino extra no lugar de uma. É o custo, contado, de uma
// operação que o alvo não tem, e ele aparece na medida final como diferença
// entre o que a representação pediu e o que a máquina executou.
//
// O QUE A MÁQUINA DE PILHA NÃO CONSEGUE APROVEITAR. A eliminação de
// subexpressão comum guarda um resultado para usá-lo duas vezes, e guardar
// exige um lugar onde guardar. Esta máquina não tem temporário nomeado: tem
// pilha, e o que está na pilha é consumido por quem está acima. A tradução aqui,
// portanto, RECALCULA o valor compartilhado — desfazendo, na prática, a
// otimização. Não é defeito do otimizador nem da máquina: é a demonstração de
// que uma otimização independente de máquina só se converte em ganho quando o
// alvo tem como realizá-la, e o mesmo código intermediário rende no alvo C, que
// tem variáveis locais.
//
// A CONSTANTE LÓGICA QUE NÃO CABE. Depois da dobra, uma condição pode virar um
// valor lógico conhecido, e a máquina não tem instrução que empilhe verdadeiro
// ou falso. A saída não é inventar a instrução: é a eliminação de código
// inalcançável, que faz a condição desaparecer antes de chegar aqui. Se ainda
// assim um valor lógico alcançar a seleção de instruções, este arquivo RECUSA e
// diz por quê — gerar algo aproximado seria emitir código que a máquina não
// executa.
#ifndef PENEIRA_14_CODEGEN_H
#define PENEIRA_14_CODEGEN_H
#include <cstddef>
#include <string>
#include <vector>
#include "13_objeto.h"
#include "14_ir.h"
namespace peneira {
struct ResultadoDaGeracao {
ProgramaObjeto objeto;
std::vector<std::string> erros;
// Quantas instruções a mais a expansão do desvio por verdadeiro custou, e
// quantos recálculos a ausência de temporário nomeado impôs. Os dois números
// são o preço da máquina alvo, e existem para ser mostrados, não estimados.
std::size_t expansoesDeDesvio = 0;
std::size_t recalculos = 0;
bool ok() const { return erros.empty(); }
};
// Compila os `pattern` em autômatos determinísticos mínimos, pelo mesmo caminho
// dos primeiros capítulos, e traduz o código de cada ação para o repertório da
// máquina. O objeto devolvido passa por `validar` sem reprovação — e a
// demonstração confere isso, porque um gerador que emite objeto inválido é
// exatamente o que as restrições do capítulo anterior existem para pegar.
ResultadoDaGeracao gerarObjeto(const ProgramaIr& programa);
// Converte um autômato determinístico já construído para a forma que viaja no
// objeto, agrupando os símbolos que levam ao mesmo destino. O agrupamento não é
// cosmético: é o que mantém o arquivo legível e, portanto, conferível à mão.
AutomatoObjeto exportarAutomato(const Afd& afd, const std::string& nome);
} // namespace peneira
#endif // PENEIRA_14_CODEGEN_H14_codegen.cpp
// 14_codegen.cpp — seleção de instruções e emissão para a máquina de pilha.
#include "14_codegen.h"
#include <map>
#include <set>
#include "02_regex.h"
#include "04_afn.h"
#include "05_determinizacao.h"
namespace peneira {
namespace {
// O mesmo caminho dos primeiros capítulos, agora usado como ferramenta: a
// expressão do `pattern` vira árvore, a árvore vira autômato não determinístico
// por Thompson, o não determinístico vira determinístico por subconjuntos, e o
// determinístico é minimizado. Nada aqui é novo — e é esse o ponto.
Afd compilarPattern(const std::string& expressao, bool& ok) {
const Resultado leitura = analisarExpressao(expressao);
if (!leitura.ok) {
ok = false;
return Afd{};
}
const Afn afn = construirThompson(leitura.arvore);
const std::string alfabeto = alfabetoDoAfn(afn);
const ResultadoDaDeterminizacao determinizado = determinizar(afn, alfabeto);
ok = true;
return minimizar(determinizado.afd).afd;
}
Opcode opcodeDaComparacao(TipoDeToken operador, bool& ok) {
ok = true;
switch (operador) {
case TipoDeToken::Menor: return Opcode::CompararMenor;
case TipoDeToken::Maior: return Opcode::CompararMaior;
case TipoDeToken::MenorOuIgual: return Opcode::CompararMenorIgual;
case TipoDeToken::MaiorOuIgual: return Opcode::CompararMaiorIgual;
case TipoDeToken::IgualIgual: return Opcode::CompararIgual;
case TipoDeToken::Diferente: return Opcode::CompararDiferente;
default: break;
}
ok = false;
return Opcode::Retornar;
}
// A tradução de uma ação. A pilha não tem endereço para temporário nomeado,
// então o valor de um temporário é produzido no instante em que é consumido:
// percorre-se a definição dele, recursivamente, empilhando os operandos antes da
// operação. Quando o mesmo temporário é consumido duas vezes, o percurso
// acontece duas vezes — e é isso que desfaz a eliminação de subexpressão comum.
class Selecionador {
public:
Selecionador(const AcaoIr& acao, ResultadoDaGeracao& resultado)
: acao_{acao}, resultado_{resultado} {
for (const Quadrupla& quadrupla : acao_.codigo) {
const bool define = quadrupla.op == OpIr::Converter || quadrupla.op == OpIr::Comparar ||
quadrupla.op == OpIr::Conjuncao || quadrupla.op == OpIr::Disjuncao;
if (define) {
definicao_[quadrupla.destino] = &quadrupla;
}
}
}
std::vector<Instrucao> selecionar() {
for (const Quadrupla& quadrupla : acao_.codigo) {
switch (quadrupla.op) {
case OpIr::Rotulo:
posicaoDoRotulo_[quadrupla.rotulo] = codigo_.size();
break;
case OpIr::SeFalso:
empilhar(quadrupla.a);
pendentes_.push_back({codigo_.size(), quadrupla.rotulo});
acrescentar(Opcode::SaltarSeFalso, 0);
break;
case OpIr::SeVerdadeiro: {
// A EXPANSÃO: o alvo não tem desvio por verdadeiro.
empilhar(quadrupla.a);
const std::size_t desvioPorFalso = codigo_.size();
acrescentar(Opcode::SaltarSeFalso, 0);
pendentes_.push_back({codigo_.size(), quadrupla.rotulo});
acrescentar(Opcode::Saltar, 0);
codigo_[desvioPorFalso].operando = codigo_.size();
++resultado_.expansoesDeDesvio;
break;
}
case OpIr::Saltar:
pendentes_.push_back({codigo_.size(), quadrupla.rotulo});
acrescentar(Opcode::Saltar, 0);
break;
case OpIr::Emitir:
empilhar(quadrupla.b); // o rótulo primeiro
empilhar(quadrupla.a); // o valor depois
acrescentar(Opcode::Emitir, 0);
break;
default:
break; // as definições de temporário são emitidas sob demanda
}
}
acrescentar(Opcode::Retornar, 0);
for (const Pendente& pendente : pendentes_) {
const auto encontrado = posicaoDoRotulo_.find(pendente.rotulo);
if (encontrado == posicaoDoRotulo_.end()) {
resultado_.erros.push_back("rotulo L" + std::to_string(pendente.rotulo) +
" sem posicao: backpatching incompleto");
continue;
}
codigo_[pendente.posicao].operando = encontrado->second;
}
return codigo_;
}
private:
struct Pendente {
std::size_t posicao = 0;
std::size_t rotulo = 0;
};
void acrescentar(Opcode opcode, std::size_t operando) {
Instrucao instrucao;
instrucao.opcode = opcode;
instrucao.operando = operando;
codigo_.push_back(instrucao);
}
void empilhar(const OperandoIr& operando) {
switch (operando.especie) {
case OperandoIr::Especie::Constante:
acrescentar(Opcode::EmpilharConstante, operando.indice);
return;
case OperandoIr::Especie::Casamento:
acrescentar(Opcode::EmpilharCasamento, 0);
return;
case OperandoIr::Especie::Logico:
resultado_.erros.push_back(
"a maquina nao tem instrucao que empilhe um valor logico: a condicao "
"constante deveria ter sido eliminada antes da selecao de instrucoes");
return;
case OperandoIr::Especie::Temporario: {
const auto encontrado = definicao_.find(operando.indice);
if (encontrado == definicao_.end()) {
resultado_.erros.push_back("temporario t" + std::to_string(operando.indice) +
" usado sem definicao");
return;
}
if (jaEmitido_.count(operando.indice) != 0) {
++resultado_.recalculos;
}
jaEmitido_.insert(operando.indice);
emitirDefinicao(*encontrado->second);
return;
}
case OperandoIr::Especie::Nenhum:
resultado_.erros.push_back("operando ausente na selecao de instrucoes");
return;
}
}
void emitirDefinicao(const Quadrupla& quadrupla) {
switch (quadrupla.op) {
case OpIr::Converter:
empilhar(quadrupla.a);
acrescentar(Opcode::Valor, 0);
return;
case OpIr::Comparar: {
empilhar(quadrupla.a);
empilhar(quadrupla.b);
bool ok = false;
const Opcode opcode = opcodeDaComparacao(quadrupla.operador, ok);
if (!ok) {
resultado_.erros.push_back("comparacao sem instrucao correspondente no alvo");
return;
}
acrescentar(opcode, 0);
return;
}
case OpIr::Conjuncao:
case OpIr::Disjuncao:
empilhar(quadrupla.a);
empilhar(quadrupla.b);
acrescentar(quadrupla.op == OpIr::Conjuncao ? Opcode::Conjuncao : Opcode::Disjuncao,
0);
return;
default:
resultado_.erros.push_back("definicao de temporario com operacao inesperada");
return;
}
}
const AcaoIr& acao_;
ResultadoDaGeracao& resultado_;
std::map<std::size_t, const Quadrupla*> definicao_;
std::map<std::size_t, std::size_t> posicaoDoRotulo_;
std::vector<Pendente> pendentes_;
std::vector<Instrucao> codigo_;
std::set<std::size_t> jaEmitido_;
};
} // namespace
AutomatoObjeto exportarAutomato(const Afd& afd, const std::string& nome) {
AutomatoObjeto automato;
automato.nome = nome;
automato.alfabeto = afd.alfabeto();
// `quantidadeDeEstados` inclui o estado de erro, que no objeto é implícito:
// toda transição não declarada leva a ele.
automato.estados = afd.quantidadeDeEstados() - 1;
automato.inicial = afd.estadoInicial();
for (std::size_t estado = 0; estado < automato.estados; ++estado) {
if (afd.ehDeAceitacao(estado)) {
automato.aceitacao.push_back(estado);
}
// Agrupa por destino: uma linha por par (origem, destino), com todos os
// símbolos que fazem a travessia.
std::map<std::size_t, std::string> porDestino;
for (const char simbolo : automato.alfabeto) {
const Estado destino = afd.transicao(estado, simbolo);
if (destino == afd.estadoDeErro()) {
continue;
}
porDestino[destino].push_back(simbolo);
}
for (const auto& par : porDestino) {
automato.transicoes.push_back(
AutomatoObjeto::Transicao{estado, par.second, par.first});
}
}
return automato;
}
ResultadoDaGeracao gerarObjeto(const ProgramaIr& programa) {
ResultadoDaGeracao resultado;
resultado.objeto.versao = 1;
resultado.objeto.constantes = programa.constantes;
for (const PadraoIr& padrao : programa.padroes) {
bool ok = false;
const Afd afd = compilarPattern(padrao.expressao, ok);
if (!ok) {
resultado.erros.push_back("o pattern \"" + padrao.nome + "\" nao compila");
continue;
}
resultado.objeto.automatos.push_back(exportarAutomato(afd, padrao.nome));
}
for (const AcaoIr& acao : programa.acoes) {
RegraObjeto regra;
regra.automato = acao.padrao;
regra.ligacao = acao.ligacao;
Selecionador selecionador{acao, resultado};
regra.codigo = selecionador.selecionar();
std::size_t profundidade = 0;
if (!profundidadeExigida(regra.codigo, profundidade)) {
resultado.erros.push_back(
"o codigo emitido para uma acao nao tem profundidade de pilha calculavel");
}
regra.profundidade = profundidade;
resultado.objeto.regras.push_back(regra);
}
return resultado;
}
} // namespace peneiraA seleção de instruções traduz para o repertório fixo, e para mais nada. É aqui que aparece o tópico que o percurso vinha adiando: o que fazer quando o alvo não tem a operação. Neste projeto o caso é concreto e nasceu sozinho, sem que eu o fabricasse: a representação intermediária tem desvio por condição verdadeira, porque o curto-circuito da disjunção o produz naturalmente, e a máquina do capítulo anterior só tem desvio por falso. A expansão é mecânica — desvia-se por falso para a instrução seguinte e salta-se incondicionalmente para o destino —, e custa uma instrução e um destino a mais por ocorrência. A demonstração conta as ocorrências em vez de mencioná-las.
Vale dizer por que a representação não foi desenhada com o repertório da máquina em mente, o que teria evitado a expansão. Porque desenhá-la assim é desistir do que ela serve: uma representação moldada sobre um alvo específico é aquele alvo escrito de outro jeito, e o segundo alvo — que tem desvio por verdadeiro — pagaria pela restrição do primeiro sem receber nada em troca.
A segunda consequência do repertório é mais sutil e aparece adiante, na medição: a máquina de pilha não tem temporário nomeado. O valor de um temporário, aqui, é produzido no instante em que é consumido, percorrendo a definição dele; quando o mesmo temporário é consumido duas vezes, o percurso acontece duas vezes. A seleção de instruções, portanto, desfaz a eliminação de subexpressão comum — e conta quantas vezes fez isso.
Há ainda um terceiro caso, e ele nasce de uma otimização em vez de nascer do repertório. Depois da dobra de constantes, uma condição pode virar um valor lógico conhecido, e a máquina não tem instrução que empilhe verdadeiro ou falso. A saída é a eliminação de código inalcançável fazer a condição desaparecer antes de a seleção começar. O código registra isso da forma mais direta que encontrei — se um valor lógico ainda assim chegar aqui, a geração recusa e diz por quê, em vez de emitir algo aproximado.
O que me surpreendeu ao resolver. O código emitido para a descrição de referência saiu idêntico, instrução por instrução, ao que eu havia escrito à mão no capítulo anterior. Não planejei isso, e a explicação é instrutiva: quando a máquina tem um repertório pequeno e a linguagem tem poucas construções, o espaço de escolhas do gerador é estreito, e a tradução “óbvia” que um humano escreve é a mesma que o esquema produz. Em uma máquina com registradores, isso não aconteceria — a alocação de registradores é justamente onde o espaço de escolhas explode.
Onde é fácil errar. Guardar ponteiro para uma quádrupla de um vetor que ainda vai crescer. O mapa de definições que a seleção monta aponta para dentro do código da ação, e uma inserção posterior invalidaria tudo. A ordem aqui é montar o mapa depois de o código estar completo, e o comentário registra a regra porque ela é invisível na assinatura. Como verificar que está correta: rode o objeto gerado contra as restrições do formato antes de executá-lo. Objeto que não passa é defeito de gerador, e o carregamento o pega antes de a máquina executar uma instrução — que é exatamente para isso que aquelas restrições foram escritas.
1.3 Tarefa 2: Executar o objeto sobre entrada real
O que a tarefa pede
Pôr o sistema em execução de ponta a ponta: da entrada escrita na linguagem até o resultado observável, com o objeto emitido efetivamente executado — pelo motor construído ou pelo ambiente de execução escolhido como alvo —, sobre um caso que ninguém preparou para o teste. Implementar e demonstrar também a regra que resolve a ambiguidade que a linguagem admite: onde mais de uma leitura é possível no mesmo ponto, o sistema precisa escolher, e a escolha precisa estar escrita antes de estar no código.
Entrada que ninguém preparou é o critério mais simples de enunciar e o mais frequentemente ausente. Um sistema que processa corretamente os três exemplos escritos por quem o construiu, e falha no primeiro arquivo real, não está pronto: está ajustado aos próprios casos.
O ponta a ponta desta solução tem uma característica que insisto em separar de “o programa roda”: o objeto é gravado. O gerador termina, escreve um arquivo, e encerra. Depois — outro programa, outro momento — o arquivo é lido de volta do disco, verificado contra as restrições e executado. A demonstração faz literalmente isso, e não por cerimônia: se o objeto fosse passado em memória do gerador para a máquina, a fronteira entre compilar e executar existiria só na descrição da arquitetura, e qualquer suposição indevida que o gerador fizesse sobre o executor passaria despercebida para sempre.
O segundo cuidado é a conferência contra o artefato do capítulo anterior. O objeto escrito à mão e o objeto gerado automaticamente executam a mesma entrada, e as saídas têm de coincidir. É um teste diferencial, e o que o torna barato é não exigir resposta esperada escrita à mão: ele não pergunta se a saída está certa, pergunta se dois caminhos independentes chegaram à mesma. O caminho manual foi escrito lendo a especificação; o automático foi escrito pelo compilador. Um defeito que atinja os dois da mesma forma escapa — e é por isso que este teste convive com o outro, e não o substitui.
A entrada que ninguém preparou é a especificação do formato, do capítulo anterior: 10.400 bytes de texto escrito para ser lido por humanos, que atravessam o sistema produzindo cinquenta e três casamentos e duas emissões. Escolhi um documento do próprio projeto por uma razão que vale explicitar: qualquer arquivo que eu escrevesse para este teste seria, por definição, preparado. O critério só se cumpre com texto que existia antes e por outro motivo.
A regra de desambiguação é o ponto em que a tarefa cobra algo escrito antes de estar no código, e aqui a resposta é literal: ela está escrita desde o capítulo anterior, na especificação do formato, e o gerador nasceu depois dela. São duas regras e não uma. Vence o casamento mais longo; havendo empate, vence a ordem de declaração. A demonstração exibe as duas com o exemplo clássico da colisão entre palavra reservada e identificador: sobre for, os dois padrões casam três símbolos e a ordem decide — trocar a ordem das ações troca a saída; sobre form, um casa quatro e o outro três, e o mais longo vence sem que a ordem chegue a ser consultada.
Onde é fácil errar. Implementar a ordem como desempate usando comparação não estrita ao percorrer as regras. Com maior ou igual, a última regra declarada passa a vencer os empates, e a saída fica plausível — só que invertida em relação à especificação. É um caractere de diferença, não quebra nada e não é acusado por teste algum que não tenha um caso de empate. Como verificar que está correta: monte uma descrição com dois padrões que casem exatamente o mesmo trecho e rode-a duas vezes, com as ações em ordens trocadas. Se a saída não mudar, o desempate não está sendo feito pela ordem — está sendo feito por acaso.
1.4 Tarefa 3: Medir duas decisões e sustentar o julgamento
O que a tarefa pede
Produzir ao menos uma medida numérica comparando duas decisões técnicas: a quantidade de estados antes e depois da redução, o número de instruções emitidas para uma mesma construção sob duas formas de tradução, ou o volume de entrada processado por unidade de tempo. Registrar a medida por escrito, com o método usado para obtê-la.
O que fecha o percurso é o julgamento que o número sustenta: o que se ganharia mudando a decisão medida, o que se perderia e por que a escolha feita se defende. O que se cobra é argumento defensável, e nunca uma resposta única correta — a diferença entre quem construiu entendendo e quem transcreveu de algum lugar aparece inteira nesse ponto.
14_otimizacoes.pen
// 14_otimizacoes.pen — a descricao que existe para exercitar o gerador, e nao a
// linguagem. Cada acao aqui foi escrita para provocar uma decisao de traducao
// diferente, e as tres juntas cobrem o que o capitulo mede.
//
// A primeira tem condicao COMPOSTA com a mesma subexpressao dos dois lados: e
// ela que separa as duas estrategias de traducao (avaliar os dois lados x
// desviar assim que a resposta esta decidida) e a unica em que a eliminacao de
// subexpressao comum tem o que eliminar.
//
// A segunda tem condicao CONSTANTE: ela existe para a dobra de constantes, e o
// que acontece com ela depois da dobra e o caso concreto de uma operacao que a
// maquina nao tem — nao ha instrucao que empilhe um valor logico, e a saida nao
// e inventar a instrucao, e fazer a condicao desaparecer.
//
// A terceira tem DISJUNCAO: e dela que nasce o desvio por verdadeiro, que a
// representacao intermediaria tem e a maquina de pilha nao, e que a selecao de
// instrucoes precisa expandir em duas instrucoes.
pattern numero = /-?[0-9]+(\.[0-9]+)?/;
rule {
on numero(n) where value(n) > 100 and value(n) < 2000 => emit("faixa", n);
on numero(n) where 2 > 1 => emit("todos", n);
on numero(n) where value(n) < 0 or value(n) > 1000 => emit("extremo", n);
}14_medidas.md
# Peneira — as medidas do fecho do percurso
Este documento é o registro escrito das medições, com o método usado para obtê-las. Ele existe
porque uma medida sem método registrado não é medida: é um número que ninguém consegue refazer, e
que envelhece sem avisar.
Todos os números abaixo são **reproduzíveis por um comando**: `peneira codegen`, executado a partir
da raiz da variante. Se algum deles deixar de bater, o comando falha — as medições são a própria
bateria de testes, e não um relatório escrito ao lado dela.
## 1. Método
**O que se compara.** A mesma descrição, traduzida pelas duas estratégias que o repertório da
máquina admite: por **fluxo** (curto-circuito, com desvios) e por **valor** (avaliação gulosa, com
`AND`/`OR`). Nada mais muda entre as duas execuções — mesmo front-end, mesma árvore, mesmas
otimizações, mesmo alvo.
**A descrição medida** é a que existe para provocar as três decisões de tradução: uma ação com
condição composta e subexpressão repetida, uma com condição constante, e uma com disjunção.
**As grandezas.** Quatro são estáticas, contadas sobre o código: quádruplas da representação
intermediária, desvios, instruções emitidas para a máquina e profundidade de pilha exigida. Duas são
dinâmicas, contadas pela máquina durante a execução sobre a mesma amostra (`5 900 3000 42 1500`):
instruções executadas e conversões de casamento em número. A conversão é contada em separado por ser
a operação **cara** — ela percorre o texto casado —, e é ela que torna o curto-circuito observável em
vez de afirmado.
**O que não é medido, e por que.** Tempo de relógio não entra: a variante roda em três compiladores
e em três sistemas, e um número de milissegundos medido em um deles não se transporta. As contagens
acima são as mesmas em qualquer máquina, e é isso que as torna comparáveis.
## 2. As medidas
| Grandeza | por fluxo (curto-circuito) | por valor (guloso) |
| --- | --- | --- |
| quádruplas, antes → depois das otimizações | 17 → 15 | 17 → 13 |
| conversões no código | 4 → 4 | 4 → 2 |
| desvios | 5 → 4 | 3 → 2 |
| dobradas / inalcançáveis / subexpressões comuns | 1 / 1 / 0 | 1 / 1 / 2 |
| instruções emitidas | 33 | 32 |
| expansões de desvio (o `ifTrue` ausente do alvo) | 1 | 0 |
| recálculos forçados (a pilha não guarda o comum) | 0 | 2 |
| profundidade de pilha | 2 | 3 |
| instruções executadas sobre a amostra | 51 | 61 |
| **conversões executadas** | **8** | **10** |
## 3. O que os números dizem
**A eliminação de subexpressão comum aplica-se a uma das formas e não à outra**, e isso não é
acidente de implementação: na forma por fluxo, as duas ocorrências de `value(n)` caem em blocos
básicos diferentes, separadas pelo desvio, e reusar o temporário através de um desvio é inválido em
geral. A otimização acha 2 na forma gulosa e 0 na forma por fluxo — e é a mesma otimização, com o
mesmo critério.
**E o que ela ganha na representação, o alvo devolve.** As 2 subexpressões eliminadas viram 2
recálculos na emissão, porque a máquina de pilha não tem temporário nomeado onde guardar um valor
para usá-lo duas vezes. O saldo para este alvo é zero. O mesmo código intermediário, emitido para C,
mantém o ganho: lá o temporário vira variável local. A conclusão que os dois números sustentam
juntos é a que interessa: **uma otimização independente de máquina só se converte em ganho quando o
alvo tem como realizá-la.**
**A expansão custa uma instrução e um destino.** A disjunção compilada por curto-circuito produz um
desvio por verdadeiro, que a máquina não tem; a seleção de instruções o expande em desvio por falso
mais salto incondicional. Uma ocorrência, uma instrução a mais — e é por isso que a forma por fluxo
emite 33 contra 32, apesar de executar menos.
**A pilha é menor na forma por fluxo** (2 contra 3), porque ela nunca mantém dois resultados
parciais vivos ao mesmo tempo: decide e desvia. Como o formato do objeto declara a profundidade
exigida, essa diferença não é teórica — ela aparece na reserva feita no carregamento.
**A medida decisiva é a última linha.** Sobre a mesma amostra, a forma por fluxo executa 8 conversões
e a gulosa 10, com 51 contra 61 instruções. A diferença vem inteira dos casos em que a primeira
comparação já decide: `5` e `42` reprovam no primeiro teste, e a forma gulosa converte o casamento
uma segunda vez para avaliar um lado cujo resultado não muda mais nada.
## 4. O julgamento, que é o que fecha o percurso
**A referência emite por fluxo.** O argumento não é "menos instruções executadas" — é que a
diferença cresce com o que a condição custa, e neste sistema o que a condição custa é percorrer texto.
Em uma condição barata, os dois caminhos empatam na prática e a escolha seria indiferente; em uma
condição que toca a entrada, a forma gulosa paga por avaliações cujo resultado já não pode mudar a
resposta, e a conta piora com o tamanho do texto processado.
**O que se perderia mudando a decisão.** A forma gulosa é mais simples de gerar — não precisa de
rótulos em aberto nem de preenchê-los depois —, e o defeito clássico do curto-circuito é exatamente
um destino que ficou por preencher, silencioso enquanto a condição for simples. Quem escolher a forma
gulosa compra simplicidade de gerador e paga em execução; quem escolher o fluxo compra execução e
paga em um mecanismo a mais para manter correto. As duas escolhas se defendem, e é por isso que a
pergunta é de engenharia e não tem gabarito.
**O que o número não decide.** Nenhuma das duas formas muda o resultado: as saídas são idênticas, e a
demonstração falha se deixarem de ser. Otimização que muda o resultado não é otimização.
## 5. A segunda medida: os dois alvos concordam
O teste de equivalência entre os dois alvos não produz número — produz uma igualdade. O mesmo
programa-fonte, a mesma representação intermediária, dois destinos: a máquina de pilha e um programa
C compilado. Sobre a mesma entrada, as duas saídas têm de coincidir **byte a byte**.
Verificado com o compilador C encontrado na máquina em que a demonstração roda; quando não há
compilador C no caminho, a demonstração **diz que o teste não foi executado** em vez de aprová-lo em
silêncio. É a dependência de tempo de demonstração que precisa estar checada antes da aula.
O valor desse teste é não exigir resposta esperada escrita à mão: ele não pergunta se a saída está
certa, pergunta se os dois caminhos independentes chegaram à mesma. Um defeito de geração de código
que atinja os dois da mesma forma escapa — e é por isso que ele convive com a comparação contra o
objeto preenchido à mão no capítulo anterior, que é escrita por outra via.Antes das medidas, as otimizações que elas medem — e a decisão que importa em cada uma é o critério de aplicabilidade, jamais o algoritmo. Uma otimização sem critério escrito é uma receita, e receita aplicada fora do caso produz código errado que parece mais rápido.
A dobra de constantes tem dois requisitos, e é o segundo que se esquece: além de os dois operandos serem constantes, a operação tem de ser executável sobre eles. Ordem entre textos não é — a máquina a recusa, porque a linguagem não define regra de colação —, e dobrá-la aqui decidiria em tempo de compilação algo que a linguagem recusa em tempo de execução. A implementação separa os dois casos explicitamente por essa razão.
A eliminação de subexpressão comum exige que as operações sejam puras e que as duas ocorrências estejam no mesmo bloco básico. A primeira condição vale nesta linguagem por construção — não há atribuição nem efeito colateral. A segunda é conservadora de propósito: atravessando um desvio, a segunda ocorrência pode ser alcançada por um caminho que não calculou a primeira, e o temporário reusado estaria indefinido. A consequência é mensurável e é o achado mais interessante do módulo: a otimização acha duas ocorrências na forma gulosa e nenhuma na forma por curto-circuito, onde o desvio separa as duas.
A eliminação de código inalcançável só encontra algo depois da dobra, porque é a dobra que transforma uma condição em valor conhecido. É o exemplo mais simples de uma otimização que habilita outra, e a ordem em que as três rodam é, portanto, parte do desenho e não da conveniência.
As medidas estão no registro escrito, com o método; o que vale repetir aqui é o que elas sustentam. A eliminação de subexpressão comum ganha duas quádruplas na representação e devolve exatamente duas na emissão, porque a máquina de pilha não tem onde guardar o valor compartilhado e a seleção de instruções o recalcula. Saldo zero para este alvo. O mesmo código intermediário, emitido para o segundo alvo, mantém o ganho, porque lá o temporário vira variável local. A conclusão que os dois números sustentam juntos é a que eu não conseguiria defender sem eles: uma otimização independente de máquina só vira ganho quando o alvo tem como realizá-la.
A medida decisiva, porém, é a última linha da tabela. Sobre a mesma amostra, a tradução por fluxo executa oito conversões do texto casado em número e a gulosa executa dez, com cinquenta e uma contra sessenta e uma instruções. A diferença vem inteira dos casos em que a primeira comparação já decide a resposta e a forma gulosa converte o casamento uma segunda vez para avaliar um lado que não muda mais nada.
O julgamento. A referência emite por fluxo, e o argumento é que a diferença cresce com o que a condição custa; neste sistema, o que a condição custa é percorrer texto. “Menos instruções” seria a leitura pobre da mesma tabela. Em condição barata, os dois caminhos empatam na prática. O que se perderia mudando a decisão é simplicidade: a forma gulosa não precisa de destinos em aberto nem de preenchê-los depois, e o defeito clássico do curto-circuito é exatamente o destino que ficou por preencher. Quem escolhe a forma gulosa compra simplicidade de gerador e paga em execução; quem escolhe o fluxo compra execução e paga em um mecanismo a mais para manter correto. As duas se defendem, e é por isso que a pergunta é de engenharia.
Onde é fácil errar. Medir e concluir que uma das formas “é mais eficiente”, sem dizer sobre o quê. As duas emitem quase o mesmo número de instruções — trinta e três contra trinta e duas —, e quem medisse só isso concluiria que são equivalentes, ou que a gulosa é melhor. O número que separa as duas é o de conversões executadas, e ele só aparece porque a máquina conta a operação cara em separado. Como verificar que está correta: exija que as duas formas produzam saída idêntica antes de comparar qualquer custo. Otimização ou estratégia de tradução que muda o resultado deixou de ser a mesma coisa que se pretendia comparar.
1.5 O segundo alvo, e o que ele revela sobre a representação
14_emitc.h
// 14_emitc.h — o segundo alvo: a mesma representação intermediária virando um
// programa C autônomo.
//
// POR QUE EXISTE UM SEGUNDO ALVO. Enquanto há um alvo só, "a representação
// intermediária separa a frente do fundo" é uma frase que o leitor aceita por
// confiança. Com dois, é um fato observável: o mesmo programa-fonte, a mesma
// representação, dois destinos, e o front-end intocado. O que muda entre eles é
// um arquivo — este e o da seleção de instruções — e nada mais.
//
// O QUE ESTE ALVO TEM E A MÁQUINA DE PILHA NÃO. Três coisas, e as três aparecem
// na comparação de custos: variável local nomeada (o que faz a eliminação de
// subexpressão comum render aqui e não lá), desvio por condição verdadeira (o
// que dispensa a expansão em duas instruções) e constante lógica (o que permite
// emitir uma condição já dobrada sem depender da eliminação de código
// inalcançável). A lição não é que este alvo é melhor: é que a mesma
// representação, otimizada da mesma forma, rende diferente conforme o repertório
// de quem a executa.
//
// O QUE SAI DAQUI É DADO, NÃO FONTE DO PROJETO. O texto C produzido é resultado
// de execução da referência, como qualquer outra saída: não acrescenta linguagem
// ao repertório da disciplina, não tem pasta própria no projeto do professor e
// não é alcançado pela verificação de tipos da implementação.
//
// O DEFEITO QUE ESTE ARQUIVO PRODUZ MAIS FACILMENTE é escape. O emissor imprime
// texto que precisa compilar: um literal com aspas ou barra invertida mal
// escapado não vira saída errada, vira C que não compila — barato de achar — ou,
// pior, C que compila e diverge em silêncio. A defesa é o teste diferencial:
// mesma entrada, os dois alvos, saídas comparadas byte a byte.
#ifndef PENEIRA_14_EMITC_H
#define PENEIRA_14_EMITC_H
#include <string>
#include <vector>
#include "13_objeto.h"
#include "14_ir.h"
namespace peneira {
// Produz o texto de um programa C autônomo que faz o mesmo reconhecimento. Os
// autômatos vêm do objeto já gerado — são as mesmas tabelas, e recompilá-las por
// um segundo caminho produziria duas linguagens ligeiramente diferentes com o
// mesmo nome.
std::string emitirC(const ProgramaIr& programa, const ProgramaObjeto& objeto,
std::vector<std::string>& erros);
} // namespace peneira
#endif // PENEIRA_14_EMITC_H14_emitc.cpp
// 14_emitc.cpp — emissão de um programa C autônomo a partir da mesma
// representação intermediária.
#include "14_emitc.h"
#include <cmath>
#include <iomanip>
#include <map>
#include <sstream>
namespace peneira {
namespace {
// Escapa um literal para dentro do fonte C. É a função mais chata do arquivo e a
// que mais estraga se estiver errada: o defeito não aparece como saída errada,
// aparece como C que não compila.
std::string literalC(const std::string& texto) {
std::ostringstream saida;
saida << '"';
for (const char c : texto) {
switch (c) {
case '"': saida << "\\\""; break;
case '\\': saida << "\\\\"; break;
case '\n': saida << "\\n"; break;
case '\t': saida << "\\t"; break;
default:
if (static_cast<unsigned char>(c) < 0x20) {
saida << "\\x" << std::hex << static_cast<int>(c) << std::dec;
} else {
saida << c;
}
}
}
saida << '"';
return saida.str();
}
std::string numeroC(double valor) {
std::ostringstream fluxo;
fluxo << std::defaultfloat << std::setprecision(17) << valor;
std::string texto = fluxo.str();
if (texto.find('.') == std::string::npos && texto.find('e') == std::string::npos &&
texto.find("inf") == std::string::npos && texto.find("nan") == std::string::npos) {
texto += ".0";
}
return texto;
}
bool ehNumerico(const ProgramaIr& programa, const OperandoIr& operando,
const std::map<std::size_t, char>& tipoDoTemporario) {
if (operando.especie == OperandoIr::Especie::Constante) {
return programa.constantes[operando.indice].especie == EspecieDeConstante::Numero;
}
if (operando.especie == OperandoIr::Especie::Temporario) {
const auto encontrado = tipoDoTemporario.find(operando.indice);
return encontrado != tipoDoTemporario.end() && encontrado->second == 'd';
}
return false;
}
std::string operandoC(const ProgramaIr& programa, const OperandoIr& operando,
std::vector<std::string>& erros) {
switch (operando.especie) {
case OperandoIr::Especie::Temporario:
return "t" + std::to_string(operando.indice);
case OperandoIr::Especie::Logico:
// O alvo TEM constante lógica; a máquina de pilha não tinha.
return operando.logico ? "1" : "0";
case OperandoIr::Especie::Constante: {
const Constante& valor = programa.constantes[operando.indice];
if (valor.especie == EspecieDeConstante::Numero) {
return numeroC(valor.numero);
}
return literalC(valor.texto);
}
case OperandoIr::Especie::Casamento:
erros.push_back("o casamento so pode ser usado via value(), comparacao de texto ou emit");
return "0";
case OperandoIr::Especie::Nenhum:
erros.push_back("operando ausente na emissao de C");
return "0";
}
return "0";
}
std::string operadorC(TipoDeToken operador) {
switch (operador) {
case TipoDeToken::Menor: return "<";
case TipoDeToken::Maior: return ">";
case TipoDeToken::MenorOuIgual: return "<=";
case TipoDeToken::MaiorOuIgual: return ">=";
case TipoDeToken::IgualIgual: return "==";
case TipoDeToken::Diferente: return "!=";
default: return "==";
}
}
void emitirAcao(std::ostringstream& saida, const ProgramaIr& programa, std::size_t indice,
const AcaoIr& acao, std::vector<std::string>& erros) {
// O tipo de cada temporário sai da operação que o define: conversão produz
// número, o resto produz condição. Em C isso vira declaração; na máquina de
// pilha não virava nada, porque lá não havia onde declarar.
std::map<std::size_t, char> tipoDoTemporario;
for (const Quadrupla& quadrupla : acao.codigo) {
if (quadrupla.op == OpIr::Converter) {
tipoDoTemporario[quadrupla.destino] = 'd';
} else if (quadrupla.op == OpIr::Comparar || quadrupla.op == OpIr::Conjuncao ||
quadrupla.op == OpIr::Disjuncao) {
tipoDoTemporario[quadrupla.destino] = 'i';
}
}
saida << "static void acao_" << indice
<< "(const char* s, size_t ini, size_t fim)\n{\n";
for (const auto& par : tipoDoTemporario) {
saida << " " << (par.second == 'd' ? "double" : "int") << " t" << par.first << " = 0;\n";
}
saida << " (void)s; (void)ini; (void)fim;\n";
for (const Quadrupla& quadrupla : acao.codigo) {
switch (quadrupla.op) {
case OpIr::Rotulo:
saida << "L" << quadrupla.rotulo << ": ;\n";
break;
case OpIr::Converter:
saida << " t" << quadrupla.destino << " = peneira_valor(s, ini, fim);\n";
break;
case OpIr::Comparar: {
const bool numerica = ehNumerico(programa, quadrupla.a, tipoDoTemporario) &&
ehNumerico(programa, quadrupla.b, tipoDoTemporario);
if (numerica) {
saida << " t" << quadrupla.destino << " = ("
<< operandoC(programa, quadrupla.a, erros) << ' '
<< operadorC(quadrupla.operador) << ' '
<< operandoC(programa, quadrupla.b, erros) << ");\n";
break;
}
// Sobra a comparação que envolve texto ou casamento, e nela a
// linguagem só admite igualdade — a mesma regra que a máquina de
// pilha aplica, pela mesma razão: não há colação definida.
const OperandoIr& outro = quadrupla.a.especie == OperandoIr::Especie::Casamento
? quadrupla.b
: quadrupla.a;
const bool temCasamento = quadrupla.a.especie == OperandoIr::Especie::Casamento ||
quadrupla.b.especie == OperandoIr::Especie::Casamento;
if (!temCasamento) {
erros.push_back("comparacao de texto sem casamento nao e emitida para C");
break;
}
if (quadrupla.operador != TipoDeToken::IgualIgual &&
quadrupla.operador != TipoDeToken::Diferente) {
erros.push_back("este alvo nao ordena texto, como a maquina tambem nao");
break;
}
saida << " t" << quadrupla.destino << " = "
<< (quadrupla.operador == TipoDeToken::Diferente ? "!" : "")
<< "peneira_igual(s, ini, fim, " << operandoC(programa, outro, erros)
<< ");\n";
break;
}
case OpIr::Conjuncao:
case OpIr::Disjuncao:
saida << " t" << quadrupla.destino << " = ("
<< operandoC(programa, quadrupla.a, erros)
<< (quadrupla.op == OpIr::Conjuncao ? " && " : " || ")
<< operandoC(programa, quadrupla.b, erros) << ");\n";
break;
case OpIr::SeFalso:
saida << " if (!(" << operandoC(programa, quadrupla.a, erros) << ")) goto L"
<< quadrupla.rotulo << ";\n";
break;
case OpIr::SeVerdadeiro:
// UMA instrução: este alvo tem desvio por verdadeiro.
saida << " if (" << operandoC(programa, quadrupla.a, erros) << ") goto L"
<< quadrupla.rotulo << ";\n";
break;
case OpIr::Saltar:
saida << " goto L" << quadrupla.rotulo << ";\n";
break;
case OpIr::Emitir: {
const std::string rotulo = operandoC(programa, quadrupla.b, erros);
if (quadrupla.a.especie == OperandoIr::Especie::Casamento) {
saida << " printf(\" %-10s%.*s\\n\", " << rotulo
<< ", (int)(fim - ini), s + ini);\n";
} else if (quadrupla.a.especie == OperandoIr::Especie::Constante &&
programa.constantes[quadrupla.a.indice].especie ==
EspecieDeConstante::Texto) {
saida << " printf(\" %-10s%s\\n\", " << rotulo << ", "
<< operandoC(programa, quadrupla.a, erros) << ");\n";
} else {
saida << " printf(\" %-10s%.15g\\n\", " << rotulo << ", (double)("
<< operandoC(programa, quadrupla.a, erros) << "));\n";
}
break;
}
default:
break;
}
}
saida << "}\n\n";
}
} // namespace
std::string emitirC(const ProgramaIr& programa, const ProgramaObjeto& objeto,
std::vector<std::string>& erros) {
std::ostringstream saida;
saida << "/* Gerado pela Peneira a partir da representacao intermediaria.\n"
" Este arquivo e DADO produzido em tempo de execucao, nao fonte do projeto.\n"
" Compile com qualquer compilador C e execute com o arquivo de entrada como\n"
" argumento, ou com a entrada pela entrada padrao. */\n\n";
saida << "#include <stdio.h>\n#include <stdlib.h>\n#include <string.h>\n\n";
saida << "static double peneira_valor(const char* s, size_t ini, size_t fim)\n{\n"
" char buffer[64];\n"
" size_t n = fim - ini;\n"
" if (n >= sizeof buffer) n = sizeof buffer - 1;\n"
" memcpy(buffer, s + ini, n);\n"
" buffer[n] = 0;\n"
" return strtod(buffer, NULL);\n}\n\n";
saida << "static int peneira_igual(const char* s, size_t ini, size_t fim, const char* t)\n{\n"
" size_t n = fim - ini;\n"
" return strlen(t) == n && memcmp(s + ini, t, n) == 0;\n}\n\n";
// As tabelas de transição viram um `switch` por estado. A tabela densa da
// máquina não sobrevive à travessia, e não precisa: o que o objeto declara
// são as transições úteis, e é delas que este código nasce.
for (std::size_t a = 0; a < objeto.automatos.size(); ++a) {
const AutomatoObjeto& automato = objeto.automatos[a];
saida << "/* pattern \"" << automato.nome << "\" */\n";
saida << "static int trans_" << a << "(int e, char c)\n{\n";
saida << " if (c == 0) return -1;\n";
saida << " switch (e) {\n";
for (std::size_t estado = 0; estado < automato.estados; ++estado) {
bool abriu = false;
for (const AutomatoObjeto::Transicao& transicao : automato.transicoes) {
if (transicao.origem != estado) {
continue;
}
if (!abriu) {
saida << " case " << estado << ":\n";
abriu = true;
}
saida << " if (strchr(" << literalC(transicao.simbolos)
<< ", c)) return " << transicao.destino << ";\n";
}
if (abriu) {
saida << " return -1;\n";
}
}
saida << " default: break;\n }\n return -1;\n}\n\n";
saida << "static int aceita_" << a << "(int e)\n{\n switch (e) {\n";
for (const std::size_t estado : automato.aceitacao) {
saida << " case " << estado << ": return 1;\n";
}
saida << " default: break;\n }\n return 0;\n}\n\n";
// O casamento mais longo, com a mesma regra escrita na especificacao do
// formato: guarda-se o ultimo ponto de aceitacao e continua andando.
saida << "static size_t casar_" << a << "(const char* s, size_t n, size_t i)\n{\n"
<< " int e = " << automato.inicial << ";\n"
<< " size_t ate = 0;\n size_t k;\n"
<< " for (k = i; k < n; ++k) {\n"
<< " e = trans_" << a << "(e, s[k]);\n"
<< " if (e < 0) break;\n"
<< " if (aceita_" << a << "(e)) ate = k - i + 1;\n"
<< " }\n return ate;\n}\n\n";
}
for (std::size_t i = 0; i < programa.acoes.size(); ++i) {
emitirAcao(saida, programa, i, programa.acoes[i], erros);
}
saida << "int main(int argc, char** argv)\n{\n"
" FILE* arquivo = NULL;\n"
" char* s = NULL;\n"
" size_t n = 0, capacidade = 0, i = 0;\n"
" int c;\n\n"
" arquivo = (argc > 1) ? fopen(argv[1], \"rb\") : stdin;\n"
" if (arquivo == NULL) { fprintf(stderr, \"nao abriu a entrada\\n\"); return 1; }\n"
" while ((c = fgetc(arquivo)) != EOF) {\n"
" if (n + 1 >= capacidade) {\n"
" capacidade = capacidade ? capacidade * 2 : 4096;\n"
" s = (char*)realloc(s, capacidade);\n"
" if (s == NULL) return 1;\n"
" }\n"
" s[n++] = (char)c;\n"
" }\n"
" if (s == NULL) return 0;\n"
" s[n] = 0;\n"
" if (argc > 1) fclose(arquivo);\n\n"
" while (i < n) {\n"
" size_t melhor = 0, m = 0;\n"
" int regra = -1;\n";
// Uma tentativa por regra, na ordem de declaracao, e a comparacao é
// ESTRITAMENTE maior: é assim que o empate cai para a primeira regra, que é
// a regra de desambiguacao escrita na especificacao antes de estar aqui.
for (std::size_t r = 0; r < objeto.regras.size(); ++r) {
saida << " m = casar_" << objeto.regras[r].automato << "(s, n, i);"
<< " if (m > melhor) { melhor = m; regra = " << r << "; }\n";
}
saida << " if (regra < 0) { ++i; continue; }\n"
" switch (regra) {\n";
for (std::size_t r = 0; r < programa.acoes.size(); ++r) {
saida << " case " << r << ": acao_" << r << "(s, i, i + melhor); break;\n";
}
saida << " default: break;\n }\n"
" i += melhor;\n }\n"
" free(s);\n return 0;\n}\n";
return saida.str();
}
} // namespace peneiraEnquanto há um alvo só, “a representação intermediária separa a frente do fundo” é uma frase que o leitor aceita por confiança. O segundo alvo a transforma em fato observável: o mesmo programa-fonte, a mesma representação, dois destinos, e o front-end intocado. Trocar de alvo custou um arquivo.
O que este alvo tem e a máquina de pilha não tem são três coisas, e as três aparecem na comparação. Tem variável local nomeada, e por isso a eliminação de subexpressão comum rende aqui. Tem desvio por condição verdadeira, e por isso a expansão em duas instruções não acontece. Tem constante lógica, e por isso uma condição já dobrada pode ser emitida diretamente, sem depender da eliminação de código inalcançável. A lição é que a mesma representação, otimizada da mesma forma, rende diferente conforme o repertório de quem a executa — e é precisamente isso que a camada intermediária existe para tornar visível. Nenhum dos dois alvos é o melhor; eles são bons em colunas diferentes da tabela.
O defeito que este arquivo produz com mais facilidade é escape. O emissor imprime texto que precisa compilar, e um literal com aspas ou barra invertida mal escapado vira código que não compila — barato de achar — ou, pior, código que compila e diverge em silêncio. A defesa é o teste de equivalência, e ele tem uma dependência: precisa de um compilador disponível na máquina. Quando não há, a demonstração diz que o teste não foi executado, em vez de aprová-lo em silêncio — e essa dependência é de tempo de demonstração, o que significa que ela precisa estar checada antes da aula, e não descoberta durante.
Sobre a mesma entrada, o programa gerado e compilado produz saída idêntica à da máquina de pilha, byte a byte. É o teste mais barato de todo o percurso e o que me deu mais confiança no gerador.
1.6 O que fecha o percurso
O sistema agora atravessa inteiro: texto-fonte, símbolos, árvore de derivação, árvore abstrata, verificação de significado, representação intermediária, otimização, objeto gravado, execução. Cada fase entrega à seguinte a estrutura de dados real que ela consome, e nenhuma delas é alimentada por dado fabricado à mão — o que era verdade parcial no capítulo anterior, quando a máquina rodava um objeto escrito manualmente porque o gerador ainda não existia, e virou verdade inteira aqui.
Fica também o que está em aberto, e um percurso que se apresenta como completo ensina errado. A varredura tenta cada padrão em cada posição, e fundir os autômatos reduziria isso a uma passagem — é o que um gerador automático de analisador léxico faz, e é caminho conhecido e não tomado, não caminho não visto. O sistema de tipos é magro: dois tipos, sem escopo aninhado de verdade. A representação não tem forma de fluxo de dados que permitisse otimizações mais fortes que as três daqui. Todas essas ausências são escolhas de escopo, e listá-las é o que permite à próxima pessoa a mexer no sistema distinguir o que falta do que foi decidido.
O que o módulo entrega ao estudante, no fim, é a forma de defender uma decisão técnica: mostre o número, diga o que se ganharia mudando, diga o que se perderia, e sustente a escolha. O compilador é o pretexto. Nas três tarefas foi isso que se repetiu — a representação intermediária contra a tradução direta, o curto-circuito contra a avaliação gulosa, o segundo alvo contra o alvo único —, e nas três a resposta veio da mesma fonte: de contar.