1 Autômatos não determinísticos e a construção de Thompson — Projeto do Professor

Este é o projeto de referência do professor — as tarefas do Projeto Integrador deste módulo resolvidas do começo ao fim, com as decisões justificadas uma a uma. É o modelo do que cada grupo deve produzir no próprio projeto, e existe para ser estudado, não copiado: a construção que você escreve, a representação do conjunto ativo que escolhe e os casos que confere à mão são seus. O que se copia daqui é o nível de acabamento e o hábito de guardar evidência independente do próprio código.

1.1 Visão Geral

Este é o módulo mais confortável do percurso, e o conforto tem prazo. A construção de Thompson se transcreve da definição para o código quase sem adaptação: cada caso da definição vira um trecho de função, a composição dos casos vira a recursão, e o resultado funciona na primeira tentativa com uma frequência que não se repete nos módulos seguintes. O enunciado da primeira tarefa pede que se registre essa observação no diário da construção, e a razão de pedir é que perceber a diferença entre este caso e os próximos é parte do que se aprende aqui.

As três tarefas se encadeiam com clareza incomum. A primeira converte a árvore do módulo de expressões em máquina não determinística. A segunda simula essa máquina sobre uma cadeia — e a dificuldade não está no algoritmo, mas em representar um conjunto de estados simultaneamente ativos sem que a manutenção dele domine o custo. A terceira monta a bateria de casos conferidos à mão, que é a peça de maior valor duradouro deste módulo: a partir do próximo, tudo será verificado contra algo que o próprio sistema produziu, e esta bateria é a última evidência externa que resta.

Todo o conteúdo teórico do módulo é coberto pelo código: o não determinismo e a aceitação por existência de caminho estão na simulação, as transições vazias e o fecho vazio são a operação básica dela, e os quatro casos da construção — base, concatenação, alternância e fecho — são as quatro ramificações da função que constrói. O código compila com avisos tratados como erro e roda pelo subcomando que este módulo acrescenta, quinto teste da bateria; e este é o primeiro teste da suíte que pode de fato reprovar, porque devolve código de saída não-zero quando um caso conferido à mão discorda do que a simulação produz.

1.2 Tarefa 1: Converter a árvore em máquina não determinística

O que a tarefa pede

Implementar a construção que transforma a estrutura em árvore produzida pela leitura de padrões em uma máquina não determinística. A tarefa se cumpre quando qualquer expressão aceita pela leitura produz uma máquina — sem exceção reservada para um operador que ficou de fora, porque um operador não coberto aqui reaparece como falha silenciosa três capítulos adiante, sobre uma entrada que ninguém escreveu à mão.

Interface

04_afn.h

// 04_afn.h — A máquina não determinística e a construção de Thompson.
//
// Aqui a árvore produzida pela leitura de patterns vira máquina. A construção é
// indutiva sobre a estrutura da árvore, e é o único ponto do percurso em que a
// definição do quadro se transcreve quase sem adaptação: cada caso da definição
// vira uma função, e a composição dos casos vira a recursão.
//
// O que torna a construção sistemática é a INTERFACE UNIFORME dos blocos. Todo
// bloco construído tem exatamente uma entrada e exatamente uma saída, e é essa
// promessa que permite compor blocos sem saber o que há dentro deles. Se um
// único caso quebrasse a promessa — devolvendo dois estados de saída, digamos —,
// os outros três precisariam tratá-lo como exceção, e a construção deixaria de
// ser mecânica.
//
// Não determinismo aqui não é curiosidade: é ferramenta de construção. Ele
// permite que os casos sejam locais (cada um só conhece os blocos que recebe),
// ao preço de uma máquina que precisa de simulação por conjunto de estados em
// vez de um estado corrente. O arco seguinte paga esse preço de volta.

#ifndef PENEIRA_04_AFN_H
#define PENEIRA_04_AFN_H

#include <cstddef>
#include <string>
#include <vector>

#include "02_regex.h"
#include "03_afd.h"

namespace peneira {

// A transição vazia não consome símbolo. Marcamos com o byte zero porque ele não
// pode aparecer num pattern escrito por quem usa a Peneira — o texto do programa
// é uma cadeia de caracteres, e o zero termina cadeias.
inline constexpr char kEpsilon = '\0';

// O coringa `.` chegou da leitura como folha própria, e não expandido em
// alternância (decisão registrada no arco anterior). Ele precisa, portanto, de
// uma marca de transição própria: casa qualquer símbolo, mas não é vazia.
inline constexpr char kQualquer = '\x01';

struct TransicaoAfn {
    char simbolo = kEpsilon;
    Estado destino = 0;
};

// Um bloco de máquina com uma entrada e uma saída — o invariante da construção.
struct Bloco {
    Estado entrada = 0;
    Estado saida = 0;
};

// O traço de uma simulação: quais estados estavam ativos depois de cada símbolo.
// É o que mostra o não determinismo acontecendo, em vez de afirmá-lo.
struct PassoDaSimulacao {
    char simboloLido = '\0';
    std::vector<Estado> ativos;
};

struct Simulacao {
    bool aceitou = false;
    std::vector<PassoDaSimulacao> passos;
    std::size_t maiorConjuntoAtivo = 0;
};

class Afn {
public:
    Estado novoEstado();
    void adicionarTransicao(Estado origem, char simbolo, Estado destino);

    void definirInicial(Estado estado);
    void definirAceitacao(Estado estado);

    Estado inicial() const;
    Estado aceitacao() const;
    std::size_t quantidadeDeEstados() const;
    std::size_t quantidadeDeTransicoes() const;
    std::size_t quantidadeDeTransicoesVazias() const;

    // O fecho vazio de um conjunto: todos os estados alcançáveis a partir dele
    // sem consumir símbolo algum. É a operação básica da simulação, e a que
    // quem implementa esquece de aplicar ao conjunto INICIAL.
    std::vector<Estado> fechoVazio(const std::vector<Estado>& conjunto) const;

    // Acrescentado no arco da determinizacao: a construcao de subconjuntos
    // precisa percorrer as saidas de cada estado a partir de fora da classe.
    const std::vector<TransicaoAfn>& transicoesDe(Estado estado) const;

    bool aceita(const std::string& cadeia) const;
    Simulacao simular(const std::string& cadeia) const;

    std::string formatarSimulacao(const std::string& cadeia, const Simulacao& simulacao) const;

private:
    std::vector<std::vector<TransicaoAfn>> transicoes_;
    Estado inicial_ = 0;
    Estado aceitacao_ = 0;
};

// A construção propriamente dita: árvore do arco anterior em máquina.
Afn construirThompson(const Arvore& arvore);

// Um caso da bateria conferida à mão: o pattern, a cadeia e o veredito que
// determinamos sem rodar o programa.
struct CasoDeTeste {
    std::string expressao;
    std::string cadeia;
    bool esperado = false;
    std::string origem;  // arquivo:linha, para a mensagem de falha ser útil
};

struct ResultadoDaBateria {
    std::size_t total = 0;
    std::size_t passaram = 0;
    std::vector<std::string> falhas;
    bool arquivoLido = false;
};

// Lê a bateria do arquivo de casos e executa cada linha contra a simulação.
std::vector<CasoDeTeste> lerCasos(const std::string& caminho);
ResultadoDaBateria rodarBateria(const std::vector<CasoDeTeste>& casos);

}  // namespace peneira

#endif  // PENEIRA_04_AFN_H

Implementação

04_afn.cpp

#include "04_afn.h"

#include <fstream>
#include <sstream>

namespace peneira {

Estado Afn::novoEstado() {
    transicoes_.emplace_back();
    return transicoes_.size() - 1;
}

void Afn::adicionarTransicao(const Estado origem, const char simbolo, const Estado destino) {
    transicoes_[origem].push_back(TransicaoAfn{simbolo, destino});
}

void Afn::definirInicial(const Estado estado) { inicial_ = estado; }
void Afn::definirAceitacao(const Estado estado) { aceitacao_ = estado; }

Estado Afn::inicial() const { return inicial_; }
Estado Afn::aceitacao() const { return aceitacao_; }
std::size_t Afn::quantidadeDeEstados() const { return transicoes_.size(); }

const std::vector<TransicaoAfn>& Afn::transicoesDe(const Estado estado) const {
    return transicoes_[estado];
}

std::size_t Afn::quantidadeDeTransicoes() const {
    std::size_t total = 0;
    for (const std::vector<TransicaoAfn>& saidas : transicoes_) {
        total += saidas.size();
    }
    return total;
}

// recorte:inicio contar-transicoes-vazias
std::size_t Afn::quantidadeDeTransicoesVazias() const {
    std::size_t total = 0;
    for (const std::vector<TransicaoAfn>& saidas : transicoes_) {
        for (const TransicaoAfn& transicao : saidas) {
            if (transicao.simbolo == kEpsilon) {
                ++total;
            }
        }
    }
    return total;
}
// recorte:fim contar-transicoes-vazias

// recorte:inicio fecho-vazio-com-marcacao
std::vector<Estado> Afn::fechoVazio(const std::vector<Estado>& conjunto) const {
    // Busca em profundidade sobre as transições vazias, com marcação de visitado
    // num vetor denso (um byte por estado, por chamada). A marcação garante o
    // término quando há ciclo de transições vazias, o que acontece quando o
    // interior de um fecho pode ser atravessado sem ler símbolo — `a**` e
    // `(a?)*`, por exemplo. Em `a*` o retorno passa pela transição que lê `a`,
    // não há ciclo de transições vazias, e o defeito não aparece.
    std::vector<char> visitado(transicoes_.size(), 0);
    std::vector<Estado> pilha;
    std::vector<Estado> resultado;

    for (const Estado estado : conjunto) {
        if (!visitado[estado]) {
            visitado[estado] = 1;
            pilha.push_back(estado);
            resultado.push_back(estado);
        }
    }

    while (!pilha.empty()) {
        const Estado atual = pilha.back();
        pilha.pop_back();
        for (const TransicaoAfn& transicao : transicoes_[atual]) {
            if (transicao.simbolo != kEpsilon) {
                continue;
            }
            if (!visitado[transicao.destino]) {
                visitado[transicao.destino] = 1;
                pilha.push_back(transicao.destino);
                resultado.push_back(transicao.destino);
            }
        }
    }
    return resultado;
}
// recorte:fim fecho-vazio-com-marcacao

Simulacao Afn::simular(const std::string& cadeia) const {
    Simulacao simulacao;

// recorte:inicio conjunto-ativo-comeca-no-fecho
    // O conjunto inicial é o fecho vazio do estado inicial, e NÃO o estado
    // inicial sozinho. Esquecer este fecho é o defeito mais comum da simulação:
    // ele passa em quase todos os testes, porque só falha quando a máquina tem
    // transição vazia logo na entrada — o que acontece exatamente nos blocos de
    // alternância e de fecho.
    std::vector<Estado> ativos = fechoVazio({inicial_});
    simulacao.passos.push_back(PassoDaSimulacao{'\0', ativos});
    simulacao.maiorConjuntoAtivo = ativos.size();
    // recorte:fim conjunto-ativo-comeca-no-fecho

    // Marcação densa reusada entre os símbolos: zerar um vetor de bytes é mais
    // barato do que alocar um conjunto ordenado por símbolo consumido, e a
    // simulação faz isso uma vez por caractere de entrada.
    std::vector<char> presente(transicoes_.size(), 0);

    for (const char simbolo : cadeia) {
        std::vector<Estado> proximos;
        for (const Estado estado : ativos) {
            for (const TransicaoAfn& transicao : transicoes_[estado]) {
                const bool casa =
                    transicao.simbolo == simbolo ||
                    (transicao.simbolo == kQualquer && simbolo != kEpsilon);
                if (!casa) {
                    continue;
                }
                if (!presente[transicao.destino]) {
                    presente[transicao.destino] = 1;
                    proximos.push_back(transicao.destino);
                }
            }
        }
        for (const Estado estado : proximos) {
            presente[estado] = 0;
        }

        ativos = fechoVazio(proximos);
        simulacao.passos.push_back(PassoDaSimulacao{simbolo, ativos});
        if (ativos.size() > simulacao.maiorConjuntoAtivo) {
            simulacao.maiorConjuntoAtivo = ativos.size();
        }
        if (ativos.empty()) {
            // Sem estado ativo, nenhum símbolo posterior reativa coisa alguma.
            break;
        }
    }

    // Aceitação por EXISTÊNCIA de caminho: basta que o estado de aceitação esteja
    // entre os ativos ao fim. Não é preciso que todos os caminhos aceitem — e é
    // essa assimetria que distingue o não determinismo do determinismo.
    for (const Estado estado : ativos) {
        if (estado == aceitacao_) {
            simulacao.aceitou = true;
            break;
        }
    }
    return simulacao;
}

bool Afn::aceita(const std::string& cadeia) const { return simular(cadeia).aceitou; }

std::string Afn::formatarSimulacao(const std::string& cadeia, const Simulacao& simulacao) const {
    std::string texto = "  pattern sobre \"" + cadeia + "\"\n";
    for (const PassoDaSimulacao& passo : simulacao.passos) {
        texto += "    ";
        if (passo.simboloLido == '\0') {
            texto += "inicio ";
        } else {
            texto += "apos '";
            texto += passo.simboloLido;
            texto += "' ";
        }
        texto += "-> { ";
        for (std::size_t i = 0; i < passo.ativos.size(); ++i) {
            if (i > 0) {
                texto += ", ";
            }
            texto += std::to_string(passo.ativos[i]);
        }
        texto += " }\n";
    }
    texto += std::string("  resultado: ") + (simulacao.aceitou ? "ACEITA" : "RECUSA");
    texto += " | maior conjunto ativo: " + std::to_string(simulacao.maiorConjuntoAtivo) + "\n";
    return texto;
}

// --- a construção de Thompson ------------------------------------------------

namespace {

// Um caso por construtor da árvore, e a recursão faz a composição. Repare que
// nenhum caso precisa saber o que há dentro dos blocos que recebe: só que cada
// um tem uma entrada e uma saída.
Bloco construir(const Arvore& arvore, const std::size_t indice, Afn& afn) {
    const No& no = arvore.nos[indice];
    switch (no.tipo) {
// recorte:inicio thompson-caso-base
        case TipoDeNo::Simbolo:
        case TipoDeNo::Qualquer:
        case TipoDeNo::Vazio: {
            // Os três casos base têm a mesma forma — dois estados e uma
            // transição —, e diferem apenas no rótulo dela.
            const Estado entrada = afn.novoEstado();
            const Estado saida = afn.novoEstado();
            const char rotulo = no.tipo == TipoDeNo::Simbolo  ? no.simbolo
                                : no.tipo == TipoDeNo::Qualquer ? kQualquer
                                                                : kEpsilon;
            afn.adicionarTransicao(entrada, rotulo, saida);
            return Bloco{entrada, saida};
        }
        // recorte:fim thompson-caso-base
// recorte:inicio thompson-concatenacao
        case TipoDeNo::Concatenacao: {
            // A saída do primeiro passa a alimentar a entrada do segundo. Uma
            // transição vazia liga os dois em vez de fundir os estados: fundir
            // funcionaria aqui e quebraria a uniformidade da interface.
            const Bloco esquerdo = construir(arvore, no.esquerda, afn);
            const Bloco direito = construir(arvore, no.direita, afn);
            afn.adicionarTransicao(esquerdo.saida, kEpsilon, direito.entrada);
            return Bloco{esquerdo.entrada, direito.saida};
        }
        // recorte:fim thompson-concatenacao
// recorte:inicio thompson-alternancia
        case TipoDeNo::Alternancia: {
            const Bloco esquerdo = construir(arvore, no.esquerda, afn);
            const Bloco direito = construir(arvore, no.direita, afn);
            const Estado entrada = afn.novoEstado();
            const Estado saida = afn.novoEstado();
            afn.adicionarTransicao(entrada, kEpsilon, esquerdo.entrada);
            afn.adicionarTransicao(entrada, kEpsilon, direito.entrada);
            afn.adicionarTransicao(esquerdo.saida, kEpsilon, saida);
            afn.adicionarTransicao(direito.saida, kEpsilon, saida);
            return Bloco{entrada, saida};
        }
        // recorte:fim thompson-alternancia
// recorte:inicio thompson-fecho
        case TipoDeNo::Fecho: {
            const Bloco interno = construir(arvore, no.esquerda, afn);
            const Estado entrada = afn.novoEstado();
            const Estado saida = afn.novoEstado();
            afn.adicionarTransicao(entrada, kEpsilon, interno.entrada);  // uma vez ou mais
            afn.adicionarTransicao(entrada, kEpsilon, saida);            // zero vezes
            afn.adicionarTransicao(interno.saida, kEpsilon, interno.entrada);  // de novo
            afn.adicionarTransicao(interno.saida, kEpsilon, saida);            // basta
            return Bloco{entrada, saida};
        }
        // recorte:fim thompson-fecho
    }
    // Inalcançável: o switch cobre todos os construtores da árvore. O retorno
    // existe porque o compilador não sabe disso, e omiti-lo seria aviso — que
    // aqui é erro.
    return Bloco{0, 0};
}

}  // namespace

Afn construirThompson(const Arvore& arvore) {
    Afn afn;
    if (arvore.vazia()) {
        const Estado unico = afn.novoEstado();
        afn.definirInicial(unico);
        afn.definirAceitacao(unico);
        return afn;
    }
    const Bloco raiz = construir(arvore, arvore.raiz, afn);
    afn.definirInicial(raiz.entrada);
    afn.definirAceitacao(raiz.saida);
    return afn;
}

// --- a bateria de casos conferidos à mão -------------------------------------

std::vector<CasoDeTeste> lerCasos(const std::string& caminho) {
    std::vector<CasoDeTeste> casos;
    std::ifstream arquivo(caminho);
    if (!arquivo) {
        return casos;
    }

    std::string linha;
    std::size_t numeroDaLinha = 0;
    while (std::getline(arquivo, linha)) {
        ++numeroDaLinha;
        if (linha.empty() || linha[0] == '#') {
            continue;
        }
        // Formato: expressao <TAB> cadeia <TAB> aceita|recusa
        std::istringstream campos(linha);
        CasoDeTeste caso;
        std::string veredito;
        if (!std::getline(campos, caso.expressao, '\t') ||
            !std::getline(campos, caso.cadeia, '\t') || !std::getline(campos, veredito)) {
            continue;
        }
        caso.esperado = veredito == "aceita";
        caso.origem = caminho + ":" + std::to_string(numeroDaLinha);
        casos.push_back(caso);
    }
    return casos;
}

ResultadoDaBateria rodarBateria(const std::vector<CasoDeTeste>& casos) {
    ResultadoDaBateria resultado;
    resultado.arquivoLido = !casos.empty();
    for (const CasoDeTeste& caso : casos) {
        ++resultado.total;
        const Resultado leitura = analisarExpressao(caso.expressao);
        if (!leitura.ok) {
            resultado.falhas.push_back(caso.origem + ": pattern recusado pela leitura — " +
                                       leitura.erro.mensagem);
            continue;
        }
        const Afn afn = construirThompson(leitura.arvore);
        const bool obtido = afn.aceita(caso.cadeia);
        if (obtido == caso.esperado) {
            ++resultado.passaram;
            continue;
        }
        resultado.falhas.push_back(caso.origem + ": /" + caso.expressao + "/ sobre \"" +
                                   caso.cadeia + "\" — esperado " +
                                   (caso.esperado ? "aceita" : "recusa") + ", obtido " +
                                   (obtido ? "aceita" : "recusa"));
    }
    return resultado;
}

}  // namespace peneira

O que torna a construção sistemática é a interface uniforme dos blocos, e vale olhar para ela antes de qualquer caso individual. Todo bloco construído tem exatamente uma entrada e exatamente uma saída, e é essa promessa que permite compor blocos sem saber o que há dentro deles. Se um único caso a quebrasse — devolvendo dois estados de saída, por exemplo —, os outros três precisariam tratá-lo como exceção, e a construção deixaria de ser mecânica. A uniformidade é a condição de a recursão ser possível.

A decisão de manter a promessa cobra um preço visível na concatenação. Ligar a saída do primeiro bloco à entrada do segundo por uma transição vazia produz um estado a mais do que seria necessário — fundir os dois estados daria a mesma linguagem com uma máquina menor. Não fundimos, e a razão é a uniformidade: fundir exige que a concatenação conheça a estrutura interna dos blocos que recebeu, e é assim que uma construção mecânica vira um conjunto de casos especiais. O excesso de estados é temporário de todo modo — a minimização o remove no módulo seguinte.

Repare no cuidado que a tarefa cobra: nenhum operador ficou de fora. Os seis construtores que a árvore pode conter estão no switch, e três deles — símbolo, coringa e cadeia vazia — compartilham a mesma forma, diferindo apenas no rótulo da transição. O coringa está ali porque a decisão do módulo de expressões o manteve como folha própria em vez de expandi-lo, e essa decisão cobra aqui a sua primeira parcela: ele precisa de uma marca de transição própria, que casa qualquer símbolo sem ser vazia. Tê-lo esquecido produziria exatamente a falha que o enunciado antecipa — silenciosa, e visível só três módulos adiante.

O custo da construção é previsível e a demonstração o exibe: cada folha custa dois estados, a alternância e o fecho custam dois a mais cada, e a concatenação não custa estado nenhum — só uma transição vazia. A expressão que combina alternância, fecho e concatenação produz dez estados e doze transições, das quais nove são vazias. Essa proporção de transições vazias é o que a simulação terá de atravessar a cada símbolo, e é o que o módulo seguinte elimina ao determinizar.

Onde é fácil errar. No bloco do fecho, esquecer uma das quatro transições vazias. São quatro e cada uma corresponde a uma frase da definição: entrar no interno (uma vez ou mais), pular direto para a saída (zero vezes), voltar do fim do interno para o começo dele (de novo), e sair do fim do interno (basta). Faltando a segunda, o fecho deixa de aceitar a cadeia vazia; faltando a terceira, ele aceita no máximo uma repetição. Como verificar que está correta: submeta o fecho a três cadeias — vazia, uma repetição, três repetições — e uma que não casa. As quatro juntas detectam qualquer transição faltante.

1.3 Tarefa 2: Simular a máquina não determinística

O que a tarefa pede

Implementar a simulação que executa a máquina construída sobre uma cadeia de entrada. A dificuldade não está no algoritmo, e sim em manter a coleção de estados simultaneamente ativos sem que o custo dessa manutenção domine a execução — o que exige decidir como representar um conjunto de estados, e não apenas um estado.

A diferença em relação ao módulo anterior está inteira na primeira frase da simulação: o que se mantém é um conjunto de estados, e não um estado corrente. E a aceitação passa a ser por existência de caminho — basta que o estado de aceitação esteja entre os ativos ao fim, sem que os demais caminhos precisem aceitar. Essa assimetria é o não determinismo, e é o que a demonstração torna visível ao imprimir o conjunto ativo depois de cada símbolo.

A decisão de representação que a tarefa cobra é esta: mantemos o conjunto como vetor de estados mais um vetor denso de marcas, e não como conjunto ordenado. O vetor de marcas responde “este estado já está no conjunto?” em tempo constante e sem alocar; o vetor de estados preserva a ordem de inserção e é o que se percorre. A alternativa natural — um conjunto ordenado por símbolo consumido — alocaria a cada caractere de entrada, e a simulação processa texto inteiro. Zerar as marcas usadas custa uma passada sobre os estados que entraram, e não sobre todos os estados da máquina, o que mantém o custo proporcional ao conjunto ativo e não ao tamanho da máquina.

O fecho vazio é a operação básica, e há um detalhe nele que decide se a simulação funciona. Ele precisa ser aplicado ao conjunto inicial, e não apenas depois de cada símbolo. Esquecer esse primeiro fecho produz um defeito que passa em quase todos os testes: ele só se manifesta quando a máquina tem transição vazia logo na entrada — o que acontece exatamente nos blocos de alternância e de fecho, ou seja, na maioria dos patterns reais. Repare na demonstração: o conjunto inicial da expressão com alternância tem três estados antes de qualquer símbolo ser lido, e o da expressão composta tem seis.

O fecho vazio também precisa de marcação de visitado, e não por eficiência. O bloco do fecho tem uma transição vazia que volta ao próprio começo; sem marcação, a travessia gira para sempre. É o tipo de defeito que não aparece em revisão de código e trava o programa no primeiro pattern com repetição.

A simulação interrompe o consumo quando o conjunto ativo fica vazio, e essa é uma otimização legítima e não uma mudança de semântica: sem estado ativo, nenhum símbolo posterior reativa coisa alguma. O traço registra o maior conjunto ativo observado, que é a medida de quanto trabalho a simulação faz por símbolo — para a expressão composta da demonstração, sete estados simultâneos numa máquina de dez.

Onde é fácil errar. Confundir simulação com determinização. Manter o conjunto ativo em memória durante a execução não é construir o autômato determinístico: aqui os conjuntos são calculados e descartados a cada símbolo, e nenhum deles vira estado de coisa alguma. A determinização, que é justamente memorizar esses conjuntos como estados, é o assunto do módulo seguinte. Como verificar que está correta: rode a simulação sobre um pattern com alternância no começo e confira que o conjunto ativo antes do primeiro símbolo tem mais de um estado. Se tiver apenas um, falta o fecho vazio inicial.

1.4 Tarefa 3: Montar a bateria de casos conferidos à mão

O que a tarefa pede

Construir um conjunto de casos em que o resultado da simulação é comparado com o que se determinou à mão, cadeia por cadeia. Casos conferidos à mão são caros de produzir e é justamente por isso que valem: são a única evidência independente do próprio código, e a partir daqui todas as peças do sistema serão verificadas contra alguma coisa que o sistema mesmo produziu. Ficam guardados no repositório e rodando pelo comando único de reconstrução — a partir do capítulo seguinte, é essa bateria que vai avisar quando a máquina reduzida deixar de aceitar o que a original aceitava.

A bateria vive num arquivo de dados, e não em código, por uma razão que o enunciado deixa implícita: acrescentar um caso precisa ser barato a ponto de que se acrescente. Um caso que exige recompilar para existir é um caso que não vai ser escrito na tarde em que alguém descobrir a cadeia que quebra o sistema — e é justamente essa cadeia que faltava na bateria. Cada linha traz o pattern, a cadeia e o veredito, separados por tabulação, e as linhas de comentário registram por que cada grupo existe.

exemplos/04_casos.txt

# 04_casos.txt — bateria conferida A MAO, caso por caso.
#
# Formato: expressao <TAB> cadeia <TAB> aceita|recusa
#
# O veredito de cada linha foi determinado SEM rodar o programa. E essa
# independencia que da valor a bateria: a partir do proximo capitulo, tudo o
# mais sera verificado contra algo que o proprio sistema produziu, e estes
# casos serao a unica evidencia externa que resta.
#
# A cadeia vazia e o campo vazio entre dois tabuladores.

# --- casos base
a   a   aceita
a       recusa
a   b   recusa
a   aa  recusa

# --- concatenacao
ab  ab  aceita
ab  a   recusa
ab  abc recusa

# --- alternancia
a|b a   aceita
a|b b   aceita
a|b c   recusa
a|b ab  recusa
x|y|z   y   aceita

# --- fecho: o unico operador que aceita a cadeia vazia
a*      aceita
a*  a   aceita
a*  aaa aceita
a*  aab recusa
a** aaa aceita

# --- fecho positivo, reduzido a concat(x, fecho(x)) na leitura
a+      recusa
a+  a   aceita
a+  aaa aceita

# --- opcional, reduzido a alt(x, vazio) na leitura
a?      aceita
a?  a   aceita
a?  aa  recusa

# --- coringa: casa um simbolo qualquer, mas NAO a cadeia vazia
a.c abc aceita
a.c a c aceita
a.c ac  recusa
a.c abbc    recusa

# --- grupo e composicao
(ab)*       aceita
(ab)*   abab    aceita
(ab)*   aba recusa
(a|b)*c c   aceita
(a|b)*c abbac   aceita
(a|b)*c abb recusa

# --- classes de simbolos
[0-9]+  240 aceita
[0-9]+  24a recusa
[0-9]+      recusa
-?[0-9]+    -42 aceita
-?[0-9]+    42  aceita
-?[0-9]+    --42    recusa

# --- o pattern de endereco do primeiro exemplo do percurso
[a-z]+@[a-z]+\.[a-z]+   ana@exemplo.com aceita
[a-z]+@[a-z]+\.[a-z]+   ana@exemplo recusa
[a-z]+@[a-z]+\.[a-z]+   @exemplo.com    recusa

São quarenta e dois casos, e o valor deles está em uma propriedade que nenhuma ferramenta verifica: cada veredito foi determinado sem rodar o programa. Escrever o caso depois de ver o que o código faz produz um arquivo que documenta o comportamento atual — inclusive os defeitos — em vez de verificá-lo. É a diferença entre teste e registro, e ela não aparece na saída: as duas baterias passam.

Os grupos foram escolhidos para cobrir cada decisão tomada até aqui. Os casos base separam símbolo de cadeia vazia; os do fecho incluem a cadeia vazia, que é o único operador a aceitá-la; os do fecho positivo e do opcional exercitam as reduções decididas dois módulos atrás, e falhariam se a redução tivesse sido aplicada de forma inconsistente; os do coringa incluem o caso em que ele não casa a cadeia vazia; e os últimos três atacam o pattern de endereço escrito no primeiro módulo do percurso, fechando o ciclo com o exemplo que originou tudo.

O subcomando devolve código de saída não-zero quando um caso discorda, e é isso que torna a bateria um teste de verdade dentro do comando único de reconstrução. Um relatório que sempre sai com sucesso não protege ninguém: ele aparece na tela, é lido nas primeiras semanas e ignorado depois. A bateria atual passa nos quarenta e dois casos, e a mensagem de falha traz arquivo e linha do caso que discordou, mais o que se esperava e o que se obteve — porque a falha vai acontecer daqui a um módulo, quando a minimização entrar, e ler “um caso falhou” não ajuda quem precisa consertar.

Onde é fácil errar. Escrever os casos rodando o programa e conferindo se a saída “parece certa”. O arquivo resultante tem a mesma aparência e nenhum valor: ele congela os defeitos existentes como comportamento esperado. Como verificar que está correta: pegue um caso qualquer da sua bateria e refaça o veredito à mão, sem consultar o código. Se você não conseguir dizer por que aquela cadeia é aceita ou recusada, o caso foi copiado em vez de conferido.

1.5 Por que a construção é sistemática, e o que isso muda para quem implementa

O plano deste módulo pede que se explique por que a construção é sistemática, e a resposta é uma propriedade da definição que o originou, que reaparece adiante com outro nome.

A construção é sistemática porque a definição é indutiva sobre a estrutura do objeto que ela transforma. A árvore tem seis construtores, e a definição dá uma regra para cada um: três casos base, que não dependem de nada, e três casos compostos, que dependem apenas do resultado já obtido para as subárvores — nunca da forma delas. Uma definição com essa forma é um algoritmo recursivo: o algoritmo já está escrito, e o que falta é transcrevê-lo.

O que isso muda para quem implementa é concreto, e são três coisas.

A primeira é que a cobertura é verificável mecanicamente. Se cada construtor da árvore tem um caso, a construção está completa — e o compilador ajuda, porque um switch sobre o tipo de nó que esqueça um construtor gera aviso, e aviso aqui é erro. A tarefa pede que nenhum operador fique de fora, e o que garante isso é a estrutura do código espelhar a estrutura do dado.

A segunda é que a correção se argumenta por indução, e não por teste. Cada caso base produz um bloco que aceita exatamente a linguagem da folha correspondente; cada caso composto produz um bloco que aceita exatamente a composição das linguagens dos blocos que recebeu, supondo que eles estejam corretos. Somando os seis, a máquina aceita a linguagem da expressão. A bateria de casos não substitui esse argumento — ela pega erro de transcrição, que é outro tipo de defeito.

A terceira é a que interessa para o resto do percurso: este conforto não se repete. A determinização do módulo seguinte é um algoritmo de ponto fixo sobre conjuntos de estados, indutiva sobre a estrutura de coisa nenhuma, e a distância entre o enunciado e o código é bem maior. A análise sintática descendente ainda guarda algo desta forma, porque a gramática também é indutiva, mas ali a transcrição já esbarra em recursão à esquerda e em fatoração, que são justamente adaptações. E a geração de código não guarda nada: entre “traduzir a árvore para instruções” e o código que faz isso há um conjunto de decisões que nenhuma definição induz.

Notar a diferença agora é o que evita a conclusão errada mais adiante — a de que o percurso ficou difícil porque o assunto ficou difícil. O assunto não fica mais difícil: o que muda é que a definição para de escrever o código por você, e a partir dali cada linha passa a ser uma escolha que alguém precisa justificar.

1.6 Por dentro da implementação

O que vem acima explica o que foi construído e por quê. Falta o percurso: quem chama quem, em que ordem, e com que valores no instante em que a coisa decide. É o que esta seção mostra, sobre execuções concretas do binário deste ponto do percurso.

A costura com o que já existia tem dois pontos de contato. O primeiro é analisarExpressao(), escrita no módulo anterior: é ela quem produz a árvore que construirThompson() — nova aqui — consome, e é o único lugar em que o código deste módulo chama para trás. O segundo é o tipo Estado, definido em 03_afd.h: 04_afn.h o inclui e o reaproveita como tipo dos estados do autômato não determinístico, sem tocar em mais nada daquele arquivo — a classe Afd do módulo 03 não participa de nada aqui, porque a máquina deste módulo guarda uma lista de transições rotuladas por estado, e não a tabela densa do módulo anterior.

1.6.1 As alterações deste módulo

O módulo acrescenta um arquivo, e dentro dele três percursos que não existiam. Cada um recebe abaixo uma execução própria e o seu par de diagramas.

Alteração	O que passou a acontecer
construcao-de-thompson	A árvore de padrão passa a virar máquina não determinística, por uma função que se chama a si mesma seguindo a forma da árvore.
simulacao-por-conjunto-de-estados	A execução passa a manter um conjunto de estados ativos em vez de um estado corrente, e a aceitar por existência de caminho.
bateria-a-partir-de-arquivo	A verificação passa a comparar a simulação com um veredito lido de um arquivo de dados, caso a caso, sem parar no primeiro que discordar.

1.6.2 construcao-de-thompson — a árvore que vira máquina

A execução. A expressão que combina os três operadores compostos, (a|b)*c, submetida à cadeia abc:

/(a|b)*c/  -> 10 estados, 12 transicoes (9 vazias)
  pattern sobre "abc"
    inicio -> { 6, 4, 7, 8, 0, 2 }
    apos 'a' -> { 1, 5, 4, 7, 8, 0, 2 }
    apos 'b' -> { 3, 5, 4, 7, 8, 0, 2 }
    apos 'c' -> { 9 }
  resultado: ACEITA | maior conjunto ativo: 7

construirThompson() recebe a árvore de analisarExpressao() e chama construir() sobre a raiz. construir() é recursiva: o nó Concatenacao da raiz chama construir() sobre no.esquerda (o Fecho), que chama construir() sobre no.esquerda (a Alternancia), que chama construir() sobre os dois símbolos — os primeiros casos base que a recursão alcança. Só depois de as duas subárvores mais internas devolverem o Bloco de entrada e saída é que a Alternancia, o Fecho e por fim a Concatenacao acrescentam os próprios estados e transições.

%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    A["mostrarConstrucao(expressao, cadeia)"] --> B["analisarExpressao(expressao)"]
    B --> C{"leitura.ok"}
    C -- "nao" --> Z["formatarErro(expressao, leitura.erro)"]
    C -- "sim" --> D["construirThompson(leitura.arvore)"]
    D --> E{"arvore.vazia()"}
    E -- "sim" --> F["novoEstado() unico; definirInicial(unico); definirAceitacao(unico)"]
    F --> RET0["devolve afn"]
    E -- "nao" --> G["construir(arvore, arvore.raiz, afn)"]
    G --> H{"no.tipo"}
    H -- "Simbolo / Qualquer / Vazio" --> I["novoEstado() duas vezes; adicionarTransicao(entrada, rotulo, saida)"]
    I --> RET["devolve Bloco{entrada, saida}"]
    H -- "Concatenacao" --> K1["construir(arvore, no.esquerda, afn)"]
    K1 -.->|"chamada recursiva"| G
    K1 --> K2["construir(arvore, no.direita, afn)"]
    K2 -.->|"chamada recursiva"| G
    K2 --> K3["adicionarTransicao(esquerdo.saida, kEpsilon, direito.entrada)"]
    K3 --> RET
    H -- "Alternancia" --> L1["construir(arvore, no.esquerda, afn)"]
    L1 -.->|"chamada recursiva"| G
    L1 --> L2["construir(arvore, no.direita, afn)"]
    L2 -.->|"chamada recursiva"| G
    L2 --> L3["novoEstado() duas vezes; adicionarTransicao() quatro vezes (entrada->esquerdo.entrada, entrada->direito.entrada, esquerdo.saida->saida, direito.saida->saida)"]
    L3 --> RET
    H -- "Fecho" --> M1["construir(arvore, no.esquerda, afn)"]
    M1 -.->|"chamada recursiva"| G
    M1 --> M2["novoEstado() duas vezes; adicionarTransicao() quatro vezes (entrada->interno.entrada, entrada->saida, interno.saida->interno.entrada, interno.saida->saida)"]
    M2 --> RET
    RET --> N["construirThompson: definirInicial(raiz.entrada); definirAceitacao(raiz.saida)"]
    N --> O["quantidadeDeEstados()"]
    O --> P["quantidadeDeTransicoes()"]
    P --> Q["quantidadeDeTransicoesVazias()"]

No momento em que construir() é chamado pela primeira vez sobre o nó Simbolo 'a', com a árvore de /(a|b)*c/, quatro quadros estão na pilha — um por nível de aninhamento entre a raiz e a folha mais funda:

%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    Q1["construir(indice=Concatenacao) — no.esquerda=Fecho, no.direita=Simbolo 'c'"]
    Q1 -- "construir(no.esquerda) empilha o quadro seguinte" --> Q2["construir(indice=Fecho) — no.esquerda=Alternancia"]
    Q2 -- "construir(no.esquerda) empilha o quadro seguinte" --> Q3["construir(indice=Alternancia) — no.esquerda=Simbolo 'a', no.direita=Simbolo 'b'"]
    Q3 -- "construir(no.esquerda) empilha o quadro seguinte" --> Q4["construir(indice=Simbolo 'a') — caso base, devolve Bloco sem empilhar mais nada"]

A sequência mostra a mesma execução do lado de fora: cada retorno de construir() devolve um Bloco, e é só com os dois blocos das subárvores em mãos que o nó composto pode ligar suas próprias transições.

%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
sequenceDiagram
    autonumber
    participant Dm as demos/04_demo.cpp
    participant Rx as 02_regex.cpp
    participant Th as 04_afn.cpp
    participant Af as Afn
    Dm->>Rx: analisarExpressao("(a|b)*c")
    Rx-->>Dm: arvore com raiz Concatenacao
    Dm->>Th: construirThompson(arvore)
    Th->>Th: construir(arvore, indice=raiz Concatenacao, afn)
    Th->>Th: construir(arvore, indice=Fecho, afn)
    Th->>Th: construir(arvore, indice=Alternancia, afn)
    Th->>Th: construir(arvore, indice=Simbolo 'a', afn)
    Th-->>Th: Bloco{entrada, saida} (caso base 'a')
    Th->>Th: construir(arvore, indice=Simbolo 'b', afn)
    Th-->>Th: Bloco{entrada, saida} (caso base 'b')
    Th->>Af: novoEstado() duas vezes (Alternancia)
    Th->>Af: adicionarTransicao() quatro vezes (Alternancia)
    Th-->>Th: Bloco{entrada, saida} (Alternancia)
    Th->>Af: novoEstado() duas vezes (Fecho)
    Th->>Af: adicionarTransicao() quatro vezes (Fecho)
    Th-->>Th: Bloco{entrada, saida} (Fecho)
    Th->>Th: construir(arvore, indice=Simbolo 'c', afn)
    Th-->>Th: Bloco{entrada, saida} (caso base 'c')
    Th->>Af: adicionarTransicao(esquerdo.saida, kEpsilon, direito.entrada) (Concatenacao)
    Th-->>Th: Bloco{entrada, saida} (raiz, Concatenacao)
    Th->>Af: definirInicial(raiz.entrada)
    Th->>Af: definirAceitacao(raiz.saida)
    Th-->>Dm: Afn pronta
    Dm->>Af: quantidadeDeEstados()
    Af-->>Dm: 10
    Dm->>Af: quantidadeDeTransicoes()
    Af-->>Dm: 12
    Dm->>Af: quantidadeDeTransicoesVazias()
    Af-->>Dm: 9

A decisão, e o que ela descartou. quantidadeDeTransicoesVazias() percorre a lista de transições de todos os estados toda vez que é chamada, em vez de manter um contador incrementado dentro de adicionarTransicao(). Um contador responderia em tempo constante, e cobraria uma disciplina que a construção não tem hoje: nada impede que uma transição seja adicionada e depois descartada por um caminho de código futuro, e o contador registraria a inserção, não o estado final da máquina — exatamente o defeito silencioso que o módulo 03 já evitou ao escolher varrer a tabela em vez de contar escritas. A varredura custa uma passada pelas transições da máquina recém-construída, uma vez por chamada de mostrarConstrucao(), o que é irrelevante frente ao resto do trabalho.

1.6.3 simulacao-por-conjunto-de-estados — o conjunto ativo em vez do estado corrente

A execução. A mesma máquina de /(a|b)*c/, agora olhando para dentro de simular("abc"):

    inicio -> { 6, 4, 7, 8, 0, 2 }
    apos 'a' -> { 1, 5, 4, 7, 8, 0, 2 }
    apos 'b' -> { 3, 5, 4, 7, 8, 0, 2 }
    apos 'c' -> { 9 }
  resultado: ACEITA | maior conjunto ativo: 7

O conjunto inicial já tem seis estados antes de qualquer símbolo ser lido — é fechoVazio({inicial_}), chamado uma vez fora do laço, e não o estado inicial sozinho. A cada símbolo, simular() monta proximos a partir das transições dos estados ativos, aplica fechoVazio() de novo sobre esse conjunto e registra o passo. O maior conjunto observado, sete estados depois de 'a' e de 'b', é a medida do que o não determinismo custa por símbolo consumido nesta máquina.

%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    A["simular(cadeia)"] --> B["fechoVazio({inicial_})"]
    B --> C["ativos recebe o resultado; passos.push_back(passo inicial); maiorConjuntoAtivo = ativos.size()"]
    C --> D{"para cada simbolo de cadeia"}
    D -- "proximo simbolo" --> E["para cada estado em ativos, para cada transicao: transicao.simbolo == simbolo #124;#124; (transicao.simbolo == kQualquer && simbolo != kEpsilon)"]
    E --> F["proximos recebe os destinos ainda nao marcados em presente[]"]
    F --> G["fechoVazio(proximos)"]
    G --> H["ativos recebe o resultado; passos.push_back(passo do simbolo)"]
    H --> I{"ativos.size() > maiorConjuntoAtivo"}
    I -- "sim" --> J["maiorConjuntoAtivo = ativos.size()"]
    I -- "nao" --> K["segue sem atualizar"]
    J --> L{"ativos.empty()"}
    K --> L
    L -- "sim" --> M["interrompe o laco (break)"]
    L -- "nao" --> D
    D -- "os simbolos acabaram" --> N{"aceitacao_ esta entre os ativos?"}
    N -- "sim" --> O["aceitou = true"]
    N -- "nao" --> P["aceitou permanece false"]
    O --> Q["devolve Simulacao"]
    P --> Q
    M --> Q

%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
sequenceDiagram
    autonumber
    participant Dm as demos/04_demo.cpp
    participant Af as Afn
    Dm->>Af: simular("abc")
    Af->>Af: fechoVazio({inicial_})
    Af-->>Af: { 6, 4, 7, 8, 0, 2 } — 6 estados
    Af->>Af: registra o passo inicial com 6 estados ativos
    Af->>Af: consome 'a': calcula proximos a partir de ativos
    Af->>Af: fechoVazio(proximos)
    Af-->>Af: { 1, 5, 4, 7, 8, 0, 2 } — 7 estados
    Af->>Af: registra o passo apos 'a'
    Af->>Af: consome 'b': calcula proximos a partir de ativos
    Af->>Af: fechoVazio(proximos)
    Af-->>Af: { 3, 5, 4, 7, 8, 0, 2 } — 7 estados
    Af->>Af: registra o passo apos 'b'
    Af->>Af: consome 'c': calcula proximos a partir de ativos
    Af->>Af: fechoVazio(proximos)
    Af-->>Af: { 9 } — 1 estado
    Af->>Af: registra o passo apos 'c'
    Af-->>Dm: Simulacao{aceitou=true, maiorConjuntoAtivo=7}
    Dm->>Af: formatarSimulacao("abc", simulacao)
    Af-->>Dm: o traco formatado

Não há pilha de chamadas aqui: fechoVazio() percorre o próprio grafo de transições vazias com uma pilha de dados explícita, não com chamadas de função recursivas, e simular() não se chama a si mesma. Desenhar quadros de chamada para um percurso que a linguagem já expressa como laço passaria a impressão de que há uma recursão onde não há nenhuma.

A decisão, e o que ela descartou. proximos é um std::vector novo, alocado a cada símbolo consumido, com um vetor de marcas (presente) do tamanho da máquina reaproveitado entre os símbolos só para saber quem já entrou no conjunto. A alternativa seria reaproveitar também o próprio vetor proximos, limpando-o em vez de recriá-lo. Ela pouparia uma alocação por símbolo de entrada — e cobraria a obrigação de esvaziar exatamente o que a iteração anterior deixou, sem esquecer nenhuma posição: um erro de limpeza incompleta reaproveitaria estados da simulação de um caractere anterior, e o defeito só apareceria em cadeias longas o bastante para o buraco importar. A alocação por símbolo é o preço de nunca correr esse risco.

1.6.4 bateria-a-partir-de-arquivo — o veredito comparado, caso a caso

A execução. A bateria completa do módulo, quarenta e dois casos:

Bateria conferida a mao: 42/42 casos passaram.

lerCasos() lê o arquivo linha a linha, ignora comentários e linhas vazias, e separa cada linha por tabulação em expressão, cadeia e veredito. rodarBateria() recebe essa lista e, para cada caso, repete o par que as duas alterações anteriores já explicaram: analisarExpressao() seguida de construirThompson(), e então aceita() — a forma de simular() que só devolve a resposta. O resultado obtido é comparado com o veredito lido do arquivo.

%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    A["lerCasos(caminho)"] --> B{"arquivo aberto?"}
    B -- "nao" --> C["devolve casos vazio"]
    B -- "sim" --> D{"para cada linha do arquivo"}
    D -- "linha vazia ou comeca com '#'" --> D
    D -- "linha de dados" --> E["getline dividido por TAB: expressao, cadeia, veredito"]
    E --> F["caso.esperado = (veredito == 'aceita'); caso.origem = caminho + ':' + numeroDaLinha"]
    F --> D
    D -- "arquivo acabou" --> G["devolve casos"]
    G --> H["rodarBateria(casos)"]
    H --> I{"para cada caso em casos"}
    I -- "proximo caso" --> J["analisarExpressao(caso.expressao)"]
    J --> K{"leitura.ok"}
    K -- "nao" --> L["falhas.push_back(pattern recusado pela leitura)"]
    K -- "sim" --> M["construirThompson(leitura.arvore)"]
    M --> N["afn.aceita(caso.cadeia)"]
    N --> O{"obtido == caso.esperado"}
    O -- "sim" --> P["++passaram"]
    O -- "nao" --> Q["falhas.push_back(esperado X, obtido Y)"]
    L --> I
    P --> I
    Q --> I
    I -- "os casos acabaram" --> R["devolve ResultadoDaBateria"]

%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
sequenceDiagram
    autonumber
    participant Dm as demos/04_demo.cpp
    participant Ba as 04_afn.cpp
    participant Rx as 02_regex.cpp
    participant Af as Afn
    Dm->>Ba: lerCasos("exemplos/04_casos.txt")
    Ba-->>Dm: 42 casos
    Dm->>Ba: rodarBateria(casos)
    loop para cada um dos 42 casos
        Ba->>Rx: analisarExpressao(caso.expressao)
        Rx-->>Ba: arvore
        Ba->>Ba: construirThompson(leitura.arvore)
        Ba->>Af: aceita(caso.cadeia)
        Af-->>Ba: obtido
        Ba->>Ba: compara obtido com caso.esperado
    end
    Ba-->>Dm: ResultadoDaBateria{total=42, passaram=42, falhas=[]}

Não há pilha de chamadas aqui também: o laço de rodarBateria() sobre os quarenta e dois casos é iteração simples, sem que uma iteração dependa do estado empilhado de outra.

A decisão, e o que ela descartou. rodarBateria() não para no primeiro caso que discordar — ela acumula a falha em falhas e segue para o próximo. Parar cedo daria a mesma resposta para quem só quer saber se a bateria passou inteira, e cobraria caro exatamente na situação em que a bateria mais serve: quando uma mudança na construção ou na simulação quebra mais de um caso ao mesmo tempo, parar no primeiro esconde os demais, e cada consulta subsequente corrige um caso e descobre o seguinte só na próxima rodada. Percorrer os quarenta e dois sempre custa uma passada fixa — nunca mais do que isso — e devolve a lista completa do que quebrou numa execução só.