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 e é o 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
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_H01_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 peneiraRepresentamos 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. Esbarrar nesse limite executando o próprio código é o que torna o autômato do módulo seguinte uma resposta a um problema vivido em vez de 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_H01_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 peneiraA 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. Declarar cada uma com a razão pela qual não se elimina é o 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.