1 Linguagens formais e a arquitetura de um compilador — 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 cada decisão justificada e cada alternativa descartada registrada ao lado dela. É o modelo do que cada grupo deve produzir no próprio projeto, e existe para ser estudado, não copiado: a linguagem que o grupo recorta, o exemplo que ele escreve e a organização que adota são dele. O que se copia daqui é o nível de acabamento e o hábito de deixar por escrito a razão de cada escolha.

1.1 Visão Geral

Nenhuma das três tarefas deste módulo pede uma linha de código do sistema, e é por isso que elas costumam ser resolvidas mal. Fixar o recorte da linguagem, escrever à mão um exemplo válido e montar o repositório produzem decisões, e decisão errada aqui não cobra agora: cobra quatro módulos adiante, quando já existe código apoiado sobre ela e mudá-la significa reescrever peças que funcionavam. É a fatura mais parcelada do percurso.

A implementação de referência é a Peneira, uma linguagem pequena de reconhecimento de padrões em texto cujo compilador produz um motor de autômatos. Quem acompanha construindo o próprio sistema vai tomar as mesmas três decisões sobre outra linguagem, e o que interessa estudar aqui é como cada decisão foi tomada e o que ficou registrado dela — o conteúdo das decisões pertence à Peneira e não se transfere.

Além das três tarefas, o módulo tem teoria que admite implementação, e ela também está implementada. São dois blocos. O primeiro percorre os três degraus da definição — o símbolo, a cadeia e a linguagem — com as operações de cada degrau escritas como código executável, e termina esbarrando no limite que motiva o módulo seguinte. O segundo declara a arquitetura do sistema como dado: as fases, o que cada uma consome e produz, a fronteira entre a metade que analisa e a que sintetiza, a hierarquia que faz corresponder classes de gramática a classes de máquina, as formas intermediárias e a posição da interpretação diante da compilação.

A ordem em que resolvemos as três tarefas não é a ordem em que elas foram enunciadas por acaso. O recorte vem primeiro porque o exemplo válido depende dele: não se escreve uma descrição correta numa linguagem cujas fronteiras ainda não foram traçadas. O exemplo vem antes do repositório porque é ele que diz o que a bateria de testes precisa verificar, e uma bateria montada sem alvo verifica que o programa não quebra, o que é bem menos do que verificar que ele acerta. Inverter qualquer um dos dois pares produz trabalho que se refaz.

Todo o código deste ponto do percurso compila sob o padrão C++20 com avisos tratados como erro, e roda por um executável próprio deste marco, registrado como teste. Esse executável não é reescrito por módulo nenhum adiante: quem quiser voltar a este estado do sistema, meses depois, roda o binário deste marco e vê exatamente o que a turma viu no dia.

1.2 Tarefa 1: Fixar o recorte da linguagem

O que a tarefa pede

Decidir sobre que domínio os padrões da linguagem vão falar, que classe de padrões o sistema aceitará, que forma terá a descrição escrita por quem o usa e o que ele produzirá ao processá-la. É um texto curto e consequente: tudo o que vem nos módulos seguintes responde a ele, e cada ambiguidade deixada aqui reaparece adiante como retrabalho, quando já existe código apoiado sobre a decisão que faltou.

Depois, conferir o recorte item a item contra as propriedades que o projeto enumera — o usuário escrevendo padrões, os símbolos da própria linguagem saindo do mesmo motor, o aninhamento na gramática, os tipos e o escopo, o objeto produzido e o pedido do domínio que a máquina finita não atende.

Resolvemos a tarefa produzindo um documento de decisão com três entradas, cada uma seguida da alternativa que descartamos. Registrar o que não se escolheu tem cara de burocracia. É isso que torna a decisão revisitável: seis módulos adiante, quando alguém perguntar por que a expressão regular não aceita retrovisor, a resposta está escrita com a razão técnica junto, e não depende da memória de quem decidiu naquele dia.

A primeira decisão é a classe de padrões. Aceitamos concatenação, alternância, fecho, fecho positivo, opcional, classe de caracteres, coringa e agrupamento, e declaramos um núcleo mínimo de três operadores — concatenação, alternância e fecho — ao qual todos os demais são reduzidos logo depois da leitura. O efeito prático dessa separação é mensurável: a construção do autômato, a determinização e a minimização, que vêm nos módulos seguintes, tratam três casos em vez de oito. Cada operador mantido no núcleo reapareceria em todas as peças posteriores, e o preço de mantê-lo seria cobrado uma vez por peça.

O que descartamos é o item mais importante do documento. Recusamos grupos de captura e retrovisores, e a razão nada tem a ver com esforço de implementação: o retrovisor sai da classe das linguagens regulares, e um sistema que o aceitasse não poderia ser compilado para autômato finito. Aceitá-lo derrubaria a demonstração que a obra inteira existe para fazer — a de que o produto do compilador é um motor de autômatos.

A segunda decisão é a forma da descrição. Um programa é uma sequência de declarações pattern seguida de um bloco rule, com cada ação reagindo ao casamento de um padrão nomeado e opcionalmente condicionada por um where. A alternativa descartada era permitir a expressão direta na ação, sem nome. Nomear custa uma declaração e paga em três lugares: a tabela de símbolos passa a ter o que registrar, a verificação semântica passa a ter o que checar, e a mesma expressão pode ser reusada sem recompilação.

A terceira decisão é o que o sistema produz — um vetor de autômatos determinísticos, um por padrão, mais um bytecode de máquina de pilha por regra, executados por uma máquina virtual com desempate por casamento mais longo. A alternativa era interpretar a árvore diretamente. Seria mais curto e apagaria a etapa que dá sentido ao percurso: é na emissão que o autômato deixa de ser estrutura interna do reconhecedor e vira o próprio código-alvo.

docs/01_recorte.md
# O recorte da Peneira — decisões fixadas no primeiro módulo

Registro das três decisões que a Tarefa 1 pede, na forma em que ficarão travadas para todo o
percurso. Cada uma vem acompanhada da alternativa descartada, porque é a comparação que torna a
decisão compreensível quando ela precisar ser revisitada.

## Que classe de padrões o sistema aceita

**Decisão:** expressões regulares com concatenação, alternância (`|`), fecho (`*`), fecho positivo
(`+`), opcional (`?`), classe de caracteres (`[...]`), coringa (`.`) e agrupamento por parênteses.

**Núcleo mínimo:** concatenação, alternância e fecho. Os outros três são conveniência de escrita e
serão **reduzidos ao núcleo** antes de qualquer processamento — `a+` vira `aa*`, `a?` vira `(a|ε)`,
e uma classe `[abc]` vira `(a|b|c)`. A redução acontece uma única vez, logo depois da leitura, e
tudo o que vem depois trabalha só com três operadores.

**Descartado:** grupos de captura e retrovisores (*backreferences*). Não é economia de esforço — é
teoria: retrovisor sai da classe das linguagens regulares, e um sistema que o aceitasse não poderia
ser compilado para autômato finito. A decisão de recusá-lo é o que mantém o artefato coerente com o
que a obra demonstra.

## Que forma tem a descrição escrita pelo usuário

**Decisão:** um programa é uma sequência de declarações `pattern` seguida de um bloco `rule`. Cada
`pattern` associa um nome a uma expressão regular; cada ação dentro de `rule` reage ao casamento de
um `pattern` nomeado, opcionalmente condicionada por um `where`, e produz saída por `emit`.

A gramática completa está em `docs/01_gramatica.txt`, e o exemplo canônico em
`exemplos/exemplo01.pen`.

**Descartado:** sintaxe sem nomes, em que a expressão apareceria direto na ação. Nomear o padrão
custa uma declaração a mais e paga em três lugares: a tabela de símbolos passa a ter o que registrar,
a verificação semântica passa a ter o que checar (`on x` com `x` inexistente), e a mesma expressão
pode ser reusada em mais de uma ação sem ser recompilada.

## O que o sistema produz

**Decisão:** o objeto gerado tem duas partes — um vetor de autômatos finitos determinísticos, um por
`pattern`, na forma de tabelas de transição; e, para cada `rule`, um bytecode de máquina de pilha que
avalia o `where` e executa o `emit`. Uma máquina virtual própria varre a entrada, aplica os autômatos
com desempate por casamento mais longo e executa o bytecode.

**Descartado:** interpretar a árvore diretamente, sem emitir objeto. Seria mais curto e apagaria a
etapa que a obra existe para demonstrar: é na emissão que o autômato deixa de ser estrutura interna
do reconhecedor e vira **o próprio código-alvo**, que é o que faz a teoria de autômatos aparecer
duas vezes no artefato.

## Conferência do recorte, item a item

A segunda metade da tarefa é confrontar as três decisões acima com as propriedades que o percurso
inteiro vai cobrar. Registramos a conferência aqui, e não na cabeça de quem decidiu, porque a
propriedade que falta só se manifesta no módulo que dependia dela — e aí o conserto alcança tudo o
que já foi construído em cima.

| Propriedade cobrada | Onde o recorte a satisfaz | Módulo que a cobra |
| --- | --- | --- |
| O usuário escreve padrões | `pattern nome = /regex/;` é declaração de primeira classe da linguagem | expressões regulares |
| Os símbolos da própria linguagem saem do mesmo motor | o reconhecedor da Peneira é construído sobre o mesmo módulo de AFD que compila os `pattern` | análise léxica |
| A gramática tem aninhamento arbitrariamente profundo | `expr` desce a `primary`, que volta a `"(" expr ")"` — recursão sem teto de profundidade | gramáticas livres de contexto |
| Há tipos e verificação antes da execução | `where` compara número com número e texto com texto; `on x` exige `x` declarado antes | análise semântica |
| Existe objeto produzido, consumido por outro componente | o vetor de AFDs mais o bytecode são gravados e lidos por uma máquina virtual que não é o compilador | geração de código e execução |
| O domínio pede algo que a máquina finita não atende | um `pattern` de parênteses balanceados é escrevível e nenhum AFD o reconhece | lema do bombeamento |

A última linha é a que costuma faltar num recorte feito às pressas, e é a mais consequente. Sem um
pedido do domínio que o autômato finito não atenda, a subida do reconhecimento regular para o
reconhecimento com pilha vira mudança de assunto em vez de resposta a um limite provado — e o
argumento de impossibilidade, quando chegar, será sobre um exemplo de fora, não sobre a linguagem
que se está construindo.

A segunda metade da tarefa é a conferência, e ela fecha o documento numa tabela de seis linhas. Cada linha nomeia uma propriedade que o percurso vai cobrar, o ponto do recorte que a satisfaz e o módulo em que a cobrança chega. A linha que costuma faltar é a última, e é a mais cara: sem um pedido do domínio que o autômato finito não atenda, a subida do reconhecimento regular para o reconhecimento com pilha vira mudança de assunto em vez de resposta a um limite provado. Na Peneira esse pedido é um padrão de parênteses balanceados — escrevível na linguagem, e impossível para qualquer autômato finito.

A gramática, que a tarefa ainda não pede por extenso, foi registrada em separado e na forma de partida, com recursão à esquerda e sem fatoração. Ela fica feia de propósito. O módulo de gramáticas livres de contexto retoma este arquivo e registra cada transformação com a forma anterior ao lado da final, e preservar o original é o que torna aquela comparação possível.

docs/01_gramatica.txt
A gramatica da Peneira, escrita por extenso no primeiro modulo.
Esta e a forma de partida: ainda tem recursao a esquerda e ainda nao esta fatorada.
O modulo de gramaticas livres de contexto retoma este arquivo e registra cada
transformacao com a forma anterior ao lado da forma final.

--- Gramatica hospedeira (a linguagem que o usuario escreve) ---

program     := decl* ;
decl        := patternDecl | ruleBlock ;
patternDecl := "pattern" ID "=" REGEX ";" ;
ruleBlock   := "rule" "{" action* "}" ;
action      := "on" ID "(" ID ")" ( "where" expr )? "=>" "emit" "(" STRING "," expr ")" ";" ;
expr        := andExpr ( "or" andExpr )* ;
andExpr     := cmpExpr ( "and" cmpExpr )* ;
cmpExpr     := primary ( ("<"|">"|"=="|"!="|">="|"<=") primary )? ;
primary     := ID | NUMBER | STRING | "value" "(" ID ")" | "(" expr ")" ;

--- Mini-linguagem regular (o alvo dos automatos) ---

regex  := alt ;
alt    := concat ( "|" concat )* ;
concat := repeat+ ;
repeat := atom ( "*" | "+" | "?" )? ;
atom   := CHAR | "." | "[" classe "]" | "(" alt ")" ;

--- Onde cada nivel da hierarquia de Chomsky comparece ---

A gramatica hospedeira e livre de contexto (tipo 2): as producoes aninhadas de
expr/andExpr/cmpExpr/primary exigem memoria de pilha, e nenhum automato finito as
reconhece. A mini-linguagem regular tambem e descrita por uma gramatica livre de
contexto — porque a NOTACAO de expressao regular tem parenteses aninhados —, mas a
LINGUAGEM que cada expressao denota e regular (tipo 3). Confundir as duas coisas e
o erro mais frequente deste ponto do percurso: o que e regular e o conjunto de
cadeias descrito pela expressao, nao o texto da expressao.

Onde é fácil errar. O erro mais comum é decidir largo com a intenção de restringir depois. O caminho barato é o inverso: comece pelo menor recorte que ainda seja interessante de processar e amplie quando a peça correspondente estiver funcionando. Um recorte generoso escrito agora não adianta trabalho nenhum — transfere para o meio do percurso a decisão de abandoná-lo, quando abandonar já custa código. Como verificar que está correta: leia as três decisões e pergunte, para cada uma, qual módulo futuro ela restringe. Se alguma não restringir nenhum, ela era descrição fantasiada de decisão.

1.3 Tarefa 2: Escrever à mão um exemplo válido

O que a tarefa pede

Escrever, sem apoio de nenhum programa, um exemplo de descrição válida no recorte que acabou de ser fixado, e registrar ao lado dele o que se espera que o sistema faça ao recebê-lo. Este par — entrada e resultado pretendido — é o primeiro caso de verificação do percurso: é ele que o analisador de símbolos precisará reconhecer por inteiro, que a gramática precisará derivar e que o sistema completo precisará processar do começo ao fim.

O exemplo declara dois padrões e uma regra sobre cada um. É curto, e cada elemento dele está ali por uma razão que se colhe adiante.

exemplos/exemplo01.pen
// exemplo01.pen — o primeiro programa valido da Peneira, escrito a mao.
//
// Este arquivo nao e lido por nenhum programa ainda: o reconhecedor de simbolos
// so existe a partir do capitulo de analise lexica. Ele e a especificacao pelo
// exemplo — o alvo contra o qual cada fase construida adiante sera verificada.
//
// Resultado esperado sobre a entrada de teste (exemplos/entrada01.txt):
//   contato  ana.silva@exemplo.com
//   grande   1500
// A linha "contato" sai porque o texto casa o pattern email; a linha "grande"
// sai porque casa numero E satisfaz a condicao value(n) > 100.
// Dois numeros da entrada casam o pattern e NAO produzem saida: 42 falha por
// magnitude e -240.75 falha por sinal — o sinal entra no casamento, entao o
// valor comparado e negativo. Sao esses dois casos negativos que provam que o
// where esta sendo avaliado, e nao apenas o casamento.

pattern email  = /[a-z0-9._]+@[a-z]+\.[a-z]+/;
pattern numero = /-?[0-9]+(\.[0-9]+)?/;

rule {
    on email(e)                        => emit("contato", e);
    on numero(n) where value(n) > 100  => emit("grande", n);
}

O padrão email exerce concatenação, classe de caracteres e fecho positivo. O padrão numero acrescenta o opcional no sinal, o agrupamento e o aninhamento de um opcional sobre um grupo — que é justamente o caso em que a redução ao núcleo mínimo deixa de ser óbvia, e por isso precisa estar no primeiro exemplo em vez de no décimo. A regra sobre email é incondicional; a regra sobre numero carrega um where, o que obriga a tabela de símbolos, a verificação de tipo e o bytecode a existirem. Com dois padrões e duas ações, o exemplo já toca todas as fases do sistema.

O resultado esperado é a outra metade da tarefa, e a metade que costuma ser esquecida. A entrada de teste foi escrita junto:

exemplos/entrada01.txt
Relatorio de contatos do trimestre.

Responsavel: ana.silva@exemplo.com
Meta do periodo: 1500 unidades
Ajuste aplicado: -240.75
Pendencias registradas: 42

Fim do relatorio.

Sobre ela o sistema deve emitir duas linhas: uma contato para o endereço e uma grande para o valor 1500. Os outros dois números da entrada casam o padrão numero e não produzem saída, e cada um falha por um motivo diferente, o que é o ponto. O valor 42 falha por magnitude, que é o caso negativo previsível. O valor -240.75 falha por sinal, porque o sinal entra no casamento e o número comparado é negativo; esse é o caso que ninguém escreve de propósito e que revela o defeito mais confuso da fase de execução. Um sistema que emitisse três linhas estaria casando os padrões corretamente e ignorando o where, e passaria em dois terços da bateria, proporção que num relatório de progresso passa por sucesso.

Onde é fácil errar. Escrever o exemplo pensando em como implementá-lo em vez de em como usá-lo. O exemplo pertence à linguagem, não ao compilador: ele descreve o que alguém que nunca viu o código escreveria. Como verificar que está correta: confira que o exemplo usa cada operador do núcleo mínimo ao menos uma vez, que a saída esperada foi escrita antes de existir qualquer código, e que há ao menos um caso que casa o padrão e não produz saída.

1.4 Tarefa 3: Criar o repositório de trabalho

O que a tarefa pede

Montar o repositório com as três partes que sustentam um sistema construído por acumulação — a apresentação, que diz o que o sistema faz e como se compila e executa; a documentação, que guarda a especificação da linguagem, o registro das decisões técnicas e o diário da construção; e o código, organizado por responsabilidade. Deixar funcionando desde já o comando único que reconstrói tudo e roda os casos existentes, ainda que haja pouquíssimo a compilar.

A organização adotada separa o que se lê do que se compila. A documentação guarda o recorte e a gramática, escritos na primeira tarefa; a pasta de exemplos guarda o par entrada e resultado da segunda; e os fontes ficam na raiz da variante, um par de arquivos por assunto — cabeçalho com a interface, implementação com o corpo. A separação é por responsabilidade e não por módulo do percurso, e é ela que vai permitir, adiante, trocar a representação da tabela de transição sem tocar no analisador.

Cada marco tem o seu arquivo de build, e ele lista apenas os fontes que existem até ali. Declara o padrão da linguagem uma vez, aplica as flags de rigor conforme o compilador disponível e produz um executável próprio.

marcos/01/CMakeLists.txt
# Modelo do arquivo de build de um marco da Peneira.
#
# ESCRITO UMA VEZ, para a linguagem. Quem o preenche por marco e
# tools/gerar_marcos.exe (specs/marcos-executaveis.md). Os arquivos gerados a
# partir dele — marcos/NN/CMakeLists.txt — NAO se editam a mao: a edicao some na
# proxima geracao, e a lista de fontes deixa de corresponder ao marco.
#
# CUIDADO AO EDITAR ESTE MODELO: a substituicao dos marcadores alcanca o arquivo
# INTEIRO, comentario incluido. Citar um marcador aqui em cima, para explicar o
# que ele faz, injeta a lista de fontes dentro do comentario e quebra o parser —
# aconteceu na primeira versao deste arquivo.
cmake_minimum_required(VERSION 3.10.0)
project(peneira01 VERSION 0.1.0 LANGUAGES CXX)

# O padrao e declarado uma vez, aqui, e nao repetido por compilador.
set(CMAKE_CXX_STANDARD 20)
set(CMAKE_CXX_STANDARD_REQUIRED ON)
set(CMAKE_CXX_EXTENSIONS OFF)

# Os fontes deste marco: os modulos 01 a 01, e mais nada. A lista e derivada,
# nunca escrita — e o que impede o capitulo 01 de exibir uma peca que so vai
# existir adiante.
add_executable(peneira01
    ../../01_linguagem.cpp
    ../../01_pipeline.cpp
    ../../demos/01_demo.cpp
)

# Aviso e erro. Incomoda no primeiro dia e economiza semanas depois — num programa
# que manipula indices de tabela o tempo inteiro, um aviso de conversao implicita
# ignorado e um defeito adiado, nao um defeito evitado.
if(MSVC)
    target_compile_options(peneira01 PRIVATE /W4 /WX /permissive- /utf-8 /EHsc)
else()
    target_compile_options(peneira01 PRIVATE -Wall -Wextra -Wpedantic -Werror)
endif()

include(CTest)
enable_testing()

# A demonstracao deste marco roda como teste, e o diretorio de trabalho e a raiz
# da variante: os arcos que leem descricoes de `exemplos/` dependem disso, e sem
# ele reprovariam por nao achar o arquivo — falha por motivo que nada tem a ver
# com o que a demonstracao mede.
add_test(NAME demo_01 COMMAND peneira01)
set_tests_properties(demo_01 PROPERTIES
    WORKING_DIRECTORY "${CMAKE_CURRENT_SOURCE_DIR}/../..")

Três escolhas dentro dele merecem justificativa. A primeira é CMAKE_CXX_EXTENSIONS OFF: sem isso o compilador aceita extensões próprias e o código deixa de ser portável sem que ninguém perceba, porque continua compilando na máquina de quem o escreveu. A segunda é o bloco condicional de avisos, com dois conjuntos de flags porque a toolchain não privilegia sistema operacional nenhum — código que passa limpo em apenas um dos três compiladores previstos não cumpre a exigência de tipagem forte desta obra, e descobrir isso na máquina de outra pessoa é a pior hora possível.

A terceira é a lista de fontes, que não é escrita à mão e sim derivada do conjunto de arquivos do marco. Uma lista mantida a dedo passa a divergir do que existe no disco, e a divergência não dá sintoma enquanto o projeto compilar. O registro da demonstração como teste é o que dá sentido ao comando único: quando uma peça nova entrar, adiante, o executável deste marco continua sendo construído e executado, e se ele parar de funcionar a bateria acusa na hora em que a regressão entrou, e não três módulos depois, quando a suspeita já se espalhou por trinta arquivos.

Onde é fácil errar. Adiar a configuração de build porque ainda não haveria o que compilar. Feita depois, sobre dez arquivos, ela custa várias vezes o que custaria agora sobre um — e o hábito de rodar a bateria a cada mudança não se instala retroativamente. Como verificar que está correta: apague o diretório de build, reconstrua do zero com um comando e confira que o teste passa. Se a reconstrução exigir qualquer passo manual, ela não está pronta.

1.5 Do símbolo à linguagem: as operações da definição

A teoria deste módulo começa por definições que parecem não pedir código — alfabeto, cadeia, linguagem como conjunto de cadeias, união, concatenação, potência e fecho. Implementá-las é o que separa saber a definição de saber o que ela implica, e o código abaixo existe para produzir uma constatação específica no fim.

A implementação percorre três degraus, na ordem em que um se apoia no anterior. O primeiro é a cadeia: comprimento, concatenação, reverso, potência e as duas perguntas de prefixo e sufixo. Nenhuma dessas operações devolve conjunto, e é por isso que elas vêm primeiro — separá-las das operações sobre linguagens impede a confusão mais frequente deste ponto, que é tratar a concatenação de duas cadeias e a de duas linguagens como a mesma coisa, quando a segunda produz o produto de dois conjuntos.

O segundo degrau é o universo em que a linguagem vive. A função que devolve todas as cadeias de um comprimento exato sobre um alfabeto é a que torna concreta a frase “uma linguagem é um subconjunto das cadeias possíveis”: com dois símbolos e comprimento 3 são oito cadeias, e a linguagem é alguma parte delas. Sem esse degrau impresso na tela, a palavra “subconjunto” fica sendo formalidade de enunciado. O terceiro degrau traz as operações sobre linguagens propriamente ditas, e é onde o conjunto explícito começa a cobrar.

01_linguagem.h
// 01_linguagem.h — Alfabeto, cadeia e linguagem como conjunto de cadeias.
//
// Este é o vocabulário formal sobre o qual todo o resto da Peneira é construído,
// e ele vem em três degraus: o símbolo, a cadeia e a linguagem. Representamos
// linguagem como conjunto porque é exatamente o que a definição diz: uma
// linguagem sobre um alfabeto é um subconjunto de todas as cadeias possíveis
// sobre ele. Trabalhar com o conjunto explícito só é viável para linguagens
// finitas — e é por isso que os capítulos seguintes trocam esta representação pelo
// autômato, que descreve conjuntos infinitos em espaço finito.

#ifndef PENEIRA_01_LINGUAGEM_H
#define PENEIRA_01_LINGUAGEM_H

#include <cstddef>
#include <set>
#include <string>

namespace peneira {

// recorte:inicio linguagem-como-conjunto
// Uma cadeia é uma sequência finita de símbolos. Usamos std::string porque o
// alfabeto da Peneira é de caracteres; a cadeia vazia é a string vazia.
using Cadeia = std::string;

// Conjunto ordenado para que a saída seja determinística — em demonstração, uma
// ordem que muda a cada execução tira do leitor a chance de comparar dois resultados.
using Alfabeto = std::set<char>;
using Linguagem = std::set<Cadeia>;
// recorte:fim linguagem-como-conjunto

// --- Degrau 1: operações sobre cadeias -------------------------------------
// Estas quatro são as operações da definição, e nenhuma delas devolve conjunto:
// cadeia entra, cadeia (ou resposta de sim/não) sai. Separá-las das operações
// sobre linguagens é o que impede a confusão mais comum deste ponto — tratar a
// concatenação de duas cadeias e a de duas linguagens como a mesma coisa, quando
// a primeira produz um resultado e a segunda produz o produto cartesiano dos dois
// conjuntos.

// O comprimento de uma cadeia é a quantidade de símbolos nela; o da cadeia vazia
// é zero, e ela é o elemento neutro da concatenação.
std::size_t comprimento(const Cadeia& cadeia);

// Concatenação de cadeias: os símbolos da primeira seguidos dos da segunda.
Cadeia concatenarCadeias(const Cadeia& esquerda, const Cadeia& direita);

// Reverso: os mesmos símbolos na ordem inversa. Aparece cedo porque é o
// contraexemplo mais barato contra a ideia de que operar sobre texto é sempre
// percorrer da esquerda para a direita.
Cadeia reverso(const Cadeia& cadeia);

// Potência de uma cadeia: ela repetida `expoente` vezes. A potência zero é a
// cadeia vazia — mesma convenção da potência de linguagem, e pela mesma razão.
Cadeia potenciaDaCadeia(const Cadeia& cadeia, std::size_t expoente);

bool ePrefixo(const Cadeia& candidata, const Cadeia& cadeia);
bool eSufixo(const Cadeia& candidata, const Cadeia& cadeia);

// --- Degrau 2: o universo em que a linguagem vive ---------------------------

// Todas as cadeias de comprimento exato sobre um alfabeto — o Σ^n da definição.
// É a operação que torna visível o que "linguagem é subconjunto" significa: o
// conjunto devolvido aqui tem |Σ|^n elementos, e a linguagem é alguma parte dele.
Linguagem cadeiasDeComprimento(const Alfabeto& alfabeto, std::size_t tamanho);

// --- Degrau 3: operações sobre linguagens -----------------------------------

// O alfabeto de uma linguagem é o conjunto dos símbolos que ocorrem nas suas cadeias.
Alfabeto alfabetoDe(const Linguagem& linguagem);

// União: pertence ao resultado a cadeia que pertence a pelo menos uma das duas.
Linguagem uniao(const Linguagem& esquerda, const Linguagem& direita);

// Concatenação: toda cadeia de `esquerda` seguida de toda cadeia de `direita`.
// O tamanho do resultado é o produto dos tamanhos, e essa multiplicação é a razão
// pela qual a representação por conjunto não escala.
Linguagem concatenacao(const Linguagem& esquerda, const Linguagem& direita);

// Potência: a linguagem concatenada com ela mesma `expoente` vezes.
// Por definição, a potência zero é a linguagem que contém apenas a cadeia vazia —
// e não a linguagem vazia. Confundir as duas é o erro mais comum deste capítulo.
Linguagem potencia(const Linguagem& linguagem, std::size_t expoente);

// Fecho de Kleene: a união de todas as potências, da zero em diante.
// O fecho é infinito sempre que a linguagem tem alguma cadeia não vazia, então
// aqui ele é truncado por comprimento máximo. O truncamento é da implementação,
// não da definição: é o preço de materializar o conjunto.
Linguagem fechoDeKleene(const Linguagem& linguagem, std::size_t comprimentoMaximo);

bool contem(const Linguagem& linguagem, const Cadeia& cadeia);

// Formatação em notação de conjunto, com a cadeia vazia grafada como ε.
Cadeia formatar(const Linguagem& linguagem);
Cadeia formatar(const Alfabeto& alfabeto);

}  // namespace peneira

#endif  // PENEIRA_01_LINGUAGEM_H
01_linguagem.cpp
#include "01_linguagem.h"

namespace peneira {

// recorte:inicio operacoes-sobre-cadeias
std::size_t comprimento(const Cadeia& cadeia) {
    return cadeia.size();
}

Cadeia concatenarCadeias(const Cadeia& esquerda, const Cadeia& direita) {
    return esquerda + direita;
}

Cadeia reverso(const Cadeia& cadeia) {
    return Cadeia(cadeia.rbegin(), cadeia.rend());
}

Cadeia potenciaDaCadeia(const Cadeia& cadeia, const std::size_t expoente) {
    // A potência zero é a cadeia vazia, e não uma cadeia de um símbolo qualquer:
    // repetir zero vezes é não repetir. Mesma convenção da potência de linguagem,
    // e é ela que faz a cadeia vazia ser o elemento neutro da concatenação.
    Cadeia resultado;
    for (std::size_t i = 0; i < expoente; ++i) {
        resultado += cadeia;
    }
    return resultado;
}
// recorte:fim operacoes-sobre-cadeias

bool ePrefixo(const Cadeia& candidata, const Cadeia& cadeia) {
    return candidata.size() <= cadeia.size() &&
           cadeia.compare(0, candidata.size(), candidata) == 0;
}

bool eSufixo(const Cadeia& candidata, const Cadeia& cadeia) {
    return candidata.size() <= cadeia.size() &&
           cadeia.compare(cadeia.size() - candidata.size(), candidata.size(), candidata) == 0;
}

// recorte:inicio universo-das-cadeias
Linguagem cadeiasDeComprimento(const Alfabeto& alfabeto, const std::size_t tamanho) {
    // Começa do conjunto que contém só a cadeia vazia e estende um símbolo por
    // vez. O resultado tem |alfabeto| elevado a `tamanho` elementos — a contagem
    // que torna concreta a frase "uma linguagem é um subconjunto de Σ*": este é
    // um andar do universo, e a linguagem é alguma parte dele.
    Linguagem resultado{Cadeia{}};
    for (std::size_t i = 0; i < tamanho; ++i) {
        Linguagem proximoAndar;
        for (const Cadeia& prefixo : resultado) {
            for (const char simbolo : alfabeto) {
                proximoAndar.insert(prefixo + simbolo);
            }
        }
        resultado = proximoAndar;
    }
    return resultado;
}
// recorte:fim universo-das-cadeias

// recorte:inicio alfabeto-de-uma-linguagem
Alfabeto alfabetoDe(const Linguagem& linguagem) {
    Alfabeto alfabeto;
    for (const Cadeia& cadeia : linguagem) {
        for (const char simbolo : cadeia) {
            alfabeto.insert(simbolo);
        }
    }
    return alfabeto;
}
// recorte:fim alfabeto-de-uma-linguagem

// recorte:inicio uniao-e-concatenacao
Linguagem uniao(const Linguagem& esquerda, const Linguagem& direita) {
    Linguagem resultado = esquerda;
    resultado.insert(direita.begin(), direita.end());
    return resultado;
}

Linguagem concatenacao(const Linguagem& esquerda, const Linguagem& direita) {
    Linguagem resultado;
    for (const Cadeia& prefixo : esquerda) {
        for (const Cadeia& sufixo : direita) {
            resultado.insert(prefixo + sufixo);
        }
    }
    return resultado;
}
// recorte:fim uniao-e-concatenacao

// recorte:inicio potencia-zero-e-cadeia-vazia
Linguagem potencia(const Linguagem& linguagem, const std::size_t expoente) {
    // A potência zero contém a cadeia vazia. Devolver a linguagem vazia aqui
    // quebraria o fecho de Kleene inteiro, porque a concatenação com o conjunto
    // vazio aniquila o resultado em vez de preservá-lo.
    Linguagem resultado{Cadeia{}};
    for (std::size_t i = 0; i < expoente; ++i) {
        resultado = concatenacao(resultado, linguagem);
    }
    return resultado;
}
// recorte:fim potencia-zero-e-cadeia-vazia

// recorte:inicio fecho-que-precisa-parar
Linguagem fechoDeKleene(const Linguagem& linguagem, const std::size_t comprimentoMaximo) {
    Linguagem resultado{Cadeia{}};
    Linguagem nivelAtual{Cadeia{}};

    // Cresce por níveis em vez de calcular potência por potência: cada nível é o
    // anterior concatenado uma vez com a linguagem, e paramos quando nenhuma
    // cadeia nova cabe no comprimento máximo. Sem essa parada por comprimento o
    // laço não termina, porque o fecho é infinito por definição.
    while (!nivelAtual.empty()) {
        Linguagem proximoNivel;
        for (const Cadeia& cadeia : concatenacao(nivelAtual, linguagem)) {
            if (cadeia.size() <= comprimentoMaximo) {
                proximoNivel.insert(cadeia);
            }
        }
        // A cadeia vazia reaparece a cada nível se a linguagem a contiver; o
        // conjunto absorve a repetição, mas o nível precisa perder as já vistas,
        // senão o laço nunca esvazia.
        Linguagem novidades;
        for (const Cadeia& cadeia : proximoNivel) {
            if (resultado.find(cadeia) == resultado.end()) {
                novidades.insert(cadeia);
            }
        }
        resultado.insert(novidades.begin(), novidades.end());
        nivelAtual = novidades;
    }
    return resultado;
}
// recorte:fim fecho-que-precisa-parar

bool contem(const Linguagem& linguagem, const Cadeia& cadeia) {
    return linguagem.find(cadeia) != linguagem.end();
}

// recorte:inicio cadeia-vazia-impressa
Cadeia formatar(const Linguagem& linguagem) {
    Cadeia texto = "{ ";
    bool primeiro = true;
    for (const Cadeia& cadeia : linguagem) {
        if (!primeiro) {
            texto += ", ";
        }
        // A cadeia vazia é invisível quando impressa como está, e o leitor
        // conclui que o conjunto tem um elemento a menos do que tem.
        texto += cadeia.empty() ? Cadeia{"\xce\xb5"} : cadeia;
        primeiro = false;
    }
    texto += " }";
    return texto;
}
// recorte:fim cadeia-vazia-impressa

Cadeia formatar(const Alfabeto& alfabeto) {
    Cadeia texto = "{ ";
    bool primeiro = true;
    for (const char simbolo : alfabeto) {
        if (!primeiro) {
            texto += ", ";
        }
        texto += simbolo;
        primeiro = false;
    }
    texto += " }";
    return texto;
}

}  // namespace peneira

Representamos linguagem como std::set<std::string> porque é literalmente o que a definição diz. Escolhemos o conjunto ordenado, e não a tabela de dispersão, por uma razão de demonstração: ordem que muda a cada execução tira de quem lê a chance de comparar dois resultados lado a lado, e comparar lado a lado é a única verificação disponível antes de existir bateria de testes.

Duas passagens merecem atenção redobrada. A primeira é a potência zero, que devolve o conjunto contendo a cadeia vazia e não o conjunto vazio. A distinção soa pedante e derruba o fecho inteiro quando trocada: a concatenação com o conjunto vazio aniquila o resultado, ao passo que a concatenação com o conjunto que contém a cadeia vazia o preserva. É o erro mais frequente de quem implementa esta parte pela primeira vez, e ele se manifesta como um fecho de Kleene que devolve conjunto vazio para toda entrada — sintoma barato de observar e caro de diagnosticar, porque o defeito está três funções abaixo de onde ele aparece.

A segunda é o fecho de Kleene, que cresce por níveis e para quando nenhuma cadeia nova cabe no comprimento máximo. O parâmetro de comprimento não faz parte da definição, e é bom que ele incomode: o fecho é infinito sempre que a linguagem tem alguma cadeia não vazia. O parâmetro é o preço de materializar o conjunto, e é exatamente esse preço que o módulo seguinte elimina ao trocar o conjunto explícito pelo autômato, que descreve um conjunto infinito em espaço finito.

A demonstração imprime as operações sobre cadeias e depois as operações sobre duas linguagens curtas, conferíveis à mão. A última linha da saída é a que interessa: a cadeia abab é reportada como ausente do fecho truncado, e a mensagem diz explicitamente que ela está fora do recorte, não da linguagem. Sem essa distinção impressa, quem lê conclui que o fecho não contém abab, que é o oposto do verdadeiro. A constatação que fecha o bloco é esta — o conjunto explícito funciona, é curto de escrever e para de servir na primeira linguagem interessante. O limite se esbarra executando o próprio código. É isso que torna o autômato do módulo seguinte uma resposta a um problema vivido, e não uma técnica apresentada sem motivo.

Onde é fácil errar. Confundir a linguagem vazia com a linguagem que contém a cadeia vazia, em qualquer ponto do código. Como verificar que está correta: o fecho de uma linguagem com duas cadeias de um símbolo, truncado em comprimento 3, tem 15 elementos — uma cadeia vazia, duas de comprimento 1, quatro de comprimento 2 e oito de comprimento 3. Se a contagem der outro número, o erro está na potência zero ou na condição de parada, e em nenhum outro lugar.

1.6 A anatomia do sistema e a hierarquia de Chomsky

O segundo bloco teórico é a arquitetura: quais são as fases, o que cada uma consome e produz, e onde passa a fronteira entre a metade que analisa e a que sintetiza. Nenhuma fase existe ainda, e é por isso mesmo que a declaramos como dado em vez de descrevê-la em comentário.

01_pipeline.h
// 01_pipeline.h — A anatomia do sistema: as fases, o que cada uma consome e produz.
//
// Nenhuma fase existe ainda como código; o que existe aqui é a declaração da
// cadeia inteira, como dado. Declará-la agora tem uma função concreta: cada
// capítulo seguinte substitui uma linha desta tabela por implementação real, e a
// tabela continua sendo a resposta às três perguntas que valem para qualquer
// etapa — o que entra, o que sai, e por que esta vem depois daquela.

#ifndef PENEIRA_01_PIPELINE_H
#define PENEIRA_01_PIPELINE_H

#include <string>
#include <vector>

namespace peneira {

// A divisão clássica: a metade que decompõe o texto de entrada e a metade que
// constrói o resultado. O artefato de fronteira entre as duas é a árvore
// verificada — é ela que a análise entrega e a síntese consome.
enum class Metade { Analise, Sintese };

struct Fase {
    std::string nome;
    std::string consome;
    std::string produz;
    Metade metade;
};

// A cadeia da Peneira, na ordem em que será construída ao longo do percurso.
std::vector<Fase> pipelineDaPeneira();

// Um nível da hierarquia de Chomsky e a máquina que lhe corresponde, com o ponto
// do artefato em que aquele nível comparece. As duas primeiras linhas são as que
// a Peneira realiza; as duas últimas existem para situar o que fica de fora.
struct NivelDeChomsky {
    int tipo;
    std::string gramatica;
    std::string maquina;
    std::string ondeApareceNaPeneira;
};

std::vector<NivelDeChomsky> hierarquiaDeChomsky();

// Uma forma intermediária é um artefato que nenhuma das duas pontas pede: não é o
// texto que o usuário escreveu nem o resultado que ele espera. Existe porque
// separa duas fases que, coladas, ficariam presas uma à outra. Declará-las aqui
// evita a leitura ingênua da cadeia como "texto entra, resultado sai".
struct FormaIntermediaria {
    std::string nome;
    std::string faseQueProduz;
    std::string faseQueConsome;
    std::string porQueNaoSeElimina;
};

std::vector<FormaIntermediaria> formasIntermediariasDaPeneira();

// Onde cada estratégia coloca a fronteira entre traduzir e executar. A distinção
// não é entre linguagens, e sim entre implementações: a mesma linguagem admite as
// três. A Peneira é híbrida, e a linha marcada é a dela.
struct EstrategiaDeExecucao {
    std::string nome;
    std::string quandoATraducaoAcontece;
    std::string oQueDeFatoExecuta;
    std::string exemploConhecido;
    bool eAEstrategiaDaPeneira;
};

std::vector<EstrategiaDeExecucao> estrategiasDeExecucao();

std::string formatarPipeline(const std::vector<Fase>& fases);
std::string formatarHierarquia(const std::vector<NivelDeChomsky>& niveis);
std::string formatarFormasIntermediarias(const std::vector<FormaIntermediaria>& formas);
std::string formatarEstrategias(const std::vector<EstrategiaDeExecucao>& estrategias);

}  // namespace peneira

#endif  // PENEIRA_01_PIPELINE_H
01_pipeline.cpp
#include "01_pipeline.h"

#include <cstddef>

namespace peneira {

// recorte:inicio pipeline-do-tradutor
std::vector<Fase> pipelineDaPeneira() {
    return {
        {"analise lexica", "texto do programa .pen", "sequencia de simbolos com posicao",
         Metade::Analise},
        {"analise sintatica", "sequencia de simbolos", "arvore da estrutura do programa",
         Metade::Analise},
        {"analise semantica", "arvore da estrutura", "arvore verificada e tabela de simbolos",
         Metade::Analise},
        {"geracao de codigo", "arvore verificada", "objeto: vetor de AFDs + bytecode das regras",
         Metade::Sintese},
        {"execucao na maquina virtual", "objeto + texto de entrada", "saida do emit",
         Metade::Sintese},
    };
}
// recorte:fim pipeline-do-tradutor

// recorte:inicio hierarquia-de-chomsky
std::vector<NivelDeChomsky> hierarquiaDeChomsky() {
    return {
        {3, "regular", "automato finito",
         "os patterns do usuario e os simbolos da propria linguagem"},
        {2, "livre de contexto", "automato de pilha",
         "a gramatica da Peneira e o analisador descendente"},
        {1, "sensivel ao contexto", "automato linearmente limitado",
         "fora do artefato: nenhuma fase precisa deste poder"},
        {0, "irrestrita", "maquina de Turing",
         "fora do artefato: e o poder do compilador, nao o da linguagem compilada"},
    };
}
// recorte:fim hierarquia-de-chomsky

// recorte:inicio formas-intermediarias
std::vector<FormaIntermediaria> formasIntermediariasDaPeneira() {
    return {
        {"sequencia de simbolos", "analise lexica", "analise sintatica",
         "sem ela o parser voltaria a olhar caractere, e espaco e comentario reapareceriam"},
        {"arvore da estrutura", "analise sintatica", "analise semantica",
         "sem ela o verificador teria de redescobrir a estrutura a cada checagem"},
        {"tabela de simbolos", "analise semantica", "geracao de codigo",
         "guarda o que o nome significa longe do ponto do texto em que ele aparece"},
        {"arvore verificada", "analise semantica", "geracao de codigo",
         "e o artefato de fronteira: a analise entrega, a sintese consome"},
        {"objeto: AFDs + bytecode", "geracao de codigo", "maquina virtual",
         "separa compilar de executar: compila-se uma vez, executa-se sobre muitas entradas"},
    };
}
// recorte:fim formas-intermediarias

// recorte:inicio estrategias-de-execucao
std::vector<EstrategiaDeExecucao> estrategiasDeExecucao() {
    return {
        {"compilacao", "antes da execucao, uma vez", "o codigo de maquina gerado",
         "C traduzido para codigo nativo", false},
        {"interpretacao", "nao ha traducao: a estrutura e percorrida a cada execucao",
         "o interpretador, sobre a arvore ou o texto", "shell POSIX, comando a comando", false},
        {"hibrida", "antes da execucao, para uma representacao intermediaria",
         "uma maquina virtual, sobre o bytecode", "Java compilado para bytecode da JVM", true},
    };
}
// recorte:fim estrategias-de-execucao

namespace {

// Alinha a coluna para que a tabela impressa fique legível na projeção. Sem isso
// o leitor precisa contar vírgulas para saber qual campo é qual.
std::string preencher(const std::string& texto, const std::size_t largura) {
    std::string resultado = texto;
    while (resultado.size() < largura) {
        resultado += ' ';
    }
    return resultado;
}

std::string nomeDaMetade(const Metade metade) {
    return metade == Metade::Analise ? "analise" : "sintese";
}

}  // namespace

std::string formatarPipeline(const std::vector<Fase>& fases) {
    std::string texto;
    texto += preencher("FASE", 30) + preencher("CONSOME", 28) + preencher("PRODUZ", 44) + "METADE\n";
    for (const Fase& fase : fases) {
        texto += preencher(fase.nome, 30);
        texto += preencher(fase.consome, 28);
        texto += preencher(fase.produz, 44);
        texto += nomeDaMetade(fase.metade);
        texto += '\n';
    }
    return texto;
}

std::string formatarHierarquia(const std::vector<NivelDeChomsky>& niveis) {
    std::string texto;
    texto += preencher("TIPO", 6) + preencher("GRAMATICA", 22) + preencher("MAQUINA", 32) +
             "ONDE APARECE\n";
    for (const NivelDeChomsky& nivel : niveis) {
        texto += preencher(std::to_string(nivel.tipo), 6);
        texto += preencher(nivel.gramatica, 22);
        texto += preencher(nivel.maquina, 32);
        texto += nivel.ondeApareceNaPeneira;
        texto += '\n';
    }
    return texto;
}

std::string formatarFormasIntermediarias(const std::vector<FormaIntermediaria>& formas) {
    std::string texto;
    texto += preencher("FORMA", 26) + preencher("PRODUZIDA POR", 22) + preencher("CONSUMIDA POR", 24) +
             "POR QUE NAO SE ELIMINA\n";
    for (const FormaIntermediaria& forma : formas) {
        texto += preencher(forma.nome, 26);
        texto += preencher(forma.faseQueProduz, 22);
        texto += preencher(forma.faseQueConsome, 24);
        texto += forma.porQueNaoSeElimina;
        texto += '\n';
    }
    return texto;
}

std::string formatarEstrategias(const std::vector<EstrategiaDeExecucao>& estrategias) {
    std::string texto;
    texto += preencher("ESTRATEGIA", 16) + preencher("QUANDO TRADUZ", 60) +
             preencher("QUEM EXECUTA", 44) + "EXEMPLO\n";
    for (const EstrategiaDeExecucao& estrategia : estrategias) {
        // A marca na coluna do nome poupa uma legenda: quem le a tabela ve, sem
        // procurar no texto, qual das tres linhas descreve o artefato desta obra.
        texto += preencher(estrategia.eAEstrategiaDaPeneira ? "> " + estrategia.nome : "  " + estrategia.nome, 16);
        texto += preencher(estrategia.quandoATraducaoAcontece, 60);
        texto += preencher(estrategia.oQueDeFatoExecuta, 44);
        texto += estrategia.exemploConhecido;
        texto += '\n';
    }
    return texto;
}

}  // namespace peneira

A decisão de projeto aqui é modesta e rende ao longo de todo o percurso: a cadeia de fases é uma estrutura que o programa imprime, e cada módulo seguinte substitui uma linha dela por implementação real. Quem executar a demonstração no primeiro módulo e de novo no último vê a mesma tabela, no mesmo formato, descrevendo um sistema que passou a existir. A tabela responde, para qualquer fase, as três perguntas que valem sempre — o que entra, o que sai, e por que esta vem depois daquela.

A hierarquia de Chomsky entra na mesma forma, com quatro níveis e a indicação de onde cada um comparece na Peneira. As duas primeiras linhas são as que o artefato realiza: os padrões do usuário e os símbolos da própria linguagem são regulares, reconhecidos por autômato finito; a gramática da linguagem é livre de contexto, reconhecida por autômato de pilha. O critério que separa um degrau do seguinte é quanta memória a máquina precisa ter — quem só sabe em que estado está não sabe quantas vezes já entrou nele —, e é essa frase que explica por que os parênteses balanceados caem fora do degrau regular. As duas últimas linhas existem para situar o que fica de fora, e a quarta traz a distinção que mais confunde neste ponto: a máquina de Turing é o poder do compilador, não o da linguagem compilada.

As duas últimas tabelas respondem a perguntas que a cadeia de fases levanta e não resolve. A primeira lista as formas intermediárias, artefatos que nenhuma das duas pontas pede — não são o texto que o usuário escreveu nem o resultado que ele espera — e que existem porque separam duas fases que, coladas, ficariam presas uma à outra. Cada uma é declarada com a razão pela qual não se elimina. É isso que impede a leitura ingênua da arquitetura como “texto entra, resultado sai”: a sequência de símbolos existe para que o analisador sintático nunca volte a olhar caractere; a tabela de símbolos existe porque o significado de um nome precisa sobreviver longe do ponto do texto em que ele aparece; e o objeto emitido existe porque compilar uma vez e executar muitas é o que distingue este sistema de um que reinterpretasse a descrição a cada entrada.

A segunda tabela situa a interpretação, e é a que mais desfaz confusão neste ponto do percurso. A distinção entre compilar e interpretar separa implementações, e não linguagens: a mesma linguagem admite as três estratégias. O que a tabela fixa é onde cada uma coloca a fronteira entre traduzir e executar, e qual das três é a nossa. A Peneira traduz antes da execução, mas não para código de máquina — para uma representação intermediária que uma máquina virtual executa. A linha marcada é a híbrida, e saber isso agora evita a pergunta recorrente sobre por que existe uma máquina virtual num percurso que se anuncia como de compiladores.

Repare que o campo de fronteira entre as metades é a árvore verificada. Nomeá-lo explicitamente resolve, já no primeiro módulo, uma pergunta que costuma ficar vaga até o fim: a análise entrega a árvore, a síntese a consome, e nada atravessa essa fronteira em outro formato. A tabela também deixa anunciado o que a última fase vai enfrentar, porque nenhuma máquina de destino oferece exatamente as operações que a linguagem oferece — o que a máquina não faz, o tradutor faz por ela, e cobra em instruções. O valor dessa conta é medido no fim do percurso; por ora ela é uma promessa registrada na arquitetura.

Onde é fácil errar. Escrever a anatomia como comentário no cabeçalho de um arquivo. Comentário não é executável, não é verificável e envelhece em silêncio; a tabela como dado é impressa, comparada e corrigida junto com o código. Como verificar que está correta: confira que toda fase declarada consome exatamente o que a anterior produz. Se houver um salto — uma fase que consome algo que ninguém produziu —, falta uma linha na tabela, e essa lacuna vira uma peça esquecida quatro módulos adiante.

1.7 Por dentro da implementação

As seções anteriores dizem o que o código faz e por que ele foi escrito assim. Falta o percurso: qual função chama qual, em que ordem, e em que ponto exato a execução decide. Como este é o primeiro módulo, não há estado anterior sobre o qual costurar — tudo aqui passou a existir agora, e o marco 01 é a primeira execução do sistema. Ele acrescentou cinco coisas que mudam percurso:

  1. operacoes-sobre-cadeias — as quatro operações da definição sobre uma cadeia só, mais as duas perguntas de posição.
  2. universo-das-cadeias — a construção de todas as cadeias de um comprimento exato sobre um alfabeto.
  3. operacoes-sobre-linguagens — alfabeto, união, concatenação e potência, agora sobre conjuntos.
  4. fecho-que-precisa-parar — o fecho de Kleene, com a condição de parada que a definição não tem.
  5. anatomia-como-dado — as quatro tabelas da arquitetura e o formatador que as imprime alinhadas.

Cada uma tem abaixo o seu cenário, tirado da execução do marco 01, com o fluxo do controle e a conversa entre os arquivos.

1. As operações sobre cadeias. O cenário é o das primeiras linhas da saída — w = aab e v = ba. A execução chama comprimento(), que devolve 3; concatenarCadeias(), que devolve aabba; reverso(), que devolve baa; e potenciaDaCadeia() duas vezes, com expoente 0 e com expoente 3, produzindo a cadeia vazia e aabaabaab. Fecham o bloco ePrefixo("aa", w), que responde sim, e eSufixo("aa", w), que responde nao.

%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    E["demos/01_demo.cpp<br/>w = aab, v = ba"]
    C1["comprimento()"]
    C2["concatenarCadeias()"]
    C3["reverso()"]
    C4["potenciaDaCadeia()"]
    D{"i &lt; expoente"}
    P["ePrefixo()"]
    S["eSufixo()"]

    E --> C1
    C1 -->|"3"| C2
    C2 -->|"aabba"| C3
    C3 -->|"baa"| C4
    C4 --> D
    D -->|"verdadeiro: resultado += cadeia"| C4
    D -->|"falso: devolve aabaabaab"| P
    P -->|"sim"| S
    S -->|"nao"| F["fim da primeira demonstracao"]


%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
sequenceDiagram
    participant Demo as demos/01_demo.cpp
    participant Ling as 01_linguagem.cpp

    Demo->>Ling: comprimento(w = aab)
    Ling-->>Demo: 3
    Demo->>Ling: concatenarCadeias(w, v)
    Ling-->>Demo: aabba
    Demo->>Ling: reverso(w)
    Ling-->>Demo: baa
    Demo->>Ling: potenciaDaCadeia(w, expoente = 0)
    Ling-->>Demo: cadeia vazia
    Demo->>Ling: potenciaDaCadeia(w, expoente = 3)
    Ling-->>Demo: aabaabaab
    Demo->>Ling: ePrefixo(aa, w)
    Ling-->>Demo: true
    Demo->>Ling: eSufixo(aa, w)
    Ling-->>Demo: false

Só uma das seis decide alguma coisa: potenciaDaCadeia() é a única com laço, e o teste i < expoente é o que faz a potência zero devolver a cadeia vazia sem nenhum caso especial escrito. As outras cinco são expressões de uma linha, e é isso que as tira do desenho — o percurso delas não tem bifurcação a mostrar. Poderíamos ter escrito o acúmulo como resultado = concatenarCadeias(resultado, cadeia), reusando a operação que já existe uma linha acima; o custo é uma cópia da cadeia inteira por volta do laço, contra o acréscimo em lugar do +=, e a economia de uma função reusada não paga uma cópia quadrática no comprimento do resultado.

2. O universo das cadeias. O cenário é cadeiasDeComprimento(sigma, 3) com sigma = { a, b }, cuja saída é { aaa, aab, aba, abb, baa, bab, bba, bbb }, seguida da contagem 8 cadeias.

%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    E["demos/01_demo.cpp<br/>sigma = a, b · tamanho = 3"]
    C["cadeiasDeComprimento()"]
    D1{"i &lt; tamanho"}
    D2{"proximo prefixo em resultado"}
    D3{"proximo simbolo em alfabeto"}
    F["formatar()"]

    E --> C
    C -->|"resultado comeca com a cadeia vazia"| D1
    D1 -->|"verdadeiro"| D2
    D2 -->|"ha prefixo"| D3
    D3 -->|"ha simbolo: proximoAndar.insert(prefixo + simbolo)"| D3
    D3 -->|"acabou o alfabeto"| D2
    D2 -->|"acabaram os prefixos: resultado = proximoAndar"| D1
    D1 -->|"falso: devolve 8 cadeias"| F
    F -->|"conjunto impresso em notacao de chaves"| S["saida do marco 01"]


%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
sequenceDiagram
    participant Demo as demos/01_demo.cpp
    participant Ling as 01_linguagem.cpp

    Demo->>Ling: cadeiasDeComprimento(sigma = a b, tamanho = 3)
    Ling-->>Demo: conjunto de 8 cadeias
    Demo->>Ling: formatar(sigma)
    Ling-->>Demo: chaves a, b
    Demo->>Ling: formatar(andar)
    Ling-->>Demo: chaves aaa, aab, aba, abb, baa, bab, bba, bbb

São três laços aninhados, e a ordem em que estão importa: o de fora conta os andares, o do meio percorre o que já se tem e o de dentro estende com um símbolo. cadeiasDeComprimento() começa do conjunto que contém a cadeia vazia — a mesma semente da potência —, e é por isso que ela devolve o conjunto com um elemento quando o tamanho pedido é zero, em vez de devolver conjunto vazio. A alternativa era enumerar os índices de 0 a |Σ|^n - 1 e converter cada índice para a base do tamanho do alfabeto: a mesma quantidade de trabalho, sem os conjuntos intermediários. O custo é de leitura, e é o que decidiu. A versão por andares mostra na tela o que a expressão “um andar do universo” significa; a versão por conversão de base esconde a construção dentro de uma aritmética que nada tem a ver com linguagens formais.

3. As operações sobre linguagens. O cenário são as linguagens A = { a, b } e B = { 0, 1 } da segunda demonstração. alfabetoDe(A) devolve { a, b }, uniao(A, B) devolve { 0, 1, a, b }, concatenacao(A, B) devolve { a0, a1, b0, b1 }, e potencia() é chamada com expoente 0, que produz { ε }, e com expoente 2, que produz { aa, ab, ba, bb }.

%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    E["demos/01_demo.cpp<br/>A = a, b · B = 0, 1"]
    AL["alfabetoDe()"]
    U["uniao()"]
    C["concatenacao()"]
    P["potencia()"]
    D{"i &lt; expoente"}
    F["formatar()"]

    E --> AL
    AL -->|"a, b"| U
    U -->|"0, 1, a, b"| C
    C -->|"a0, a1, b0, b1"| P
    P -->|"resultado comeca com a cadeia vazia"| D
    D -->|"verdadeiro: resultado = concatenacao(resultado, linguagem)"| C
    C -->|"volta ao laco da potencia"| D
    D -->|"falso, expoente 0: cadeia vazia"| F
    D -->|"falso, expoente 2: aa, ab, ba, bb"| F
    F -->|"cadeia vazia impressa como epsilon"| S["saida do marco 01"]


%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
sequenceDiagram
    participant Demo as demos/01_demo.cpp
    participant Ling as 01_linguagem.cpp

    Demo->>Ling: alfabetoDe(A = a b)
    Ling-->>Demo: alfabeto a, b
    Demo->>Ling: uniao(A, B)
    Ling-->>Demo: 0, 1, a, b
    Demo->>Ling: concatenacao(A, B)
    Ling-->>Demo: a0, a1, b0, b1
    Demo->>Ling: potencia(A, expoente = 0)
    Ling-->>Demo: so a cadeia vazia
    Demo->>Ling: potencia(A, expoente = 2)
    Ling->>Ling: concatenacao(resultado, A) — primeira volta
    Ling-->>Ling: a, b
    Ling->>Ling: concatenacao(resultado, A) — segunda volta
    Ling-->>Ling: aa, ab, ba, bb
    Ling-->>Demo: aa, ab, ba, bb
    Demo->>Ling: formatar(potencia zero)
    Ling-->>Demo: chaves epsilon

A única chamada entre funções deste degrau é a de potencia() para concatenacao(), uma vez por volta do laço — o diagrama de sequência mostra as duas voltas do expoente 2, com o resultado intermediário de cada uma. formatar() é sobrecarregada, e as duas versões existem porque Alfabeto e Linguagem são conjuntos de coisas diferentes; só a de Linguagem precisa trocar a cadeia vazia por ε, porque um alfabeto não tem elemento invisível. Uma alternativa razoável era escrever potencia() por recursão — concatenacao(linguagem, potencia(linguagem, expoente - 1)), com a potência zero como caso base. O número de concatenações seria o mesmo, e o preço é ter um caso base que só se lê saindo do fundo da recursão, quando a decisão que este bloco quer manter à vista é justamente a semente do resultado, escrita na primeira linha da função.

4. O fecho que precisa parar. O cenário é fechoDeKleene(A, 3), que devolve as 15 cadeias impressas na linha A* ate 3, seguido de contem(fecho, "aba"), que responde sim, e de contem(fecho, "abab"), que responde nao (fora do recorte, nao da linguagem).

%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    E["demos/01_demo.cpp<br/>A = a, b · comprimentoMaximo = 3"]
    FK["fechoDeKleene()"]
    D1{"!nivelAtual.empty()"}
    CC["concatenacao()"]
    D2{"cadeia.size() &lt;= comprimentoMaximo"}
    D3{"resultado.find(cadeia) == resultado.end()"}
    CT["contem()"]
    F["formatar()"]

    E --> FK
    FK -->|"resultado e nivelAtual comecam com a cadeia vazia"| D1
    D1 -->|"verdadeiro"| CC
    CC -->|"cadeias do proximo nivel"| D2
    D2 -->|"cabe: proximoNivel.insert(cadeia)"| D3
    D2 -->|"nao cabe: descartada"| D3
    D3 -->|"nova: entra em novidades"| D1
    D3 -->|"ja vista: fica de fora, senao o laco nunca esvazia"| D1
    D1 -->|"falso: nivelAtual vazio, devolve 15 cadeias"| CT
    CT -->|"aba: sim · abab: nao"| F
    F --> S["saida do marco 01"]


%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
sequenceDiagram
    participant Demo as demos/01_demo.cpp
    participant Ling as 01_linguagem.cpp

    Demo->>Ling: fechoDeKleene(A = a b, comprimentoMaximo = 3)
    Ling->>Ling: concatenacao(nivelAtual, A) — nivel 1
    Ling-->>Ling: a, b
    Ling->>Ling: concatenacao(nivelAtual, A) — nivel 2
    Ling-->>Ling: aa, ab, ba, bb
    Ling->>Ling: concatenacao(nivelAtual, A) — nivel 3
    Ling-->>Ling: aaa ate bbb, oito cadeias
    Ling->>Ling: concatenacao(nivelAtual, A) — nivel 4
    Ling-->>Ling: dezesseis cadeias, todas acima do comprimento maximo
    Ling-->>Demo: 15 cadeias
    Demo->>Ling: formatar(fecho)
    Ling-->>Demo: chaves epsilon, a, aa, aaa ate bbb
    Demo->>Ling: contem(fecho, aba)
    Ling-->>Demo: true
    Demo->>Ling: contem(fecho, abab)
    Ling-->>Demo: false

O que o fluxo torna visível são os dois filtros dentro do laço, que a leitura corrida do código funde num só. O primeiro, cadeia.size() <= comprimentoMaximo, é o que impede o nível de crescer além do recorte. O segundo, resultado.find(cadeia) == resultado.end(), é o que faz o laço terminar: sem ele, uma linguagem que contenha a cadeia vazia devolveria para sempre o mesmo nível, o conjunto acumulado pararia de mudar e a condição !nivelAtual.empty() nunca seria falsa. A sequência mostra as quatro chamadas a concatenacao() do cenário — três produzem cadeias que cabem, a quarta produz dezesseis cadeias de comprimento 4, todas descartadas, e é ela que esvazia o nível. A alternativa era somar as potências, chamando potencia() de 0 até um expoente máximo: além de recalcular do zero cada potência, ela obrigaria a demonstração a escolher um teto de expoente, e o que o argumento do módulo precisa é de um teto de comprimento. Com um alfabeto de símbolos de tamanho 1 os dois coincidem; na primeira linguagem com cadeias de tamanhos diferentes, deixam de coincidir.

5. A anatomia como dado. O cenário é a terceira demonstração do marco, que imprime quatro tabelas: 5 fases, 4 níveis de Chomsky, 5 formas intermediárias e 3 estratégias de execução, esta última com o sinal > na linha hibrida.

%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
    E["demos/01_demo.cpp<br/>terceira demonstracao do marco 01"]
    P1["pipelineDaPeneira()"]
    P2["hierarquiaDeChomsky()"]
    P3["formasIntermediariasDaPeneira()"]
    P4["estrategiasDeExecucao()"]
    F1["formatarPipeline()"]
    F2["formatarHierarquia()"]
    F3["formatarFormasIntermediarias()"]
    F4["formatarEstrategias()"]
    NM["nomeDaMetade()"]
    PR["preencher()"]
    D{"resultado.size() &lt; largura"}
    S["saida do marco 01: quatro tabelas"]

    E --> P1
    E --> P2
    E --> P3
    E --> P4
    P1 -->|"5 fases"| F1
    P2 -->|"4 niveis"| F2
    P3 -->|"5 formas"| F3
    P4 -->|"3 estrategias"| F4
    F1 --> NM
    NM -->|"analise ou sintese"| PR
    F1 --> PR
    F2 --> PR
    F3 --> PR
    F4 --> PR
    PR --> D
    D -->|"verdadeiro: resultado += espaco"| D
    D -->|"falso: coluna alinhada"| S


%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
sequenceDiagram
    participant Demo as demos/01_demo.cpp
    participant Pipe as 01_pipeline.cpp

    Demo->>Pipe: pipelineDaPeneira()
    Pipe-->>Demo: 5 fases, de analise lexica a execucao na maquina virtual
    Demo->>Pipe: formatarPipeline(fases)
    Pipe->>Pipe: preencher(FASE, largura = 30)
    Pipe-->>Pipe: cabecalho alinhado
    Pipe->>Pipe: nomeDaMetade(Metade::Analise)
    Pipe-->>Pipe: analise
    Pipe-->>Demo: tabela de 5 linhas
    Demo->>Pipe: hierarquiaDeChomsky()
    Pipe-->>Demo: 4 niveis, do tipo 3 ao tipo 0
    Demo->>Pipe: formatarHierarquia(niveis)
    Pipe-->>Demo: tabela de 4 linhas
    Demo->>Pipe: formasIntermediariasDaPeneira()
    Pipe-->>Demo: 5 formas, da sequencia de simbolos ao objeto
    Demo->>Pipe: formatarFormasIntermediarias(formas)
    Pipe-->>Demo: tabela de 5 linhas
    Demo->>Pipe: estrategiasDeExecucao()
    Pipe-->>Demo: 3 estrategias, com a hibrida marcada
    Demo->>Pipe: formatarEstrategias(estrategias)
    Pipe-->>Demo: tabela de 3 linhas, hibrida com o sinal de maior

O percurso é o mesmo quatro vezes, e o diagrama existe para mostrar exatamente isso: uma função devolve o dado — pipelineDaPeneira(), hierarquiaDeChomsky(), formasIntermediariasDaPeneira(), estrategiasDeExecucao() — e a formatadora correspondente percorre o vetor chamando preencher() uma vez por coluna. preencher() e nomeDaMetade() moram num escopo anônimo porque nenhum outro arquivo os chama, e nomeDaMetade() é o único ponto do bloco que traduz um valor de enumeração para texto, em vez de guardar o texto já pronto no dado. A alternativa era uma formatadora só, genérica, recebendo um vetor de vetores de texto e as larguras das colunas: são quatro funções quase iguais, e reduzi-las a uma é o reflexo certo em quase todo lugar. O custo aqui é o tipo. Com Fase, NivelDeChomsky, FormaIntermediaria e EstrategiaDeExecucao declarados, trocar dois campos de lugar numa linha da tabela não compila; com vetores de texto, compila e sai errado na projeção — e ninguém confere quatro tabelas coluna a coluna antes da aula.