1 Módulo 12: Projeto do Professor — Quando a Gramática Já Não Basta
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 12
O front-end ficou pronto no módulo 10, e desde então o compilador aceita qualquer programa bem formado. Este módulo é onde ele passa a recusar programas bem formados que não fazem sentido.
A atividade tem quatro partes. Construir a tabela de símbolos com o tratamento de escopo que a linguagem exige. Implementar as verificações de declaração e de compatibilidade de tipos. Produzir um conjunto de programas com erros semânticos deliberados, acompanhado das mensagens que o compilador dá para cada um. E registrar as decisões de projeto sobre a organização dos percursos — quantos são, o que cada um coleta, e por que nessa ordem.
Resolvi a atividade e a decisão que mais rendeu foi uma que eu não tinha previsto ao escrever o plano. A pergunta que o verificador de tipos da Peneira precisa responder é se um pattern casa sempre um número, porque é disso que depende a legalidade de value(n). Eu esperava ter de resolver isso com uma anotação no programa ou com uma heurística sobre o texto da expressão regular. Nenhuma das duas foi necessária: a pergunta é a pergunta de inclusão de linguagens, e a inclusão é decidida pela diferença de autômatos que o módulo 6 já tinha construído. O verificador de tipos desta linguagem não confia no programador e não adivinha — ele decide, com a mesma maquinaria de autômatos que o resto do compilador usa para outra coisa.
Os dois erros de compilação que me custaram tempo estão registrados no fim, e os dois foram pegos pelo verificador estrito, não por revisão.
1.2 Tarefa 1: Mostrar que a sintaxe não basta
A atividade — exibir programas bem formados e sem sentido, e explicar por que a gramática não os rejeita.
Comecei pelo programa que motiva o módulo inteiro. Ele está em exemplos/erros_semanticos.pen e atravessa o front-end sem um único diagnóstico:
12_demos.cpp
#include "12_demos.h"
#include <ostream>
#include <string>
#include <vector>
#include "01_diagnostico.h"
#include "01_source.h"
#include "10_ast.h"
#include "10_parser.h"
#include "12_atributos.h"
#include "12_sema.h"
#include "12_simbolos.h"
#include "12_tipos.h"
namespace peneira::demo {
namespace {
// O programa correto, o mesmo dos módulos anteriores.
const char* kProgramaCorreto =
"pattern email = /[a-z0-9._]+@[a-z]+\\.[a-z]+/;\n"
"pattern numero = /-?[0-9]+(\\.[0-9]+)?/;\n"
"\n"
"rule {\n"
" on email(e) => emit(\"contato\", e);\n"
" on numero(n) where value(n) > 100 => emit(\"grande\", n);\n"
"}\n";
// Sintaticamente impecável, semanticamente absurdo. Cada linha do bloco tem um
// defeito diferente, e nenhum deles é detectável pela gramática.
const char* kProgramaAbsurdo =
"pattern email = /[a-z0-9._]+@[a-z]+\\.[a-z]+/;\n"
"pattern numero = /-?[0-9]+(\\.[0-9]+)?/;\n"
"\n"
"rule {\n"
" on telefone(t) => emit(\"tel\", t);\n"
" on email(e) where value(e) > 10 => emit(\"alto\", e);\n"
" on numero(n) where n > 100 => emit(\"grande\", n);\n"
" on numero(x) => emit(\"qualquer\", \"fixo\");\n"
"}\n";
struct Analise {
SourceFile arquivo;
DiagnosticBag diagnosticos;
AstPtr raiz;
std::size_t errosSintaticos = 0;
};
// Roda o front-end dos módulos 7 e 10 e devolve tudo junto. O objeto guarda o
// SourceFile por valor porque o analisador mantém referência a ele: devolver
// só a árvore deixaria a referência pendurada.
Analise analisar(const std::string& nome, const std::string& texto) {
Analise a{SourceFile::fromText(nome, texto), DiagnosticBag{}, nullptr, 0};
a.raiz = analisarArquivo(a.arquivo, a.diagnosticos, a.errosSintaticos);
return a;
}
} // namespace
void mostrarSintaticoVersusSemantico(std::ostream& out) {
out << "correcao sintatica NAO e correcao semantica\n\n";
Analise a = analisar("absurdo.pen", kProgramaAbsurdo);
out << "o programa abaixo passa inteiro pelo front-end do modulo 10:\n\n"
<< kProgramaAbsurdo << '\n';
out << " erros sintaticos: " << a.errosSintaticos << '\n'
<< " nos na arvore: " << (a.raiz ? contarNos(*a.raiz) : 0) << "\n\n";
out << "a gramatica nao tem como reclamar de nenhum deles, e a razao e\n"
"estrutural: a correspondencia entre uma declaracao e um uso a\n"
"distancia arbitraria nao e exprimivel por gramatica livre de\n"
"contexto. E o mesmo resultado do modulo 9, agora com consequencia\n"
"de engenharia: o que a gramatica nao captura tem de virar codigo.\n\n";
DiagnosticBag semanticos;
const ResultadoSemantico r = verificarArquivo(a.arquivo, *a.raiz, semanticos);
out << "o que a analise semantica encontra no mesmo programa:\n\n";
semanticos.printAll(a.arquivo, out);
out << "\n erros semanticos: " << r.errosSemanticos
<< ", avisos: " << r.avisos << '\n';
}
void mostrarTabelaDeSimbolos(std::ostream& out) {
out << "a tabela de simbolos da Peneira\n\n";
Analise a = analisar("contatos.pen", kProgramaCorreto);
DiagnosticBag semanticos;
const ResultadoSemantico r = verificarArquivo(a.arquivo, *a.raiz, semanticos);
out << "padroes declarados e compilados no percurso 1:\n";
for (const PadraoCompilado& p : r.padroes) {
out << " " << p.nome << " notacao " << p.notacao << '\n'
<< " automato minimo: " << p.automato.quantidadeDeEstados()
<< " estados\n"
<< " tipo do casamento: " << nomeDoTipo(p.tipoDoCasamento)
<< '\n';
}
out << "\ninstrumentacao dos percursos:\n"
<< " nos visitados no percurso 1 (declaracoes): "
<< r.nosVisitadosPercurso1 << '\n'
<< " nos visitados no percurso 2 (usos): "
<< r.nosVisitadosPercurso2 << '\n'
<< " consultas a tabela: "
<< r.consultasNaTabela << '\n';
out << "\ndois percursos, e nao um, porque a linguagem permite que o bloco\n"
"rule apareca antes dos pattern que ele referencia. Com um percurso\n"
"so, um padrao declarado depois do uso seria reportado como\n"
"inexistente.\n";
out << "\nerros: " << r.errosSemanticos << ", avisos: " << r.avisos << '\n';
}
void mostrarEstrategiasDeEscopo(std::ostream& out) {
out << "duas estrategias de escopo, medidas\n\n";
// O mesmo roteiro de operações nas duas tabelas, com profundidade
// crescente. O que interessa é o custo de consulta em função da
// profundidade, e é ele que decide qual estrategia serve a esta
// linguagem.
out << " profundidade | sondagens A (empilhada) | sondagens B "
"(encadeada)\n";
out << " -------------+-------------------------+------------------\n";
for (std::size_t profundidade = 1; profundidade <= 8; ++profundidade) {
TabelaEmpilhada a;
TabelaEncadeada b;
SimboloSemantico global;
global.nome = "padrao_global";
global.especie = Especie::Padrao;
a.declarar(global);
b.declarar(global);
for (std::size_t i = 0; i < profundidade; ++i) {
a.entrarEscopo();
b.entrarEscopo();
SimboloSemantico local;
local.nome = "ligacao_" + std::to_string(i);
local.especie = Especie::Ligacao;
a.declarar(local);
b.declarar(local);
}
a.zerarSondagens();
b.zerarSondagens();
// Dez consultas ao nome mais externo, que é o pior caso da estratégia
// empilhada: ela precisa atravessar todos os escopos internos antes de
// achar.
for (int k = 0; k < 10; ++k) {
(void)a.consultar("padrao_global");
(void)b.consultar("padrao_global");
}
out << " " << (profundidade < 10 ? " " : " ") << profundidade
<< " | " << a.sondagens()
<< (a.sondagens() < 10 ? " " : (a.sondagens() < 100 ? " " : ""))
<< " | " << b.sondagens() << '\n';
}
out << "\n A estrategia empilhada paga a profundidade em toda consulta; a\n"
" encadeada consulta em tempo constante e paga na saida de escopo.\n"
" A Peneira vive na PRIMEIRA linha da tabela: um escopo global com\n"
" os pattern, mais um escopo de acao com a variavel de ligacao. Ali\n"
" a diferenca e de uma sondagem por consulta — 20 contra 10 em dez\n"
" consultas. Escolhemos a empilhada porque, nessa faixa, a vantagem\n"
" da outra nao existe e a saida de escopo e um pop em vez de um\n"
" laco de desfazimento.\n";
}
void mostrarInferenciaDeTipos(std::ostream& out) {
out << "o tipo de um casamento, decidido por automato\n\n";
out << "a pergunta 'este pattern casa sempre um numero?' e a pergunta de\n"
"inclusao de linguagens:\n\n"
" L(padrao) contido em L(NUMERO) <=> L(padrao) \\ L(NUMERO) = "
"vazio\n\n"
"e a diferenca de automatos seguida do teste de vacuidade sao as\n"
"operacoes do modulo 6. O verificador de tipos nao adivinha e nao\n"
"pergunta ao programador: ele decide.\n\n";
out << " automato de NUMERO (referencia): "
<< afdDeNumero().quantidadeDeEstados() << " estados\n\n";
Analise a = analisar("contatos.pen", kProgramaCorreto);
DiagnosticBag semanticos;
const ResultadoSemantico r = verificarArquivo(a.arquivo, *a.raiz, semanticos);
out << " padrao | estados | L(p) \\ L(NUMERO) | tipo inferido\n";
out << " ---------+---------+------------------+--------------\n";
for (const PadraoCompilado& p : r.padroes) {
const bool numerico = p.tipoDoCasamento == Tipo::Numero;
out << " " << p.nome;
for (std::size_t i = p.nome.size(); i < 8; ++i) {
out << ' ';
}
out << " | " << p.automato.quantidadeDeEstados()
<< (p.automato.quantidadeDeEstados() < 10 ? " " : " ")
<< " | " << (numerico ? "vazia " : "nao vazia ")
<< " | " << nomeDoTipo(p.tipoDoCasamento) << '\n';
}
out << "\ne dai sai a checagem de 'value': ela e permitida sobre a ligacao\n"
"de 'numero' e recusada sobre a de 'email', sem que ninguem tenha\n"
"escrito uma anotacao de tipo em lugar nenhum.\n";
}
void mostrarAtributos(std::ostream& out) {
out << "traducao dirigida por sintaxe: os dois fluxos, e a ordem\n\n";
Analise a = analisar("contatos.pen", kProgramaCorreto);
const GrafoDeAtributos g = construirGrafo(*a.raiz);
out << formatarGrafo(g) << '\n';
std::size_t sintetizados = 0;
std::size_t herdados = 0;
for (const Atributo& at : g.atributos) {
if (at.fluxo == Fluxo::Sintetizado) {
++sintetizados;
} else {
++herdados;
}
}
out << " sintetizados: " << sintetizados << " (o tipo sobe)\n"
<< " herdados: " << herdados << " (o escopo desce)\n\n";
const std::vector<std::size_t> ordem = ordemDeAvaliacao(g);
if (ordem.empty()) {
out << " HA CICLO no grafo: a gramatica de atributos e malformada\n";
} else {
out << " ordem topologica de avaliacao (" << ordem.size()
<< " passos):\n ";
for (std::size_t i = 0; i < ordem.size(); ++i) {
out << "[" << ordem[i] << "]";
if (i + 1 < ordem.size()) {
out << " ";
}
}
out << "\n\n Sem ciclo, logo a gramatica e bem definida. Repare que a\n"
" ordem nao e pos-ordem nem pre-ordem: os herdados exigem que o\n"
" pai venha antes, os sintetizados exigem que os filhos venham\n"
" antes, e so a ordem topologica atende as duas exigencias.\n\n";
}
const ClasseDaGramatica classe = classificar(g);
out << " S-atribuida: " << (classe.sAtribuida ? "sim" : "nao") << '\n'
<< " L-atribuida: " << (classe.lAtribuida ? "sim" : "nao") << '\n'
<< " " << classe.justificativa << '\n';
}
void mostrarErrosSemanticos(std::ostream& out) {
out << "erros semanticos deliberados e as mensagens produzidas\n\n";
Analise a = analisar("absurdo.pen", kProgramaAbsurdo);
DiagnosticBag semanticos;
const ResultadoSemantico r = verificarArquivo(a.arquivo, *a.raiz, semanticos);
semanticos.printAll(a.arquivo, out);
out << "\n erros: " << r.errosSemanticos << ", avisos: " << r.avisos
<< '\n';
out << "\n Quatro defeitos, quatro diagnosticos, e nenhum deles interrompeu\n"
" a verificacao dos demais. Cada mensagem nomeia o identificador\n"
" envolvido e aponta a posicao — que e o padrao exigivel a partir\n"
" deste modulo, agora que ha informacao suficiente para isso.\n";
}
} // namespace peneira::demoA demonstração --semantica roda o front-end sobre ele e reporta o que encontra:
erros sintaticos: 0
nos na arvore: 24Zero erros sintáticos, e o programa contém quatro defeitos. A primeira ação referencia um padrão telefone que não foi declarado em lugar nenhum. A segunda aplica value a uma variável ligada ao padrão de endereço eletrônico, que não casa números. A terceira compara diretamente um casamento com um literal numérico, sem a conversão. A quarta declara uma variável de ligação que não usa.
Vale enunciar por que a gramática não tem como reclamar de nenhum deles, porque a resposta é a mesma do módulo 9 e agora tem consequência de engenharia. A correspondência entre uma declaração e um uso a distância arbitrária não é exprimível por gramática livre de contexto: seria preciso lembrar, no momento do uso, de um conjunto ilimitado de nomes declarados antes, e a pilha do autômato não serve para isso — ela guarda o que falta reconhecer, não um dicionário. O resultado teórico do módulo 9, que lá parecia um exercício de fronteira, é o que obriga esta fase a existir.
A separação é limpa e vale para a linguagem de qualquer grupo: a sintaxe decide forma, a semântica decide sentido, e a fronteira entre as duas não é questão de gosto — é o que o formalismo alcança.
Onde é fácil errar aqui. Empurrar para a gramática o que é semântico, na tentativa de detectar cedo. Dá para escrever uma gramática que aceita value apenas sobre certos identificadores, e o preço é uma gramática que muda toda vez que a linguagem ganha um padrão. A regra que uso é: se a verificação depende de algo declarado em outro ponto do programa, ela é semântica.
Como verificar. O teste é o próprio programa acima: se o front-end reporta erro nele, o defeito está no analisador sintático, não no programa.
1.3 Tarefa 2: A tabela de símbolos, e as duas estratégias de escopo
A atividade — construir a tabela de símbolos com o tratamento de escopo adequado à linguagem, justificando a escolha.
Comecei decidindo o que a tabela guarda, e cada campo entrou porque alguma verificação precisa dele — nenhum entrou por completude.
12_simbolos.h
#ifndef PENEIRA_12_SIMBOLOS_H
#define PENEIRA_12_SIMBOLOS_H
#include <cstddef>
#include <cstdint>
#include <string>
#include <unordered_map>
#include <vector>
#include "01_source.h"
#include "12_tipos.h"
namespace peneira {
// O que a tabela guarda. A escolha dos campos não é neutra: cada um existe
// porque alguma verificação precisa dele.
//
// nome — a chave da consulta
// especie — distingue o que foi declarado por `pattern` do que foi ligado
// por `on p(x)`; sem isso, `on numero(numero)` passaria batido
// tipo — o que a verificação de tipos consome
// posicao — para a mensagem "declarado aqui" da redeclaração
// usado — para o aviso de declaração sem uso, que só pode ser emitido
// depois que a árvore inteira foi percorrida
enum class Especie : std::uint8_t { Padrao, Ligacao };
const char* nomeDaEspecie(Especie e) noexcept;
struct SimboloSemantico {
std::string nome;
Especie especie = Especie::Padrao;
Tipo tipo = Tipo::Texto;
Position posicao{0, 0, 0};
bool usado = false;
// Só para Especie::Padrao: o índice do autômato compilado na lista de
// padrões. O módulo 14 vai emitir esse vetor; guardar o índice aqui é o
// que liga o nome ao autômato sem que a tabela conheça a classe Afd.
std::size_t indicePadrao = 0;
};
// ---------------------------------------------------------------------------
// Estratégia A: uma tabela por escopo, empilhadas.
// ---------------------------------------------------------------------------
//
// Entrar num escopo empilha uma tabela vazia; sair desempilha e destrói. A
// consulta caminha a pilha do topo para a base e para no primeiro acerto — é
// a regra de visibilidade escrita como percurso.
//
// Compromisso: entrada e saída de escopo custam O(1) e não tocam nos símbolos
// existentes, mas a consulta custa O(profundidade) no pior caso, porque um
// nome global visto do fundo de dez escopos aninhados exige dez consultas
// falhadas antes do acerto.
class TabelaEmpilhada {
public:
TabelaEmpilhada();
void entrarEscopo();
void sairEscopo();
std::size_t profundidade() const noexcept;
// Insere no escopo atual. Devolve false se o nome já existe **neste**
// escopo — sombrear um nome de escopo externo é legítimo e não é erro.
bool declarar(const SimboloSemantico& s);
// Consulta obedecendo à visibilidade: do escopo atual para fora.
const SimboloSemantico* consultar(const std::string& nome) const;
SimboloSemantico* consultarMutavel(const std::string& nome);
// Consulta restrita ao escopo atual, que é o que a checagem de
// redeclaração precisa.
const SimboloSemantico* consultarLocal(const std::string& nome) const;
// Instrumentação: quantas tabelas foram examinadas nas consultas. É o
// número que torna o compromisso mensurável em vez de afirmado.
std::size_t sondagens() const noexcept;
void zerarSondagens() noexcept;
std::vector<const SimboloSemantico*> todosDoEscopoAtual() const;
private:
std::vector<std::unordered_map<std::string, SimboloSemantico>> escopos_;
mutable std::size_t sondagens_ = 0;
};
// ---------------------------------------------------------------------------
// Estratégia B: tabela única, com pilha de declarações por nome.
// ---------------------------------------------------------------------------
//
// Um só mapa, do nome para a pilha de declarações ativas daquele nome. A
// declaração mais recente fica no topo, e é ela que a consulta devolve — a
// visibilidade vira o topo da pilha em vez de um percurso.
//
// Compromisso invertido em relação à estratégia A: a consulta é O(1) sempre,
// independente da profundidade, mas sair de um escopo custa O(declarações
// daquele escopo), porque cada nome declarado nele precisa ser desempilhado.
// Por isso a classe mantém a trilha de desfazimento — sem ela, sair de escopo
// exigiria varrer o mapa inteiro.
class TabelaEncadeada {
public:
TabelaEncadeada();
void entrarEscopo();
void sairEscopo();
std::size_t profundidade() const noexcept;
bool declarar(const SimboloSemantico& s);
const SimboloSemantico* consultar(const std::string& nome) const;
SimboloSemantico* consultarMutavel(const std::string& nome);
const SimboloSemantico* consultarLocal(const std::string& nome) const;
std::size_t sondagens() const noexcept;
void zerarSondagens() noexcept;
private:
struct Entrada {
SimboloSemantico simbolo;
std::size_t nivel = 0;
};
std::unordered_map<std::string, std::vector<Entrada>> pilhasPorNome_;
// Trilha de desfazimento: os nomes declarados em cada nível, na ordem.
std::vector<std::vector<std::string>> trilha_;
std::size_t nivel_ = 0;
mutable std::size_t sondagens_ = 0;
};
// A Peneira usa a estratégia A. A razão é a profundidade: a linguagem tem
// exatamente dois níveis de escopo — o global, com os `pattern`, e o da ação,
// com a variável de ligação —, e com profundidade dois a vantagem de consulta
// da estratégia B não se paga. A estratégia B está implementada assim mesmo,
// e é exercitada pela demonstração comparativa: a decisão só é defensável se
// medida, e as duas precisam existir para haver medida.
using TabelaDeSimbolos = TabelaEmpilhada;
} // namespace peneira
#endif // PENEIRA_12_SIMBOLOS_HO nome é a chave. A espécie distingue o que foi declarado por pattern do que foi ligado por on p(x), e sem ela um programa que usa um padrão como se fosse valor passaria batido. O tipo é o que a verificação de tipos consome. A posição existe para a mensagem de redeclaração poder dizer onde estava a primeira, porque “já declarado” sem dizer onde obriga o autor a procurar. E o campo usado só pode ser lido depois que a árvore inteira foi percorrida, o que já antecipa a discussão de percursos da tarefa 4.
A parte que exigiu decisão de verdade foi o escopo. A atividade pede que o grupo trate escopos aninhados se a linguagem tiver, e a Peneira tem: os pattern são globais, e cada on p(x) abre um escopo com a variável de ligação x, visível apenas dentro daquela ação. São dois níveis, e é a existência do segundo que justifica a tabela ter escopos em vez de ser um mapa único.
Há duas estratégias clássicas para isso, e implementei as duas. A razão é que o compromisso entre elas é o conteúdo do tópico, e afirmar um compromisso sem medi-lo é o tipo de afirmação que este material não faz.
12_simbolos.cpp
#include "12_simbolos.h"
namespace peneira {
const char* nomeDaEspecie(Especie e) noexcept {
switch (e) {
case Especie::Padrao: return "padrao";
case Especie::Ligacao: return "ligacao";
}
return "<desconhecida>";
}
// ---------------------------------------------------------------------------
// TabelaEmpilhada
// ---------------------------------------------------------------------------
TabelaEmpilhada::TabelaEmpilhada() {
// O escopo global já nasce aberto. Sem isso, todo usuário da classe teria
// de lembrar de abrir um, e esquecer produziria acesso a pilha vazia.
escopos_.emplace_back();
}
void TabelaEmpilhada::entrarEscopo() { escopos_.emplace_back(); }
void TabelaEmpilhada::sairEscopo() {
// O escopo global nunca sai. Proteger aqui é mais barato que descobrir o
// desbalanceamento como acesso inválido três fases adiante.
if (escopos_.size() > 1) {
escopos_.pop_back();
}
}
std::size_t TabelaEmpilhada::profundidade() const noexcept {
return escopos_.size();
}
bool TabelaEmpilhada::declarar(const SimboloSemantico& s) {
auto& atual = escopos_.back();
if (atual.find(s.nome) != atual.end()) {
return false;
}
atual.emplace(s.nome, s);
return true;
}
const SimboloSemantico* TabelaEmpilhada::consultar(const std::string& nome) const {
// Do topo para a base: a primeira ocorrência encontrada é a visível, e é
// exatamente isso que faz o sombreamento funcionar sem código extra.
for (std::size_t i = escopos_.size(); i > 0; --i) {
++sondagens_;
const auto& escopo = escopos_[i - 1];
const auto it = escopo.find(nome);
if (it != escopo.end()) {
return &it->second;
}
}
return nullptr;
}
SimboloSemantico* TabelaEmpilhada::consultarMutavel(const std::string& nome) {
for (std::size_t i = escopos_.size(); i > 0; --i) {
++sondagens_;
auto& escopo = escopos_[i - 1];
const auto it = escopo.find(nome);
if (it != escopo.end()) {
return &it->second;
}
}
return nullptr;
}
const SimboloSemantico* TabelaEmpilhada::consultarLocal(const std::string& nome) const {
const auto& atual = escopos_.back();
const auto it = atual.find(nome);
return it == atual.end() ? nullptr : &it->second;
}
std::size_t TabelaEmpilhada::sondagens() const noexcept { return sondagens_; }
void TabelaEmpilhada::zerarSondagens() noexcept { sondagens_ = 0; }
std::vector<const SimboloSemantico*> TabelaEmpilhada::todosDoEscopoAtual() const {
std::vector<const SimboloSemantico*> saida;
for (const auto& par : escopos_.back()) {
saida.push_back(&par.second);
}
return saida;
}
// ---------------------------------------------------------------------------
// TabelaEncadeada
// ---------------------------------------------------------------------------
TabelaEncadeada::TabelaEncadeada() { trilha_.emplace_back(); }
void TabelaEncadeada::entrarEscopo() {
++nivel_;
trilha_.emplace_back();
}
void TabelaEncadeada::sairEscopo() {
if (nivel_ == 0) {
return;
}
// Aqui está o custo desta estratégia, e ele é visível: cada nome declarado
// no nível que termina precisa ser desempilhado individualmente. Sem a
// trilha, a alternativa seria varrer o mapa inteiro procurando entradas
// deste nível — trocaria um custo proporcional às declarações do escopo
// por outro proporcional ao programa todo.
for (const std::string& nome : trilha_.back()) {
const auto it = pilhasPorNome_.find(nome);
if (it != pilhasPorNome_.end() && !it->second.empty()) {
it->second.pop_back();
if (it->second.empty()) {
pilhasPorNome_.erase(it);
}
}
}
trilha_.pop_back();
--nivel_;
}
std::size_t TabelaEncadeada::profundidade() const noexcept {
return nivel_ + 1;
}
bool TabelaEncadeada::declarar(const SimboloSemantico& s) {
// A consulta vem antes da inserção de propósito: `operator[]` criaria uma
// pilha vazia para o nome mesmo quando a declaração vai ser recusada, e
// essa entrada fantasma faria `consultar` devolver nulo por um caminho
// diferente do "nome inexistente" — mesma resposta, motivo diferente, e a
// diferença apareceria mais tarde como um erro difícil de localizar.
const auto existente = pilhasPorNome_.find(s.nome);
if (existente != pilhasPorNome_.end() && !existente->second.empty() &&
existente->second.back().nivel == nivel_) {
return false;
}
pilhasPorNome_[s.nome].push_back(Entrada{s, nivel_});
trilha_.back().push_back(s.nome);
return true;
}
const SimboloSemantico* TabelaEncadeada::consultar(const std::string& nome) const {
++sondagens_;
const auto it = pilhasPorNome_.find(nome);
if (it == pilhasPorNome_.end() || it->second.empty()) {
return nullptr;
}
return &it->second.back().simbolo;
}
SimboloSemantico* TabelaEncadeada::consultarMutavel(const std::string& nome) {
++sondagens_;
const auto it = pilhasPorNome_.find(nome);
if (it == pilhasPorNome_.end() || it->second.empty()) {
return nullptr;
}
return &it->second.back().simbolo;
}
const SimboloSemantico* TabelaEncadeada::consultarLocal(const std::string& nome) const {
const auto it = pilhasPorNome_.find(nome);
if (it == pilhasPorNome_.end() || it->second.empty()) {
return nullptr;
}
if (it->second.back().nivel != nivel_) {
return nullptr;
}
return &it->second.back().simbolo;
}
std::size_t TabelaEncadeada::sondagens() const noexcept { return sondagens_; }
void TabelaEncadeada::zerarSondagens() noexcept { sondagens_ = 0; }
} // namespace peneiraA estratégia empilhada mantém uma tabela por escopo. Entrar empilha uma tabela vazia, sair desempilha e destrói, e a consulta caminha do topo para a base parando no primeiro acerto — a regra de visibilidade escrita como percurso, sem código extra para sombreamento. A estratégia encadeada mantém um mapa único do nome para a pilha de declarações ativas daquele nome; a consulta devolve o topo e custa o mesmo em qualquer profundidade, mas sair de escopo exige desempilhar cada nome declarado nele, e é por isso que a classe carrega uma trilha de desfazimento.
Instrumentei as duas com um contador de sondagens e medi. A demonstração --escopos faz dez consultas ao nome mais externo — o pior caso da empilhada — em profundidades crescentes:
| Profundidade | Sondagens (empilhada) | Sondagens (encadeada) |
|---|---|---|
| 1 | 20 | 10 |
| 2 | 30 | 10 |
| 4 | 50 | 10 |
| 8 | 90 | 10 |
O compromisso fica visível: a empilhada paga a profundidade em toda consulta, a encadeada paga na saída de escopo e consulta em tempo constante.
E fica visível também que, para esta linguagem, a escolha é a empilhada. A Peneira vive na primeira linha da tabela: um escopo global e um de ação. Ali a diferença é de uma sondagem por consulta, e a estratégia mais simples de destruir corretamente vence — sair de escopo é um pop, sem trilha de desfazimento para manter em dia. A conclusão se inverteria numa linguagem com blocos aninhados profundos, e é por isso que a medição importa mais que a preferência.
Onde é fácil errar aqui. Tratar redeclaração e sombreamento como o mesmo caso. Declarar duas vezes o mesmo nome no mesmo escopo é erro; declarar um nome que já existe num escopo externo é sombreamento, e é legítimo. A distinção exige uma consulta restrita ao escopo atual, separada da consulta que respeita a visibilidade — são duas operações, e uni-las produz um compilador que recusa programas válidos.
Como verificar. O teste que uso é de simetria: depois de entrar e sair de um escopo, a tabela tem de responder exatamente o que respondia antes. Na estratégia encadeada, é esse teste que pega a trilha de desfazimento incompleta, e ele falha em silêncio se a única coisa verificada for o caminho feliz.
1.4 Tarefa 3: O tipo decidido por autômato
A atividade — implementar a verificação de compatibilidade de tipos.
O sistema de tipos da Peneira tem três tipos e nenhum construtor de tipo: número, texto e um tipo de erro.
12_tipos.h
#ifndef PENEIRA_12_TIPOS_H
#define PENEIRA_12_TIPOS_H
#include <cstdint>
#include <string>
#include "03_afd.h"
namespace peneira {
// O sistema de tipos da Peneira.
//
// São três tipos e nenhuma construção composta — nem registro, nem função,
// nem vetor. Isso torna a **equivalência estrutural** e a **equivalência por
// nome** indistinguíveis aqui: sem construtores de tipo não há duas árvores
// de tipo diferentes com a mesma forma, então as duas noções colapsam.
// Registro isso porque a distinção é central em linguagens maiores e não tem
// como ser exercitada nesta: numa linguagem com registros, `struct {int x;}`
// e `struct {int y;}` são estruturalmente diferentes e `Ponto` e `Par`
// declarados iguais são estruturalmente iguais e nominalmente diferentes.
enum class Tipo : std::uint8_t {
Numero,
Texto,
// Tipo de erro. Existe para que uma expressão malformada não produza uma
// cascata de mensagens: quem recebe Erro como operando cala a boca, porque
// o erro de verdade já foi reportado embaixo. É a técnica que evita o
// relatório de trinta linhas para um defeito só.
Erro,
};
const char* nomeDoTipo(Tipo t) noexcept;
// Compatibilidade dos operandos de uma comparação.
//
// A regra é a mais restritiva possível: os dois lados têm de ter o **mesmo**
// tipo. Não há conversão implícita nenhuma nesta linguagem, e a decisão é
// deliberada — em `where value(n) > "100"` a intenção do autor é ambígua, e
// converter em silêncio escolheria uma das leituras sem avisar. A conversão
// existe, mas é explícita e tem nome: `value`.
//
// Devolve Erro quando os tipos não casam, e propaga Erro sem reclamar.
bool comparacaoValida(Tipo esquerda, Tipo direita) noexcept;
// Os operadores de ordem (`>`, `<`, `>=`, `<=`) só fazem sentido sobre número;
// os de igualdade (`==`, `!=`) valem para os dois tipos. Comparar textos por
// ordem seria definível (ordem lexicográfica), e não defini: a linguagem não
// tem caso de uso, e um operador que existe sem uso é superfície de erro.
bool operadorDeOrdem(const std::string& operador) noexcept;
// Inferência do tipo de um casamento de padrão.
//
// Aqui está a decisão de projeto que dá identidade a esta fase, e ela reusa o
// que o módulo 6 construiu. A pergunta "o que este `pattern` casa é sempre um
// número?" é a pergunta de **inclusão de linguagens**:
//
// L(padrao) subconjunto de L(NUMERO) <=> L(padrao) \ L(NUMERO) = vazio
//
// e a diferença de dois autômatos finitos, seguida do teste de vacuidade, é
// exatamente o par de operações do módulo 6. Nenhuma heurística sobre o texto
// da expressão regular, nenhuma anotação do programador: o tipo é **decidido**,
// e é decidido pela mesma maquinaria de autômatos que o resto do compilador já
// usa para outra coisa.
//
// O caso degenerado importa: um padrão cuja linguagem é vazia é subconjunto de
// qualquer coisa, inclusive dos números. Tratar isso como Numero seria
// tecnicamente correto e praticamente inútil, então a função devolve Texto e
// quem chama reporta o padrão vazio como problema à parte.
Tipo inferirTipoDoCasamento(const Afd& padrao);
// O autômato mínimo da categoria NUMERO, construído a partir da mesma
// especificação léxica do módulo 2 e memorizado na primeira chamada. É o lado
// direito da inclusão acima.
const Afd& afdDeNumero();
} // namespace peneira
#endif // PENEIRA_12_TIPOS_HDuas decisões merecem defesa antes do código.
A primeira é o tipo de erro. Ele existe para que uma expressão malformada não gere uma cascata: quem recebe erro como operando não reclama, porque o defeito de verdade já foi reportado embaixo. É a técnica que evita o relatório de trinta linhas para um problema só, e ela custa três linhas.
A segunda é a ausência de conversão implícita, e ela é deliberada. Em where value(n) > "100" a intenção do autor é ambígua, e converter em silêncio escolheria uma das leituras sem avisar. A conversão existe nesta linguagem, e ela tem nome: value. Tornar a conversão visível no programa é o que permite ao compilador recusar o resto.
Vale registrar o que esta linguagem não consegue exercitar. A distinção entre equivalência estrutural e equivalência por nome é central em linguagens com registros e apelidos de tipo, e aqui ela colapsa: sem construtores de tipo, não há duas árvores de tipo distintas com a mesma forma, nem duas declarações distintas com a mesma estrutura. Anoto isso no cabeçalho em vez de fingir que o assunto foi coberto.
1.4.1 A parte que decide, em vez de adivinhar
Aqui está o problema central do módulo. value(n) só faz sentido se o padrão ligado a n casar sempre um número. Como o compilador sabe disso?
Considerei as duas saídas óbvias e descartei as duas. Pedir uma anotação ao programador transfere ao autor uma verificação que o compilador tem informação para fazer. Inspecionar o texto da expressão regular procurando dígitos é heurística, e heurística erra nos dois sentidos.
A saída certa apareceu ao reler o que o módulo 6 tinha deixado pronto. A pergunta
L(\text{padrao}) \subseteq L(\text{NUMERO})
é equivalente a
L(\text{padrao}) \setminus L(\text{NUMERO}) = \emptyset
e a diferença de dois autômatos finitos, seguida do teste de vacuidade, são exatamente as duas operações que o módulo 6 implementou. O tipo do casamento é decidido, não estimado:
12_tipos.cpp
#include "12_tipos.h"
#include <string>
#include <vector>
#include "02_lexico.h"
#include "04_notacao.h"
#include "04_thompson.h"
#include "05_determinizacao.h"
#include "05_minimizacao.h"
#include "06_fechamento.h"
namespace peneira {
const char* nomeDoTipo(Tipo t) noexcept {
switch (t) {
case Tipo::Numero: return "numero";
case Tipo::Texto: return "texto";
case Tipo::Erro: return "<erro>";
}
return "<desconhecido>";
}
bool comparacaoValida(Tipo esquerda, Tipo direita) noexcept {
// Erro é absorvente e silencioso: o defeito já foi reportado no operando.
if (esquerda == Tipo::Erro || direita == Tipo::Erro) {
return true;
}
return esquerda == direita;
}
bool operadorDeOrdem(const std::string& operador) noexcept {
return operador == ">" || operador == "<" || operador == ">=" ||
operador == "<=";
}
const Afd& afdDeNumero() {
// Construído uma vez, na primeira chamada, e reusado. O caminho é o mesmo
// pipeline dos módulos 4 e 5 — notação, Thompson, subconjuntos, Moore —
// aplicado à notação que já está na especificação léxica do módulo 2. Não
// há uma segunda definição de "o que é um número" neste compilador, e é
// essa unicidade que impede o verificador de tipos e o analisador léxico
// de divergirem.
static const Afd numero = [] {
std::string notacao;
for (const CategoriaLexica& c : especificacaoLexica()) {
if (c.nome == "NUMERO") {
notacao = c.notacao;
break;
}
}
const ResultadoNotacao r = analisarNotacao(notacao);
const Afn afn = thompson(*r.expressao, "NUMERO");
return minimizar(determinizar(afn, "NUMERO"), "NUMERO");
}();
return numero;
}
Tipo inferirTipoDoCasamento(const Afd& padrao) {
const Afd& numero = afdDeNumero();
// O alfabeto tem de ser explícito e comum aos dois autômatos. Esta é a
// armadilha que o módulo 6 documentou: a diferença é definida com o
// complemento embutido, e o complemento só está certo em relação a um
// alfabeto declarado. Inferir o alfabeto dos símbolos usados faria a
// resposta sair certa para os símbolos que aparecem e errada, em silêncio,
// para os demais.
const std::vector<Simbolo> alfabeto = alfabetoComum(padrao, numero);
// L(padrao) \ L(numero) vazio <=> todo casamento do padrão é um número.
const Afd sobra = diferencaAfd(padrao, numero, alfabeto, "sobra");
if (!linguagemVazia(sobra)) {
return Tipo::Texto;
}
// Padrão de linguagem vazia é subconjunto de tudo, e classificá-lo como
// número seria verdadeiro e inútil. Devolvemos Texto; o padrão vazio é
// reportado à parte, como o defeito que ele é.
if (linguagemVazia(padrao)) {
return Tipo::Texto;
}
return Tipo::Numero;
}
} // namespace peneiraA demonstração --tipos mostra o resultado sobre o programa de exemplo:
automato de NUMERO (referencia): 5 estados
padrao | estados | L(p) \ L(NUMERO) | tipo inferido
---------+---------+------------------+--------------
email | 6 | nao vazia | texto
numero | 5 | vazia | numeroO padrão numero tem diferença vazia e é classificado como numérico; o de endereço eletrônico não, e é texto. Ninguém escreveu anotação de tipo em lugar nenhum, e a partir daí value é permitido sobre a ligação de um e recusado sobre a do outro.
Duas armadilhas ficaram documentadas no código. A primeira é o alfabeto explícito: a diferença tem o complemento embutido, e o complemento só está certo em relação a um alfabeto declarado — inferi-lo dos símbolos que aparecem daria resposta certa para eles e errada, em silêncio, para os demais. É a mesma lição que o módulo 6 já tinha pago. A segunda é o padrão de linguagem vazia, que é subconjunto de tudo, inclusive dos números: classificá-lo como numérico seria tecnicamente correto e praticamente inútil, então ele é reportado à parte, como o defeito que é.
Registro também o que não fiz e por quê. O autômato de referência do número é construído a partir da mesma especificação léxica do módulo 2, pelo mesmo caminho de Thompson, subconjuntos e minimização. Não há uma segunda definição de “o que é um número” neste compilador, e é essa unicidade que impede o verificador de tipos e o analisador léxico de divergirem — que foi exatamente o defeito de cinco módulos corrigido no módulo 7.
Onde é fácil errar aqui. Inverter a diferença. L(NUMERO) \ L(padrao) também é uma pergunta legítima, e é a pergunta errada: ela responde se o padrão casa todos os números, e não se casa apenas números. A inversão passa nos testes com o padrão que é idêntico ao número, que é justamente o primeiro que se testa.
Como verificar. O padrão numero do exemplo tem notação idêntica à da categoria NUMERO, e o autômato mínimo dele tem os mesmos 5 estados do de referência — o módulo 5 já tinha mostrado que o autômato mínimo é único, então a coincidência de tamanho é a confirmação esperada. Um padrão estritamente mais restrito, como só dígitos sem sinal, também tem de sair numérico; se sair texto, a diferença está invertida.
1.5 Tarefa 4: Os percursos, e por que são dois
A atividade — organizar as verificações como percursos sobre a árvore e registrar as decisões de projeto.
12_sema.h
#ifndef PENEIRA_12_SEMA_H
#define PENEIRA_12_SEMA_H
#include <cstddef>
#include <string>
#include <vector>
#include "01_diagnostico.h"
#include "03_afd.h"
#include "10_ast.h"
#include "12_simbolos.h"
#include "12_tipos.h"
namespace peneira {
// Análise semântica da Peneira.
//
// Organizada em DOIS percursos sobre a árvore, e a quantidade não é escolha
// estética. O primeiro coleta as declarações de `pattern`; o segundo verifica
// as ações. Um percurso só não bastaria, e a razão é concreta: a linguagem
// permite que um bloco `rule` apareça antes do `pattern` que ele referencia,
// e um verificador de passagem única acusaria "padrao nao declarado" para um
// padrão declarado três linhas abaixo. Ou se aceita a ordem obrigatória de
// declaração, ou se faz dois percursos. Escolhemos dois.
//
// O primeiro percurso também é onde os autômatos dos padrões são construídos,
// porque o tipo da variável de ligação depende do autômato — e o segundo
// percurso precisa do tipo pronto. Essa dependência é o que fixa a ordem entre
// os dois: não é preferência, é o grafo de dependências mandando.
struct PadraoCompilado {
std::string nome;
std::string notacao;
Afd automato;
Tipo tipoDoCasamento = Tipo::Texto;
};
struct ResultadoSemantico {
// Os padrões na ordem de declaração. O módulo 14 emite este vetor.
std::vector<PadraoCompilado> padroes;
std::size_t errosSemanticos = 0;
std::size_t avisos = 0;
// Instrumentação dos percursos, para a demonstração.
std::size_t nosVisitadosPercurso1 = 0;
std::size_t nosVisitadosPercurso2 = 0;
std::size_t consultasNaTabela = 0;
};
class AnalisadorSemantico {
public:
AnalisadorSemantico(const SourceFile& fonte, DiagnosticBag& diagnosticos);
// Verifica a árvore inteira. Não para no primeiro erro: cada verificação
// reporta e segue, porque um relatório com os cinco problemas do programa
// vale cinco execuções de um que para no primeiro.
ResultadoSemantico verificar(const NoAst& raiz);
private:
// Percurso 1: coleta declarações de padrão, compila os autômatos e infere
// o tipo do casamento de cada um.
void coletarDeclaracoes(const NoAst& no);
// Percurso 2: verifica as ações, as condições e as emissões.
void verificarUsos(const NoAst& no);
void verificarAcao(const NoAst& acao);
// Avalia o tipo de uma expressão, reportando o que estiver errado no
// caminho. Devolve Tipo::Erro quando não conseguiu decidir — e o valor de
// erro é absorvente, o que impede a cascata de mensagens.
Tipo tipoDe(const NoAst& expr);
void erro(const NoAst& no, const std::string& mensagem);
void aviso(const NoAst& no, const std::string& mensagem);
const SourceFile& fonte_;
DiagnosticBag& diagnosticos_;
TabelaDeSimbolos tabela_;
ResultadoSemantico resultado_;
};
// Atalho para as demonstrações e para o programa principal.
ResultadoSemantico verificarArquivo(const SourceFile& arquivo,
const NoAst& raiz,
DiagnosticBag& diagnosticos);
} // namespace peneira
#endif // PENEIRA_12_SEMA_HA decisão é quantos percursos, e a resposta aqui é dois. Não por gosto: por duas dependências concretas.
A primeira é que a linguagem permite que o bloco rule apareça antes dos pattern que ele referencia. Um verificador de passagem única acusaria “padrão não declarado” para um padrão declarado três linhas abaixo. Ou se exige ordem de declaração — restrição real imposta ao usuário para conveniência do compilador —, ou se fazem dois percursos. Escolhi dois.
A segunda é mais forte e não tem alternativa. O tipo da variável de ligação depende do autômato do padrão, que é construído no primeiro percurso; o segundo percurso precisa desse tipo pronto para verificar value. A ordem entre os dois não é preferência, é o grafo de dependências mandando.
Então o primeiro percurso coleta declarações, compila autômatos e infere tipos; o segundo verifica ações, condições e emissões:
12_sema.cpp
#include "12_sema.h"
#include <string>
#include <utility>
#include "04_notacao.h"
#include "04_thompson.h"
#include "05_determinizacao.h"
#include "05_minimizacao.h"
#include "06_fechamento.h"
namespace peneira {
AnalisadorSemantico::AnalisadorSemantico(const SourceFile& fonte,
DiagnosticBag& diagnosticos)
: fonte_(fonte), diagnosticos_(diagnosticos) {}
void AnalisadorSemantico::erro(const NoAst& no, const std::string& mensagem) {
diagnosticos_.error(no.posicao, mensagem);
++resultado_.errosSemanticos;
}
void AnalisadorSemantico::aviso(const NoAst& no, const std::string& mensagem) {
diagnosticos_.warning(no.posicao, mensagem);
++resultado_.avisos;
}
// ---------------------------------------------------------------------------
// Percurso 1 — declarações
// ---------------------------------------------------------------------------
void AnalisadorSemantico::coletarDeclaracoes(const NoAst& no) {
++resultado_.nosVisitadosPercurso1;
if (no.tipo == TipoAst::DeclPadrao) {
// Redeclaração. A mensagem cita a posição da primeira ocorrência,
// porque "ja declarado" sem dizer onde obriga o autor a procurar.
if (const SimboloSemantico* anterior = tabela_.consultarLocal(no.texto)) {
erro(no, "padrao '" + no.texto +
"' ja declarado na linha " +
std::to_string(anterior->posicao.line));
return;
}
// Compila a expressão regular pelo mesmo caminho dos módulos 4 e 5.
// Um erro de notação aqui é erro semântico, não léxico: o analisador
// léxico reconheceu um PADRAO bem formado (delimitado por barras); o
// que está malformado é o conteúdo dele, e só quem sabe interpretá-lo
// pode reclamar.
const ResultadoNotacao r = analisarNotacao(no.conteudo);
if (!r.ok || !r.expressao) {
erro(no, "expressao regular invalida no padrao '" + no.texto +
"': " + r.erro);
return;
}
const Afn afn = thompson(*r.expressao, no.texto);
Afd automato = minimizar(determinizar(afn, no.texto), no.texto);
// Padrão que não casa com nada nunca dispara a regra. É defeito, e o
// compilador tem como saber: a linguagem do autômato é vazia.
if (linguagemVazia(automato)) {
aviso(no, "o padrao '" + no.texto +
"' nao casa com nenhuma cadeia: a regra que o usar "
"nunca dispara");
}
const Tipo tipoCasamento = inferirTipoDoCasamento(automato);
SimboloSemantico s;
s.nome = no.texto;
s.especie = Especie::Padrao;
s.tipo = tipoCasamento;
s.posicao = no.posicao;
s.indicePadrao = resultado_.padroes.size();
tabela_.declarar(s);
// Inicialização agregada, e não campo a campo: `Afd` não tem
// construtor padrão — todo autômato nasce com nome, por decisão do
// módulo 3 —, então um `PadraoCompilado p;` vazio nem compila. Montar
// o registro de uma vez é o que respeita essa invariante.
resultado_.padroes.push_back(PadraoCompilado{
no.texto, no.conteudo, std::move(automato), tipoCasamento});
return;
}
for (const AstPtr& filho : no.filhos) {
if (filho) {
coletarDeclaracoes(*filho);
}
}
}
// ---------------------------------------------------------------------------
// Percurso 2 — usos
// ---------------------------------------------------------------------------
void AnalisadorSemantico::verificarUsos(const NoAst& no) {
++resultado_.nosVisitadosPercurso2;
if (no.tipo == TipoAst::Acao) {
verificarAcao(no);
return;
}
for (const AstPtr& filho : no.filhos) {
if (filho) {
verificarUsos(*filho);
}
}
}
void AnalisadorSemantico::verificarAcao(const NoAst& acao) {
// `on <padrao>(<ligacao>)`. O padrão referenciado tem de existir.
SimboloSemantico* padrao = tabela_.consultarMutavel(acao.texto);
Tipo tipoDaLigacao = Tipo::Erro;
if (padrao == nullptr) {
erro(acao, "padrao '" + acao.texto + "' nao foi declarado");
} else if (padrao->especie != Especie::Padrao) {
erro(acao, "'" + acao.texto +
"' nao e um padrao: e uma variavel de ligacao");
} else {
padrao->usado = true;
tipoDaLigacao = padrao->tipo;
}
// A ligação abre um escopo. É o único escopo aninhado da linguagem, e é o
// que justifica a tabela ter escopos em vez de ser um mapa só.
tabela_.entrarEscopo();
SimboloSemantico ligacao;
ligacao.nome = acao.conteudo;
ligacao.especie = Especie::Ligacao;
ligacao.tipo = tipoDaLigacao;
ligacao.posicao = acao.posicao;
tabela_.declarar(ligacao);
// Sombreamento: se a variável de ligação tem o mesmo nome de um padrão, o
// padrão fica invisível dentro da ação. É legítimo — a regra de
// visibilidade diz que o mais interno vence — e é confuso o bastante para
// merecer aviso.
if (padrao != nullptr && acao.conteudo == acao.texto) {
aviso(acao, "a variavel de ligacao '" + acao.conteudo +
"' tem o mesmo nome do padrao e o esconde dentro "
"desta acao");
}
// filhos[0] é a condição `where`, ou nulo quando a ação não tem uma.
if (!acao.filhos.empty() && acao.filhos[0]) {
const Tipo tipoCondicao = tipoDe(*acao.filhos[0]);
if (tipoCondicao != Tipo::Erro && tipoCondicao != Tipo::Numero) {
// A condição precisa ser um valor de verdade, e o único jeito de
// produzir um nesta linguagem é comparar ou combinar comparações.
// Uma condição que é só `n` não é verificável.
erro(*acao.filhos[0],
"a condicao de 'where' precisa ser uma comparacao, e nao um "
"valor de tipo " +
std::string(nomeDoTipo(tipoCondicao)));
}
}
// O último filho é a emissão.
if (!acao.filhos.empty() && acao.filhos.back() &&
acao.filhos.back()->tipo == TipoAst::Emissao) {
const NoAst& emissao = *acao.filhos.back();
if (!emissao.filhos.empty() && emissao.filhos[0]) {
tipoDe(*emissao.filhos[0]);
}
}
// Uma variável de ligação declarada e nunca usada indica, quase sempre,
// que a ação deveria ter uma condição e não tem. O aviso só pode sair
// aqui, depois de a subárvore inteira ter sido percorrida — é o exemplo
// mais simples de verificação que exige a informação coletada, e não a
// que desce.
if (const SimboloSemantico* l = tabela_.consultarLocal(acao.conteudo)) {
if (!l->usado) {
aviso(acao, "a variavel de ligacao '" + acao.conteudo +
"' nao e usada nesta acao");
}
}
tabela_.sairEscopo();
}
// ---------------------------------------------------------------------------
// Tipos
// ---------------------------------------------------------------------------
Tipo AnalisadorSemantico::tipoDe(const NoAst& expr) {
switch (expr.tipo) {
case TipoAst::LiteralNumero:
return Tipo::Numero;
case TipoAst::LiteralTexto:
return Tipo::Texto;
case TipoAst::Referencia: {
SimboloSemantico* s = tabela_.consultarMutavel(expr.texto);
if (s == nullptr) {
erro(expr, "'" + expr.texto + "' nao foi declarado");
return Tipo::Erro;
}
s->usado = true;
if (s->especie == Especie::Padrao) {
erro(expr, "'" + expr.texto +
"' e um padrao e nao pode ser usado como "
"valor; use a variavel de ligacao da acao");
return Tipo::Erro;
}
// Uma referência a variável de ligação vale o texto casado. Mesmo
// quando o padrão só casa números, o casamento continua sendo
// texto: é `value` que converte, e essa separação é o que torna a
// conversão visível no programa.
return Tipo::Texto;
}
case TipoAst::ValorDe: {
SimboloSemantico* s = tabela_.consultarMutavel(expr.texto);
if (s == nullptr) {
erro(expr, "'" + expr.texto +
"' nao foi declarado; 'value' so se aplica a "
"uma variavel de ligacao");
return Tipo::Erro;
}
s->usado = true;
if (s->especie != Especie::Ligacao) {
erro(expr, "'value' so se aplica a variavel de ligacao, e '" +
expr.texto + "' e um padrao");
return Tipo::Erro;
}
// AQUI está a verificação que só o autômato consegue decidir. O
// tipo guardado no símbolo veio de `L(padrao) subconjunto de
// L(NUMERO)`, decidido no percurso 1 pela diferença de autômatos
// do módulo 6. Sem isso, restaria confiar no programador ou falhar
// em tempo de execução.
if (s->tipo != Tipo::Numero) {
erro(expr,
"'value(" + expr.texto +
")' exige um padrao que case apenas numeros, e o "
"padrao ligado a '" +
expr.texto + "' casa tambem cadeias que nao sao");
return Tipo::Erro;
}
return Tipo::Numero;
}
case TipoAst::Comparacao: {
const Tipo esquerda =
expr.filhos.size() > 0 && expr.filhos[0]
? tipoDe(*expr.filhos[0])
: Tipo::Erro;
const Tipo direita =
expr.filhos.size() > 1 && expr.filhos[1]
? tipoDe(*expr.filhos[1])
: Tipo::Erro;
if (!comparacaoValida(esquerda, direita)) {
erro(expr, "comparacao entre tipos incompativeis: " +
std::string(nomeDoTipo(esquerda)) + " e " +
std::string(nomeDoTipo(direita)) +
"; esta linguagem nao converte implicitamente");
return Tipo::Erro;
}
if (operadorDeOrdem(expr.texto) && esquerda == Tipo::Texto) {
erro(expr, "o operador '" + expr.texto +
"' exige numeros, e os operandos sao texto");
return Tipo::Erro;
}
// A comparação produz um valor de verdade. A linguagem não tem
// tipo booleano próprio, e representá-lo como Numero é a decisão
// que evita um terceiro tipo usado em um lugar só.
return (esquerda == Tipo::Erro || direita == Tipo::Erro)
? Tipo::Erro
: Tipo::Numero;
}
case TipoAst::Ou:
case TipoAst::E: {
bool houveErro = false;
for (const AstPtr& filho : expr.filhos) {
if (!filho) {
continue;
}
const Tipo t = tipoDe(*filho);
if (t == Tipo::Erro) {
houveErro = true;
} else if (t != Tipo::Numero) {
erro(*filho,
"operando de conectivo logico precisa ser uma "
"comparacao, e nao um valor de tipo " +
std::string(nomeDoTipo(t)));
houveErro = true;
}
}
return houveErro ? Tipo::Erro : Tipo::Numero;
}
default:
return Tipo::Erro;
}
}
// ---------------------------------------------------------------------------
ResultadoSemantico AnalisadorSemantico::verificar(const NoAst& raiz) {
resultado_ = ResultadoSemantico{};
tabela_.zerarSondagens();
coletarDeclaracoes(raiz);
verificarUsos(raiz);
// Padrão declarado e nunca referenciado por nenhuma ação. Só pode ser
// detectado depois dos dois percursos, com a tabela inteira montada.
for (const SimboloSemantico* s : tabela_.todosDoEscopoAtual()) {
if (s->especie == Especie::Padrao && !s->usado) {
diagnosticos_.warning(
s->posicao,
"o padrao '" + s->nome +
"' foi declarado e nunca usado por nenhuma acao");
++resultado_.avisos;
}
}
resultado_.consultasNaTabela = tabela_.sondagens();
return resultado_;
}
ResultadoSemantico verificarArquivo(const SourceFile& arquivo,
const NoAst& raiz,
DiagnosticBag& diagnosticos) {
AnalisadorSemantico sema(arquivo, diagnosticos);
return sema.verificar(raiz);
}
} // namespace peneiraA demonstração --simbolos instrumenta os dois:
nos visitados no percurso 1 (declaracoes): 13
nos visitados no percurso 2 (usos): 6
consultas a tabela: 5O segundo percurso visita menos nós que o primeiro porque ele para nas ações — a partir dali, a travessia é feita pela avaliação de tipos, que desce pela expressão.
Há uma terceira coisa que não é percurso e vale nomear: os avisos de “declarado e nunca usado” só podem sair depois dos dois, com a tabela inteira montada. É o exemplo mais simples de verificação que depende de informação coletada, e não de informação que desce — a mesma distinção que a tarefa seguinte formaliza.
Sobre a qualidade do relato, que a atividade avalia. Toda mensagem nomeia o identificador envolvido, aponta a posição e diz a natureza do problema, e nenhuma interrompe a verificação das demais. A do value indevido é a que mais trabalhei, porque a mensagem óbvia — “tipo incompatível” — não ajuda ninguém; a que ficou explica que o padrão ligado àquela variável casa também cadeias que não são números, que é a informação que o autor precisa para corrigir.
Onde é fácil errar aqui. Fazer o segundo percurso reabrir o escopo da ação e esquecer de fechá-lo em algum caminho de retorno antecipado. O sintoma é sutil: as ações seguintes passam a enxergar a variável de ligação da anterior, e o compilador aceita um programa que referencia uma variável de outra ação. Por isso a entrada e a saída de escopo estão no mesmo bloco de função, sem retorno no meio.
Como verificar. A profundidade da tabela tem de ser a mesma antes e depois de verificar cada ação. É uma checagem de duas linhas e pega a classe inteira de defeitos de escopo desbalanceado.
1.6 Tarefa 5: A tradução dirigida por sintaxe, com o mecanismo à vista
A atividade — especificar as traduções com atributos sintetizados e herdados e determinar a ordem de avaliação a partir das dependências.
O verificador da tarefa anterior avalia atributos o tempo todo, e avalia de um jeito que esconde o mecanismo: a recursão da linguagem hospedeira resolve a ordem sozinha, e quem lê o código vê chamadas de função, não um grafo de dependências. Escrevi um módulo à parte para expor o que aquele esconde.
12_atributos.h
#ifndef PENEIRA_12_ATRIBUTOS_H
#define PENEIRA_12_ATRIBUTOS_H
#include <cstddef>
#include <cstdint>
#include <string>
#include <vector>
#include "10_ast.h"
namespace peneira {
// Tradução dirigida por sintaxe, tornada observável.
//
// O verificador de `12_sema` avalia atributos o tempo todo, mas avalia de um
// jeito que esconde o mecanismo: a recursão da linguagem hospedeira resolve a
// ordem sozinha, e quem lê o código vê chamadas de função, não um grafo de
// dependências. Este arquivo existe para expor o que aquele esconde —
// construir explicitamente os atributos, as dependências entre eles e a ordem
// de avaliação que delas decorre.
//
// Não é código morto nem exercício paralelo: é o mesmo cálculo do verificador,
// feito com a maquinaria visível, e a demonstração confronta os dois
// resultados. Se divergirem, um dos dois está errado.
enum class Fluxo : std::uint8_t {
// Sintetizado: o valor sobe. Calculado a partir dos atributos dos filhos.
Sintetizado,
// Herdado: o valor desce. Calculado a partir do pai ou dos irmãos.
Herdado,
};
const char* nomeDoFluxo(Fluxo f) noexcept;
// Uma ocorrência de atributo: um atributo nomeado, preso a um nó da árvore.
// O identificador do nó é o índice na numeração em pré-ordem, que é estável e
// dispensa guardar ponteiros num grafo que sobrevive à travessia.
struct Atributo {
std::size_t no = 0;
std::string nome;
Fluxo fluxo = Fluxo::Sintetizado;
std::string valor;
// Índices, no vetor de atributos, daqueles de que este depende. É a aresta
// do grafo de dependências, e é o que determina a ordem de avaliação.
std::vector<std::size_t> depende;
};
// O grafo de dependências de atributos de uma árvore.
struct GrafoDeAtributos {
std::vector<Atributo> atributos;
// Rótulo de cada nó, para a impressão.
std::vector<std::string> rotulosDeNo;
};
// Constrói o grafo para a árvore dada, com dois atributos por nó de expressão:
//
// `escopo` — HERDADO. Desce da ação para os operandos e carrega o nome da
// variável de ligação visível ali. É herdado porque a informação
// nasce acima do ponto onde é usada: a expressão `value(n) > 100`
// não tem, em si, como saber o que é `n`.
// `tipo` — SINTETIZADO. Sobe dos operandos para o operador. É sintetizado
// porque o tipo de uma comparação é função dos tipos dos lados,
// e de mais nada.
//
// Ter os dois na mesma árvore é o ponto: um desce, o outro sobe, e a ordem de
// avaliação tem de respeitar as duas direções ao mesmo tempo. É por isso que a
// ordem não é "pós-ordem" nem "pré-ordem", e sim a ordem topológica do grafo.
GrafoDeAtributos construirGrafo(const NoAst& raiz);
// Ordem topológica das ocorrências de atributo. Devolve os índices na ordem em
// que podem ser avaliados; vazio se houver ciclo.
//
// A existência da ordem é o que torna a gramática de atributos **bem
// definida**. Uma gramática cujo grafo tem ciclo não é avaliável em ordem
// nenhuma, e o ciclo é um defeito da especificação, não do programa de
// entrada. Detectá-lo aqui, e não com um estouro de pilha em tempo de
// execução, é o motivo de o grafo existir.
std::vector<std::size_t> ordemDeAvaliacao(const GrafoDeAtributos& g);
// Verifica se a gramática de atributos usada cabe na classe S-atribuída
// (somente sintetizados) ou na L-atribuída (sintetizados mais herdados que só
// dependem do pai e dos irmãos à esquerda). A classificação decide se a
// tradução pode ser feita durante a análise sintática, em um percurso só, ou
// se exige a árvore construída antes.
struct ClasseDaGramatica {
bool sAtribuida = false;
bool lAtribuida = false;
std::string justificativa;
};
ClasseDaGramatica classificar(const GrafoDeAtributos& g);
std::string formatarGrafo(const GrafoDeAtributos& g);
} // namespace peneira
#endif // PENEIRA_12_ATRIBUTOS_HSão dois atributos por nó de expressão, um de cada fluxo, e a escolha deles é o que faz a demonstração valer.
O atributo escopo é herdado: desce da ação para os operandos, carregando a variável de ligação visível ali. É herdado porque a informação nasce acima do ponto onde é usada — a expressão value(n) > 100 não tem, em si, como saber o que é n.
O atributo tipo é sintetizado: sobe dos operandos para o operador. É sintetizado porque o tipo de uma comparação é função dos tipos dos lados, e de mais nada.
O nó value(n) é onde os dois se encontram, e é o mais instrutivo da árvore: o tipo que ele sintetiza depende do escopo que ele herdou, porque saber se n é numérico exige saber a que padrão n está ligado. Uma dependência que sobe, alimentada por uma que desceu.
12_atributos.cpp
#include "12_atributos.h"
#include <sstream>
#include <unordered_map>
#include <utility>
namespace peneira {
namespace {
// Chave de uma ocorrência de atributo: (nó, nome). Serve para achar o índice
// de um atributo já criado quando outra ocorrência precisa depender dele.
std::string chaveDe(std::size_t no, const std::string& nome) {
return std::to_string(no) + ":" + nome;
}
struct Construtor {
GrafoDeAtributos grafo;
std::unordered_map<std::string, std::size_t> indicePorChave;
std::size_t criar(std::size_t no, const std::string& nome, Fluxo fluxo,
std::string valor) {
Atributo a;
a.no = no;
a.nome = nome;
a.fluxo = fluxo;
a.valor = std::move(valor);
grafo.atributos.push_back(std::move(a));
const std::size_t indice = grafo.atributos.size() - 1;
indicePorChave.emplace(chaveDe(no, nome), indice);
return indice;
}
void ligar(std::size_t destino, std::size_t origem) {
grafo.atributos[destino].depende.push_back(origem);
}
};
// Numera os nós em pré-ordem e registra os rótulos. A numeração é o que dá
// identidade estável a cada nó no grafo — e ela precisa percorrer a árvore
// exatamente como `visitar` faz, saltando os filhos nulos, senão os índices
// dos dois percursos deixam de casar.
void numerar(const NoAst& no, Construtor& c) {
std::string rotulo = nomeDoTipoAst(no.tipo);
if (!no.texto.empty()) {
rotulo += " '" + no.texto + "'";
}
c.grafo.rotulosDeNo.push_back(rotulo);
for (const AstPtr& filho : no.filhos) {
if (filho) {
numerar(*filho, c);
}
}
}
// Percorre a árvore criando as ocorrências de atributo e suas dependências.
// `escopoDoPai` é o índice do atributo herdado `escopo` do nó acima, ou
// kSemAtributo quando não há.
constexpr std::size_t kSemAtributo = static_cast<std::size_t>(-1);
std::size_t visitar(const NoAst& no, Construtor& c, std::size_t& proximo,
std::size_t escopoDoPai);
// Cria o atributo herdado `escopo` do nó e o liga ao do pai.
std::size_t herdarEscopo(std::size_t meu, Construtor& c,
std::size_t escopoDoPai, const std::string& valor) {
const std::size_t esc = c.criar(meu, "escopo", Fluxo::Herdado, valor);
if (escopoDoPai != kSemAtributo) {
// A dependência aponta para cima: o escopo do filho é função do escopo
// do pai. É esta aresta, e só ela, que impede a avaliação puramente em
// pós-ordem.
c.ligar(esc, escopoDoPai);
}
return esc;
}
std::size_t visitar(const NoAst& no, Construtor& c, std::size_t& proximo,
std::size_t escopoDoPai) {
const std::size_t meu = proximo++;
switch (no.tipo) {
case TipoAst::Acao: {
// A ação é onde a variável de ligação nasce. O escopo que ela passa
// adiante é diferente do que recebeu — é o ponto em que o atributo
// herdado ganha conteúdo em vez de só repassar.
const std::size_t esc =
herdarEscopo(meu, c, escopoDoPai, no.conteudo);
const std::size_t tipo =
c.criar(meu, "tipo", Fluxo::Sintetizado, "acao");
for (const AstPtr& filho : no.filhos) {
if (!filho) {
continue;
}
const std::size_t tipoFilho = visitar(*filho, c, proximo, esc);
if (tipoFilho != kSemAtributo) {
c.ligar(tipo, tipoFilho);
}
}
return tipo;
}
case TipoAst::Comparacao:
case TipoAst::Ou:
case TipoAst::E: {
const std::size_t esc = herdarEscopo(meu, c, escopoDoPai, "");
const std::size_t tipo =
c.criar(meu, "tipo", Fluxo::Sintetizado, "logico");
for (const AstPtr& filho : no.filhos) {
if (!filho) {
continue;
}
const std::size_t tipoFilho = visitar(*filho, c, proximo, esc);
if (tipoFilho != kSemAtributo) {
// Sintetizado: o tipo do operador depende do tipo dos
// filhos. A aresta aponta para baixo.
c.ligar(tipo, tipoFilho);
}
}
return tipo;
}
case TipoAst::ValorDe: {
// `value(n)` é o único ponto em que os dois fluxos se encontram: o
// tipo que ele sintetiza depende do escopo que ele herdou, porque
// saber se `n` é numérico exige saber a que padrão `n` está ligado.
const std::size_t esc = herdarEscopo(meu, c, escopoDoPai, "");
const std::size_t tipo =
c.criar(meu, "tipo", Fluxo::Sintetizado, "numero");
c.ligar(tipo, esc);
return tipo;
}
case TipoAst::Referencia: {
const std::size_t esc = herdarEscopo(meu, c, escopoDoPai, "");
const std::size_t tipo =
c.criar(meu, "tipo", Fluxo::Sintetizado, "?");
c.ligar(tipo, esc);
return tipo;
}
case TipoAst::LiteralNumero: {
// Literal não precisa do escopo: o tipo é da folha. É o caso-base
// que faz a ordem topológica ter por onde começar.
return c.criar(meu, "tipo", Fluxo::Sintetizado, "numero");
}
case TipoAst::LiteralTexto: {
return c.criar(meu, "tipo", Fluxo::Sintetizado, "texto");
}
default: {
// Programa, DeclPadrao, BlocoRegra, Emissao: repassam o escopo e
// não sintetizam tipo próprio.
const std::size_t esc = herdarEscopo(meu, c, escopoDoPai, "");
for (const AstPtr& filho : no.filhos) {
if (filho) {
visitar(*filho, c, proximo, esc);
}
}
return kSemAtributo;
}
}
}
} // namespace
const char* nomeDoFluxo(Fluxo f) noexcept {
switch (f) {
case Fluxo::Sintetizado: return "sintetizado";
case Fluxo::Herdado: return "herdado";
}
return "<desconhecido>";
}
GrafoDeAtributos construirGrafo(const NoAst& raiz) {
Construtor c;
numerar(raiz, c);
std::size_t visitados = 0;
visitar(raiz, c, visitados, kSemAtributo);
return std::move(c.grafo);
}
std::vector<std::size_t> ordemDeAvaliacao(const GrafoDeAtributos& g) {
const std::size_t n = g.atributos.size();
std::vector<std::size_t> grau(n, 0);
std::vector<std::vector<std::size_t>> saida(n);
for (std::size_t i = 0; i < n; ++i) {
for (const std::size_t dep : g.atributos[i].depende) {
// i depende de dep, logo dep vem antes: aresta dep -> i.
saida[dep].push_back(i);
++grau[i];
}
}
// Ordenação topológica de Kahn. A escolha dela, e não de uma busca em
// profundidade, é deliberada: Kahn detecta o ciclo pelo que sobra sem
// precisar de estado de cor por vértice, e o que sobra é exatamente o
// conjunto de atributos mutuamente dependentes que se quer mostrar ao
// autor da gramática.
std::vector<std::size_t> prontos;
for (std::size_t i = 0; i < n; ++i) {
if (grau[i] == 0) {
prontos.push_back(i);
}
}
std::vector<std::size_t> ordem;
ordem.reserve(n);
while (!prontos.empty()) {
const std::size_t atual = prontos.back();
prontos.pop_back();
ordem.push_back(atual);
for (const std::size_t seguinte : saida[atual]) {
if (--grau[seguinte] == 0) {
prontos.push_back(seguinte);
}
}
}
if (ordem.size() != n) {
return {}; // há ciclo: a gramática de atributos é malformada
}
return ordem;
}
ClasseDaGramatica classificar(const GrafoDeAtributos& g) {
ClasseDaGramatica r;
bool temHerdado = false;
for (const Atributo& a : g.atributos) {
if (a.fluxo == Fluxo::Herdado) {
temHerdado = true;
break;
}
}
r.sAtribuida = !temHerdado;
if (r.sAtribuida) {
r.lAtribuida = true;
r.justificativa =
"somente atributos sintetizados: avaliavel em pos-ordem, e "
"portanto durante a analise sintatica ascendente";
return r;
}
// L-atribuída exige que todo herdado dependa apenas do pai ou de irmãos à
// esquerda. Na construção acima, o único herdado é `escopo`, e ele depende
// exclusivamente do `escopo` do pai — nunca de irmão nenhum. Verificamos
// isso em vez de afirmar: a checagem é comparar o nó de origem com o nó de
// destino e exigir que a origem esteja acima na numeração em pré-ordem.
bool ok = true;
for (const Atributo& a : g.atributos) {
if (a.fluxo != Fluxo::Herdado) {
continue;
}
for (const std::size_t dep : a.depende) {
if (g.atributos[dep].no >= a.no) {
ok = false;
break;
}
}
if (!ok) {
break;
}
}
r.lAtribuida = ok;
r.justificativa =
ok ? "ha herdados, mas todos dependem so de no anterior em pre-ordem: "
"avaliavel em um percurso da esquerda para a direita"
: "ha herdado dependendo de irmao a direita: exige mais de um "
"percurso";
return r;
}
std::string formatarGrafo(const GrafoDeAtributos& g) {
std::ostringstream out;
out << " ocorrencias de atributo: " << g.atributos.size() << '\n';
for (std::size_t i = 0; i < g.atributos.size(); ++i) {
const Atributo& a = g.atributos[i];
out << " [" << i << "] no " << a.no << " (" << g.rotulosDeNo[a.no]
<< ") ." << a.nome << " = " << (a.valor.empty() ? "-" : a.valor)
<< " [" << nomeDoFluxo(a.fluxo) << "]";
if (!a.depende.empty()) {
out << " depende de";
for (const std::size_t d : a.depende) {
out << " [" << d << "]";
}
}
out << '\n';
}
return out.str();
}
} // namespace peneiraA demonstração --atributos constrói o grafo do programa de exemplo e ordena:
ocorrencias de atributo: 19
sintetizados: 7 (o tipo sobe)
herdados: 12 (o escopo desce)
ordem topologica de avaliacao (19 passos)
S-atribuida: nao
L-atribuida: simTrês leituras.
A primeira é que a ordem de avaliação não é pós-ordem nem pré-ordem. Os herdados exigem que o pai venha antes; os sintetizados exigem que os filhos venham antes; só a ordem topológica do grafo atende às duas exigências ao mesmo tempo. Quem tenta avaliar tudo em um percurso de direção fixa descobre isso da pior maneira, com um atributo lido antes de existir.
A segunda é que a ausência de ciclo é o que torna a gramática de atributos bem definida. Uma especificação cujo grafo tem ciclo não é avaliável em ordem nenhuma, e o ciclo é defeito da especificação, não do programa de entrada. Usei a ordenação de Kahn precisamente porque o que sobra ao final é o conjunto de atributos mutuamente dependentes — a informação que o autor da gramática precisa para consertar.
A terceira é a classificação. A gramática não é S-atribuída, porque tem herdados; é L-atribuída, porque todo herdado depende apenas de um nó anterior na pré-ordem, nunca de irmão à direita. E isso não é detalhe taxonômico: ser L-atribuída significa que a tradução poderia ser feita em um único percurso da esquerda para a direita, e portanto durante a análise sintática descendente, sem construir a árvore. Não é o que fizemos — a árvore existe porque os módulos 13 e 14 precisam dela —, mas a propriedade está verificada em vez de suposta.
Onde é fácil errar aqui. Numerar os nós num percurso e visitá-los em outro. O grafo referencia nós por índice de pré-ordem, e as duas travessias precisam saltar os filhos nulos exatamente da mesma forma — a ação sem where tem um filho nulo. Se divergirem, os índices deixam de casar e o grafo aponta para os nós errados, sem erro nenhum aparecendo.
Como verificar. O confronto direto: os tipos que a ordenação topológica produz têm de coincidir com os que o verificador da tarefa 4 calcula por recursão. Se divergirem, um dos dois está errado, e a divergência diz qual nó investigar.
1.7 Tarefa 6: O corpus de erros e o compilador rodando
A atividade — produzir programas com erros semânticos deliberados, com as mensagens que o compilador dá para cada um.
O corpus está em exemplos/erros_semanticos.pen, e cada ação carrega um defeito de natureza diferente. A saída de --semerros, literal:
absurdo.pen:5:5: erro: padrao 'telefone' nao foi declarado
on telefone(t) => emit("tel", t);
^
absurdo.pen:6:25: erro: 'value(e)' exige um padrao que case apenas numeros,
e o padrao ligado a 'e' casa tambem cadeias que nao sao
on email(e) where value(e) > 10 => emit("alto", e);
^
absurdo.pen:7:27: erro: comparacao entre tipos incompativeis: texto e numero;
esta linguagem nao converte implicitamente
on numero(n) where n > 100 => emit("grande", n);
^
absurdo.pen:8:5: aviso: a variavel de ligacao 'x' nao e usada nesta acao
on numero(x) => emit("qualquer", "fixo");
^
erros: 3, avisos: 1Quatro defeitos, quatro diagnósticos, nenhum interrompendo a verificação dos demais. Vale reparar no terceiro, porque é o que justifica a existência de value: comparar diretamente um casamento com um número é erro de tipo, e a mensagem diz que a linguagem não converte implicitamente — que é a informação que leva o autor à correção.
E há um marco de infraestrutura neste módulo que não estava na lista de tarefas e que precisava acontecer. Até aqui, o comando principal do compilador imprimia um relatório de fases pendentes; a partir de agora ele roda o compilador de verdade sobre o arquivo:
> peneira exemplos/contatos.pen
fases do compilador:
analise lexica pronta (modulo 7)
analise sintatica pronta (modulo 10)
analise semantica pronta (modulo 12)
geracao de codigo pendente (modulo 14)
execucao pendente (modulo 15)
padroes compilados: 2, avisos: 0com código de saída não nulo quando há erro. Uma decisão dentro disso merece registro: a semântica só roda quando não houve erro sintático. Rodá-la sobre uma árvore gravemente incompleta produziria erros semânticos que são consequência do defeito sintático, e não do programa — ruído que esconde a causa real.
Onde é fácil errar aqui. Montar o corpus só com erros que o compilador já detecta. O corpus útil é escrito antes, a partir do que a linguagem permite escrever de errado, e é ele que revela as verificações que faltam. Dois dos quatro casos acima entraram assim.
Como verificar. Cada programa do corpus tem de produzir exatamente a quantidade esperada de diagnósticos, nem mais nem menos. Um a mais indica cascata — sinal de que o tipo de erro não está sendo absorvido; um a menos indica verificação faltando.
1.8 Os dois defeitos de compilação, e o que eles ensinam
Os dois foram pegos pelo verificador estrito no momento da escrita, e nenhum teria aparecido em revisão de código.
O primeiro foi um choque de nomes com três módulos de distância. Chamei a entrada da tabela de símbolos de Simbolo, que é o nome óbvio — e Simbolo já existia desde o módulo 3, como o símbolo do alfabeto do autômato, um inteiro de um byte. O compilador reportou redefinição com tipo básico diferente, e a correção foi adotar o padrão que o módulo 7 já tinha estabelecido ao nomear o símbolo léxico: a entrada da tabela virou símbolo semântico. A lição é de projeto cumulativo — num sistema que cresce por dez módulos, o nome mais natural para um conceito novo costuma já estar ocupado por um conceito antigo, e o verificador é quem avisa.
O segundo foi mais interessante. O registro que guarda um padrão compilado contém um autômato, e o compilador recusou construí-lo vazio: Afd não tem construtor padrão, porque no módulo 3 decidi que todo autômato nasce com nome. A invariante de três módulos atrás bloqueou o código de agora, e estava certa em bloquear — um autômato sem nome não teria como aparecer em diagnóstico nenhum. A correção foi montar o registro de uma vez, por inicialização agregada, em vez de campo a campo.
1.9 Verificação da entrega
| Item | Como conferir | Estado nesta referência |
|---|---|---|
| Tabela de símbolos | Campos justificados por verificação que os usa | Seis campos, cada um com consumidor |
| Tratamento de escopo | Aninhamento tratado e estratégia justificada | Duas estratégias implementadas e medidas |
| Verificação de declaração | Uso de nome não declarado detectado | Detectado, com posição e nome |
| Verificação de tipos | Operação sobre tipo incompatível detectada | Detectada, com os dois tipos na mensagem |
| Inferência do tipo de casamento | Decidida, não estimada | Inclusão de linguagens por diferença de autômatos |
| Corpus de erros deliberados | Programas com defeitos e as mensagens de cada um | Quatro defeitos distintos, 3 erros e 1 aviso |
| Continuação após o primeiro erro | Todos os defeitos reportados numa execução | Quatro diagnósticos, nenhuma interrupção |
| Qualidade do diagnóstico | Nome, posição e natureza do problema | Atende nos quatro |
| Organização dos percursos | Quantidade e ordem registradas e justificadas | Dois, com a dependência que fixa a ordem |
| Atributos e ordem de avaliação | Sintetizados e herdados, com dependências | 19 ocorrências, sem ciclo, L-atribuída |
| Compilação limpa | Modo estrito, aviso como erro | Sem nenhum diagnóstico |
| Regressão dos módulos anteriores | Demonstrações de 2 a 10 continuam corretas | Verificadas |
O que quero deixar registrado sobre esta entrega é a economia estrutural que ela expôs. O módulo 6 construiu interseção, complemento e diferença de autômatos para responder a uma pergunta de teoria — quais operações preservam a regularidade — e naquele momento a utilidade prática era o teste de equivalência entre reconhecedores. Seis módulos depois, essas mesmas operações decidem o sistema de tipos de uma linguagem de programação. Não foi planejado assim, e é o tipo de retorno que só aparece quando as peças são construídas de verdade em vez de descritas.
Fica também um aviso para o módulo 13, que começa agora. O vetor de padrões compilados que esta fase produz é a primeira metade do programa objeto, e a decisão sobre o formato dele precisa ser tomada antes de a geração de código começar a consumi-lo.