flowchart TB
E["Linha de entrada<br/>n caracteres"] --> P0["Posicao 0:<br/>escolhe extensao do 1o coringa"]
P0 --> T1["tenta casar o resto"]
T1 -->|falha| P0
T1 -->|falha esgotada| P1["Posicao 1:<br/>refaz o trabalho inteiro"]
P1 --> T2["tenta casar o resto"]
T2 -->|falha| P1
T2 -->|falha esgotada| PN["Posicao n-1:<br/>refaz mais uma vez"]
PN --> R["Custo cresce com o cubo<br/>do comprimento da linha"]
E --> U["Uma passada, sem retroceder:<br/>conjunto de pontos ativos avanca junto"]
U --> S["Custo proporcional ao<br/>comprimento da linha"]
1 Expressões regulares e linguagens regulares
Uma linha de texto que decide sobre um conjunto sem fim — e a distância exata entre o que ela promete e o que o programa entrega.
Escreva a* num papel. São duas posições: uma letra e um asterisco. Agora tente listar o que essa expressão descreve. Começa na cadeia vazia. Segue com a, depois aa, depois aaa. Você desiste antes do conjunto acabar, porque ele não acaba.
Duas posições de um lado, infinito do outro. A conta fecha porque o asterisco não descreve cadeia nenhuma. Ele descreve uma operação sobre um conjunto de cadeias, e o conjunto é que cresce. O texto da expressão cresce com o número de construções que você digita; o conjunto descrito cresce com o número de combinações que aquelas construções permitem. As duas grandezas não têm relação entre si.
Pois é dessa desproporção que sai a resposta para a pergunta deixada em aberto no capítulo anterior. Uma linguagem infinita não cabe em memória nenhuma; uma descrição finita dela cabe numa linha. A expressão regular é a primeira dessas descrições que você vai escrever. Ela vem com duas definições, uma classe de linguagens batizada com o nome dela e um limite que se mede em memória.
O que passa a estar ao seu alcance. Escrever a definição indutiva de expressão regular e a da linguagem que ela denota. Determinar exatamente que cadeias uma expressão descreve, casos de borda inclusive. Reduzir classes de símbolos, quantificadores e abreviações a um núcleo pequeno, e dizer em números quanto essa redução custa. Compor especificações usando as propriedades de fechamento, sabendo o que elas garantem e onde param. E decidir, diante de duas expressões diferentes, se elas descrevem o mesmo conjunto.
1.1 Sete caracteres, e um serviço inteiro parado
Quarenta e seis anos entre a técnica publicada e a conta cobrada por não a usar.
Em 2 de julho de 2019, a Cloudflare parou. O relatório do incidente, assinado por John Graham-Cumming, aponta uma regra recém-publicada de um filtro de tráfego. Dentro dela, um fragmento de padrão que cabe em sete caracteres: .*.*=.*.
Olhe o fragmento com calma. Ele é uma expressão regular perfeitamente legítima. A linguagem que ela denota é modesta — qualquer texto que tenha um sinal de igual em algum lugar. Nada ali sai da classe regular, e nada ali pede memória além da que uma máquina de estados fixos carrega. Pela teoria, decidir sobre uma linha de mil caracteres custaria mil passos.
Acontece que o motor não trabalhava assim. Ele retrocedia: escolhia uma extensão para o primeiro coringa, seguia adiante, falhava, voltava, escolhia outra e refazia o trabalho a partir de cada posição possível. Com três coringas encadeados, o custo de examinar uma linha passa a crescer com o cubo do comprimento dela. Dobrar o tamanho da linha multiplica o trabalho por oito.
Pare um instante nisto. A teoria dizia mil passos, e o serviço parou. Onde exatamente está o erro: na teoria, no padrão que alguém escreveu, ou em outro lugar? Responda antes de seguir — as três respostas levam a decisões de projeto bem diferentes.
O erro mora na distância entre a garantia e quem a realiza, e essa distância tem quase setenta anos de história. Em 15 de dezembro de 1951, Stephen Kleene assinou na RAND o memorando RM-704. O assunto declarado eram redes de neurônios — texto, busca e programa de computador ficaram todos de fora daquelas páginas. A publicação saiu em 1956, na coletânea Automata Studies, organizada por Shannon e McCarthy.
Kleene queria dizer, em espaço finito, que conjuntos de sequências de eventos um arranjo de células nervosas distinguiria. Repare no que ele escolheu como matéria-prima: escolher entre alternativas, seguir de uma etapa à seguinte e repetir. Três operações, e nenhuma quarta. Uma rede de neurônios também não tinha uma quarta coisa a fazer.
Dezessete anos se passaram antes de alguém usar aquilo para procurar palavras em arquivos. Em junho de 1968, nos Bell Labs, Ken Thompson publicou nas Communications of the ACM um artigo curto chamado Regular Expression Search Algorithm. Ele tinha 25 anos. O programa descrito ali lia uma expressão regular e escrevia código de máquina do IBM 7094 a partir dela.
A propriedade que importa está no que aquele código fazia com a entrada: percorria o texto uma vez, sem jamais voltar a uma posição já lida. Veja o mecanismo num caso mínimo. Diante do padrão a*ab e do texto aaab, um programa que escolha primeiro quantos a o fecho consome tem quatro escolhas, e três levam a um beco. O método de Thompson não escolhe. Ele mantém, a cada posição, o conjunto de todos os pontos do padrão em que a leitura poderia estar, e avança esse conjunto inteiro de uma vez.
Cinco anos depois, em 1973, a técnica saiu do laboratório. A pedido de Doug McIlroy, um comando enterrado dentro do editor ed foi extraído e virou programa próprio, herdando o nome da sequência de teclas que o invocava: g/re/p. E é aqui que 2019 fica incômodo. Decidir numa passada estava publicado desde 1968 e instalado em qualquer máquina desde 1973. Naquele 2 de julho, a distância entre a garantia e a entrega veio de o motor escolhido não usar uma técnica que estava ali havia quarenta e seis anos.
A garantia é da classe; a conta é da implementação.
Guarde a frase. Ela volta na última seção como critério de decisão, e é ela que separa duas perguntas que quase todo mundo funde numa só: o que a notação pode descrever, e quanto custa decidir com ela.
1.1.1 O que a Peneira faz com esta notação
A Peneira, o sistema de referência desta obra, tem uma declaração chamada pattern, e o que se escreve entre as barras dela é exatamente a notação deste capítulo. Uma linha como pattern numero = /-?[0-9]+(\.[0-9]+)?/; é uma expressão regular com três operadores de conveniência dentro, e daqui a poucas páginas você vai saber quantos nós ela custa.
O capítulo anterior terminou deixando uma tarefa em aberto: escrever à mão, em português, o padrão mais longo que a sua linguagem precisa aceitar. Aquele texto vira agora uma expressão, e a passagem de um para o outro é o primeiro trabalho de tradução do percurso — de uma descrição informal para uma que uma máquina consegue processar sem interpretar intenção.
Duas coisas da Peneira voltam a pesar aqui, e elas explicam por que este capítulo pesa mais do que o assunto sugere. A primeira é que os padrões declarados por quem escreve o programa viram autômatos, e o objeto que o compilador grava em disco é um vetor desses autômatos. A segunda é que os símbolos da própria linguagem Peneira — as palavras pattern, rule, on, where, os identificadores, os números — também são descritos por expressões regulares e reconhecidos pelo mesmo maquinário.
A notação, portanto, comparece duas vezes no mesmo sistema, em alturas diferentes. Ela é o que o usuário escreve e é o que o compilador usa para ler o que o usuário escreveu. Uma decisão tomada aqui sobre quais operadores existem afeta os dois lados de uma vez, e é essa dupla incidência que torna a escolha do núcleo mínimo uma decisão de arquitetura em vez de um detalhe de notação.
1.2 A notação tem duas definições, e você precisa das duas
Uma diz o que se pode escrever; a outra diz que conjunto foi escrito.
Qual é a diferença entre a|bc e (a|b)c? Dois caracteres de texto, e dois conjuntos que compartilham exatamente uma cadeia. A primeira expressão descreve a e bc. A segunda descreve ac e bc. Trocar uma pela outra num filtro muda quais mensagens passam, e ninguém percebe olhando depressa.
Dizer isso com precisão exige duas definições separadas, e mantê-las separadas é o que torna as duas dizíveis. A primeira trata do texto: que sequências de caracteres têm direito ao nome de expressão regular. A segunda trata do significado: que conjunto cada texto desses descreve. Confundi-las é o atalho que produz frases como “a expressão reconhece a cadeia”, e essa frase custa caro adiante.
1.2.1 A forma: o que conta como expressão
Antes da notação, o que o objeto faz. Uma expressão regular é um texto escrito segundo regras rígidas, e nada mais. Ela não roda, não decide e não sabe o que significa.
NotaA definição de expressão regular, no enunciado formal
Seja \Sigma um alfabeto. O conjunto das expressões regulares sobre \Sigma é definido por indução: \emptyset é uma expressão regular; \varepsilon é uma expressão regular; a é uma expressão regular, para cada a \in \Sigma; e, se r e s são expressões regulares, então (r \mid s), (rs) e (r^*) também são. Nada mais é expressão regular.
Seis cláusulas, quatro linhas. Três dizem o que é uma expressão elementar, duas dizem como combinar o que já existe, e a última fecha a porta. Sobre \Sigma = \{a, b\}, a entra pela terceira cláusula, (a|b) pela quarta e ((a|b)*) pela sexta. Cada objeto novo se constrói a partir de objetos já construídos, sempre em um número finito de passos.
A frase final é a que faz o trabalho pesado, e é a mais fácil de ler depressa. Sem “nada mais é expressão regular”, a definição descreveria qualquer conjunto que contivesse aquelas construções, inclusive o conjunto de todos os textos possíveis. A cláusula de fecho impede a definição de aceitar o universo por omissão.
A tradução dessa definição para um tipo de dados sai quase literal, com duas divergências que valem atenção.
02_regex.h
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;
};As seis cláusulas viraram seis casos do tipo, e a correspondência para aí. O conjunto vazio não ganhou caso próprio, porque nenhuma notação prática oferece jeito de escrevê-lo e uma expressão que o denotasse recusaria toda entrada — resultado que se obtém mais rápido não escrevendo padrão algum. Em compensação, o coringa ganhou um caso que a definição não previa, e a conta dessa exceção aparece na seção seguinte.
Agora a convenção que permite parar de digitar parênteses. A definição escreve parênteses em toda combinação, e ninguém escreve padrões assim. A convenção é fixa: o fecho liga mais forte que a concatenação, e a concatenação liga mais forte que a alternância. É ela que decide entre os dois conjuntos que abriram esta seção.
flowchart TB
subgraph G1["a|bc — a alternancia fica na raiz"]
A1["alternancia"] --> A2["a"]
A1 --> A3["concatenacao"]
A3 --> A4["b"]
A3 --> A5["c"]
end
subgraph G2["(a|b)c — a concatenacao fica na raiz"]
B1["concatenacao"] --> B2["alternancia"]
B2 --> B3["a"]
B2 --> B4["b"]
B1 --> B5["c"]
end
A gramática do padrão diz a precedência sem enunciá-la em lugar nenhum:
Cada produção chama a de precedência mais alta. A alternância chama a concatenação, que chama a repetição, que chama o átomo. Um analisador com uma função por produção herda a precedência da ordem das chamadas.
02_regex.cpp
// 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;
}A alternativa comum é guardar a precedência numa tabela de prioridades e consultá-la durante a leitura. Ela funciona, e é por funcionar que engana. Existindo duas descrições da mesma convenção, a primeira alteração feita numa delas desalinha as duas, e nenhum compilador acusa a divergência. A gramática acima e a cadeia de chamadas são a mesma descrição, escrita uma vez.
A associatividade segue o mesmo caminho, e mora na forma da árvore construída.
02_regex.cpp
// 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;
}O laço acumula à esquerda: cada repetição encontrada vira o filho direito de um nó cujo filho esquerdo é tudo o que veio antes. Para a concatenação, agrupar de um lado ou do outro daria a mesma linguagem. Para operadores em que a diferença importa — a subtração numa linguagem aritmética, digamos —, a mesma técnica separa uma implementação correta de uma que devolve o número errado com toda a confiança do mundo.
Uma consequência disso costuma incomodar. O parêntese não sobrevive à leitura: depois de construída, a árvore de (ab)c fica indistinguível da árvore de abc. Ele existiu para dizer onde a precedência mudava, cumpriu o papel e sumiu. Pelo mesmo motivo, a** e a+* são aceitos em vez de recusados. Aplicar o fecho ao resultado de um fecho é redundante, e redundante fica bem longe de malformado.
Malformado é outra coisa, e as formas de sê-lo são poucas. Em a(b|c falta o fecha-parênteses. Em *ab, o operador de repetição aparece sem ter a que se aplicar. Em [a-z falta o fecha-colchetes. Em ab)c sobra um fecha-parênteses depois do fim. Nos quatro casos há um ponto do texto em que a leitura para, e nomear esse ponto separa uma mensagem útil de um lacônico “sintaxe inválida”.
Esse ponto merece cuidado, porque nem sempre coincide com a posição do defeito. Em a(b|c o parêntese que abriu está na posição 2, e a leitura só descobre que ele nunca fechou ao chegar ao fim do texto. O fim é onde a falta se constata, e é também onde o parêntese vai ser digitado. Apontar a posição 2 obrigaria quem corrige a percorrer o resto da expressão procurando onde ela acaba.
1.2.2 O conjunto: o que a expressão denota
Você escreveu a*. Que conjunto exatamente acabou de escrever? A ponte entre o texto e o conjunto é uma segunda definição, escrita pela mesma indução da primeira.
NotaA linguagem denotada, no enunciado formal
A linguagem denotada por uma expressão regular r, escrita L(r), é definida pela mesma indução: L(\emptyset) = \emptyset; L(\varepsilon) = \{\varepsilon\}; L(a) = \{a\} para a \in \Sigma; L(r \mid s) = L(r) \cup L(s); L(rs) = L(r)\,L(s); e L(r^*) = L(r)^*.
Repare no que as três últimas cláusulas fazem. Elas não definem nada de novo. Apenas transferem para o mundo das expressões três operações sobre linguagens que o capítulo anterior já tinha definido. A barra vertical é a união. A justaposição é a concatenação. O asterisco é o fecho de Kleene.
Calcule um caso de baixo para cima e veja a indução trabalhando. Tome (a|b)a sobre \Sigma = \{a, b\}. As folhas primeiro: L(a) = \{a\} e L(b) = \{b\}. A alternância em seguida, dando \{a, b\}. A concatenação por último, dando \{aa, ba\}. Nenhum passo precisou olhar mais de um nível abaixo, e é isso que torna o cálculo automatizável.
Refaça agora com a|ba, que difere por um par de parênteses. A concatenação vem antes, porque a precedência mudou: L(ba) = \{ba\}, e depois \{a\} \cup \{ba\} = \{a, ba\}. Dois conjuntos de duas cadeias cada, com exatamente uma em comum. A diferença entre as expressões é tipográfica; a diferença entre os conjuntos, não.
Os erros que mais custam neste ponto não estão nas expressões complicadas. Estão nas curtas, e quase todos envolvem a diferença entre não ter nada e ter o nada. Compare L(\emptyset) com L(\varepsilon): cardinalidade zero contra cardinalidade um. Concatenar qualquer coisa com o primeiro devolve o vazio, porque não há com o que emparelhar. Concatenar com o segundo devolve a coisa original. Um aniquila e o outro é neutro, e escrever um no lugar do outro produz um sistema que rejeita tudo, com o sintoma aparecendo longe da linha responsável.
Some a isso três bordas que fecham o inventário. A primeira soa contraditória e não é: L(\emptyset^*) = \{\varepsilon\}, porque o fecho de qualquer linguagem contém a cadeia vazia. A segunda: a+ e a* não denotam a mesma linguagem, e a diferença de um único elemento decide se a entrada vazia é aceita. A terceira: o tamanho do texto nada diz sobre o tamanho da linguagem. Uma alternância de literais pode ocupar meia página e denotar quinze cadeias.
Com as duas definições na mesa, a terceira sai quase de graça.
NotaLinguagem regular, no enunciado formal
Uma linguagem L \subseteq \Sigma^* é regular quando existe uma expressão regular r sobre \Sigma tal que L(r) = L.
O menor exemplo é uma linguagem finita. O conjunto \{aa, ab, ba\} é regular, e a expressão que o descreve se escreve enumerando: aa|ab|ba. O argumento se generaliza sem esforço, e o resultado merece ser guardado: toda linguagem finita é regular. Basta escrever a alternância de todos os seus elementos. Esse fato decide um caso importante duas seções adiante.
O saldo desta seção
A expressão denota um conjunto. Ela é uma descrição parada num arquivo, e não reconhece coisa alguma. Reconhecer é uma ação, e ações exigem uma máquina que leia símbolos, mude de estado e devolva resposta. Dizer que a expressão reconhece uma cadeia é o modo mais rápido de apagar a razão de existirem quatro capítulos entre esta página e a primeira entrada sendo aceita ou recusada.
1.3 O núcleo se define por uma recusa
Abra a documentação de qualquer ferramenta de padrões e conte os operadores. Serão dezenas: classes de símbolos, faixas, quantificadores contados, coringas, âncoras, atalhos para dígito e para espaço em branco. A definição formal lista três operadores e três folhas. A distância entre as duas listas é enorme, e nenhum daqueles acréscimos amplia o que se pode descrever. Cada um abrevia uma composição dos três originais, e o nome disso é açúcar sintático.
O critério que decide quem fica no núcleo cabe numa linha: fica o que não se reduz. Um operador pertence ao núcleo quando não existe maneira de escrever, usando só os outros, uma expressão que denote sempre a mesma linguagem. Aplicado à lista inteira das notações de uso corrente, esse critério devolve três operadores — concatenação, alternância e fecho — mais duas folhas, o símbolo literal e a cadeia vazia.
1.3.1 As reduções, escritas em pares
Por que o núcleo pequeno vale a pena, se manter os operadores extras pareceria mais simples? A resposta mora nos quatro capítulos seguintes. Cada operador mantido reaparece como um caso a mais na construção do autômato, um caso a mais na determinização e um caso a mais na minimização. Um operador custa três implementações, três oportunidades de errar e três lugares para consertar.
Faça a conta com números. Com o núcleo reduzido, cada uma dessas três peças trata três casos internos. Com uma notação de oito operadores mantidos, cada uma trata oito. São quinze casos a mais no total, espalhados por três arquivos que precisam concordar entre si. Essa multiplicação por três é o que transforma a redução numa decisão de arquitetura.
Uma redução se registra como um par: a notação de partida à esquerda, a expressão equivalente do núcleo à direita. O par permite conferir a redução sem executar nada. Basta ler os dois lados e perguntar se denotam o mesmo conjunto.
| Notação de partida | Expressão equivalente do núcleo |
|---|---|
x+ |
xx* |
x? |
(x\|ε) |
[abc] |
a\|b\|c |
[a-c] |
[abc], e daí a\|b\|c |
(x) |
x |
A última linha é a que costuma incomodar. O parêntese de agrupamento reduz a nada: não vira nó, não vira folha e não deixa marca. Repare também que duas dessas reduções dependem de ordem. A faixa só chega à alternância depois de virar enumeração, e o fecho positivo só duplica a subárvore depois de a subárvore estar pronta. Um par cujo lado direito ainda contenha açúcar é um par pela metade.
02_regex.cpp
// 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;
}Repare no momento em que a redução acontece. Ela roda durante a leitura, e não numa passada posterior sobre a árvore pronta. O objeto que sai dali já não conhece o fecho positivo, o opcional nem a classe de símbolos, e nenhuma peça construída depois precisará aprendê-los. Guardar os operadores de conveniência para reduzi-los mais tarde parece mais organizado, e transfere a cada peça seguinte a obrigação de perguntar se a árvore recebida já foi normalizada.
A redução do fecho positivo esconde uma armadilha, e adverti-la não basta. Execute-a até a falha. Para escrever xx* é preciso da subárvore de x duas vezes, uma direta e outra sob o fecho. A economia óbvia é apontar os dois lugares para o mesmo nó. Faça isso e o resultado deixa de ser uma árvore: passa a ser um grafo, com dois pais apontando para o mesmo filho.
02_regex.cpp
// 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;
}O sintoma aparece dois capítulos adiante, longe da linha que o causou. A construção que transforma a árvore em autômato percorre a estrutura a partir da raiz e cria estados novos para cada nó visitado. Com o nó compartilhado, ela passa duas vezes pelo mesmo nó e liga ao mesmo trecho de máquina duas passagens que deveriam ser distintas. O autômato aceita cadeias que o padrão não descrevia, e a árvore impressa continua parecendo perfeita.
1.3.2 O que a conveniência custa, em nós
A classe de símbolos é a redução mais fácil de escrever e a que mais nós produz. Digite [a-z]: três caracteres, contando os colchetes. A expressão equivalente do núcleo tem 26 folhas, uma por letra, e 25 nós de alternância para juntá-las. São 51 nós, ou dezessete nós por caractere digitado.
A conta se generaliza numa fórmula que serve para qualquer faixa: uma faixa de n símbolos produz n folhas e n-1 alternâncias, isto é, 2n-1 nós. A faixa de dígitos [0-9] produz 19. A de minúsculas produz 51. A relação é linear, e é por ser linear que ela surpreende quem espera que três caracteres digitados custem alguma coisa próxima de três.
flowchart TB
subgraph A["[a-c] reduzido ao nucleo: 5 nos para 3 caracteres digitados"]
R1["alternancia"] --> R2["alternancia"]
R2 --> R3["'a'"]
R2 --> R4["'b'"]
R1 --> R5["'c'"]
end
subgraph B["[a-c]+ reduzido: a subarvore inteira aparece duas vezes"]
C1["concatenacao"] --> C2["alternancia<br/>5 nos"]
C1 --> C3["fecho"]
C3 --> C4["alternancia<br/>5 nos, clonados"]
end
02_regex.cpp
// 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;
}O laço de dentro é onde a conta nasce: uma folha por código de símbolo da faixa, e uma alternância a cada folha depois da primeira. Empilhe agora as reduções. [a-z]+ duplica a subárvore e acrescenta o fecho e a concatenação: 51 + 51 + 1 + 1 = 104 nós. [a-z]? acrescenta a folha da cadeia vazia e uma alternância, dando 53. Três faixas concatenadas custam 3 \times 51 + 2 = 155.
Ponha essas três faixas sob fecho positivo. São 18 caracteres digitados. A subárvore de 155 nós é clonada, ganha um nó de fecho e um de concatenação, e o total chega a 312 nós. Dezoito caracteres de um lado, trezentos e doze do outro, e nada de errado aconteceu no caminho.
A conta acima sugere algo que seria falso. A árvore ficou dezessete vezes maior que o texto, e a linguagem denotada não mudou de tamanho nenhum: [a-z] e a alternância das vinte e seis letras descrevem exatamente as mesmas cadeias. O que a redução multiplica é a representação. O engano da seção anterior reaparece de outro ângulo — a* tem duas posições e denota conjunto infinito; a faixa tem 51 nós e denota vinte e seis cadeias.
O que a máquina não faz, o tradutor faz por ela — e cobra em instruções.
A máquina, aqui, é a construção do autômato que vem adiante, e ela conhece apenas as seis cláusulas do núcleo. O tradutor é a leitura da expressão, e a moeda com que ele paga são nós de árvore. O valor é pequeno de propósito. Medir a conta barata agora é o que torna previsível a forma dela quando a mesma cobrança voltar em ordens de grandeza bem maiores.
Complemento: dois filtros, e eles dão respostas diferentes
O coringa é redutível — denota a alternância de todos os símbolos do alfabeto — e mesmo assim ficou no núcleo. A razão está na fórmula: sobre o alfabeto dos caracteres imprimíveis, expandir um único coringa produziria quase uma centena de folhas, mais as alternâncias que as juntam, para dizer o que uma folha diz sozinha. O quantificador contado teve destino oposto. Ele também é redutível, e mesmo assim foi descartado da notação inteira. Um quantificador sem teto declarado permite que alguém escreva uma repetição de cinquenta mil numa linha de configuração. A pessoa não percebe, e produz uma árvore de dezenas de milhares de nós. Redutibilidade decide o que pode sair do núcleo; tamanho e utilidade decidem o que convém que saia. Quem funde os dois filtros lê como esquecimento aquilo que foi decisão.
O que sustenta as duas escolhas acima é o registro. Cada redução vai anotada em par, cada exceção vai anotada com a razão ao lado, e as duas coisas ficam num documento que sobrevive à conversa em que foram decididas. Quem encontrar o coringa no núcleo daqui a seis meses vai perguntar por que ele está lá. Achar a resposta escrita, ou não achar, separa um sistema de uma pilha de remendos.
1.4 O fechamento é cerca, e ela delimita por dentro
Combinar duas especificações regulares nunca produz coisa que saia da classe — e o limite disso se mede em memória.
Você escreveu duas expressões, cada uma descrevendo um pedaço do que o seu sistema precisa aceitar, e agora quer juntá-las. A pergunta que deveria vir antes de qualquer coisa é se o resultado ainda é descritível pela mesma notação. Juntar duas coisas fáceis produz uma coisa difícil?
1.4.1 Três operações, e o direito de trabalhar por partes
NotaFechamento sob as três operações, no enunciado formal
Se L_1 e L_2 são linguagens regulares sobre \Sigma, então L_1 \cup L_2, L_1 L_2 e L_1^* são regulares. A demonstração é imediata pela definição de expressão regular: dadas expressões r_1 e r_2 com L(r_1) = L_1 e L(r_2) = L_2, as expressões (r_1 \mid r_2), (r_1 r_2) e (r_1^*) são expressões regulares por construção, e a definição da linguagem denotada lhes atribui exatamente aquelas linguagens.
A demonstração cabe em duas linhas porque as duas definições foram escritas para isso. Uma diz que combinar expressões produz expressão; a outra diz que a linguagem do resultado é a combinação das linguagens. Emende as duas e o resultado sai sozinho. Duas linhas, aqui, dizem que as definições foram bem escolhidas.
Repare no tipo de demonstração que essa é, porque a diferença importa em engenharia. Ela é construtiva: não se limita a garantir que a expressão do resultado existe em algum lugar, ela diz qual é. A expressão da união é literalmente (r_1 \mid r_2), escrita colando os dois textos com uma barra no meio. Uma demonstração de existência pura garantiria o mesmo e deixaria você sem o objeto na mão.
Por que exatamente essas três operações? A resposta vem da leitura da hierarquia pela memória, feita no capítulo anterior. União, concatenação e fecho são precisamente o que uma máquina de memória finita executa sem precisar de memória extra. Unir é oferecer dois caminhos a partir do mesmo ponto. Concatenar é emendar o fim de um trajeto no começo do outro. Fechar é devolver o fim ao começo. Nenhuma das três exige contar, lembrar quantidade ou guardar um pedaço da entrada.
O que o resultado entrega, na prática, é o direito de trabalhar por partes. Um reconhecedor de números precisa aceitar três formas: inteiro sem sinal, inteiro com sinal e número com parte decimal. Escreva cada uma isolada, sem pensar nas outras, e junte as três com alternância. O conjunto é regular por construção, e em nenhum momento você precisou olhar para as três ao mesmo tempo.
Isso elimina uma pergunta do dia a dia. No analisador que constrói a árvore não existe nada do tipo “o resultado desta combinação continua na classe?”. A pergunta não aparece porque a resposta é sempre sim. Uma classe que não fosse fechada exigiria uma verificação a cada combinação, e verificações desse tipo, feitas milhares de vezes durante a leitura de um arquivo, custam mais que a própria leitura.
Há um limite honesto a declarar, e ele será cobrado adiante. O fechamento garante que o resultado é regular, e nada diz sobre o tamanho da máquina que reconhecerá esse resultado. Compor dez expressões produz uma expressão regular, e a máquina correspondente pode ter um número de estados desconfortavelmente maior que a soma dos estados das dez. Garantia de classe, custo de implementação: a mesma separação que 2 de julho de 2019 tornou concreta.
1.4.2 O que a cerca barra, e o que ela deixa passar
Tudo o que o resultado acima diz é sobre o que acontece dentro da classe. Do que existe fora do terreno ele nada fala, e é fácil ler a garantia como se ela fosse uma escada — como se compor operadores suficientes acabasse alcançando qualquer coisa.
Veja o caso que mede o limite: a linguagem dos parênteses balanceados, com aninhamento de qualquer profundidade. Escreva (), depois (()), depois ((())), sem teto. Nenhuma composição de união, concatenação e fecho descreve esse conjunto, e a razão está na memória.
Quem só sabe em que estado está não sabe quantas vezes já entrou nele.
Refaça o argumento das casas de pombo, agora sobre o fechamento. Fixe uma máquina de memória finita com k estados, escolhidos antes de ela rodar. Apresente a ela k+1 profundidades diferentes de abertura. Como há k estados e k+1 entradas, duas dessas profundidades terminam obrigatoriamente no mesmo estado.
flowchart TB
E1["( — uma abertura"] --> Q1["q1"]
E2["(( — duas aberturas"] --> Q2["q2"]
E3["((( — tres aberturas"] --> Q3["q3"]
E4["(((( — quatro aberturas"] --> QX["cai num dos tres<br/>estados ja ocupados"]
QX --> D["Dali em diante a maquina trata<br/>as duas profundidades do mesmo jeito"]
D --> F["Apresentados os fechamentos,<br/>uma das duas respostas esta errada"]
Chame de i e j essas duas profundidades. Dali em diante a máquina não as distingue mais, e trata de modo idêntico tudo o que vier depois. Apresente agora i fechamentos. Para a entrada que abriu i vezes, a resposta certa é aceitar; para a que abriu j vezes, a resposta certa é recusar. A máquina responde a mesma coisa às duas, e uma das duas respostas está errada. Acrescentar estados não salva, porque o argumento se refaz para qualquer k finito.
A máquina leu mil aberturas, guardou o que podia guardar, chegou ao fim com um único fechamento e aceitou.
O mesmo argumento derruba um segundo requisito, e ele é menos óbvio. Considere as cadeias formadas por um bloco qualquer seguido de uma cópia exata dele — aa, abab, abcabc. Comparar a segunda metade com a primeira exige lembrar a primeira inteira, e os blocos não têm comprimento limitado. Essa linguagem fica de fora até da classe seguinte da hierarquia, a das livres de contexto, resultado que Hopcroft, Motwani e Ullman registram e cuja demonstração usa ferramenta que este percurso ainda não tem. Guarde a forma dessa exigência: ela volta com nome próprio duas seções adiante.
O que a cerca não impede
O limite acima costuma ser lido com mais força do que tem, e a leitura exagerada estreita o projeto sem necessidade. A cerca barra o aninhamento sem profundidade máxima, e não o aninhamento. Aceitar parênteses balanceados até profundidade três descreve um conjunto finito de formas, e toda linguagem finita é regular, como já ficou estabelecido. A expressão fica feia e comprida, e ela existe, que é a única coisa exigida. O mesmo vale para qualquer requisito com teto declarado. Um sistema que precise reconhecer construções aninhadas pode declarar profundidade máxima e continuar inteiro dentro da classe, com todas as garantias de desempenho que ela oferece. O que separa uma restrição defensável de um defeito é uma linha escrita: a profundidade máxima consta da especificação, ou não consta.
O procedimento que decide entre as duas situações tem três passos. Primeiro, escreva o requisito em português, com atenção às palavras que indicam quantidade sem limite: qualquer profundidade, quantas vezes for preciso, do mesmo tamanho. Segundo, pergunte o que a máquina precisaria guardar entre uma leitura e a seguinte. Terceiro, pergunte se aquilo tem teto conhecido antes de a entrada existir.
Havendo teto, o requisito cabe na classe. Não havendo, ele não cabe, e insistir na notação produz um padrão que parece funcionar em todos os casos testados. E há um terceiro resultado, o mais comum na prática e o menos declarado: o requisito está escrito de forma ambígua e o procedimento não responde. O passo seguinte, então, é reescrever o requisito, e não escolher a classe no chute.
1.5 Quem pula a cerca, e quem só parece pular
Em 1997, em Cambridge, Hazel publicou a PCRE, uma biblioteca de casamento de padrões que replicava a sintaxe de uma linguagem popular na época. A sintaxe que ela consolidou virou o padrão de fato de quase tudo o que se escreve hoje, e é bem maior que a de Kleene: âncoras, grupos de captura, quantificadores não gulosos, verificação adiante e retrovisão. Quantos desses acréscimos ainda cabem dentro da cerca?
Quase todos. A exceção é a retrovisão, o operador que permite exigir, mais adiante no padrão, a repetição de um trecho já casado. Aplique a ele a pergunta que decide tudo neste capítulo. A máquina precisaria lembrar o bloco inteiro, caractere por caractere, para conferi-lo depois, e o bloco não tem tamanho limitado. Memória fixa não guarda trecho ilimitado, e o argumento da seção anterior se refaz sem alteração alguma.
A retrovisão, portanto, sai da classe regular. Um padrão que a use não pode ser compilado para autômato finito, e ela deixa de ser açúcar sintático pelo mesmo motivo — açúcar abrevia sem ampliar, e este operador amplia. A conta tem nome e tem fonte: casar padrão com retrovisor é problema NP-completo, resultado que Aho registra no Handbook of Theoretical Computer Science, de 1990.
Três outros acréscimos parecem sair da classe e não saem, e confundi-los com a retrovisão leva a decisões conservadoras demais. A verificação adiante exige que, a partir de certa posição, o texto satisfaça outro padrão, sem consumir o trecho — e o que se verifica adiante é ele próprio regular, de modo que o resultado permanece dentro da cerca. O grupo de captura marca um trecho para extração posterior, e a linguagem descrita é exatamente a mesma com e sem ele. O quantificador não guloso muda qual trecho é escolhido quando há mais de uma escolha possível, e não muda quais cadeias pertencem à linguagem.
O discriminador que separa os três da retrovisão cabe numa pergunta, e ela é sempre a mesma: o operador exige lembrar um trecho da entrada cujo tamanho não tem teto? Se exige, sai da classe. Se não exige, fica dentro dela, por mais elaborada que a notação pareça.
flowchart TB
P["Padrao escrito"] --> D{"Exige lembrar um trecho<br/>de tamanho sem teto?"}
D -->|"Sim"| B["Familia com retrocesso<br/>PCRE, 1997"]
D -->|"Nao"| N["Familia sem retrocesso<br/>RE2, 2010"]
B --> BC["Aceita o operador<br/>e abre mao da garantia de tempo"]
N --> NC["Recusa o operador<br/>e decide numa passada"]
BC --> S["A garantia de tempo vale o que vale<br/>o pior padrao carregado pelo mesmo motor"]
Essa pergunta também separa as duas famílias de motor que existem. A da PCRE implementa a notação completa, retrovisão inclusive, e obtém isso por retrocesso: quando uma escolha não fecha, o motor volta e tenta outra. O retrocesso é o que torna possível implementar um operador fora da classe, e é também o que abriu a porta para o custo cúbico de 2 de julho de 2019. A do RE2, publicada pelo Google em 2010, faz a escolha oposta. Ela recusa os operadores que saem da classe. Em troca, compila o padrão para uma máquina de estados que decide numa passada — o mesmo compromisso que Thompson havia publicado em 1968.
A assimetria aparece quando muitos padrões dividem o mesmo processo. Um serviço que aplica centenas de padrões a cada mensagem executa todos no mesmo motor. Com retrocesso, basta que um deles case com uma entrada infeliz para que o tempo de resposta do serviço inteiro se degrade, e os outros, corretamente escritos, param junto. A garantia de tempo é propriedade do conjunto, e vale o que vale o pior membro dele. Escolher entre as duas famílias é decidir de quem é o risco.
1.6 Duas expressões, a mesma linguagem
A árvore responde a uma pergunta; a linguagem é outra.
NotaEquivalência de expressões, no enunciado formal
Duas expressões regulares r e s sobre \Sigma são equivalentes, escrito r \equiv s, quando L(r) = L(s). A equivalência é relação entre as linguagens denotadas, e não entre os textos das expressões nem entre as estruturas construídas a partir deles.
A segunda frase separa duas coisas que se confundem o tempo todo. As expressões a+ e aa* são equivalentes, e as árvores delas, depois da redução, coincidem — porque a redução de + produz literalmente xx*. A coincidência das árvores, nesse caso, é consequência da equivalência, e não a definição dela.
Essa coincidência é aproveitável como verificação, e é a mais barata que existe para a leitura de expressões. Confira quatro pares: a+ contra aa*, [abc] contra a alternância equivalente, [a-c] contra [abc], e (ab)c contra abc. Coincidindo as quatro árvores, a redução está sendo aplicada de forma consistente pelos quatro caminhos. Comparar árvores exige convertê-las a uma forma canônica de texto, e a forma prefixa serve bem.
02_regex.cpp
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 += ')';
}Cada tipo de nó vira um nome fixo seguido dos filhos entre parênteses, e a árvore inteira vira uma cadeia de caracteres. As quatro convergências viram quatro comparações de texto, que rodam sem ninguém olhando.
flowchart LR
A1["a+"] --> P1["concat('a', fecho('a'))"]
A2["aa*"] --> P1
B1["[abc]"] --> P2["alt(alt('a', 'b'), 'c')"]
B2["alternancia de a, b e c"] --> P2
C1["[a-c]"] --> P2
D1["(ab)c"] --> P3["concat(concat('a', 'b'), 'c')"]
D2["abc"] --> P3
Agora o limite dessa verificação, e ele é fácil de atropelar. Sobre \Sigma = \{a, b\}, as expressões (a\mid b)^* e (a^*b^*)^* denotam ambas o conjunto de todas as cadeias sobre esses dois símbolos. São equivalentes pela definição acima. As árvores delas são visivelmente diferentes, e a comparação de texto responde que diferem.
A resposta do comparador está certa para a pergunta que ele faz — “estas duas árvores são a mesma?” — e errada para a pergunta que ele não faz. Ninguém errou ao escrever o comparador; o que falta é a declaração do que ele mede. Ele detecta redução inconsistente, que é o defeito para o qual foi construído, e localiza o problema num caminho específico. Fora disso, devolve conclusões erradas com aparência de medida.
Fica então um terceiro estado, que quem está aprendendo a avaliar sistemas costuma pular. A verificação estrutural responde “são a mesma árvore” ou “são árvores diferentes”. A primeira resposta implica equivalência. A segunda nada implica sobre as linguagens: ela informa que os instrumentos disponíveis não decidem aquela pergunta. A equivalência plena tem resposta, e o caminho é outro. Converta cada expressão na máquina que a reconhece, reduza cada máquina à forma mínima e compare as duas mínimas. Esse procedimento só fica disponível depois dos capítulos de construção e de minimização.
Enquanto isso, alguns pares equivalentes continuam soando errados na primeira leitura. Percorra três. O primeiro é (a^*)^* \equiv a^*: aplicar o fecho ao resultado de um fecho parece dever produzir algo maior, e o conjunto já estava saturado. O segundo é o par (a\mid b)^* \equiv (a^*b^*)^*, cuja intuição resiste porque o lado direito parece impor uma ordem — ele a impõe dentro de cada repetição, e o fecho externo desfaz a ordem inteiramente. O terceiro sai na direção contrária: a^*b^* e (a\mid b)^* não são equivalentes, porque a primeira exige que todo a venha antes de todo b, e ba fica de fora.
O método que resolve os três dispensa intuição. Escreva as cadeias curtas de cada lado, em ordem de comprimento, e compare. Coincidindo até comprimento três ou quatro, a suspeita de equivalência ganha força; divergindo, o contraexemplo está na mão, com nome e sobrenome. A coincidência das listas curtas não demonstra equivalência, e tratá-la como demonstração é justamente o buraco que a comparação de máquinas mínimas vem tapar.
1.7 A teoria em execução: a primeira peça de código
A Peneira, o sistema de referência desta obra, ganha aqui a sua primeira peça: o leitor de expressões de padrão. Ela recebe o texto de um padrão. Devolve a árvore reduzida ao núcleo — ou o primeiro erro, com a posição exata no texto. É pequena, e cada decisão tomada nela reaparece nos quatro capítulos seguintes.
1.7.1 O núcleo escolhido e as reduções registradas
A decisão de núcleo foi registrada como documento. As reduções vão em pares, e as recusas vão justificadas. Esse registro se paga adiante. Alguém vai perguntar por que o coringa não foi reduzido como a classe de símbolos foi. Nenhuma memória precisa ser consultada: a resposta está escrita, com a razão de tamanho ao lado.
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.
Duas entradas do documento merecem sua atenção. Nelas o critério foi aplicado e deu respostas diferentes. O coringa não é reduzido, embora seja redutível. Expandi-lo produziria quase uma centena de folhas por ocorrência sobre o alfabeto de caracteres imprimíveis — exceção tomada por razão de tamanho e registrada com a razão ao lado. Já o quantificador contado foi descartado apesar de passar no critério de redutibilidade, por não acrescentar nada ao que a obra demonstra. Redutibilidade decide o que não entra no núcleo; utilidade decide o que sequer entra na notação.
1.7.2 O leitor de expressões
O analisador é recursivo-descendente e escrito à mão. Uma função por produção da gramática do padrão, sem gerador. A precedência não aparece em tabela nem em comentário. Ela está na ordem em que as produções se chamam: 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_H
02_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 peneira
Duas decisões de implementação que a seção teórica anunciou aparecem aqui concretizadas. Uma é a representação por índice num vetor, no lugar do ponteiro. A árvore fica copiável sem construtor de cópia. Não vaza. E a duplicação que a redução do fecho positivo exige vira cópia de faixa contígua. A outra decisão é de momento: a redução acontece durante a leitura. O que sai daqui já não conhece o fecho positivo, o opcional nem a classe de símbolos, e nenhuma peça posterior precisará aprendê-los.
Um detalhe do analisador resolve um caso concreto que a gramática de partida não previa. A barra invertida retira o significado especial do símbolo seguinte. Ela foi acrescentada por necessidade. O padrão de endereço do exemplo escrito no capítulo anterior precisa de um ponto literal. Sem escape, o ponto seria lido como coringa e o padrão casaria o que não devia. Quando o exemplo cobra uma construção que a gramática não previa, quem cede é a gramática — e a mudança vai registrada no mesmo documento onde a decisão original está.
Dica
A verificação desta peça é a convergência de notações, e ela roda no próprio programa: a árvore de a+ comparada com a de aa*, a de uma classe com a da alternância equivalente, a de uma faixa com a da enumeração, e a de uma expressão agrupada com a da mesma sem parênteses. A comparação é de texto, sobre a forma prefixa canônica — não inspeção visual de duas figuras.
1.7.3 O custo da redução, em números
A mesma demonstração imprime o número de nós de cada árvore. É aqui que a decisão de núcleo deixa de ser retórica. Quanto custa, em nós, o padrão de endereço do capítulo anterior — aqui na forma reduzida, com as três faixas de letras e sem a classe de dígitos e pontuação que o programa de exemplo declarava? Ele 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. Vinte e um caracteres digitados, trezentos e dezoito nós construídos: a árvore ficou mais de quinze vezes maior que o texto, e nada de errado aconteceu.
Ver o número é o que transforma “a redução tem custo” de afirmação em fato. É a primeira vez no percurso em que uma decisão de projeto vira medida. Instrumente o seu sistema para reportar esse tamanho. Faça isso desde a primeira versão. Sem esse número, uma decisão inocente de notação encarece cada peça posterior e você não percebe.
Sobre a recusa do malformado, a demonstração exibe quatro expressões inválidas seguidas. A primeira não interrompe as outras. O analisador devolve um resultado que ou traz a árvore ou traz o erro, em vez de lançar exceção. Numa expressão com grupo não fechado, o cursor cai no fim do texto, e não no parêntese que abriu. É lá que a falta se constata, e é lá que você põe o parêntese que faltou.
1.8 O saldo: a expressão descreve, e ainda não reconhece
Metade da dívida do capítulo anterior fica paga aqui; a outra metade continua exatamente onde estava.
A expressão regular é a descrição finita que faltava: uma linha de texto que decide sobre um conjunto infinito de entradas, com sintaxe própria, semântica própria e uma classe de linguagens que leva o nome dela. Essa parte está saldada.
A outra parte não andou um passo. Nada do que foi escrito aqui decide coisa alguma sobre uma entrada concreta. Diante de uma expressão e de uma cadeia, a definição da linguagem denotada diz qual é a resposta certa e não diz como obtê-la. Calcular L(r) para uma expressão com fecho significaria construir um conjunto infinito, que é a operação que o capítulo anterior já mostrou não caber em memória nenhuma.
flowchart LR
E["Expressao regular:<br/>descricao finita do infinito"] --> A["Arvore reduzida<br/>ao nucleo"]
A -.->|"falta"| M["Maquina deterministica<br/>definida e executada"]
M -.->|"falta"| C["Construcao que le<br/>a arvore e desenha a maquina"]
C -.->|"falta"| Z["Reducao da maquina<br/>ao menor tamanho"]
Z ==> Q["Equivalencia plena,<br/>enfim decidivel"]
Falta uma máquina que leia a cadeia símbolo a símbolo, mude de estado a cada leitura e devolva resposta em tempo proporcional ao comprimento da entrada. Ela chega em ordem específica: primeiro a máquina determinística, mais simples de definir e de executar; depois a construção que transforma qualquer expressão numa máquina; depois o procedimento que reduz a máquina ao menor tamanho possível.
Fica daqui um critério de decisão que serve além destas páginas, e ele encurta discussão de projeto. Diante de qualquer proposta de acrescentar um operador a uma notação de padrões, faça duas perguntas nesta ordem. É possível escrever esse operador compondo os que já existem? Sendo possível, ele é açúcar, e o custo dele é o número de nós que a redução produz — mensurável, e portanto negociável. Ele exige lembrar um trecho da entrada cujo tamanho não tem teto? Exigindo, ele sai da classe, e o que se perde junto é a garantia de tempo sobre todos os padrões que compartilham o mesmo motor.
O mesmo par de perguntas julga um requisito antes de ele virar código, e é ali que rende mais. Um requisito escrito em português que peça aninhamento sem teto, ou a repetição de um trecho de tamanho livre, responde sim à segunda pergunta. Descobrir isso enquanto o requisito é só um texto custa uma conversa; descobrir depois custa a fase inteira. Quase todo operador de uso corrente responde sim à primeira pergunta e não à segunda, e é o que torna a notação escrita em 1951 para descrever redes de neurônios ainda suficiente três quartos de século depois.
1.8.1 A máquina que a árvore ainda espera
A árvore que sai do leitor de expressões da Peneira não decide nada. Ela é uma estrutura na memória, reduzida ao núcleo, pronta para ser lida por outra peça — e essa outra peça é a que falta. O objeto que o compilador da Peneira grava em disco é um vetor de tabelas de transição, uma por pattern declarado, e nenhuma dessas tabelas existe ainda.
A ordem em que elas passam a existir é a ordem dos capítulos seguintes. Primeiro a máquina determinística, definida e executada sobre entradas escritas à mão, sem nenhuma expressão envolvida. Depois a construção que percorre a árvore deste capítulo e produz uma máquina a partir dela — e é ali que a decisão de clonar em vez de compartilhar subárvore cobra ou perdoa. Depois a redução da máquina ao menor tamanho possível, que é o que torna o vetor de tabelas gravável sem desperdício.
Antes de virar a página, faça uma coisa com o seu próprio sistema. Pegue o padrão mais longo que a sua especificação prevê, escreva-o na notação completa, e depois reescreva-o usando somente concatenação, alternância e fecho. Conte os nós dos dois lados. O primeiro número mede o que você digita; o segundo mede o que a próxima peça vai ter de percorrer, estado por estado. A distância entre os dois é a conta deste capítulo, e ela reaparece multiplicada quando a árvore virar máquina.
O que segue é o que cabe a você construir com a notação desta etapa. Duas dessas tarefas não pedem uma linha de código, e são justamente as que decidem o tamanho de tudo o que vem depois.
Tarefa 1: Escrever a especificação do que você vai construir
Escolha um dos assuntos propostos e escreva, por extenso, o que o seu sistema fará. O documento é em Markdown, fica versionado junto do código e é o texto ao qual você voltará em todos os capítulos seguintes para conferir se o que está construindo ainda é o que pretendia construir.
A escolha do assunto é a decisão mais cara de desfazer do percurso inteiro. Trocá-lo no meio custa o que já foi construído; testá-lo aqui, enquanto ele é só um texto, custa uma tarde. Assunto próprio, fora dos propostos, é aceito desde que a especificação responda às perguntas que fecham a lista de propostas — todas, por escrito.
O vocabulário desta tarefa. Faltam doze capítulos para os termos abaixo ganharem a definição precisa. Aqui basta a versão curta, que é o suficiente para escrever o documento.
Padrão — a descrição de uma forma que trechos da entrada podem ter. Entrada — o texto ou a sequência que o sistema lê e examina. Reconhecer — decidir se um trecho da entrada tem a forma que um padrão descreve. Regra — o que o sistema faz quando reconhece algo. Aninhamento — uma construção que contém outra do mesmo tipo por dentro, sem limite fixo de profundidade. Objeto — o arquivo que o tradutor grava ao terminar, contendo o que a máquina precisa para trabalhar. Execução — o momento, posterior e separado, em que outro componente lê o objeto e o roda sobre uma entrada. Verificação — o exame que o tradutor faz antes de gravar o objeto, e que pode recusar o que está escrito.
Sete seções compõem o documento. Cada uma responde a uma pergunta, e cada uma tem um sinal característico de que saiu errada.
1. O domínio e a cena. Pergunta: sobre o que fala a sua linguagem, e quem se beneficiaria de escrevê-la? Descreva o domínio, a pessoa que escreveria algo nessa linguagem e o que ela quer obter. Sinal de erro: a seção descreve um programa em vez de um domínio — se ela fala em arquivos, laços e estruturas, ainda não chegou à cena.
2. O que se escreve na linguagem. Pergunta: como é, na prática, um texto escrito nela? Mostre de três a cinco exemplos completos, inventados por você, do mais simples ao mais elaborado. Escreva-os como se a linguagem já existisse. Sinal de erro: os exemplos são todos variações do mesmo formato — sinal de que a linguagem tem uma construção só, e uma construção só não sustenta o percurso.
3. O que o sistema aceita e o que recusa. Pergunta: dado um texto qualquer, o que faz dele válido? Descreva as formas aceitas e, para cada tipo de erro previsível, o que o sistema responde — a mensagem que a pessoa recebe e o que ela consegue fazer com essa mensagem. Sinal de erro: a seção lista o que é aceito e cala sobre o inválido. Metade do uso real de qualquer linguagem é descobrir por que o que se escreveu não funcionou.
4. Onde a linguagem se aninha. Pergunta: que construção da sua linguagem contém outra do mesmo tipo por dentro, sem profundidade máxima? Aponte-a e mostre um exemplo com três níveis. Sinal de erro: não existe nenhuma. Uma linguagem cujos comandos são todos de formato fixo dispensa metade do que este percurso ensina, e a lacuna aparecerá tarde, quando já houver código escrito.
5. O que se verifica antes de rodar. Pergunta: que texto está bem escrito e mesmo assim não faz sentido? Descreva os erros que o sistema apanha antes de executar qualquer coisa: um nome usado sem ter sido declarado, dois valores de naturezas incompatíveis combinados, uma referência a algo que não existe. Nomeie as naturezas de valor que a sua linguagem distingue. Sinal de erro: todos os valores são da mesma natureza e nada pode ser usado errado. Sem incompatibilidade possível, não há o que verificar.
6. O que o sistema produz, e quem executa. Pergunta: o que fica gravado quando o tradutor termina, e quem lê aquilo depois? Descreva o objeto produzido — o que ele contém, em que ordem — e o componente separado que o lê e o executa sobre uma entrada, possivelmente noutro momento, com o tradutor já encerrado. Sinal de erro: a resposta é “o sistema mostra o resultado”. Mostrar o resultado na hora é uma coisa; gravar um objeto que outra coisa executa depois é outra, e é a segunda que este percurso constrói.
7. A pergunta que você vai responder medindo. Pergunta: que dúvida sobre o seu sistema não se resolve olhando, só medindo? Escreva a pergunta, a grandeza que a responde, a abordagem de referência contra a qual ela será comparada e — este é o campo que se costuma pular — o resultado que contrariaria a sua expectativa. Sinal de erro: a pergunta tem resposta conhecida antes da medida, ou a comparação é contra nada. Qualquer coisa ganha do vazio.
O que a especificação não pede, e por bom motivo. Nada de arquitetura, estrutura de dados, biblioteca ou algoritmo. Faltam doze capítulos para essas decisões terem base, e antecipá-las produz um documento copiado de fora que ninguém entende e ninguém segue. Descreva comportamento: o que existe na cena, o que a pessoa faz, o que o sistema aceita, o que recusa e como avisa.
Duas restrições valem sobre qualquer assunto escolhido, e ambas já foram enunciadas. Nenhum gerador automático de analisador entra no sistema: o reconhecimento nasce de máquinas construídas à mão, e essa é a razão de o percurso existir. E o sistema tem de funcionar sem depender do sistema operacional de quem o compila — nada de recurso exclusivo de uma plataforma.
Vale reler a especificação pronta procurando o assunto que parece bom e falha: 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. Os quatro passam despercebidos na leitura entusiasmada da própria proposta, que é a única leitura que ela recebe antes de o código começar.
Tarefa 2: Escolher o núcleo mínimo de operadores
Decida quais operadores de padrão o seu 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. Registre a decisão junto com as reduções, na forma de pares que mostrem a notação de partida e a expressão equivalente no núcleo.
O critério de inclusão é a impossibilidade de reduzir. Um operador que se exprime pela composição de outros é conveniência de quem escreve o padrão, não capacidade nova do sistema — e mantê-lo no núcleo multiplica por três o trabalho de cada capítulo seguinte em troca de nada.
Tarefa 3: Ler a expressão e convertê-la em árvore
Implemente 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. Esta é a primeira peça de código do sistema, e o primeiro ponto em que uma decisão de representação passa a ter consequência: a árvore produzida aqui é exatamente o que a construção da máquina consumirá no capítulo seguinte.
A tarefa se cumpre quando duas notações diferentes para o mesmo padrão convergem para a mesma estrutura. Essa convergência é 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.
Tarefa 4: Recusar a expressão malformada com a posição do problema
Faça 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. Trate esta tarefa como requisito técnico e não como 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.