1 Expressões regulares e linguagens regulares — Projeto do Professor
Este é o projeto de referência do professor — as tarefas do Projeto Integrador deste módulo resolvidas do começo ao fim, com as decisões justificadas uma a uma. É o modelo do que cada grupo deve produzir no próprio projeto, e existe para ser estudado, não copiado: o núcleo que você escolhe, a estrutura que constrói e as mensagens que escreve são seus. O que se copia daqui é o nível de acabamento e o hábito de medir o custo de cada decisão em vez de estimá-lo.
1.1 Visão Geral
Aqui entra a primeira peça de código da Peneira, e com ela o primeiro ponto do percurso em que uma decisão de representação passa a ter consequência mensurável. As quatro tarefas se encadeiam: a primeira escreve por extenso o que o sistema vai fazer, em comportamento e sem uma linha sobre como; a segunda decide o que ele trata de fato; a terceira constrói a peça que lê o pattern e produz a estrutura correspondente; e a quarta exige que essa peça recuse o texto malformado dizendo onde está o defeito.
A ordem importa, e ela não é a que o instinto sugere. Escrever a especificação antes de escolher o núcleo parece perder tempo com prosa quando já se poderia estar decidindo operadores — mas é a especificação que diz quais operadores o domínio pede, e a decisão tomada sem ela é chute com aparência de critério.
A tentação natural, e o enunciado da quarta tarefa já a antecipa, é tratá-la como acabamento e deixá-la para quando o resto estiver funcionando. Resolvemos as três tarefas de código juntas, e o motivo é econômico: a posição do erro só é barata enquanto a leitura está num lugar só. Assim que ela se espalhar — e vai se espalhar, porque o mesmo analisador será reusado pelo reconhecedor de símbolos alguns módulos adiante —, acrescentar posição significa passar a carregá-la por todos os pontos que já existem.
Além das quatro tarefas, o módulo tem conteúdo teórico que pede código próprio: as propriedades de fechamento das linguagens regulares, e a equivalência entre expressões distintas. A última seção trata das duas, e não por obrigação de cobertura — a equivalência é justamente o que a nossa verificação de convergência mede, e as propriedades de fechamento são o que garante que compor patterns não nos tira da classe que sabemos compilar.
Todo o código deste módulo compila com avisos tratados como erro, e a demonstração roda pelo binário deste ponto do percurso — que traz as peças do módulo anterior e mais a que entra aqui. O binário do módulo anterior continua existindo, e continua sendo executado.
1.2 Tarefa 1: Escrever a especificação do que você vai construir
O que a tarefa pede
Escolher um dos assuntos propostos e escrever, por extenso, o que o sistema fará. O documento é em Markdown, fica versionado junto do código e é o texto ao qual se volta em todos os capítulos seguintes para conferir se o que está sendo construído ainda é o que se pretendia construir. Sete seções o compõem: o domínio e a cena, o que se escreve na linguagem, o que o sistema aceita e o que recusa, onde a linguagem se aninha, o que se verifica antes de rodar, o que o sistema produz e quem executa, e a pergunta que será respondida medindo. Nada de arquitetura, estrutura de dados, biblioteca ou algoritmo — descreve-se comportamento.
O assunto da Peneira nós já escolhemos no capítulo anterior, e essa é a única diferença entre a nossa resolução e a de um grupo que começa agora: o que para o grupo é decisão, para nós é o recorte já fixado. O que a tarefa cobra é o resto — e o resto é a maior parte dela.
A tentação, aqui, é escrever um documento curto porque o assunto já está decidido. Resistimos, e o motivo aparece na terceira seção, a que trata do que o sistema recusa. Enquanto o recorte do capítulo anterior dizia que classe de padrões o sistema aceita, a especificação precisa dizer o que acontece quando alguém escreve um padrão errado — a mensagem exata, com linha, coluna e o que se esperava. Embutida aí está a decisão de que a Peneira relata todos os erros de uma vez em vez de parar no primeiro, e ela custaria caro se fosse tomada no capítulo em que o analisador já existe. Tomada aqui, ela é uma frase.
A quinta seção, a da verificação prévia, tem a mesma natureza. Ela obrigou a nomear as quatro naturezas de valor da linguagem e, com isso, a decidir uma assimetria que atravessa todo o percurso: um trecho casado da entrada vale onde se espera texto, mas não vale onde se espera número. Ler o número escrito num trecho é pedido explícito, e o nome dele é value. A alternativa era deixar o sistema adivinhar pela forma do que está escrito. Descartamos por ser a maneira mais confiável de produzir o resultado errado sem ninguém perceber — e por ser a decisão que, adiada, teria de ser tomada por quem escrevesse a verificação, olhando o código pronto.
A sexta seção é a que separa este projeto de um programa que mostra o resultado na tela. Ela fixa que o tradutor grava um objeto e encerra, e que outro componente lê esse objeto e o executa depois, sobre outra entrada, sem a descrição original por perto. É a decisão de maior alcance do documento: ela é o que faz a teoria de autômatos aparecer duas vezes no artefato, uma como estrutura interna do reconhecedor e outra como o próprio conteúdo do objeto gravado. Interpretar a árvore direto seria mais curto e apagaria a metade do percurso que existe para demonstrar exatamente isso.
A sétima e última muda de assunto de propósito: ela fixa o que se vai afirmar sobre a linguagem no fim do percurso, e com que evidência. Escrevemos ali a pergunta, a grandeza, a referência de comparação e — o campo que se costuma pular — o resultado que contrariaria a expectativa. Esse último campo é o que impede que a medição do último capítulo seja um número escolhido depois de ver o resultado.
docs/especificacao.md
# A Peneira — especificação do que vai ser construído
Este documento responde às sete perguntas da tarefa, na ordem em que ela as faz. Ele descreve
comportamento: o que existe na cena, o que a pessoa escreve, o que o sistema aceita, o que
recusa e como avisa. Não há aqui uma linha sobre estrutura de dados, algoritmo ou biblioteca.
Essas decisões chegam nos capítulos seguintes, e antecipá-las produziria um documento que
promete o que ainda não se sabe cumprir.
É a este texto que voltaremos em cada arco, para conferir se o que está sendo construído continua
sendo o que se pretendia construir.
## 1. O domínio e a cena
A Peneira fala sobre texto que carrega informação sem ter formato. Relatórios exportados de um
sistema, registros de execução de um serviço, correspondência arquivada, planilhas coladas em
mensagens, catálogos que alguém digitou ao longo de anos sem combinar um padrão: material em que a
informação existe, é legível por uma pessoa e não é acessível a nenhuma consulta.
Quem escreveria algo nessa linguagem é a pessoa que tem uma pilha desse material e uma pergunta
específica sobre ele. Não é programadora. Sabe descrever o que procura — "os endereços de correio
eletrônico", "os valores acima de mil", "as datas do último trimestre" — e sabe dizer o que quer
receber de volta. Hoje ela tem três saídas, e as três são ruins: ler tudo à mão, o que não escala;
pedir a alguém que escreva um programa, o que a coloca na fila de outra pessoa a cada pergunta
nova; ou aprender uma ferramenta de propósito geral, que cobra semanas para devolver a primeira
resposta.
O que ela quer obter é uma saída regular a partir de uma entrada irregular: linhas rotuladas,
uma por achado, que ela possa levar para onde já sabe trabalhar. E quer poder mudar a pergunta
amanhã sem mudar de ferramenta: trocar o que se procura deve custar reescrever três linhas de
descrição, não reescrever um programa.
A cena, então, é esta: a pessoa escreve num arquivo o que procura e o que quer que aconteça quando
cada coisa for encontrada; entrega esse arquivo e a pilha de texto à Peneira; recebe a saída
rotulada. Entre uma pergunta e a seguinte, o que muda é o arquivo de descrição.
## 2. O que se escreve na linguagem
Uma descrição da Peneira tem duas partes: os **padrões**, que dão nome às formas procuradas, e as
**regras**, que dizem o que fazer quando uma forma é encontrada. Os quatro exemplos abaixo vão do
mais simples ao mais elaborado, e são escritos como se a linguagem já existisse.
**Primeiro — o mínimo que já é útil.** Encontrar endereços de correio eletrônico e rotulá-los.pattern email = /[a-z0-9._]+@[a-z]+.[a-z]+/;
rule { on email(e) => emit(“contato”, e); }
**Segundo — duas formas procuradas ao mesmo tempo.** A ordem das declarações é a ordem em que os
padrões são tentados, e é ela que decide o desempate quando dois casam no mesmo ponto.
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) => emit(“valor”, n); }
**Terceiro — a condição.** Nem todo achado interessa. A regra pode exigir que o que foi encontrado
satisfaça uma condição antes de produzir saída.
pattern numero = /-?[0-9]+(.[0-9]+)?/; pattern codigo = /[A-Z]{2}-[0-9]+/;
rule { on numero(n) where value(n) > 100 => emit(“grande”, n); on codigo(c) where c != “XX-0” => emit(“codigo”, c); }
**Quarto — a condição composta.** Faixas, exclusões e combinações, escritas como se escreve uma
frase.
pattern numero = /-?[0-9]+(.[0-9]+)?/; pattern data = /[0-9]{2}/[0-9]{2}/[0-9]{4}/;
rule { on numero(n) where (value(n) > 100 and value(n) < 900) or (value(n) > 2000 and value(n) != 2500) => emit(“faixa”, n);
on data(d) where d != "01/01/1970" => emit("data", d);}
Os quatro exemplos são variações de uso, e não do mesmo formato: o primeiro tem só padrão e
emissão; o segundo introduz a competição entre padrões; o terceiro, a condição; o quarto, a
condição com estrutura própria. É essa progressão que o percurso vai construir, nesta ordem.
## 3. O que o sistema aceita e o que recusa
É válida a descrição que declara seus padrões antes de usá-los, escreve cada padrão numa notação de
forma que o sistema saiba reconhecer, e cujas regras se referem apenas a padrões declarados e
comparam coisas comparáveis. Tudo o mais é recusado antes de a pilha de texto ser lida — a
Peneira nunca começa a processar uma entrada para descobrir no meio que a descrição estava errada.
Toda recusa traz três coisas: onde, com linha e coluna; o que foi encontrado; e o que se
esperava ali. A terceira é a que faz a diferença para quem não programa, e é a que costuma
faltar nas ferramentas que essa pessoa já tentou usar.
| O que está errado | O que a pessoa recebe |
| --- | --- |
| falta o ponto e vírgula da declaração | `linha 3, coluna 41: esperava ";" ao fim da declaração de padrão; encontrei "rule"` |
| parêntese aberto e não fechado no padrão | `linha 2, coluna 18: parêntese aberto na coluna 12 nunca é fechado` |
| um `*` sem nada à esquerda para repetir | `linha 2, coluna 15: "*" repete o que vem antes, e não há nada antes dele` |
| a regra cita um padrão que não existe | `linha 7, coluna 8: "emails" não foi declarado; há um padrão chamado "email"` |
| dois padrões com o mesmo nome | `linha 4, coluna 9: "numero" já foi declarado na linha 2` |
| comparação entre coisas de naturezas diferentes | `linha 8, coluna 22: comparo texto com número; use value(n) para ler o número` |
| a entrada não existe ou não pode ser lida | `não consegui abrir "relatorio.txt"` |
Duas decisões de comportamento, ambas contra o instinto de quem escreve o sistema. A primeira: um
erro não interrompe a leitura da descrição. A Peneira segue conferindo o que vem depois e
relata tudo o que encontrou de uma vez — quem escreveu quatro erros de digitação quer os quatro na
primeira tentativa, não um por execução. A segunda: quando o nome citado não existe mas se parece
com um que existe, a mensagem sugere o nome próximo. Custa pouco e resolve, sozinha, a classe
de erro mais frequente de quem digita nomes.
Sobre a entrada, a postura é oposta: um trecho que não casa nenhum padrão não é erro. É o caso
normal, porque a pilha de texto é feita de material que não interessa, e a peneira existe
justamente para deixá-lo passar. O sistema termina com sucesso e sem saída quando nada foi encontrado.
## 4. Onde a linguagem se aninha
A condição de uma regra contém condições por dentro, sem profundidade máxima. É o ponto de
aninhamento da linguagem, e ele é real: cada parte de um `and` ou de um `or` pode ser, por sua vez,
uma condição composta, e o parêntese permite escrever isso em qualquer profundidade.
Um exemplo com três níveis, onde a numeração à direita indica quanto se desceu:
pattern numero = /-?[0-9]+(.[0-9]+)?/;
rule { on numero(n) where ((value(n) > 100 and value(n) < 900) // nível 3 or (value(n) > 2000 and value(n) < 2900)) // nível 2 and value(n) != 500 // nível 1 => emit(“faixa”, n); }
Há um segundo aninhamento, e ele é de outra natureza: dentro do padrão, os parênteses também se
aninham sem teto, e `((ab)|c)*d` é escrevível. Os dois são aninhamentos da notação; o que se
procura no texto, esse, continua sendo forma sem memória. Essa distinção volta adiante, quando o
percurso mostrar que existem pedidos que a Peneira não consegue atender por essa razão, e o
principal deles é este: um padrão que reconheça parênteses balanceados — encontrar no texto
qualquer trecho da forma `(((...)))` com abre e fecha em quantidades iguais. Ele é fácil de
descrever em português, e nenhuma forma sem memória o reconhece. A especificação registra desde já
que esse pedido fica de fora, e o capítulo que explicar por quê o fará sobre esta linguagem, e
não sobre um exemplo de fora.
## 5. O que se verifica antes de rodar
Há descrições bem escritas que não fazem sentido, e a Peneira as recusa antes de tocar na entrada.
A linguagem distingue quatro **naturezas de valor**. O **casamento** é o trecho da entrada que um
padrão reconheceu — não é texto qualquer: sabe-se de qual padrão veio. O **texto** é uma cadeia
entre aspas. O **número** é um valor numérico. A condição é o que uma comparação produz, e o
que `and` e `or` combinam.
Um casamento vale onde se espera texto, porque um trecho da entrada é texto. Um casamento não
vale onde se espera número: ler o número que está escrito num trecho é um pedido explícito, e o
nome dele é `value`. A assimetria é deliberada — `value(n) > 100` diz que se quer comparar
magnitude, e `n != "XX-0"` diz que se quer comparar o que está escrito. Deixar o sistema adivinhar
qual das duas a pessoa quis é como se produz o resultado errado que ninguém percebe.
O que se recusa antes de rodar, então: nome citado e não declarado; nome declarado duas vezes;
comparação de ordem entre coisas que não são números; comparação de igualdade entre naturezas
diferentes; e uso de `value` sobre o que não é casamento. O que se avisa, sem recusar: padrão
declarado e nunca usado — a descrição funciona, mas quase sempre a pessoa esqueceu a regra.
## 6. O que o sistema produz, e quem executa
O trabalho é feito em **dois momentos separados**, por dois componentes que não se encontram.
O **tradutor** lê a descrição, confere tudo o que a seção anterior enumera e, se estiver tudo certo,
grava um **objeto** — um arquivo, não uma tela. Terminado isso, ele encerra. O objeto contém, em
ordem: uma identificação que diz que aquilo é um objeto da Peneira e em que versão foi gravado; os
padrões, na ordem em que foram declarados, cada um na forma já preparada para reconhecer; e as
regras, na ordem em que aparecem, cada uma com a condição e a emissão prontas para serem
executadas. A ordem importa e é parte da especificação: é ela que determina o desempate entre
padrões que casam no mesmo ponto.
O **executor** é outro componente. Ele lê o objeto e uma entrada, e produz a saída. Não conhece a
descrição original, não a lê e não precisa dela: um objeto gravado hoje roda amanhã, em outra
máquina, sobre outra entrada, sem que o arquivo de descrição esteja presente. É essa separação que
faz a pessoa poder escrever a descrição uma vez e aplicá-la a mil arquivos depois.
O executor varre a entrada da esquerda para a direita, e em cada posição procura o casamento mais
longo entre todos os padrões. Empate de comprimento é resolvido pela ordem de declaração: vence o
declarado primeiro. Encontrado o casamento, a regra correspondente avalia sua condição, e a saída
sai — uma linha, com o rótulo e o valor emitido — se a condição for satisfeita. A varredura recomeça
logo depois do trecho casado, nunca dentro dele.
Um objeto de versão diferente da que o executor entende é recusado com uma mensagem que diz as duas
versões. Objeto truncado ou corrompido também é recusado — e antes de qualquer execução, não no
meio dela.
## 7. A pergunta que vai ser respondida medindo
**A pergunta:** avaliar a condição de uma regra parando no primeiro fator que já decide o
resultado compensa o que custa, ou a parada antecipada é complicação que se paga com nada?
Ela não se resolve olhando. Parar cedo evita trabalho, mas exige que a execução saiba desviar no
meio da condição, e desviar tem custo próprio; avaliar tudo é mais simples e às vezes trabalha à
toa. Qual dos dois efeitos domina depende da forma das condições que as pessoas realmente escrevem,
e isso é fato do mundo, não teorema.
**A grandeza que responde:** o número de vezes que a execução precisa ler o número escrito num
trecho casado, sobre uma entrada fixa. Essa é a operação cara — ela percorre o texto casado
inteiro, caractere a caractere, enquanto todas as outras olham valores já prontos. Contamos junto,
como grandeza secundária, o total de passos executados, para saber se a economia numa foi anulada
pela outra.
**A referência de comparação:** a mesma descrição, sobre a mesma entrada, com a condição avaliada
por inteiro sempre. Nada mais muda entre as duas execuções — mesma leitura, mesmos padrões, mesmo
objeto salvo pela parte que se quer medir. Sem essa referência, qualquer número que se obtenha ganha
do vazio.
**O resultado que contrariaria a expectativa:** que as duas estratégias façam o mesmo número de
leituras de número — o que significaria que as condições escritas na descrição medida não têm fator
que decida sozinho, e a pergunta estaria mal posta; ou que a parada antecipada leia menos números e
mesmo assim execute mais passos no total, o que a tornaria uma troca, e não uma melhora. Os dois
resultados são possíveis, e é por isso que a pergunta é medida em vez de respondida.
Onde é fácil errar. Escrever a seção dos exemplos com três amostras que são o mesmo exemplo com nomes trocados. Os nossos quatro sobem em degraus deliberados — só padrão e emissão; dois padrões competindo pela mesma posição; a condição; a condição composta —, e é essa progressão que vai virar a ordem de construção dos capítulos seguintes. Três variações do primeiro exemplo teriam passado na leitura e não teriam dito nada sobre o que construir depois.
Como verificar que está correta. Releia a especificação pronta procurando os quatro assuntos que parecem bons e falham: o que executa direto sem gravar objeto, o que tem comandos de formato fixo sem aninhamento, o que trata todo valor como sendo da mesma natureza e o que toma o reconhecedor pronto de uma biblioteca. No nosso caso, as três seções centrais — aninhamento, verificação prévia e objeto produzido — respondem aos três primeiros por escrito, e a do aninhamento vai além do que a tarefa exige: ela registra o pedido que a Peneira não vai atender — encontrar trechos de parênteses balanceados —, para que a impossibilidade, quando for demonstrada, seja sobre esta linguagem e não sobre um exemplo de fora.
1.3 Tarefa 2: Escolher o núcleo mínimo de operadores
O que a tarefa pede
Decidir quais operadores de padrão o sistema tratará de fato e quais notações de conveniência serão reduzidas a esse núcleo antes de qualquer processamento. A escolha parece pequena e determina o tamanho de tudo o que vem depois: cada operador mantido no núcleo reaparece em todas as peças seguintes, na construção da máquina, na conversão para forma determinística e na tradução final. A decisão se registra junto com as reduções, na forma de pares que mostram a notação de partida e a expressão equivalente no núcleo.
O critério é o que o enunciado diz: entra no núcleo o que não se reduz. Aplicá-lo é mais direto do que parece, e o resultado são três operadores — concatenação, alternância e fecho — mais duas folhas, o símbolo literal e a cadeia vazia. Tudo o mais que o usuário escreve vira composição disso durante a leitura.
docs/02_nucleo_minimo.md
# O núcleo mínimo de operadores e as reduções
Decisão do segundo arco da Peneira. O critério de inclusão no núcleo é um só:
**a impossibilidade de reduzir**. Um operador que se exprime pela composição de
outros é conveniência de quem escreve o pattern, não capacidade nova do sistema.
## O núcleo
Três operadores e duas folhas.
| Construção | Papel |
| -------------- | ------------------------------------------------ |
| concatenação | núcleo — uma coisa seguida de outra |
| alternância | núcleo — uma coisa ou outra |
| fecho | núcleo — zero ou mais repetições |
| símbolo | folha — um símbolo literal do alfabeto |
| cadeia vazia | folha — produzida pela redução do opcional |
Tudo o mais que o usuário pode escrever é reduzido a isto durante a leitura.
Consequência direta, e a razão de a decisão valer o documento: a construção de
Thompson, a determinização e a minimização tratarão **três** casos internos, e
não oito. Cada operador mantido no núcleo reapareceria em cada uma dessas peças.
## As reduções, em pares
| O usuário escreve | A árvore recebe |
| ----------------- | -------------------------------------- |
| `x+` | `concat(x, fecho(x))` |
| `x?` | `alt(x, vazio)` |
| `[abc]` | `alt(alt('a', 'b'), 'c')` |
| `[a-c]` | `alt(alt('a', 'b'), 'c')` |
| `(x)` | `x` — o grupo não sobrevive à leitura |
| `\.` | `'.'` — símbolo literal |
O grupo merece nota. Parênteses existem para o leitor humano dizer onde a
precedência muda; uma vez que a árvore está construída, a estrutura **é** a
precedência, e um nó de agrupamento não teria o que guardar. A árvore de `(ab)c`
e a de `abc` são a mesma, e é assim que deve ser.
A redução de `x+` duplica a subárvore `x`. Não compartilhamos o índice entre as
duas ocorrências: compartilhar produziria um grafo, e a construção de Thompson
passaria duas vezes pelos mesmos estados, gerando uma máquina errada. O preço é
que o custo de `x+` é o dobro do de `x`, mais um nó — e a demonstração mede isso.
## A exceção, e por que ela é honesta
O coringa `.` **não** é reduzido. Em princípio ele é redutível: é a alternância de
todos os símbolos do alfabeto. Na prática, o alfabeto da Peneira é o dos
caracteres imprimíveis, e essa expansão produziria quase uma centena de folhas por
ocorrência — uma árvore que ninguém lê, para dizer o que uma folha diz.
Mantivemos o coringa como folha própria, com o custo de que cada peça posterior
tenha um caso a mais para tratar. É uma exceção ao critério de inclusão, tomada
por razão de tamanho e não de expressividade, e está registrada aqui para que
quem a encontrar adiante saiba que ela foi decidida, e não esquecida.
A classe de símbolos **é** reduzida, mesmo sendo cara pelo mesmo motivo: uma faixa
de dez símbolos vira dez folhas e nove alternâncias. A diferença é que a classe é
escrita pelo usuário com o tamanho que ele escolhe e costuma ser pequena, enquanto
o coringa tem custo fixo e máximo. A demonstração imprime o número de nós de cada
árvore justamente para que essa conta fique visível em vez de ser afirmada.
## Descartado
**Retrovisor e grupo de captura**, já recusados no arco anterior: retrovisor sai
da classe das linguagens regulares, e um pattern que o usasse não poderia ser
compilado para autômato finito.
**Quantificador contado** (`x{3,5}`). É redutível — expande em concatenações e
opcionais —, então caberia no critério. Ficou de fora por não acrescentar nada ao
que a obra demonstra e por multiplicar o tamanho da árvore de um jeito que
surpreende quem escreve o pattern. Se voltar, volta como redução, nunca como
operador de núcleo.Três entradas do documento merecem comentário, porque nelas o critério foi aplicado e deu respostas diferentes.
O grupo não sobrevive à leitura, e isso surpreende quem espera vê-lo na árvore. Parênteses existem para o leitor humano dizer onde a precedência muda; depois que a árvore está construída, a estrutura é a precedência, e um nó de agrupamento não teria o que guardar. A árvore de (ab)c e a de abc são a mesma — e a demonstração confere exatamente isso.
O coringa é a exceção, e ela é deliberada. Em princípio ele se reduz: é a alternância de todos os símbolos do alfabeto. Na prática, essa expansão produziria quase uma centena de folhas por ocorrência, para dizer o que uma folha diz. Mantivemos o coringa como folha própria, pagando o preço de que toda peça posterior tenha um caso a mais para tratar. Registramos a exceção com a razão para que, adiante, quem a encontrar saiba que ela foi decidida e não esquecida — a diferença entre as duas coisas é o que separa um sistema de uma pilha de remendos.
O quantificador contado foi descartado embora passasse no critério, e vale entender por quê. Ele é redutível, então caberia. Ficou de fora por não acrescentar nada ao que a obra demonstra, e por multiplicar o tamanho da árvore de um jeito que surpreende quem escreve o pattern. O critério de inclusão não é o único filtro: um operador redutível ainda precisa valer o que custa na experiência de quem usa a linguagem.
Onde é fácil errar. Manter um operador no núcleo “porque é fácil implementar agora”. A conta certa é a dos quatro seguintes, onde cada operador do núcleo é um caso a mais na construção da máquina, na determinização e na tradução. Como verificar que está correta: para cada operador do seu núcleo, tente escrever a redução dele usando os outros. Se conseguir, ele não pertence ao núcleo — a menos que você tenha, como no caso do coringa, uma razão de tamanho escrita ao lado.
1.4 Tarefa 3: Ler a expressão e convertê-la em árvore
O que a tarefa pede
Implementar a leitura de uma expressão de padrão e a sua conversão em uma estrutura em árvore, com a precedência e a associatividade dos operadores refletidas na forma da árvore, e não em convenção escrita à parte. A tarefa se cumpre quando duas notações diferentes para o mesmo padrão convergem para a mesma estrutura — a verificação mais barata que existe desta etapa, e a que detecta o erro mais comum, que é a redução aplicada de forma inconsistente.
Escrevemos um analisador recursivo-descendente à mão, uma função por produção da gramática do pattern, sem gerador de analisadores. A precedência não aparece em tabela nem em comentário: ela está na ordem em que as produções se chamam, e a alternância chama a concatenação, que chama a repetição, que chama o átomo. Quem lê o código lê a precedência.
02_regex.h
// 02_regex.h — Leitura de uma expressão de padrão e conversão em árvore.
//
// Primeira peça de código da Peneira. Recebe o texto de um pattern e devolve a
// árvore que a construção de Thompson consumirá no capítulo seguinte — ou o
// primeiro erro encontrado, com a posição exata no texto.
//
// A árvore usa apenas o NÚCLEO MÍNIMO decidido no capítulo anterior:
// concatenação, alternância e fecho, mais as duas folhas (símbolo e cadeia
// vazia) e o coringa. Toda notação de conveniência — `+`, `?`, classe de
// símbolos — é reduzida a esse núcleo durante a leitura, e não depois: o que
// sai daqui já não conhece os operadores reduzidos, e nenhuma peça posterior
// precisa aprendê-los.
//
// Os nós vivem num vetor e se referenciam por índice, nunca por ponteiro. A
// árvore é copiável, serializável e não vaza; e a duplicação de subárvore que a
// redução de `+` exige vira uma cópia de faixa de vetor, não um passeio
// recursivo de alocação.
#ifndef PENEIRA_02_REGEX_H
#define PENEIRA_02_REGEX_H
#include <cstddef>
#include <string>
#include <vector>
namespace peneira {
// Índice ausente. Uma folha não tem filhos; o fecho tem só o esquerdo.
inline constexpr std::size_t kSemFilho = static_cast<std::size_t>(-1);
// recorte:inicio nucleo-minimo-como-tipo
enum class TipoDeNo {
Simbolo, // um símbolo literal do alfabeto
Qualquer, // o coringa `.`
Vazio, // a cadeia vazia, produzida pela redução de `?`
Concatenacao, // núcleo
Alternancia, // núcleo
Fecho, // núcleo
};
struct No {
TipoDeNo tipo = TipoDeNo::Vazio;
char simbolo = '\0'; // significativo apenas em Simbolo
std::size_t esquerda = kSemFilho;
std::size_t direita = kSemFilho;
};
// recorte:fim nucleo-minimo-como-tipo
struct Arvore {
std::vector<No> nos;
std::size_t raiz = kSemFilho;
bool vazia() const;
};
// Erro de sintaxe com a posição em que foi detectado, contada em símbolos a
// partir de zero. Carregar a posição desde a leitura é bem mais barato do que
// acrescentá-la depois, quando a análise já está espalhada por vários pontos.
struct ErroDeSintaxe {
std::size_t posicao = 0;
std::string mensagem;
};
struct Resultado {
bool ok = false;
Arvore arvore;
ErroDeSintaxe erro;
};
// Lê a expressão e devolve a árvore reduzida ao núcleo, ou o primeiro erro.
Resultado analisarExpressao(const std::string& expressao);
// Forma prefixa canônica da árvore, em uma linha. É o que permite verificar que
// duas notações diferentes do mesmo padrão convergiram para a mesma estrutura —
// comparação de texto, e não inspeção visual de duas figuras.
std::string formatarArvore(const Arvore& arvore);
// A mensagem de erro pronta para exibição, com o cursor sob a posição.
std::string formatarErro(const std::string& expressao, const ErroDeSintaxe& erro);
// Número de nós da árvore: a medida do custo de uma redução, usada na
// demonstração para mostrar o que uma classe de símbolos larga produz.
std::size_t tamanho(const Arvore& arvore);
} // namespace peneira
#endif // PENEIRA_02_REGEX_H02_regex.cpp
#include "02_regex.h"
namespace peneira {
bool Arvore::vazia() const { return raiz == kSemFilho; }
std::size_t tamanho(const Arvore& arvore) { return arvore.nos.size(); }
namespace {
// O analisador é recursivo-descendente escrito à mão, uma função por produção da
// gramática do pattern. Ele constrói a árvore já reduzida: as funções `novo*`
// abaixo são as únicas que criam nós, e nenhuma delas cria nó de `+` ou `?`,
// porque esses operadores não existem na árvore de saída.
class Analisador {
public:
explicit Analisador(const std::string& texto) : texto_(texto) {}
Resultado analisar() {
Resultado resultado;
const std::size_t raiz = alternancia();
if (falhou_) {
resultado.ok = false;
resultado.erro = erro_;
return resultado;
}
if (posicao_ != texto_.size()) {
// Sobrou texto: o caso típico é um `)` sem abertura, que a produção
// de grupo não consome e ninguém mais reclama.
return falhar("simbolo inesperado apos o fim da expressao");
}
resultado.ok = true;
resultado.arvore.nos = nos_;
resultado.arvore.raiz = raiz;
return resultado;
}
private:
// --- construção de nós -------------------------------------------------
std::size_t novoFolha(const TipoDeNo tipo, const char simbolo) {
No no;
no.tipo = tipo;
no.simbolo = simbolo;
nos_.push_back(no);
return nos_.size() - 1;
}
std::size_t novoBinario(const TipoDeNo tipo, const std::size_t esquerda,
const std::size_t direita) {
No no;
no.tipo = tipo;
no.esquerda = esquerda;
no.direita = direita;
nos_.push_back(no);
return nos_.size() - 1;
}
std::size_t novoFecho(const std::size_t filho) {
No no;
no.tipo = TipoDeNo::Fecho;
no.esquerda = filho;
nos_.push_back(no);
return nos_.size() - 1;
}
// recorte:inicio clonar-em-vez-de-compartilhar
// Duplica a subárvore enraizada em `origem` e devolve a raiz da cópia.
// A redução de `+` precisa da subárvore duas vezes — uma vez direta e outra
// sob o fecho —, e compartilhar o mesmo índice nos dois lugares produziria
// um grafo, não uma árvore: a construção de Thompson passaria duas vezes
// pelos mesmos estados e geraria uma máquina errada.
std::size_t clonar(const std::size_t origem) {
const No& modelo = nos_[origem];
No copia;
copia.tipo = modelo.tipo;
copia.simbolo = modelo.simbolo;
// Os filhos precisam ser clonados ANTES de o pai entrar no vetor: o
// `push_back` invalida a referência `modelo`, então lemos tudo dela
// primeiro e só depois recorremos.
const std::size_t esquerdaOriginal = modelo.esquerda;
const std::size_t direitaOriginal = modelo.direita;
copia.esquerda =
esquerdaOriginal == kSemFilho ? kSemFilho : clonar(esquerdaOriginal);
copia.direita = direitaOriginal == kSemFilho ? kSemFilho : clonar(direitaOriginal);
nos_.push_back(copia);
return nos_.size() - 1;
}
// recorte:fim clonar-em-vez-de-compartilhar
// --- leitura do texto --------------------------------------------------
bool fim() const { return posicao_ >= texto_.size(); }
char atual() const { return texto_[posicao_]; }
Resultado falhar(const std::string& mensagem) {
Resultado resultado;
resultado.ok = false;
resultado.erro.posicao = posicao_;
resultado.erro.mensagem = mensagem;
return resultado;
}
std::size_t erroEm(const std::string& mensagem) {
if (!falhou_) {
falhou_ = true;
erro_.posicao = posicao_;
erro_.mensagem = mensagem;
}
return kSemFilho;
}
// --- produções ---------------------------------------------------------
// recorte:inicio precedencia-por-descida
// alternancia := concatenacao ( '|' concatenacao )*
std::size_t alternancia() {
std::size_t esquerda = concatenacao();
if (falhou_) {
return kSemFilho;
}
while (!fim() && atual() == '|') {
++posicao_;
const std::size_t direita = concatenacao();
if (falhou_) {
return kSemFilho;
}
esquerda = novoBinario(TipoDeNo::Alternancia, esquerda, direita);
}
return esquerda;
}
// recorte:fim precedencia-por-descida
// recorte:inicio associatividade-na-arvore
// concatenacao := repeticao+
// A associatividade à esquerda está na FORMA da árvore, e não numa nota
// escrita à parte: `abc` vira Concat(Concat(a,b),c).
std::size_t concatenacao() {
if (fim() || atual() == '|' || atual() == ')') {
return erroEm("esperava uma expressao aqui");
}
std::size_t esquerda = repeticao();
if (falhou_) {
return kSemFilho;
}
while (!fim() && atual() != '|' && atual() != ')') {
const std::size_t direita = repeticao();
if (falhou_) {
return kSemFilho;
}
esquerda = novoBinario(TipoDeNo::Concatenacao, esquerda, direita);
}
return esquerda;
}
// recorte:fim associatividade-na-arvore
// recorte:inicio reducao-ao-nucleo
// repeticao := atomo ( '*' | '+' | '?' )*
// Aqui moram as duas reduções ao núcleo. Aceitar sufixos repetidos custa um
// laço e evita recusar `a**`, que é redundante mas não é malformado.
std::size_t repeticao() {
std::size_t no = atomo();
if (falhou_) {
return kSemFilho;
}
while (!fim() && (atual() == '*' || atual() == '+' || atual() == '?')) {
const char sufixo = atual();
++posicao_;
if (sufixo == '*') {
no = novoFecho(no);
} else if (sufixo == '+') {
// x+ reduz a x x* — uma ocorrência obrigatória seguida do fecho.
const std::size_t copia = clonar(no);
no = novoBinario(TipoDeNo::Concatenacao, no, novoFecho(copia));
} else {
// x? reduz a (x|ε).
no = novoBinario(TipoDeNo::Alternancia, no, novoFolha(TipoDeNo::Vazio, '\0'));
}
}
return no;
}
// recorte:fim reducao-ao-nucleo
// atomo := SIMBOLO | '\' SIMBOLO | '.' | '[' classe ']' | '(' alternancia ')'
std::size_t atomo() {
if (fim()) {
return erroEm("expressao terminou antes do esperado");
}
const char simbolo = atual();
if (simbolo == '(') {
++posicao_;
const std::size_t interno = alternancia();
if (falhou_) {
return kSemFilho;
}
if (fim() || atual() != ')') {
return erroEm("falta o fecha-parenteses do grupo");
}
++posicao_;
return interno;
}
if (simbolo == '[') {
return classe();
}
if (simbolo == '\\') {
// A barra invertida tira o significado especial do símbolo seguinte.
// Sem ela não há como escrever um ponto literal, e o pattern de
// endereço do primeiro exemplo precisa exatamente disso.
++posicao_;
if (fim()) {
return erroEm("barra invertida no fim da expressao, sem o simbolo que ela escapa");
}
const char escapado = atual();
++posicao_;
return novoFolha(TipoDeNo::Simbolo, escapado);
}
if (simbolo == '.') {
++posicao_;
return novoFolha(TipoDeNo::Qualquer, '\0');
}
if (simbolo == '*' || simbolo == '+' || simbolo == '?') {
return erroEm("operador de repeticao sem expressao a que se aplicar");
}
if (simbolo == ')') {
return erroEm("fecha-parenteses sem abertura correspondente");
}
++posicao_;
return novoFolha(TipoDeNo::Simbolo, simbolo);
}
// recorte:inicio classe-custa-caro
// classe := '[' ( SIMBOLO | SIMBOLO '-' SIMBOLO )+ ']'
// Reduz a uma cadeia de alternâncias. É a redução mais cara do conjunto —
// uma faixa de dez símbolos vira dez folhas e nove nós de alternância —, e a
// demonstração mede esse custo de propósito.
std::size_t classe() {
++posicao_; // consome '['
std::size_t acumulado = kSemFilho;
bool algumSimbolo = false;
while (!fim() && atual() != ']') {
const char inicio = atual();
++posicao_;
char fimDaFaixa = inicio;
if (!fim() && atual() == '-' && posicao_ + 1 < texto_.size() &&
texto_[posicao_ + 1] != ']') {
++posicao_; // consome '-'
fimDaFaixa = atual();
++posicao_;
if (static_cast<unsigned char>(fimDaFaixa) < static_cast<unsigned char>(inicio)) {
return erroEm("faixa invertida na classe de simbolos");
}
}
for (int codigo = static_cast<unsigned char>(inicio);
codigo <= static_cast<unsigned char>(fimDaFaixa); ++codigo) {
const std::size_t folha =
novoFolha(TipoDeNo::Simbolo, static_cast<char>(codigo));
acumulado = acumulado == kSemFilho
? folha
: novoBinario(TipoDeNo::Alternancia, acumulado, folha);
}
algumSimbolo = true;
}
if (fim()) {
return erroEm("falta o fecha-colchetes da classe de simbolos");
}
++posicao_; // consome ']'
if (!algumSimbolo) {
return erroEm("classe de simbolos vazia");
}
return acumulado;
}
// recorte:fim classe-custa-caro
const std::string& texto_;
std::size_t posicao_ = 0;
std::vector<No> nos_;
bool falhou_ = false;
ErroDeSintaxe erro_;
};
// recorte:inicio forma-prefixa-comparavel
void escreverPrefixa(const Arvore& arvore, const std::size_t indice, std::string& saida) {
if (indice == kSemFilho) {
return;
}
const No& no = arvore.nos[indice];
switch (no.tipo) {
case TipoDeNo::Simbolo:
saida += '\'';
saida += no.simbolo;
saida += '\'';
return;
case TipoDeNo::Qualquer:
saida += "qualquer";
return;
case TipoDeNo::Vazio:
saida += "vazio";
return;
case TipoDeNo::Concatenacao:
saida += "concat(";
break;
case TipoDeNo::Alternancia:
saida += "alt(";
break;
case TipoDeNo::Fecho:
saida += "fecho(";
break;
}
escreverPrefixa(arvore, no.esquerda, saida);
if (no.direita != kSemFilho) {
saida += ", ";
escreverPrefixa(arvore, no.direita, saida);
}
saida += ')';
}
// recorte:fim forma-prefixa-comparavel
} // namespace
Resultado analisarExpressao(const std::string& expressao) {
if (expressao.empty()) {
Resultado resultado;
resultado.ok = false;
resultado.erro.posicao = 0;
resultado.erro.mensagem = "expressao vazia";
return resultado;
}
Analisador analisador(expressao);
return analisador.analisar();
}
std::string formatarArvore(const Arvore& arvore) {
if (arvore.vazia()) {
return "(arvore vazia)";
}
std::string saida;
escreverPrefixa(arvore, arvore.raiz, saida);
return saida;
}
std::string formatarErro(const std::string& expressao, const ErroDeSintaxe& erro) {
std::string saida = " " + expressao + '\n';
saida += " ";
// A posição é contada em símbolos desde zero; o cursor vai exatamente sob o
// símbolo recusado. Uma mensagem sem esta linha obriga quem escreveu o
// pattern a procurar o defeito, que é justamente o trabalho que ela deveria
// poupar.
for (std::size_t i = 0; i < erro.posicao && i < expressao.size(); ++i) {
saida += ' ';
}
saida += "^ ";
saida += erro.mensagem;
saida += " (posicao " + std::to_string(erro.posicao) + ")";
return saida;
}
} // namespace peneiraDuas decisões de implementação merecem justificativa, e as duas cobram preço adiante se forem tomadas de outro jeito.
A primeira é a representação: os nós vivem num vetor e se referenciam por índice, nunca por ponteiro. Custa uma indireção a mais na leitura do código e paga em três lugares — a árvore fica copiável sem escrever construtor de cópia, não vaza memória, e a duplicação de subárvore que a redução do fecho positivo exige vira cópia de faixa de vetor. Num percurso cujo assunto é justamente grafo com ciclo, essa escolha vai reaparecer quando os estados do autômato precisarem de representação, e é bom que a primeira vez seja aqui, onde o objeto ainda é uma árvore e o erro é barato.
A segunda é que a redução acontece durante a leitura, e não numa passada posterior. O que sai do analisador já não conhece o fecho positivo, o opcional nem a classe de símbolos, e nenhuma peça construída daqui em diante precisará aprendê-los. A alternativa — guardar os operadores de conveniência na árvore e reduzi-los depois — parece mais organizada e transfere para toda peça seguinte a obrigação de perguntar se a árvore que recebeu já foi normalizada.
Um detalhe da duplicação merece atenção porque o erro correspondente é silencioso. Ao reduzir o fecho positivo, a subárvore aparece duas vezes: uma direta e outra sob o fecho. Compartilhar o mesmo índice nas duas posições produziria um grafo, não uma árvore, e a construção de Thompson do módulo seguinte passaria duas vezes pelos mesmos estados, gerando uma máquina errada. Clonamos, portanto, e o custo dessa clonagem é o que a demonstração mede.
Dois pontos menores do analisador resolvem casos que costumam ser esquecidos até aparecerem como defeito. O primeiro é a barra invertida, que retira o significado especial do símbolo seguinte. Ela não estava na gramática de partida do módulo anterior, e foi acrescentada aqui por necessidade concreta: o pattern de endereço do exemplo escrito lá precisa de um ponto literal, e sem escape não há como escrevê-lo — o ponto seria lido como coringa e o pattern casaria coisas que não deveria. Quando o exemplo cobra uma construção que a gramática não previa, quem cede é a gramática, e o registro da mudança vai para o mesmo documento onde ela foi decidida.
O segundo é a repetição de sufixos. Aceitamos a** e a+* em vez de recusá-los, e a razão é que eles são redundantes, não malformados: a definição de fecho tolera perfeitamente ser aplicada de novo sobre o próprio resultado. Recusar exigiria uma regra a mais no analisador para proibir algo que não faz mal a ninguém, e mensagens de erro que proíbem o inofensivo ensinam quem escreve o pattern a desconfiar das que importam.
A convergência de notações é a verificação da tarefa, e ela roda no próprio programa. A demonstração compara a árvore de a+ com a de aa*, a de uma classe com a da alternância explícita equivalente, a de uma faixa com a da enumeração, e a de uma expressão agrupada com a da mesma expressão sem parênteses. As quatro convergem, e a comparação é de texto — a forma prefixa canônica —, não inspeção visual de duas figuras.
A mesma demonstração imprime o número de nós de cada árvore, e é aqui que a Tarefa 1 deixa de ser retórica. O pattern de endereço do exemplo escrito no módulo anterior tem vinte e um símbolos e produz trezentos e dezoito nós. A conta é o preço das três faixas de vinte e seis símbolos, cada uma expandida em alternâncias, duas vezes por causa do fecho positivo. Ver o número é o que transforma “a redução tem custo” de afirmação em fato, e é a primeira vez no percurso em que uma decisão de projeto vira medida.
Onde é fácil errar. Refletir a precedência numa tabela de prioridades consultada pelo analisador, em vez de na ordem das produções. Funciona, e a primeira mudança de gramática desalinha as duas descrições sem que nada acuse. Como verificar que está correta: escreva o mesmo padrão de duas maneiras diferentes e compare as árvores por texto. Se as duas formas convergem para uma reescrita da expressão, e não para a mesma estrutura, alguma redução está sendo aplicada em um caminho e não no outro.
1.5 Tarefa 4: Recusar a expressão malformada com a posição do problema
O que a tarefa pede
Fazer o sistema recusar expressões malformadas apontando onde está o problema. Encerrar a execução informando apenas que a expressão é inválida é metade do trabalho, e a metade que não serve a quem escreveu a expressão: a mensagem existe para que alguém corrija o texto, e uma mensagem sem posição obriga essa pessoa a procurar. É requisito técnico, e não acabamento — o custo de acrescentar a posição depois, quando a leitura já está distribuída em vários pontos do código, é várias vezes maior do que o de carregá-la desde o começo.
O analisador não lança exceção nem encerra o programa: devolve um resultado que ou traz a árvore, ou traz o erro com a posição. Essa escolha é o que permite que a demonstração exiba quatro expressões malformadas seguidas, sem que a primeira interrompa as outras três — e é a mesma forma de que o reconhecedor de símbolos precisará adiante, quando um erro num pattern não puder derrubar a compilação do programa inteiro.
A posição é registrada no ponto em que o defeito é detectado, e uma decisão explícita acompanha isso: guardamos o primeiro erro e ignoramos os seguintes. Um analisador que continua depois da falha produz erros em cascata, todos derivados do primeiro, e quem lê a lista perde tempo com os que desaparecerão sozinhos assim que o defeito real for corrigido.
Repare no que a demonstração mostra sobre as quatro expressões recusadas. Em a(b|c, o cursor cai no fim do texto, e não no parêntese que abriu — porque é ali que a falta é constatada, e é ali que quem corrige vai digitar. Em *ab, ele cai no primeiro símbolo, com a mensagem dizendo que o operador de repetição não tem a que se aplicar; nomear o que faltou é o que separa uma mensagem útil de um “sintaxe inválida”. Em ab)c, o cursor para no fecha-parênteses, apontando o símbolo que sobrou depois do fim da expressão.
A mensagem é montada com a expressão original e uma segunda linha com o cursor sob a posição. Escolhemos essa forma em vez de “erro na coluna 5” porque a contagem manual de colunas é justamente o trabalho que a mensagem deveria poupar.
Onde é fácil errar. Reportar a posição em que o analisador está em vez daquela em que o problema é. As duas coincidem na maioria dos casos e divergem exatamente nos que confundem, como o grupo não fechado. Como verificar que está correta: escreva quatro ou cinco expressões malformadas de tipos diferentes e leia as mensagens fingindo que não conhece o código. Se alguma delas não disser o que fazer para corrigir, ela ainda não está pronta.
1.6 Fechamento e equivalência: o que o núcleo garante
Os dois tópicos teóricos que não viram tarefa do projeto são as propriedades de fechamento e a equivalência entre expressões distintas. Nenhum dos dois pede código novo — pedem que se enxergue o que o código já escrito diz sobre eles.
O fechamento é a garantia que sustenta o núcleo. Dizer que as linguagens regulares são fechadas sob união, concatenação e fecho é dizer que compor duas especificações regulares por qualquer um dos três operadores produz outra especificação regular. É o que autoriza o analisador a construir a árvore combinando subárvores sem jamais perguntar se o resultado ainda pertence à classe — a resposta é sempre sim, e é por isso que a pergunta não aparece em lugar nenhum do código.
Vale notar o que não decorre disso. As linguagens regulares também são fechadas sob complemento e interseção, mas a nossa notação não oferece operador para nenhum dos dois. Fechamento é propriedade da classe; operador é decisão de projeto. A classe permitiria; nós recusamos, porque um operador que não é redutível ao núcleo o expandiria — e complemento, em particular, exige a máquina determinística completa, que só existe dois módulos adiante.
A equivalência é o que a nossa verificação de convergência mede, e ela merece uma ressalva honesta. Duas expressões podem denotar a mesma linguagem sem produzir a mesma árvore: (a|b)* e (a*b*)* denotam ambas todas as cadeias sobre dois símbolos, e as árvores são diferentes. A comparação estrutural que implementamos detecta a equivalência que vem da redução — a que interessa aqui, porque o erro que ela caça é a redução inconsistente. A equivalência semântica plena é outra pergunta, e ela tem resposta: comparar as máquinas mínimas correspondentes, que é o que o módulo de minimização vai permitir. Registrar agora que a nossa verificação é a mais fraca das duas evita que alguém conclua adiante que ela falhou, quando na verdade ela nunca prometeu isso.
Onde é fácil errar. Tomar a convergência estrutural por equivalência de linguagens e concluir que duas expressões denotam linguagens diferentes só porque as árvores diferem. Como verificar que está correta: submeta ao seu comparador um par de expressões equivalentes mas estruturalmente distintas e confira que ele responde “árvores diferentes” — a resposta certa para a pergunta que ele faz, e a errada para a pergunta que ele não faz.