1 Módulo 04: Projeto do Professor — A Notação Vira Máquina
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. A notação que o seu grupo decidir suportar será outra, e o corte que vocês fizerem nela também.
1.1 Visão Geral do Módulo 04
Este é o módulo em que o projeto para de depender de autômatos desenhados à mão. A atividade pede a tradução automática de uma expressão regular para o autômato não determinístico correspondente — e, antes disso, algo que passa despercebido no enunciado e ocupa metade do trabalho: para traduzir a expressão, o programa precisa primeiro ler a expressão.
Até aqui, as duas árvores de expressão que existiam no projeto foram construídas chamando funções em código, uma união de cada vez. Isso funcionou para duas categorias e não escala: a especificação léxica tem seis, e o programa Peneira do usuário vai declarar quantos padrões ele quiser, em tempo de execução. Não há como construí-los à mão.
Então o módulo tem três frentes. A primeira é o analisador da mini-notação de expressões regulares, que transforma texto em árvore. A segunda é a construção de Thompson, que transforma árvore em autômato. A terceira é o fecho vazio, sem o qual o autômato resultante não pode ser executado. E o fechamento é o confronto: o autômato gerado a partir de -?[0-9]+(\.[0-9]+)? tem de reconhecer exatamente as mesmas cadeias que o autômato que desenhei à mão no módulo 3. Aquele desenho vira gabarito.
Uma decisão atravessa o módulo e precisa ser dita cedo: fixei um alfabeto. O ponto e as classes negadas só têm significado por complemento, e complemento exige um universo. Adotei o ASCII imprimível mais tabulação, retorno e nova linha. A consequência aparece rápido e é boa didaticamente — a expressão [^"] vira a união de noventa e sete símbolos, e o autômato correspondente fica enorme. Esse inchaço é real, é o preço da uniformidade da construção, e é exatamente o que a minimização do módulo 5 vai cobrar de volta.
1.2 Tarefa 1: O analisador da mini-notação
A atividade — fazer o programa ler uma expressão regular e apreender sua estrutura, documentando quais operadores a notação suporta e por quê.
Escrevi um analisador por descida recursiva, com uma função por variável da gramática. A gramática é a do enunciado do projeto, com as variáveis na ordem de precedência: a alternativa liga mais fraco, depois a concatenação, depois os sufixos de repetição, e o átomo liga mais forte.
04_notacao.h
#ifndef PENEIRA_04_NOTACAO_H
#define PENEIRA_04_NOTACAO_H
#include <cstddef>
#include <string>
#include <vector>
#include "02_regex.h"
#include "03_afd.h"
namespace peneira {
// O alfabeto sobre o qual a notação opera. Precisa ser declarado e finito
// porque o ponto e as classes negadas são definidos por complemento: `.` é a
// união de todos os símbolos do alfabeto, e `[^"]` é a união de todos menos um.
// Sem alfabeto fixado, nenhuma das duas construções tem significado.
//
// Adotei o ASCII imprimível mais tabulação, retorno e nova linha. É o conjunto
// que os programas Peneira usam de fato, e mantê-lo pequeno importa: cada
// símbolo do alfabeto vira dois estados na construção de Thompson quando
// aparece numa classe negada.
const std::vector<Simbolo>& alfabetoDaNotacao();
// Resultado da análise. Em caso de falha, a posição aponta o caractere em que
// o analisador desistiu — sem posição, a mensagem de erro é inútil.
struct ResultadoNotacao {
RegexPtr expressao;
bool ok = false;
std::string erro;
std::size_t posicao = 0;
};
// Analisa a mini-notação de expressões regulares e devolve a árvore do módulo 2.
//
// Gramática suportada, em descida recursiva:
//
// alt := concat ( "|" concat )*
// concat := repeticao+
// repeticao := atomo ( "*" | "+" | "?" )*
// atomo := CARACTERE | "." | "[" classe "]" | "(" alt ")" | "\" CARACTERE
// classe := "^"? ( CARACTERE "-" CARACTERE | CARACTERE )+
//
// Escolhas registradas: sem contadores `{m,n}`, sem grupos de captura, sem
// retrovisores e sem âncoras. Os três últimos não são regulares ou não fazem
// sentido fora de um motor de busca; o primeiro é açúcar que expandiria a
// árvore sem ensinar nada de novo.
ResultadoNotacao analisarNotacao(const std::string& texto);
} // namespace peneira
#endif // PENEIRA_04_NOTACAO_H04_notacao.cpp
#include "04_notacao.h"
#include <set>
#include <utility>
namespace peneira {
const std::vector<Simbolo>& alfabetoDaNotacao() {
static const std::vector<Simbolo> alfabeto = [] {
std::vector<Simbolo> v;
v.push_back(static_cast<Simbolo>('\t'));
v.push_back(static_cast<Simbolo>('\n'));
v.push_back(static_cast<Simbolo>('\r'));
for (unsigned int c = 32; c <= 126; ++c) {
v.push_back(static_cast<Simbolo>(c));
}
return v;
}();
return alfabeto;
}
namespace {
// Traduz o caractere que vem depois da barra invertida.
//
// As três sequências de controle precisam de tratamento explícito: sem ele,
// `\t` na notação produziria a letra "t", e o autômato do espaço em branco
// reconheceria as letras n, r e t em vez de nova linha, retorno e tabulação —
// erro silencioso, porque o autômato fica bem formado e reconhece a linguagem
// errada. Para qualquer outro caractere, a barra apenas remove o significado
// especial, e é isso que faz `\.` casar um ponto literal.
char traduzirEscape(char c) {
switch (c) {
case 't':
return '\t';
case 'n':
return '\n';
case 'r':
return '\r';
default:
return c;
}
}
// Analisador por descida recursiva sobre o texto da notação. Uma função por
// variável da gramática, na mesma ordem em que elas aparecem no cabeçalho.
class AnalisadorDeNotacao {
public:
explicit AnalisadorDeNotacao(const std::string& texto) : texto_(texto) {}
ResultadoNotacao analisar() {
if (texto_.empty()) {
return falhar(0, "expressao vazia");
}
RegexPtr r = alt();
if (!ok_) {
return resultado_;
}
if (posicao_ != texto_.size()) {
return falhar(posicao_, "caractere inesperado");
}
ResultadoNotacao bom;
bom.expressao = std::move(r);
bom.ok = true;
return bom;
}
private:
bool fim() const { return posicao_ >= texto_.size(); }
char atual() const { return texto_[posicao_]; }
RegexPtr falharComNulo(std::size_t onde, std::string mensagem) {
falhar(onde, std::move(mensagem));
return vazioRegex();
}
ResultadoNotacao falhar(std::size_t onde, std::string mensagem) {
if (ok_) { // preserva o primeiro erro, que é o informativo
ok_ = false;
resultado_.ok = false;
resultado_.erro = std::move(mensagem);
resultado_.posicao = onde;
}
return resultado_;
}
RegexPtr alt() {
RegexPtr esquerda = concat();
while (ok_ && !fim() && atual() == '|') {
++posicao_;
RegexPtr direita = concat();
if (!ok_) break;
esquerda = uniaoRegex(std::move(esquerda), std::move(direita));
}
return esquerda;
}
// A concatenação não tem operador escrito: ela é a justaposição. O laço
// para quando encontra algo que não pode iniciar um átomo — fim do texto,
// barra vertical ou parêntese de fechamento.
RegexPtr concat() {
RegexPtr resultado = repeticao();
if (!ok_) return resultado;
while (!fim() && atual() != '|' && atual() != ')') {
RegexPtr proximo = repeticao();
if (!ok_) break;
resultado = concatRegex(std::move(resultado), std::move(proximo));
}
return resultado;
}
// Aceita sufixos repetidos: `a**` é legal e equivale a `a*`. Aceitar em vez
// de recusar evita um caso especial sem custo, já que a estrela é
// idempotente — identidade conferida no módulo 2.
RegexPtr repeticao() {
RegexPtr base = atomo();
while (ok_ && !fim()) {
const char c = atual();
if (c == '*') {
base = estrelaRegex(std::move(base));
} else if (c == '+') {
base = maisUmRegex(std::move(base));
} else if (c == '?') {
base = opcionalRegex(std::move(base));
} else {
break;
}
++posicao_;
}
return base;
}
RegexPtr atomo() {
if (fim()) {
return falharComNulo(posicao_, "esperava um atomo e o texto acabou");
}
const char c = atual();
if (c == '(') {
++posicao_;
RegexPtr dentro = alt();
if (!ok_) return dentro;
if (fim() || atual() != ')') {
return falharComNulo(posicao_, "parentese nao fechado");
}
++posicao_;
return dentro;
}
if (c == '[') {
return classe();
}
if (c == '.') {
++posicao_;
return uniaoDoAlfabeto(std::set<Simbolo>{}, true);
}
if (c == '\\') {
++posicao_;
if (fim()) {
return falharComNulo(posicao_, "barra invertida no fim do texto");
}
const char escapado = traduzirEscape(atual());
++posicao_;
return simboloRegex(escapado);
}
if (c == '*' || c == '+' || c == '?' || c == '|' || c == ')') {
return falharComNulo(posicao_, "operador sem operando a esquerda");
}
++posicao_;
return simboloRegex(c);
}
// Classe de caracteres. Com `^` na frente, o conjunto é complementado
// contra o alfabeto declarado — e é aí que a expressão explode de tamanho,
// porque a negação de um símbolo vira a união dos outros noventa e sete.
RegexPtr classe() {
const std::size_t inicio = posicao_;
++posicao_; // consome '['
bool negada = false;
if (!fim() && atual() == '^') {
negada = true;
++posicao_;
}
std::set<Simbolo> membros;
bool algum = false;
while (!fim() && atual() != ']') {
char primeiro = atual();
if (primeiro == '\\') {
++posicao_;
if (fim()) {
return falharComNulo(posicao_, "barra invertida no fim da classe");
}
primeiro = traduzirEscape(atual());
}
++posicao_;
if (!fim() && atual() == '-' && posicao_ + 1 < texto_.size() &&
texto_[posicao_ + 1] != ']') {
++posicao_; // consome '-'
char ultimo = atual();
if (ultimo == '\\') {
++posicao_;
if (fim()) {
return falharComNulo(posicao_,
"barra invertida no fim da faixa");
}
ultimo = traduzirEscape(atual());
}
++posicao_;
if (static_cast<unsigned char>(ultimo) <
static_cast<unsigned char>(primeiro)) {
return falharComNulo(posicao_, "faixa invertida na classe");
}
for (unsigned int s = static_cast<unsigned char>(primeiro);
s <= static_cast<unsigned char>(ultimo); ++s) {
membros.insert(static_cast<Simbolo>(s));
}
} else {
membros.insert(static_cast<Simbolo>(primeiro));
}
algum = true;
}
if (fim()) {
return falharComNulo(inicio, "classe nao fechada");
}
++posicao_; // consome ']'
if (!algum) {
return falharComNulo(inicio, "classe vazia");
}
return uniaoDoAlfabeto(membros, negada);
}
// Monta a união dos símbolos escolhidos. Quando `complementar` é verdadeiro,
// os escolhidos são os que ficam DE FORA.
RegexPtr uniaoDoAlfabeto(const std::set<Simbolo>& membros, bool complementar) {
RegexPtr resultado;
bool primeiro = true;
for (const Simbolo s : alfabetoDaNotacao()) {
const bool pertence = membros.count(s) > 0;
if (complementar == pertence) {
continue;
}
RegexPtr atomoSimbolo = simboloRegex(static_cast<char>(s));
resultado = primeiro ? std::move(atomoSimbolo)
: uniaoRegex(std::move(resultado),
std::move(atomoSimbolo));
primeiro = false;
}
if (primeiro) {
// Nenhum símbolo sobrou: a classe denota a linguagem vazia.
return vazioRegex();
}
return resultado;
}
const std::string& texto_;
std::size_t posicao_ = 0;
bool ok_ = true;
ResultadoNotacao resultado_;
};
} // namespace
ResultadoNotacao analisarNotacao(const std::string& texto) {
AnalisadorDeNotacao analisador(texto);
return analisador.analisar();
}
} // namespace peneiraHá uma circularidade agradável neste ponto do projeto que vale notar em voz alta: estamos escrevendo um analisador sintático, à mão, seis módulos antes de estudar análise sintática. Ele é pequeno o bastante para caber na intuição, e no módulo 10, quando o assunto chegar formalmente, o reconhecimento vai ser imediato — a estrutura de uma função por variável da gramática é a mesma.
Quatro decisões merecem defesa.
O que a notação suporta, e o que não. Suporto os seis construtores da teoria mais as formas derivadas — repetição opcional, uma-ou-mais, classes com faixa, classes negadas, ponto e parênteses. Deixei de fora contadores como {2,5}, grupos de captura, retrovisores e âncoras. Os retrovisores ficaram de fora porque não são regulares — incluí-los seria sair da classe de linguagens que a disciplina estuda, e é justamente essa fronteira que o módulo 2 pediu para reconhecer. Âncoras não fazem sentido fora de um motor de busca em texto. Contadores são açúcar puro: a{2,3} expande para aa(a)? sem ensinar nada de novo, e a expansão inflaria a árvore. Cortar foi decisão de escopo, não limitação técnica, e está registrada no cabeçalho.
A concatenação não tem operador escrito. Ela é a justaposição, e por isso o laço que a analisa não procura um símbolo: ele continua enquanto o que vem a seguir puder iniciar um átomo, e para quando encontra fim de texto, barra vertical ou parêntese de fechamento. Essa lista de “o que faz parar” é a parte fácil de errar. Esquecer o parêntese de fechamento faz a concatenação engolir o fecho do grupo e o erro aparece três níveis acima, com mensagem inútil.
Sufixos de repetição são aceitos em cadeia. A expressão a** é aceita e equivale a a*. Poderia recusar como erro de sintaxe, e resolvi aceitar — a estrela é idempotente, identidade que o módulo 2 conferiu, então aceitar não introduz ambiguidade e elimina um caso especial. É uma escolha, não um descuido, e está comentada.
Toda falha carrega posição. O resultado da análise traz a mensagem e o índice do caractere em que o analisador desistiu. Sem posição, o usuário recebe “expressão inválida” diante de um padrão de quarenta caracteres e não tem por onde começar. E a primeira falha é preservada: erros posteriores costumam ser consequência da primeira, e reportar o último é reportar o sintoma.
Onde é fácil errar aqui. No tratamento do hífen dentro de classe. Em [a-z] ele é operador de faixa; em [a-] é um símbolo literal, porque não há nada depois dele. A verificação precisa olhar um caractere adiante para decidir, e é fácil escrever a condição de modo que [a-] consuma o colchete de fechamento como fim de faixa. Tratei checando explicitamente que o caractere seguinte ao hífen não é o colchete.
Como verificar. A demonstração roda a análise sobre dez expressões válidas e oito inválidas. As inválidas são as que importam: texto vazio, parêntese aberto sem fechar, parêntese fechado sem abrir, operador sem operando à esquerda, classe não fechada, classe vazia, faixa invertida e barra invertida no fim do texto. Cada uma precisa produzir mensagem e posição, e nenhuma pode ser aceita.
1.3 Tarefa 2: A construção de Thompson
A atividade — implementar a tradução automática da árvore da expressão para o autômato não determinístico.
Antes da tradução, o autômato de destino. Ele difere do determinístico do módulo 3 em duas coisas, e ambas mudam a estrutura de dados: um par de estado e símbolo leva a um conjunto de estados, e existem transições que não consomem símbolo.
04_afn.h
#ifndef PENEIRA_04_AFN_H
#define PENEIRA_04_AFN_H
#include <cstddef>
#include <map>
#include <set>
#include <string>
#include <vector>
#include "02_cadeia.h"
#include "03_afd.h"
namespace peneira {
// Autômato finito não determinístico com transições vazias.
//
// Duas diferenças em relação ao determinístico do módulo 3, e ambas mudam a
// estrutura de dados: um par (estado, símbolo) leva a um CONJUNTO de estados,
// e existem transições que não consomem símbolo algum. Guardo as vazias
// separadas das demais em vez de reservar um símbolo especial para elas —
// reservar um símbolo obrigaria a excluí-lo do alfabeto e a lembrar disso em
// todo lugar.
//
// Os fragmentos produzidos pela construção de Thompson têm exatamente um
// estado inicial e um final, e a classe assume isso.
class Afn {
public:
explicit Afn(std::string nome);
Estado novoEstado();
void adicionarTransicao(Estado de, Simbolo simbolo, Estado para);
void adicionarVazia(Estado de, Estado para);
void definirInicial(Estado e);
void definirFinal(Estado e);
const std::string& nome() const noexcept;
Estado inicial() const noexcept;
Estado final() const noexcept;
std::size_t quantidadeDeEstados() const noexcept;
std::size_t quantidadeDeTransicoes() const;
std::size_t quantidadeDeVazias() const;
// Fecho vazio: todos os estados alcançáveis a partir do conjunto dado sem
// consumir símbolo algum, incluindo os próprios estados de partida.
// É a peça que o módulo 5 vai reutilizar dentro da determinização.
std::set<Estado> fechoVazio(const std::set<Estado>& conjunto) const;
// Conjunto de estados alcançáveis consumindo exatamente um símbolo.
std::set<Estado> mover(const std::set<Estado>& conjunto, Simbolo simbolo) const;
// Simulação: acompanha um conjunto de estados em vez de um só. Funciona, e
// é cara — a cada entrada refaz o cálculo de fechos e conjuntos que o
// módulo 5 fará uma vez só, na determinização.
bool aceita(const Cadeia& s) const;
// Símbolos que aparecem em alguma transição não vazia.
std::vector<Simbolo> simbolosUsados() const;
// Acesso usado pela determinização do módulo 5.
const std::map<Simbolo, std::set<Estado>>& transicoesDe(Estado e) const;
std::string resumo() const;
private:
std::string nome_;
Estado inicial_ = kSemEstado;
Estado final_ = kSemEstado;
std::vector<std::map<Simbolo, std::set<Estado>>> transicoes_;
std::vector<std::set<Estado>> vazias_;
};
} // namespace peneira
#endif // PENEIRA_04_AFN_H04_afn.cpp
#include "04_afn.h"
#include <sstream>
#include <stdexcept>
#include <utility>
#include <vector>
namespace peneira {
namespace {
const std::map<Simbolo, std::set<Estado>>& mapaVazio() {
static const std::map<Simbolo, std::set<Estado>> vazio;
return vazio;
}
} // namespace
Afn::Afn(std::string nome) : nome_(std::move(nome)) {}
Estado Afn::novoEstado() {
transicoes_.emplace_back();
vazias_.emplace_back();
return transicoes_.size() - 1;
}
void Afn::adicionarTransicao(Estado de, Simbolo simbolo, Estado para) {
if (de >= transicoes_.size() || para >= transicoes_.size()) {
throw std::out_of_range("transicao entre estados inexistentes");
}
transicoes_[de][simbolo].insert(para);
}
void Afn::adicionarVazia(Estado de, Estado para) {
if (de >= vazias_.size() || para >= vazias_.size()) {
throw std::out_of_range("transicao vazia entre estados inexistentes");
}
vazias_[de].insert(para);
}
void Afn::definirInicial(Estado e) { inicial_ = e; }
void Afn::definirFinal(Estado e) { final_ = e; }
const std::string& Afn::nome() const noexcept { return nome_; }
Estado Afn::inicial() const noexcept { return inicial_; }
Estado Afn::final() const noexcept { return final_; }
std::size_t Afn::quantidadeDeEstados() const noexcept {
return transicoes_.size();
}
std::size_t Afn::quantidadeDeTransicoes() const {
std::size_t total = 0;
for (const auto& porEstado : transicoes_) {
for (const auto& par : porEstado) {
total += par.second.size();
}
}
return total;
}
std::size_t Afn::quantidadeDeVazias() const {
std::size_t total = 0;
for (const auto& destinos : vazias_) {
total += destinos.size();
}
return total;
}
std::set<Estado> Afn::fechoVazio(const std::set<Estado>& conjunto) const {
// Busca em profundidade sobre as transições vazias, com pilha explícita.
// Recursão aqui seria natural e perigosa: a estrela de Thompson cria ciclo
// de transições vazias, e sem a marcação de visitado a recursão não
// terminaria. A marcação é o que garante a parada, não a estrutura do laço.
std::set<Estado> resultado(conjunto);
std::vector<Estado> pilha(conjunto.begin(), conjunto.end());
while (!pilha.empty()) {
const Estado atual = pilha.back();
pilha.pop_back();
if (atual >= vazias_.size()) {
continue;
}
for (const Estado destino : vazias_[atual]) {
if (resultado.insert(destino).second) {
pilha.push_back(destino);
}
}
}
return resultado;
}
std::set<Estado> Afn::mover(const std::set<Estado>& conjunto,
Simbolo simbolo) const {
std::set<Estado> resultado;
for (const Estado e : conjunto) {
if (e >= transicoes_.size()) {
continue;
}
const auto it = transicoes_[e].find(simbolo);
if (it != transicoes_[e].end()) {
resultado.insert(it->second.begin(), it->second.end());
}
}
return resultado;
}
bool Afn::aceita(const Cadeia& s) const {
if (inicial_ == kSemEstado || final_ == kSemEstado) {
return false;
}
std::set<Estado> atual = fechoVazio(std::set<Estado>{inicial_});
for (const char c : s) {
atual = fechoVazio(mover(atual, static_cast<Simbolo>(c)));
if (atual.empty()) {
return false;
}
}
return atual.count(final_) > 0;
}
std::vector<Simbolo> Afn::simbolosUsados() const {
std::set<Simbolo> distintos;
for (const auto& porEstado : transicoes_) {
for (const auto& par : porEstado) {
distintos.insert(par.first);
}
}
return std::vector<Simbolo>(distintos.begin(), distintos.end());
}
const std::map<Simbolo, std::set<Estado>>& Afn::transicoesDe(Estado e) const {
if (e >= transicoes_.size()) {
return mapaVazio();
}
return transicoes_[e];
}
std::string Afn::resumo() const {
std::ostringstream saida;
saida << nome_ << ": " << quantidadeDeEstados() << " estados, "
<< quantidadeDeTransicoes() << " transicoes com simbolo, "
<< quantidadeDeVazias() << " transicoes vazias, "
<< simbolosUsados().size() << " simbolos distintos";
return saida.str();
}
} // namespace peneiraGuardei as transições vazias separadas das demais, em vez de reservar um símbolo especial para representá-las. A alternativa é comum e tem um custo escondido: o símbolo reservado precisa ser excluído do alfabeto em todo lugar que percorre símbolos, e esquecer disso num único ponto produz comportamento errado difícil de rastrear. Dois campos distintos tornam o esquecimento impossível.
Agora a construção.
04_thompson.h
#ifndef PENEIRA_04_THOMPSON_H
#define PENEIRA_04_THOMPSON_H
#include <string>
#include "02_regex.h"
#include "04_afn.h"
namespace peneira {
// Construção de Thompson: traduz a árvore de uma expressão regular no autômato
// finito não determinístico correspondente.
//
// A propriedade que faz a construção funcionar é a composicionalidade: cada
// fragmento produzido tem exatamente UM estado de entrada e UM de saída, e
// nenhuma transição entra na entrada ou sai da saída por fora do fragmento.
// Com essa uniformidade, compor dois fragmentos é ligar saída de um à entrada
// de outro por transição vazia — sem caso especial, sem inspecionar o que há
// dentro. É por isso que a construção tem seis casos e não vinte.
Afn thompson(const Regex& r, std::string nome);
} // namespace peneira
#endif // PENEIRA_04_THOMPSON_H04_thompson.cpp
#include "04_thompson.h"
#include <utility>
namespace peneira {
namespace {
// Um fragmento é o par (entrada, saída) devolvido por cada caso da construção.
// Todo o resto do fragmento fica dentro do autômato que está sendo montado.
struct Fragmento {
Estado entrada;
Estado saida;
};
Fragmento construir(const Regex& r, Afn& destino) {
switch (r.tipo) {
case TipoRegex::Vazio: {
// Dois estados sem ligação alguma: nada leva da entrada à saída,
// então nenhuma cadeia é aceita. É a linguagem vazia.
const Estado entrada = destino.novoEstado();
const Estado saida = destino.novoEstado();
return Fragmento{entrada, saida};
}
case TipoRegex::Epsilon: {
// Uma transição vazia liga entrada a saída: aceita só a cadeia
// vazia, sem consumir símbolo.
const Estado entrada = destino.novoEstado();
const Estado saida = destino.novoEstado();
destino.adicionarVazia(entrada, saida);
return Fragmento{entrada, saida};
}
case TipoRegex::Simbolo: {
const Estado entrada = destino.novoEstado();
const Estado saida = destino.novoEstado();
destino.adicionarTransicao(entrada, static_cast<Simbolo>(r.simbolo),
saida);
return Fragmento{entrada, saida};
}
case TipoRegex::Uniao: {
// Entrada nova com transição vazia para os dois fragmentos, e
// saída nova recebendo transição vazia de ambos. O não determinismo
// está aqui: da entrada, sem ler nada, dá para estar nos dois
// caminhos ao mesmo tempo.
const Fragmento a = construir(*r.esquerda, destino);
const Fragmento b = construir(*r.direita, destino);
const Estado entrada = destino.novoEstado();
const Estado saida = destino.novoEstado();
destino.adicionarVazia(entrada, a.entrada);
destino.adicionarVazia(entrada, b.entrada);
destino.adicionarVazia(a.saida, saida);
destino.adicionarVazia(b.saida, saida);
return Fragmento{entrada, saida};
}
case TipoRegex::Concatenacao: {
// Único caso que não cria estado novo: liga a saída do primeiro à
// entrada do segundo. Poderíamos fundir os dois estados e economizar
// um, e não fazemos — fundir quebraria a garantia de que cada
// fragmento tem entrada e saída próprias, que é o que dispensa os
// casos especiais.
const Fragmento a = construir(*r.esquerda, destino);
const Fragmento b = construir(*r.direita, destino);
destino.adicionarVazia(a.saida, b.entrada);
return Fragmento{a.entrada, b.saida};
}
case TipoRegex::Estrela: {
// Quatro transições vazias: pular o fragmento inteiro (zero
// repetições), entrar nele, voltar da saída para a entrada (mais
// uma repetição) e sair. O laço de volta é o que cria ciclo de
// transições vazias — e é por causa dele que o fecho vazio precisa
// marcar os estados já visitados.
const Fragmento a = construir(*r.esquerda, destino);
const Estado entrada = destino.novoEstado();
const Estado saida = destino.novoEstado();
destino.adicionarVazia(entrada, a.entrada);
destino.adicionarVazia(entrada, saida);
destino.adicionarVazia(a.saida, a.entrada);
destino.adicionarVazia(a.saida, saida);
return Fragmento{entrada, saida};
}
}
// Inalcançável para um valor válido do enumerado; o modo estrito exige o
// retorno em todos os caminhos.
const Estado entrada = destino.novoEstado();
const Estado saida = destino.novoEstado();
return Fragmento{entrada, saida};
}
} // namespace
Afn thompson(const Regex& r, std::string nome) {
Afn automato(std::move(nome));
const Fragmento raiz = construir(r, automato);
automato.definirInicial(raiz.entrada);
automato.definirFinal(raiz.saida);
return automato;
}
} // namespace peneiraO que faz a construção funcionar é a composicionalidade, e ela merece ser enunciada com precisão porque é o conceito do módulo. Todo fragmento produzido tem exatamente um estado de entrada e um de saída, e nada de fora do fragmento entra na sua entrada nem sai da sua saída. Com essa uniformidade garantida, compor dois fragmentos é ligar a saída de um à entrada do outro por transição vazia — sem inspecionar o que há dentro, sem caso especial. É por isso que a construção tem seis casos e não vinte.
Uma escolha que parece desperdício e não é: no caso da concatenação, eu poderia fundir a saída do primeiro fragmento com a entrada do segundo e economizar um estado. Não fundi. Fundir quebra a garantia de que cada fragmento tem entrada e saída próprias, e é justamente essa garantia que dispensa os casos especiais em toda a construção. Economizar um estado aqui custaria a uniformidade inteira — e os estados sobrando serão eliminados pela minimização, de graça, no módulo 5.
O caso da estrela cria quatro transições vazias e, entre elas, o laço de volta da saída do fragmento para a sua entrada. Esse laço é um ciclo de transições vazias, e é a razão pela qual o fecho vazio precisa marcar estados já visitados: sem marcação, o percurso não terminaria. Deixei isso comentado nos dois lugares — no laço da estrela e no algoritmo do fecho — porque quem depurar um deles vai querer entender o outro.
1.3.1 Quanto custa, em estados
A construção tem custo previsível, e vale calculá-lo porque o número explica o módulo seguinte. Cada símbolo gasta dois estados. Cada união gasta dois além dos que os seus dois lados já gastaram. Cada estrela gasta dois. A concatenação não gasta nenhum. Uma expressão com n símbolos e u uniões e estrelas produz, portanto, 2n + 2u estados.
Aplicando à classe negada [^"], que a especificação usa em TEXTO: o alfabeto declarado tem noventa e oito símbolos, a negação de um deles deixa noventa e sete, e a união desses noventa e sete é montada com noventa e seis operadores de união. São 2 \times 97 + 2 \times 96 = 386 estados para um único átomo da expressão. Somando a estrela que a envolve e as duas aspas, a expressão inteira de TEXTO fica em 386 + 2 + 2 + 2 = 392 estados — que é exatamente o que o programa reporta.
Trezentos e noventa e dois estados para reconhecer texto entre aspas é absurdo, e é o resultado correto do algoritmo. A construção de Thompson não tenta economizar — ela troca tamanho por uniformidade, e a uniformidade é o que a torna implementável em seis casos. O tamanho é problema de outro módulo: a determinização vai reorganizar esses estados e a minimização vai provar qual é o menor autômato equivalente. Quando esse número cair, no módulo 5, o aluno vai saber exatamente de onde ele veio.
Onde é fácil errar aqui. Implementar o fecho vazio recursivamente sem marcação de visitado. A recursão é a forma natural de escrever e trava na primeira estrela. Usei pilha explícita com conjunto de visitados, e a inserção no conjunto é o próprio teste — só empilho o estado se a inserção disse que ele é novo.
Como verificar. A demonstração do fecho usa a*, que é o menor exemplo com o ciclo — quatro estados, uma transição com símbolo e quatro vazias. Rodando, o fecho vazio do estado inicial sai como um conjunto de três estados que já inclui o final, sem consumir símbolo algum:
fecho vazio de {q2} = {q0, q2, q3}É exatamente isso que faz a* aceitar a cadeia vazia. Depois de consumir um a, o conjunto passa a {q0, q1, q3} — e a presença de q0, que é a entrada do fragmento interno, é o laço de volta da estrela aparecendo no resultado, pronto para outro a. Ver o conjunto crescer e voltar torna o ciclo concreto de um jeito que o desenho não consegue.
1.4 Tarefa 3: O confronto com o gabarito
A atividade — demonstrar que a tradução produziu o autômato certo.
O autômato não determinístico pode ser executado. A simulação acompanha um conjunto de estados em vez de um só: parte do fecho vazio do estado inicial, e a cada símbolo calcula para onde o conjunto inteiro pode ir e fecha de novo sobre as transições vazias. A cadeia é aceita se o conjunto final contiver o estado final.
Vale reparar no que essa simulação é, porque é o argumento que motiva o módulo inteiro seguinte: ela é a construção de subconjuntos feita na hora, uma entrada de cada vez. Cada execução recalcula os mesmos fechos e os mesmos conjuntos que a execução anterior já tinha calculado. Determinizar, no módulo 5, é fazer esse trabalho uma vez só, guardar o resultado e nunca mais refazê-lo.
Com a simulação disponível, o confronto é direto: o autômato gerado a partir da notação de NUMERO e o autômato desenhado à mão no módulo 3 têm de dar o mesmo veredicto para cada uma das treze cadeias do corpus daquela categoria — as seis que devem ser aceitas e as sete que devem ser rejeitadas.
04_demos.cpp
#include "04_demos.h"
#include <ostream>
#include <set>
#include <string>
#include <vector>
#include "02_lexico.h"
#include "03_afd.h"
#include "03_reconhecedores.h"
#include "04_afn.h"
#include "04_notacao.h"
#include "04_thompson.h"
namespace peneira::demo {
namespace {
std::string conjuntoEmTexto(const std::set<Estado>& c) {
std::string saida = "{";
bool primeiro = true;
for (const Estado e : c) {
if (!primeiro) saida += ", ";
saida += "q" + std::to_string(e);
primeiro = false;
}
return saida + "}";
}
// Constrói o autômato de uma categoria a partir da notação registrada na
// especificação léxica do módulo 2.
Afn deNotacao(const std::string& notacao, const std::string& nome) {
const ResultadoNotacao r = analisarNotacao(notacao);
if (!r.ok) {
return Afn(nome + " (falhou)");
}
return thompson(*r.expressao, nome);
}
} // namespace
void mostrarAnaliseDaNotacao(std::ostream& out) {
out << "alfabeto declarado: " << alfabetoDaNotacao().size() << " simbolos\n\n";
const std::vector<std::string> exemplos{
"a", "ab", "a|b", "a*", "a+", "a?", "(a|b)*c", "[a-z]", "[0-9]+",
"-?[0-9]+(\\.[0-9]+)?",
};
out << "expressoes aceitas pela notacao:\n";
for (const std::string& e : exemplos) {
const ResultadoNotacao r = analisarNotacao(e);
out << " " << e << " -> ";
if (r.ok) {
const std::string forma = formatarRegex(*r.expressao);
out << (forma.size() > 46 ? forma.substr(0, 43) + "..." : forma)
<< " (" << forma.size() << " caracteres expandidos)\n";
} else {
out << "ERRO: " << r.erro << " na posicao " << r.posicao << '\n';
}
}
out << "\nexpressoes que a notacao recusa, com a posicao do erro:\n";
const std::vector<std::string> ruins{"", "(a", "a)", "*a", "[a", "[]",
"[z-a]", "a\\"};
for (const std::string& e : ruins) {
const ResultadoNotacao r = analisarNotacao(e);
out << " \"" << e << "\" -> "
<< (r.ok ? std::string("aceitou (nao deveria)")
: r.erro + " na posicao " + std::to_string(r.posicao))
<< '\n';
}
}
void mostrarFechoVazio(std::ostream& out) {
// a* tem o ciclo de transicoes vazias que a estrela cria.
const ResultadoNotacao r = analisarNotacao("a*");
const Afn automato = thompson(*r.expressao, "a*");
out << automato.resumo() << "\n\n";
out << "estado inicial: q" << automato.inicial() << ", final: q"
<< automato.final() << "\n\n";
const std::set<Estado> inicio{automato.inicial()};
out << "fecho vazio de " << conjuntoEmTexto(inicio) << " = "
<< conjuntoEmTexto(automato.fechoVazio(inicio)) << '\n';
out << " sem consumir simbolo algum, o automato ja esta em varios\n"
<< " estados ao mesmo tempo — inclusive no final, que e o que faz\n"
<< " a cadeia vazia ser aceita por a*.\n\n";
const std::set<Estado> apos = automato.fechoVazio(
automato.mover(automato.fechoVazio(inicio), static_cast<Simbolo>('a')));
out << "apos consumir 'a': " << conjuntoEmTexto(apos) << '\n';
out << " o laco de volta da estrela reaparece aqui: o conjunto contem\n"
<< " de novo a entrada do fragmento, pronta para outro 'a'.\n\n";
out << "aceita cadeia vazia? " << (automato.aceita("") ? "sim" : "nao")
<< "\naceita \"aaa\"? " << (automato.aceita("aaa") ? "sim" : "nao")
<< "\naceita \"ab\"? " << (automato.aceita("ab") ? "sim" : "nao") << '\n';
}
void mostrarThompson(std::ostream& out) {
out << "cada construtor da expressao vira um fragmento de tamanho fixo:\n\n";
const std::vector<std::string> exemplos{"a", "ab", "a|b", "a*", "(a|b)*"};
for (const std::string& e : exemplos) {
const ResultadoNotacao r = analisarNotacao(e);
const Afn automato = thompson(*r.expressao, e);
out << " " << e << " -> " << automato.quantidadeDeEstados()
<< " estados, " << automato.quantidadeDeTransicoes()
<< " com simbolo, " << automato.quantidadeDeVazias() << " vazias\n";
}
out << "\nDois estados por simbolo, mais dois por uniao e dois por\n"
<< "estrela. A concatenacao nao cria estado: so liga a saida de um\n"
<< "fragmento a entrada do outro.\n\n";
out << "agora as categorias reais da especificacao lexica:\n";
for (const CategoriaLexica& c : especificacaoLexica()) {
const ResultadoNotacao r = analisarNotacao(c.notacao);
if (!r.ok) {
out << " " << c.nome << ": notacao fora da mini-linguagem — "
<< r.erro << " na posicao " << r.posicao << '\n';
continue;
}
const Afn automato = thompson(*r.expressao, c.nome);
out << " " << c.nome << ": " << automato.quantidadeDeEstados()
<< " estados\n";
}
}
void mostrarConfronto(std::ostream& out) {
out << "o automato gerado precisa reconhecer exatamente o que o automato\n"
<< "construido a mao no modulo 3 reconhece.\n\n";
const ResultadoNotacao r = analisarNotacao("-?[0-9]+(\\.[0-9]+)?");
const Afn gerado = thompson(*r.expressao, "NUMERO gerado");
const Afd manual = afdNumero();
out << " a mao (modulo 3): " << manual.quantidadeDeEstados() << " estados\n";
out << " gerado (Thompson): " << gerado.quantidadeDeEstados()
<< " estados\n\n";
std::size_t conferem = 0;
std::size_t divergem = 0;
for (const CategoriaLexica& c : especificacaoLexica()) {
if (c.nome != "NUMERO") continue;
for (const Cadeia& cadeia : c.aceitas) {
const bool a = manual.aceita(cadeia);
const bool b = gerado.aceita(cadeia);
if (a == b && a) {
++conferem;
} else {
++divergem;
out << " DIVERGE em \"" << cadeia << "\": manual="
<< (a ? "aceita" : "rejeita") << ", gerado="
<< (b ? "aceita" : "rejeita") << '\n';
}
}
for (const Cadeia& cadeia : c.rejeitadas) {
const bool a = manual.aceita(cadeia);
const bool b = gerado.aceita(cadeia);
if (a == b && !a) {
++conferem;
} else {
++divergem;
out << " DIVERGE em \"" << cadeia << "\": manual="
<< (a ? "aceita" : "rejeita") << ", gerado="
<< (b ? "aceita" : "rejeita") << '\n';
}
}
}
out << " veredictos iguais: " << conferem << ", divergentes: " << divergem
<< '\n';
out << "\nO gerado tem muito mais estados e reconhece a mesma linguagem.\n"
<< "Essa folga e o preco da uniformidade da construcao — e e ela que\n"
<< "a determinizacao e a minimizacao do modulo 5 vao cobrar de volta.\n";
}
} // namespace peneira::demoRepare que o confronto compara veredictos, e não apenas conta acertos. Para cada cadeia, ele exige que os dois autômatos concordem e que a concordância seja no valor esperado. Um confronto que só verificasse concordância passaria se os dois estivessem errados do mesmo jeito.
O relatório também imprime a contagem de estados dos dois, e o contraste é o resultado mais eloquente do módulo:
a mao (modulo 3): 5 estados
gerado (Thompson): 168 estados
veredictos iguais: 13, divergentes: 0Cento e sessenta e oito estados contra cinco, para reconhecer exatamente a mesma linguagem, com veredicto idêntico nas treze cadeias do corpus. Thompson cria dois estados por símbolo e mais dois por união ou estrela, sem nenhuma tentativa de economia — e os [0-9] da expressão, expandidos em dez símbolos cada, respondem pela maior parte do inchaço. Essa folga é o preço da uniformidade, e é a evidência mais concreta de por que a minimização existe.
Onde é fácil errar aqui. Escrever o confronto usando apenas as cadeias que o corpus manda aceitar. Se o autômato gerado aceitar tudo — defeito plausível, bastaria marcar o estado errado como final —, um confronto só de aceitas passaria com nota máxima. As sete rejeitadas são as que têm poder de detecção.
1.5 Referência teórica: a equivalência entre os dois modelos
O módulo enuncia que autômatos determinísticos e não determinísticos reconhecem exatamente a mesma classe de linguagens, e o resultado é surpreendente na direção que interessa.
Uma das direções é imediata e cabe em uma frase: todo autômato determinístico já é um não determinístico, bastando ler cada destino único como um conjunto de um elemento. Não escrevi conversão para isso porque a conversão é a identidade — o código seria uma cópia de estrutura sem conteúdo.
A outra direção é o teorema de verdade, e o algoritmo que a demonstra é a construção de subconjuntos, que chega no módulo 5. Deixei explicitamente sem código aqui, e não por falta de espaço: a simulação implementada neste módulo é o algoritmo, executado sob demanda. Quem entender que o conjunto de estados acompanhado durante a simulação é um estado do autômato determinizado já entendeu a construção antes de vê-la. Preferi deixar essa percepção madurar como observação sobre o código deste módulo, em vez de antecipar o algoritmo.
1.6 Tópicos deste módulo sem código de referência
Um tópico ficou sem implementação própria, e registro o motivo.
A motivação para introduzir o não determinismo é argumentativa, não implementável: o não determinismo é conveniente para especificar e inconveniente para executar. O que o código deste módulo faz é dar corpo aos dois lados dessa frase — a construção de Thompson mostra a conveniência, gerando o autômato por seis regras uniformes sem nenhum raciocínio caso a caso; e a simulação mostra o inconveniente, refazendo trabalho a cada entrada. A frase fica demonstrada pelo contraste entre as duas peças, e não por um exemplo dedicado.
1.7 Verificação da entrega
| Item | Como conferir | Estado nesta referência |
|---|---|---|
| Analisador da notação | Aceita as expressões válidas, recusa as inválidas com posição | Dez válidas e oito inválidas na demonstração |
| Operadores documentados | Cabeçalho registra o que entra e o que fica de fora, com motivo | Atende |
| Alfabeto declarado | Ponto e negação têm universo definido | ASCII imprimível mais três de controle |
| Construção de Thompson | Seis casos, um por construtor, com entrada e saída únicas | Atende |
| Fecho vazio | Termina na presença de ciclo | Pilha explícita com marcação de visitado |
| Simulação do autômato | Acompanha conjunto de estados | Atende |
| Confronto com o gabarito | Veredicto igual ao do autômato manual nas treze cadeias | 13 iguais, 0 divergentes |
| Código compila limpo | Nenhum aviso sob o modo estrito | Atende, verificado por compilação e execução |
O custo em estados das seis categorias da especificação, gerado a partir da notação:
| Categoria | Estados após Thompson |
|---|---|
| ESPACO | 30 |
| PONTUACAO | 64 |
| NUMERO | 168 |
| IDENTIFICADOR | 250 |
| TEXTO | 392 |
| PADRAO | 392 |
Vale olhar essa tabela como o enunciado do problema do módulo 5. Mil duzentos e noventa e seis estados, somados, para reconhecer as seis categorias de uma linguagem minúscula. Nenhum deles foi escolhido por alguém: todos vieram das seis regras da construção, aplicadas sem exceção. O módulo seguinte vai reorganizá-los pela determinização e depois provar, pela minimização, qual é o menor autômato que faz o mesmo trabalho.
O que quero deixar registrado sobre esta entrega é a mudança de patamar que ela representa. Até o módulo 3, o projeto reconhecia o que eu tinha desenhado. A partir daqui, ele reconhece o que for escrito na notação — e as quatro categorias da especificação léxica que ficaram sem autômato no módulo passado deixam de exigir trabalho manual. O que falta para o analisador léxico do módulo 7 não é mais capacidade de construir autômatos: é fazê-los rodar rápido, que é o assunto do módulo 5, e resolver o desempate entre padrões que casam a mesma entrada, que é o do próprio 7.