%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
T["uma linha da entrada"] --> P0["tentativa a partir da posição 0"]
P0 --> R0{"casou até o fim?"}
R0 -->|"não"| V0["volta atrás e redistribui<br/>o que cada parte consumiu"]
V0 --> P0
R0 -->|"esgotou as divisões"| P1["tentativa a partir da posição 1"]
P1 --> R1{"casou até o fim?"}
R1 -->|"não"| V1["volta atrás de novo"]
V1 --> P1
R1 -->|"esgotou as divisões"| PN["e assim até a última posição"]
PN --> C["o trabalho cresce com o cubo<br/>do comprimento da linha"]
1 Expressões regulares e linguagens regulares
Sete caracteres derrubaram um serviço mundial em 2019, e a notação que os escreveu já tinha 68 anos.
Este é o capítulo de uma notação que quase todo mundo usa sem definição. Aqui ela ganha sintaxe, semântica e limite, nessa ordem. Leia com papel ao lado: as contas de tamanho de árvore se conferem à mão em dois minutos, e uma delas contraria o que a intuição promete.
Escreva a* num papel. São duas posições: uma letra e um asterisco. O conjunto que elas descrevem começa na cadeia vazia, segue por a, aa, aaa, e você não termina de escrevê-lo. É por essa desproporção que a notação existe. Duas posições contra um conjunto sem fim.
O capítulo anterior parou exatamente aqui. Lá uma linguagem era guardada por extenso, como lista, e a lista quebrou na primeira operação que produz infinitos elementos. O que entra no lugar da lista é um texto curto. E a pergunta vem em seguida: que conjunto, precisamente, um texto curto desses descreve?
Antes de responder, uma advertência de vocabulário que vale o capítulo inteiro. A expressão descreve um conjunto. Ela não lê entrada nenhuma, não percorre texto e não responde sim ou não sobre cadeia alguma. Quem responde é uma máquina, e a máquina só aparece daqui a dois capítulos. Troque os dois verbos e três capítulos de construção de autômato ficam sem explicação, entre este ponto e o primeiro reconhecedor que funciona.
1.1 Sete caracteres, quarenta e seis anos depois da solução
A notação prometia decidir numa passada; o motor que a executava tinha escolhido outro caminho.
Em 2 de julho de 2019, a Cloudflare publicou um relatório assinado por John Graham-Cumming sobre uma pane nos seus serviços. No centro do relato havia um fragmento de expressão regular com sete caracteres: .*.*=.*. Sete. O fragmento não tem defeito nenhum enquanto notação, e descreve um conjunto perfeitamente comum: qualquer coisa, seguida de qualquer coisa, seguida de um sinal de igual, seguido de qualquer coisa.
O problema mora em quem executa. Um motor que experimenta divisões, uma de cada vez, precisa decidir onde termina o primeiro trecho livre e onde começa o segundo. As duas fronteiras são independentes, sobre a mesma linha.
Siga o desenho e a conta aparece sozinha. Para cada posição de partida, o motor tenta cada divisão possível entre os dois primeiros trechos. Depois refaz o trabalho inteiro na posição seguinte. É o cubo do comprimento da linha: dobre a linha e o trabalho fica oito vezes maior.
Pois é: sete caracteres.
Agora recue 68 anos. Em dezembro de 1951, Stephen Kleene entregou à RAND Corporation um memorando de nome burocrático, RM-704. O assunto declarado eram redes de neurônios: que sequências de estímulos um arranjo de células nervosas consegue separar das demais. Para falar de conjuntos de sequências, e não de sequências avulsas, Kleene inventou uma notação de três operadores. O texto saiu impresso em 1956, na coletânea Automata Studies, organizada por Claude Shannon e John McCarthy. Não há uma linha ali sobre procurar palavra dentro de arquivo.
Dezessete anos separam aquele memorando do primeiro programa que usou a notação para vasculhar texto. Em junho de 1968, as Communications of the ACM publicaram quatro páginas de Ken Thompson, então com 25 anos, nos Bell Labs: Regular Expression Search Algorithm. O programa descrito ali lia uma expressão regular e escrevia, a partir dela, código de máquina do IBM 7094 para procurar aquele padrão. Ele compilava a expressão em vez de interpretá-la, e o que saía dali rodava direto na máquina.
O que o método garante interessa mais do que a emissão de código. Tome a expressão a*ab e a cadeia aaab. Conte de quantas maneiras dá para repartir aquela cadeia entre as três partes da expressão. O fecho pode consumir nenhum a, um, dois ou três: quatro divisões, e só uma termina bem. Um método que as experimenta uma a uma testa, falha, recua e testa de novo. O de 1968 não escolhe. Ele carrega todas as divisões ao mesmo tempo, como um conjunto de pontos ativos dentro da expressão, e faz o conjunto inteiro avançar um caractere por vez.
Cinco anos depois a técnica saiu do laboratório quase por acidente. Em 1973, a pedido de Doug McIlroy, o mecanismo de busca por expressão que morava dentro do editor ed foi extraído e virou programa próprio, o g/re/p. Deixou de ser recurso de uma ferramenta e passou a ser ferramenta. Quarenta e seis anos depois disso é que sete caracteres derrubaram um serviço mundial — e não por falta de técnica publicada.
A garantia é da classe; a entrega é da implementação.
A frase separa duas afirmações que costumam sair coladas. “Expressões regulares são lentas” fala da classe, e é falsa. “Aquele motor, sobre aquele padrão, ficou lento” fala de uma implementação, e pode ser verdadeira. Quem confunde as duas troca de tecnologia quando devia trocar de motor.
1.1.1 O sistema que vai receber a primeira peça de código
O sistema de referência que acompanha estas páginas chama-se Peneira. É uma linguagem pequena em que se declaram padrões sobre texto e se escrevem regras que reagem ao casamento desses padrões. O compilador dela não produz código de máquina: produz um motor de autômatos, um por padrão declarado, mais um bytecode curto para cada regra. Ela existe para ser estudada, e não copiada — o sistema que você construir é seu, sobre o domínio que escolher.
Até aqui a Peneira era só descrição. Havia o recorte da linguagem escrito à mão, a gramática registrada na forma de partida, um programa de exemplo com dois padrões e uma regra sobre cada um. Nenhuma linha daquilo era lida por programa algum. A partir deste ponto isso muda, e o que muda é exatamente o assunto deste capítulo.
O primeiro dos nove módulos da Peneira lê a mini-notação de padrões e devolve a árvore correspondente. É a peça que consome o texto que aparece entre barras numa declaração de pattern, e é a primeira do sistema a existir como código. As seis cláusulas, a precedência que decide o encaixe, a redução ao núcleo e a recusa com posição aparecem todas ali dentro. A forma que elas tomam é um analisador recursivo-descendente — uma função por construção da notação, chamando-se na ordem que instala a precedência — escrito por inteiro, sem gerador.
Há uma razão de arquitetura para essa peça vir primeiro, e ela se colhe ao longo de todo o percurso. Os padrões que quem usa a linguagem declara viram autômatos finitos. Os símbolos da própria Peneira — as palavras pattern, rule, where, os parênteses, os identificadores — também são reconhecidos por autômatos finitos, construídos pelo mesmo maquinário. A mesma peça serve os dois níveis, e é essa dupla aparição que impede a teoria de autômatos de virar preâmbulo esquecível de uma caixa fechada.
Uma decisão do recorte volta a ter peso aqui, agora com o argumento da cerca na mão. A Peneira recusa retrovisão, e a recusa está escrita desde o primeiro documento do sistema. O motivo, que naquele momento era uma promessa, já foi dito: um padrão com retrovisão não pode ser compilado para autômato finito, e o produto do compilador da Peneira é justamente um vetor de autômatos finitos.
1.2 Que texto é uma expressão, e que encaixe ele esconde
O significado de um padrão não sai da ordem dos caracteres: sai do encaixe que a leitura constrói a partir deles.
Enquanto a resposta a essa pergunta for “eu reconheço quando vejo”, não há como escrever o programa que lê o padrão. E é esse programa que produz o objeto de que todas as peças seguintes vão precisar. A resposta vem por indução, na forma de sempre neste assunto: alguns objetos são expressões por decreto, umas poucas regras fabricam expressões novas a partir das existentes, e uma última frase fecha a porta.
NotaDefinição — Expressão regular sobre um alfabeto
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.
Conte: três casos de base e três de composição, seis ao todo. Sobre \Sigma = \{a, b\}, o texto a entra pela terceira cláusula, (a|b) pela quarta e ((a|b)*) pela sexta. Cada objeto novo carrega o histórico de como foi construído, e é desse histórico que sai a árvore.
Agora o que a definição não exige, que é a metade costumeiramente pulada. Ela não pede que o operando de um fecho seja não vazio. A cláusula de composição vale para toda expressão r, e \emptyset é uma delas, de modo que (\emptyset^*) é texto bem formado por mais estranho que soe. Ela também não promete que expressões diferentes descrevam conjuntos diferentes, e não diz uma palavra sobre tamanho. Guarde o caso do fecho sobre o vazio: ele volta a morder na seção seguinte.
1.2.1 A convenção que decide a forma da árvore
Vamos por partes. Escreva a|bc e pergunte-se o que foi escrito. Ou é a alternativa entre a e a concatenação bc, ou é a concatenação entre a alternativa a|b e o símbolo c. As duas leituras cabem nos mesmos quatro caracteres. A primeira descreve a e bc; a segunda descreve ac e bc. Uma convenção precisa decidir, ou o texto não significa nada.
A convenção é a de sempre. O fecho amarra mais forte que a concatenação, e a concatenação amarra mais forte que a alternância. Sob ela, a|bc é a alternativa, e quem quiser a outra leitura escreve (a|b)c. Os parênteses existem para isso e só para isso.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TB
subgraph A["a|bc"]
A1(("alternância"))
A2(("'a'"))
A3(("concatenação"))
A4(("'b'"))
A5(("'c'"))
A1 --> A2
A1 --> A3
A3 --> A4
A3 --> A5
end
subgraph B["(a|b)c"]
B1(("concatenação"))
B2(("alternância"))
B3(("'c'"))
B4(("'a'"))
B5(("'b'"))
B1 --> B2
B1 --> B3
B2 --> B4
B2 --> B5
end
NotaDefinição — Árvore sintática de uma expressão regular
Uma árvore é um conjunto finito de nós em que cada nó tem uma sequência ordenada de filhos e em que todo nó, exceto um — a raiz —, é filho de exatamente um outro nó. Nó sem filhos chama-se folha, e a subárvore de um nó é esse nó com todos os seus descendentes. A árvore sintática de uma expressão regular r segue a mesma indução da definição anterior: as três expressões de base viram folhas rotuladas com o próprio símbolo; (s \mid t) e (st) viram uma raiz rotulada com o operador, tendo por filhos, nessa ordem, as árvores de s e de t; e (s^*) vira uma raiz de um filho só. Duas expressões têm a mesma árvore quando os rótulos e a ordem dos filhos coincidem em todos os nós.
A precedência precisa morar em algum lugar do programa que lê a expressão, e há duas maneiras de instalá-la. Uma é a tabela de prioridades, consultada a cada operador. Outra é a ordem em que as funções de leitura se chamam: a que trata alternância chama a que trata concatenação, que chama a que trata repetição, que chama a que trata o átomo. Quem desce primeiro amarra menos forte.
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;
}
DicaNo código
A ordem das chamadas é a única cópia da precedência neste programa. A função da alternância pede uma concatenação antes de procurar a barra vertical, e é isso — e só isso — que faz o fecho amarrar mais forte do que a concatenação. A tabela de prioridades resolveria igual hoje e deixaria a mesma regra escrita em dois lugares; na primeira mudança de gramática, um dos dois ficaria para trás sem aviso.
1.2.2 O parêntese que some, e o clone que precisa existir
Cinco expressões, da menor à maior, com a árvore em forma linear e a contagem de nós ao lado. A forma linear escreve o rótulo da raiz seguido dos filhos entre parênteses, o que permite comparar duas árvores como se comparam dois textos.
| Expressão | Árvore, em forma linear | Nós |
|---|---|---|
a |
'a' |
1 |
ab |
concat('a', 'b') |
3 |
a|bc |
alt('a', concat('b', 'c')) |
5 |
(a|b)*c |
concat(fecho(alt('a', 'b')), 'c') |
6 |
(ab|c)*d[0-2]? |
concat(concat(fecho(alt(concat('a', 'b'), 'c')), 'd'), alt(alt(alt('0', '1'), '2'), vazio)) |
16 |
A primeira linha é a mais informativa das cinco e passa despercebida. O símbolo a atravessa quatro níveis de leitura — alternância, concatenação, repetição, átomo — e nenhum deles cria nó. Um nó nasce quando há operador de verdade, não quando uma função é chamada. A segunda linha traz o operador que ninguém digitou: em ab não existe símbolo de concatenação, e mesmo assim há um nó de concatenação ali. A justaposição é o operador invisível da notação, e quem lê o padrão tem de inventá-lo ao juntar dois átomos vizinhos.
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;
}
DicaNo código
O acumulador entrega a resposta: ele parte do fator mais à esquerda e pendura cada novo fator por cima do que já tinha juntado. Daí abc sair como concat(concat('a', 'b'), 'c'), e não com o agrupamento invertido. A definição da notação não escolhe entre os dois agrupamentos, porque os dois denotam o mesmo conjunto; o programa tem de escolher, e a escolha fica gravada na forma da árvore, sem nenhuma outra cópia que possa contradizê-la.
A quarta linha da tabela responde a uma pergunta de custo que costuma ficar sem resposta. (a|b)*c tem sete caracteres, dois deles parênteses, e produz seis nós: os dois parênteses custam zero. Orientaram a leitura, mudaram o encaixe e não deixaram vestígio. Daí (ab)c e abc produzirem a mesma cadeia de rótulos na mesma ordem. Depois que a árvore existe, a estrutura é a precedência, e um nó de agrupamento não teria o que guardar.
Há um caso em que a árvore precisa duplicar material, e o erro correspondente é silencioso. Um trecho pode aparecer duas vezes na estrutura, uma vez direto e outra sob um fecho. A tentação é apontar as duas posições para o mesmo lugar e economizar memória. A contagem de nós fica menor do que a esperada, e menor parece bom.
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;
}
DicaNo código
Copiar a subárvore, em vez de apontar para ela, evita um defeito que só aparece dois capítulos adiante. Compartilhar o nó faria dele filho de dois pais, e a definição acima proíbe isso: o que nasceria seria um grafo, não uma árvore. O percurso que constrói a máquina passaria duas vezes pelo mesmo trecho e ligaria uma porção só de máquina onde deveriam existir duas passagens distintas. A máquina sai errada, e o defeito aparece longe da linha que o causou.
Falta o texto que não é expressão. Quatro formas de malformação cobrem quase tudo o que se escreve por engano. O grupo que não fecha, como a(b|c. O operador de repetição sem nada a que se aplicar, como *ab. A classe sem o colchete final, como [a-z. E o símbolo que sobra depois do fim, como ab)c. Nos quatro casos a recusa precisa vir com uma posição, ou quem escreveu o padrão procurará o defeito à mão.
E a posição a reportar é aquela em que o problema é, que nem sempre coincide com aquela em que o leitor está. Em a(b|c, o cursor cai no fim do texto, e não no parêntese que abriu. Parece contraintuitivo até você perguntar onde a pessoa vai digitar a correção: no fim. É ali que a falta se constata, e é ali que ela se conserta.
Duas construções parecem malformadas e não são. A barra invertida retira o significado especial do símbolo seguinte, e sem ela não há como exigir um ponto literal dentro de um padrão. Já a** e a+* são apenas redundantes: a definição de fecho tolera ser aplicada sobre o próprio resultado. Recusá-los exigiria uma regra a mais para proibir o inofensivo, e mensagem de erro que proíbe o inofensivo ensina quem lê a desconfiar das que importam.
1.3 Que conjunto exatamente você acabou de escrever
Duas posições de texto podem descrever um conjunto sem fim; dez posições podem descrever um conjunto com um elemento só.
A definição da seção anterior diz quais textos são expressões e não diz o que eles significam. São duas perguntas separadas, e a segunda se responde com a mesma indução da primeira. Se a expressão foi construída por composição, a linguagem dela se calcula a partir das linguagens das partes.
1.3.1 O cálculo que sobe pela árvore
As três operações que a semântica invoca chegam prontas do capítulo anterior, sobre conjuntos de cadeias: união, concatenação e fecho. O que a definição abaixo faz é amarrar cada construção da notação a uma delas.
NotaDefinição — A linguagem denotada
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)^*.
Calcule sobre a árvore de (a|b)c, de baixo para cima. As folhas a e b denotam \{a\} e \{b\}. A alternância acima delas denota a união, \{a, b\}. A folha c denota \{c\}. A concatenação na raiz forma todos os pares, um de cada lado, e emenda cada par numa cadeia: sai \{ac, bc\}.
Repare: nenhuma etapa desse cálculo voltou a olhar o texto original.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart BT
F1(("'a'")) --> A(("alternância"))
F2(("'b'")) --> A
A --> C(("concatenação"))
F3(("'c'")) --> C
F1 -.->|"denota"| L1["{a}"]
F2 -.->|"denota"| L2["{b}"]
F3 -.->|"denota"| L3["{c}"]
A -.->|"denota"| L4["{a, b}"]
C -.->|"denota"| L5["{ac, bc}"]
Refaça o cálculo sobre (a|b)* e veja o fecho entrar em ação. A subárvore da alternância denota \{a, b\}, como antes. O fecho reúne as potências dessa linguagem a partir da de expoente zero: a potência zero é \{\varepsilon\}, a primeira é \{a, b\}, a segunda é \{aa, ab, ba, bb\}. Cada andar dobra a contagem do anterior, e a reunião de todos eles é o conjunto de todas as cadeias sobre dois símbolos. Quatro caracteres de texto, um conjunto que a enumeração nunca alcança.
O que a definição não promete contraria o costume de quem usa a notação por hábito. Ela não garante que expressões diferentes denotem conjuntos diferentes. Não diz se o conjunto é finito ou infinito. E não promete relação alguma entre o tamanho do texto e o tamanho do conjunto: a* tem duas posições e denota um conjunto sem fim, enquanto abcdefghij tem dez posições e denota um conjunto com um elemento.
1.3.2 O vazio, o nada e a cadeia vazia
Duas das seis cláusulas produzem objetos que quase todo mundo confunde. A expressão \emptyset denota o conjunto sem elementos. A expressão \varepsilon denota o conjunto cujo único elemento é a cadeia sem símbolos. Escreva as cardinalidades lado a lado e a distância aparece: zero elementos de um lado, um elemento do outro.
A diferença tem consequência operacional, e ela aparece na concatenação. Concatenar com \emptyset aniquila: para formar um par é preciso um elemento de cada lado, e do lado vazio não há elemento nenhum. Concatenar com \varepsilon preserva, porque emendar uma cadeia com outra sem símbolos devolve a própria cadeia. Um multiplica por zero; o outro multiplica por um. Na prática, é a mesma aritmética de sempre, com conjuntos no lugar de números.
Pergunta para levar adiante. O que acontece com um programa que troca essas duas folhas por engano? Responda antes de seguir, e depois compare com o parágrafo abaixo.
Veja bem o estrago. O programa recusa tudo, e não reclama de nada. A leitura funciona, a árvore é construída, o cálculo desce pela estrutura e devolve o conjunto vazio na raiz. Fica um sistema que compila, roda, não acusa erro algum e não aceita cadeia alguma. O sintoma não aparece na linha responsável, porque ela está correta em tudo o mais.
O caso mais sedutor é outro, e é aquele que ficou pendurado na seção anterior: quanto vale L(\emptyset^*)? A resposta que se apresenta sozinha é que o fecho de um conjunto sem elementos não tem o que produzir, logo o resultado é vazio. O raciocínio parece impecável e está errado. O fecho reúne as potências a partir da de expoente zero, e a potência zero de qualquer linguagem é \{\varepsilon\}, inclusive a da vazia. Portanto L(\emptyset^*) = \{\varepsilon\}, um conjunto de um elemento.
Existe ainda uma leitura errada que vem de fora da notação, e é a mais teimosa das três. Em muitos campos de busca de arquivos o asterisco significa “qualquer coisa”, e quem chega com esse hábito lê a* como “um a seguido de qualquer coisa”. A definição acima diz outra coisa: a* denota apenas cadeias formadas por a. A convenção veio de fora, ninguém pediu para desinstalá-la, e ela permanece ativa até alguém apontá-la.
Com as duas definições no lugar, a classe se define numa linha. Ela não fala de máquina, não fala de gramática e não fala de algoritmo.
NotaDefinição — Linguagem regular
Uma linguagem L \subseteq \Sigma^* é regular quando existe uma expressão regular r sobre \Sigma tal que L(r) = L.
Repare no que ela pede e no que não pede. Pede existência, não construção: uma linguagem é regular quando há uma expressão que a denote, mesmo que ninguém saiba exibi-la. Não pede unicidade, e é essa ausência que torna necessária a subseção seguinte. E não menciona autômato nenhum, o que é restrição temporária deste ponto do percurso.
O menor exemplo é qualquer linguagem finita. Tome L = \{ab, c\}: a expressão ab|c a denota. O argumento se repete para toda linguagem finita, escrevendo a alternância de todas as cadeias dela, uma a uma. É um argumento sem graça, e ele volta com juros na seção do fechamento. O conjunto das cadeias sobre \{a, b\} que terminam em b também é regular, denotado por (a|b)*b. Já o das que têm o mesmo número de a e de b fica fora do alcance da notação, e a razão vem adiante.
1.3.3 Duas escritas, o mesmo conjunto
Como a definição pede existência e não unicidade, nada impede que duas expressões diferentes denotem exatamente a mesma linguagem. Isso levanta uma questão operacional que atravessa o resto do percurso.
NotaDefinição — Equivalência de expressões
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 frase final merece releitura, porque ela adverte contra o atalho que vem a seguir. O atalho existe e é barato: depois da redução ao núcleo, duas escritas diferentes da mesma coisa frequentemente convergem para a mesma árvore.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
P1["a+"] --> T1["concat('a', fecho('a'))"]
P2["aa*"] --> T1
P3["[abc]"] --> T2["alt(alt('a','b'), 'c')"]
P4["a|b|c"] --> T2
P5["[a-c]"] --> T2
P6["(ab)c"] --> T3["concat(concat('a','b'), 'c')"]
P7["abc"] --> T3
O primeiro par é a+ contra aa*, e os dois chegam a concat('a', fecho('a')). O segundo é [abc] contra a|b|c. O terceiro acrescenta [a-c] ao mesmo destino, o que mostra a faixa como açúcar sobre a enumeração, que por sua vez é açúcar sobre a alternância. O quarto é (ab)c contra abc, e a convergência confere que o grupo não sobreviveu à leitura. A comparação precisa de uma forma canônica que sirva de texto.
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 += ')';
}
DicaNo código
Comparar árvores vira comparar textos, e é esse o serviço do percurso. Ele escreve o rótulo da raiz, abre parênteses, desce à esquerda, põe a vírgula, desce à direita e fecha. Duas árvores iguais produzem a mesma cadeia de caracteres; duas diferentes produzem cadeias diferentes. O olho falha justamente no caso difícil, em que duas estruturas grandes diferem num nó no meio; a comparação de cadeias não falha em caso nenhum.
Só que essa verificação prova menos do que o nome sugere. Ela detecta a equivalência que vem da redução, e nada além. O par de referência é (a \mid b)^* contra (a^*b^*)^*: as duas denotam todas as cadeias sobre dois símbolos, com árvores completamente diferentes. Tome ba. Na primeira, ela sai escolhendo b e depois a. Na segunda, sai em duas voltas, com o bloco de a vazio na primeira e o de b vazio na segunda, porque o fecho admite expoente zero.
Submetido a esse par, o comparador responde que as árvores diferem. A resposta está certa para a pergunta que ele faz e errada para a pergunta que não lhe foi feita. Concluir dali que as duas denotam linguagens diferentes é caro justamente porque a ferramenta parece ter dado um veredito sobre linguagens. Um segundo caso mostra o mesmo com menos disfarce: a|a e a denotam a mesma linguagem, e têm três nós contra um.
A equivalência plena tem resposta, e ela passa por converter cada expressão em máquina, reduzir cada máquina ao menor tamanho e comparar as duas mínimas. Todo esse maquinário existe, é mecânico, e está a três capítulos daqui.
Alguns pares equivalentes são difíceis de acreditar, e outros são difíceis de recusar. Comece por (a^*)^* \equiv a^*: aplicar o fecho sobre algo que já está sob fecho parece que deveria produzir mais coisa, e não produz, porque o conjunto já estava saturado. Agora o par que engana mais, e ele vem logo depois do anterior: a^*b^* e (a \mid b)^* não são equivalentes, porque a cadeia ba pertence à segunda e não à primeira. Um quarto par fecha a série: a* e a+ diferem por um único elemento, a cadeia vazia — a diferença mais fácil de perder de vista, porque a cadeia vazia sai impressa como nada, e nada dentro de uma lista some.
O procedimento que resolve os quatro casos é sempre o mesmo, e ele não é olhar. Exiba uma cadeia que esteja num conjunto e não no outro, ou mostre que qualquer cadeia de um se constrói no outro. ba resolveu o terceiro caso em duas letras, e a cadeia vazia resolveu o quarto sem gastar nenhuma.
1.4 Três operadores, duas folhas e uma exceção com a razão escrita
Vinte e seis letras cabem em três caracteres digitados e custam 51 nós de árvore.
A notação de Kleene tem três operadores. A notação que qualquer ferramenta oferece hoje tem uns dez, contando classes de símbolos, faixas, o fecho positivo, o opcional, o coringa e o quantificador contado. As duas listas têm o mesmo poder de descrição: tudo o que a longa escreve, a curta também escreve, com mais caracteres. Sabendo disso, a pergunta que sobra é de projeto. Quantos desses operadores o programa que lê o padrão precisa tratar?
1.4.1 O núcleo se decide por uma recusa
A primeira resposta tentadora é tratar todos. Cada operador ganha o seu caso, cada caso ganha o seu tipo de nó, e a árvore fica parecida com o texto que a originou. Funciona no primeiro dia. Quebra no capítulo seguinte, porque cada tipo de nó reaparece em cada peça construída depois.
Faça a aritmética com números para sentir o tamanho da diferença. As três peças que vêm a seguir percorrem a árvore e precisam de um caso por tipo de nó: a construção da máquina, a determinização e a redução ao menor tamanho. Com o núcleo, cada uma trata três casos internos, o que dá nove trechos de código ao todo. Sem ele, cada uma trata oito, o que dá vinte e quatro. Cada um desses vinte e quatro é um lugar onde um defeito pode nascer.
Veja só: nove trechos de código contra vinte e quatro.
A segunda tentativa inverte o critério. Em vez de perguntar o que é conveniente tratar, pergunte o que é impossível reduzir. Um operador que se exprime pela composição de outros não acrescenta capacidade nenhuma ao sistema: acrescenta comodidade a quem digita. Aplicado com honestidade, esse critério deixa de pé três operadores e duas folhas.
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;
};
DicaNo código
O vocabulário inteiro de um nó cabe em seis rótulos, não cinco. Concatenação, alternância e fecho são os três operadores. Símbolo e cadeia vazia são as duas folhas. A sexta entrada é o coringa, que está ali por uma exceção declarada, com a razão escrita ao lado. Fechar a lista num tipo é o que faz o compilador cobrar quem esquecer um caso nas peças seguintes.
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;
}
DicaNo código
A redução entra durante a leitura, dentro da mesma função que reconhece o sufixo, e não numa passada posterior sobre a árvore pronta. O que sai do leitor já não conhece fecho positivo, opcional nem classe de símbolos. Nenhuma peça construída daqui em diante precisará aprendê-los, e nenhuma precisará perguntar se a árvore que recebeu já foi normalizada.
Repare no que a redução do opcional faz aparecer. A folha da cadeia vazia não corresponde a nada que alguém digite: não existe jeito de escrever a cadeia vazia num padrão, porque uma alternativa sem lado direito é erro de sintaxe. Aquela folha só nasce de uma redução, e existe porque x? precisa dizer “isto ou nada” com os operadores que sobraram.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
E1["x+"] -->|"reduz a"| N1["concat(x, fecho(x))"]
E2["x?"] -->|"reduz a"| N2["alt(x, vazio)"]
E3["[abc]"] -->|"reduz a"| N3["alt(alt('a','b'), 'c')"]
E4["[a-c]"] -->|"reduz a"| N3
E5["(x)"] -->|"reduz a"| N5["x — o grupo não deixa nó"]
E6["ponto escapado"] -->|"reduz a"| N6["'.' — símbolo literal"]
Confira a linha do fecho positivo e veja a igualdade fechar. À esquerda, L(x^+) é o conjunto das cadeias formadas por uma ou mais repetições do que x denota. À direita, L(x)\,L(x)^* concatena uma ocorrência obrigatória com zero ou mais, o que produz exatamente as mesmas cadeias. A redução do opcional se confere igual: L(x) \cup \{\varepsilon\} é o que x? significa em português.
1.4.2 O preço que ninguém vê no texto do padrão
Veja só o que uma faixa de letras custa. Quantos nós você acha que [a-z] produz? A faixa tem três caracteres dentro dos colchetes, e a resposta que quase todo mundo dá fica em torno de meia dúzia.
Veja só o tamanho da conta.
Ela é curta. Uma faixa de n símbolos vira n folhas, uma por símbolo, mais n-1 alternâncias para juntá-las duas a duas: 2n-1 nós ao todo. Para [0-9], dez folhas e nove alternâncias, 19 nós. Para [a-z], vinte e seis folhas e vinte e cinco alternâncias, 51 nós — a partir de três caracteres digitados. Dá dezessete nós por caractere escrito.
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;
}
DicaNo código
Nenhuma escolha alternativa faria a conta baixar, e é isso que o trecho mostra. O laço interno percorre os códigos entre o início e o fim da faixa e, para cada um, cria uma folha e a pendura no acumulado por uma alternância. O preço não vem de código malfeito: vem da estrutura que a definição de árvore pede. A faixa abrevia no texto e devolve em nós.
| O que se escreve | Caracteres | Nós |
|---|---|---|
[0-9] |
5 | 19 |
[a-z] |
5 | 51 |
[a-z]? |
6 | 53 |
[a-z]+ |
6 | 104 |
[a-z][a-z][a-z] |
15 | 155 |
([a-z][a-z][a-z])+ |
18 | 312 |
Empilhe as reduções e o número sobe rápido, de cara. O fecho positivo duplica a subárvore, e a duplicação é literal: a faixa de 51 nós aparece duas vezes, mais o nó do fecho e o da concatenação, o que dá 104. O opcional é mais barato porque não duplica nada, e acrescenta dois nós sobre os 51, chegando a 53. A última linha da tabela combina as duas operações: 18 caracteres digitados, 312 nós construídos.
Na prática, veja o que isso quer dizer para quem escreve o padrão. A pessoa acrescentou um par de parênteses e um sinal de mais, dois caracteres, e dobrou a estrutura. Nada no texto indica que aquele gesto tem custo, e nada no comportamento indica isso depois: o programa lê, constrói e encerra sem reclamar. O custo só aparece se alguém o medir de propósito.
Há um caso em que a conta some, e ele merece registro. Uma classe de um símbolo só, escrita [a], produz uma folha e nenhuma alternância. Três caracteres digitados, um nó construído — o único ponto da tabela em que a notação de conveniência sai mais cara no texto do que na árvore.
Separe duas grandezas antes de tirar conclusão. Uma é o tamanho da árvore, que acabamos de medir em nós. A outra é o tamanho da linguagem denotada, que pode ser infinito com árvore minúscula. As duas não se correspondem, e quem as confunde conclui que a* tem árvore grande por descrever um conjunto sem fim.
Falta explicar por que o coringa ficou no núcleo, já que ele passa no critério de redutibilidade sem esforço: ele é a alternância de todos os símbolos do alfabeto. A razão é a conta acima, aplicada ao alfabeto inteiro dos caracteres imprimíveis, e a expansão produziria quase uma centena de folhas por ocorrência para dizer o que uma folha diz. A classe de símbolos tem o tamanho que quem escreve escolhe, e costuma ser pequena; o coringa tem custo fixo e máximo, todas as vezes.
O inverso também acontece, e mostra que há dois filtros trabalhando aqui. O quantificador contado, do tipo x{3,5}, é redutível e caberia entre as reduções. Ficou de fora por multiplicar o tamanho da árvore de um jeito que surpreende quem escreve. Redutibilidade decide o que pode sair do núcleo; tamanho e utilidade decidem o que convém que saia.
Leia agora o degrau que essa conta desenha. A máquina, aqui, é a construção do autômato: ela conhece seis cláusulas e nada além disso, e é por isso que ela é simples. O tradutor é a leitura da expressão, e é ele quem absorve toda a conveniência de notação que a máquina não trata. A moeda desta etapa são nós de árvore, e ela é modesta de propósito. O que a máquina não faz, o tradutor faz por ela — e cobra em instruções.
1.5 O leitor de padrões da Peneira, funcionando
Vinte e um caracteres digitados, trezentos e dezoito nós construídos, e nada de errado aconteceu.
As definições das páginas anteriores têm uma contrapartida que roda, e ela cabe num executável só. O marco da Peneira neste ponto lê expressões, reduz cada uma ao núcleo, imprime a árvore em forma prefixa, conta os nós e recusa o texto malformado apontando a posição do defeito. Nenhum autômato existe ainda.
A demonstração imprime quatro blocos, nessa ordem. Primeiro os cinco padrões que o capítulo percorreu passo a passo, com a mesma escrita e na mesma sequência, seguidos da convergência entre [0-2] e 0|1|2. Depois os três padrões do programa de exemplo, cada um com a forma prefixa e a contagem de nós. Depois as quatro convergências de notação. Por fim, as quatro expressões malformadas, cada uma reexibida com o cursor sob a posição do problema.
1.5.1 O núcleo, decidido e registrado
A decisão do núcleo não mora no código: mora num documento versionado ao lado dele, com as reduções escritas em pares e as exceções com a razão junto. O documento é curto de propósito, porque ele será relido toda vez que alguém quiser saber por que determinada notação não tem nó próprio.
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 da tabela de descartados merecem leitura conjunta, porque elas exibem os dois filtros trabalhando em direções diferentes. A retrovisão saiu por expressividade: ele atravessa a cerca, e um padrão que o usasse não teria autômato finito. O quantificador contado saiu por utilidade: ele é redutível, cabia no critério, e ficou de fora por multiplicar o tamanho da árvore sem acrescentar nada ao que o percurso demonstra.
A interface do módulo declara os seis rótulos de nó e o resultado que a leitura devolve. Repare que o resultado traz a árvore ou o erro, e nunca lança exceção nem encerra o programa: é essa forma que permite exibir quatro expressões malformadas seguidas sem que a primeira interrompa as outras três.
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
1.5.2 A recusa que diz onde
A implementação é um analisador recursivo-descendente com uma função por produção, e a precedência mora na ordem em que elas se chamam. Não há tabela de prioridades, e não há comentário declarando a convenção — há a descida, que é a única cópia da decisão dentro do sistema.
A parte que costuma ser tratada como acabamento está tratada como requisito. Cada função de leitura pode falhar, e a falha registra a posição em que o defeito foi constatado, com a mensagem dizendo o que se esperava ali. Só o primeiro erro é guardado: um analisador que continua depois da falha produz erros em cascata, todos derivados do primeiro, e todos desaparecem sozinhos quando o defeito real é corrigido.
Acompanhe as quatro recusas da demonstração, porque uma delas contraria a expectativa. Em *ab, o cursor cai no primeiro símbolo, com a mensagem dizendo que o operador de repetição não tem a que se aplicar. Em [a-z, ele cai depois do último símbolo lido, onde falta o fecha-colchetes. Em ab)c, ele para no fecha-parênteses que sobrou depois do fim da expressão. E em a(b|c, ele cai no fim do texto, e não no parêntese que abriu.
Essa quarta posição é a que ensina. O parêntese que abriu está correto; o que falta é o que fecha, e a falta só se constata quando o texto acaba sem ele. É também onde a pessoa vai digitar a correção. A mensagem é montada reexibindo a expressão original com uma segunda linha e o cursor sob a posição, em vez de dizer “erro na coluna 5” — porque contar colunas com o dedo é justamente o trabalho que a mensagem deveria poupar.
1.5.3 O que os padrões do exemplo custam
O programa de exemplo da Peneira declara dois padrões, e a demonstração mede os dois mais um terceiro, de calibração. Os números saem da execução, e não de estimativa.
| Padrão | Caracteres | Nós |
|---|---|---|
a(b|c)*d |
8 | 8 |
-?[0-9]+ |
8 | 44 |
[a-z]+@[a-z]+\.[a-z]+ |
21 | 318 |
A primeira linha é a de calibração e existe para dar escala às outras duas. Oito caracteres, oito nós, tudo conferível a olho na forma prefixa impressa: uma concatenação de a com um fecho de alternância, e a folha d no fim. É a árvore que cabe na tela e que serve de referência para ler a próxima.
A segunda linha já não fecha à mão com conforto. O padrão de número tem oito caracteres e produz 44 nós, e a explicação está inteira nas reduções: a faixa de dez dígitos custa 19 nós, o fecho positivo a duplica e acrescenta dois nós, chegando a 40, e o sinal opcional acrescenta os três restantes. Nada ali é desperdício, e nada ali foi digitado por quem escreveu o padrão.
A terceira linha é o ponto do capítulo, com valor. São 21 símbolos escritos e 318 nós construídos, mais de quinze vezes o tamanho do texto. A conta é o preço de três faixas de vinte e seis símbolos, cada uma expandida em 51 nós, cada uma duplicada pelo fecho positivo, mais as duas folhas literais e as quatro concatenações que juntam tudo. Ver o número é o que transforma “a redução tem custo” de afirmação em fato.
E nada de errado aconteceu. O programa lê o padrão, constrói os 318 nós, imprime a contagem e encerra sem reclamar de coisa alguma. O número é grande e é o número certo — a moeda desta etapa são nós de árvore, e a conta reaparece medida em estados no capítulo seguinte, com a mesma origem e outra unidade.
1.6 O fechamento é cerca, e ela delimita por dentro
Compor especificações regulares nunca sai da classe — e é justamente por isso que a classe tem limite.
Junte duas linguagens regulares pela união e o resultado continua regular. Emende uma na outra e continua regular. Repita uma delas indefinidamente e continua regular. Isso soa como boa notícia, e é. O que quase ninguém observa é que a mesma propriedade, lida ao contrário, diz onde a classe termina.
NotaTeorema — Fechamento sob as três operações
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: 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.
O menor exemplo cabe em duas linhas. Tome L_1 = \{ab\} e L_2 = \{c\}, denotadas por ab e por c. A união é denotada por ab|c, a concatenação por abc, e o fecho da primeira por (ab)*. Nenhuma dessas expressões precisou ser inventada: as cláusulas de composição as produziram mecanicamente.
O que o teorema não afirma merece nota. Ele não diz que essas são as únicas operações sob as quais a classe é fechada. As linguagens regulares também são fechadas sob complemento e sob interseção, e nenhuma das duas aparece na notação de Kleene. Fechamento é propriedade da classe; operador é decisão de projeto, e as duas coisas não se implicam. Por que essas três, então? Porque união, concatenação e fecho são exatamente o que uma máquina de memória finita executa sem precisar de memória extra.
A consequência prática passa despercebida por ser confortável. Você pode escrever a especificação de um padrão complicado em pedaços, conferir cada pedaço separadamente e compor tudo depois, sem jamais perguntar se o resultado ainda pertence à classe. Um trecho regular pode ir para dentro de um fecho, o fecho para dentro de uma alternância, a alternância para dentro de outra concatenação. Vinte níveis de encaixe são tão regulares quanto um. Isso aparece no código como uma ausência: em nenhum ponto de um leitor de expressões existe uma verificação do tipo “o resultado desta junção ainda é regular?”.
Agora leia a mesma propriedade ao contrário. Se compor nunca sai da classe, então compor nunca alcança o que está fora dela. Nenhuma quantidade de alternâncias, concatenações e fechos empilhados atravessa a fronteira.
Imagina a cena. Tome os parênteses balanceados, com aninhamento sem profundidade máxima. () pertence, (()) pertence com dois níveis, (()()) pertence com dois ramos, e (() não pertence a coisa alguma. Existe expressão regular que denote esse conjunto? Suponha que sim, e que a máquina correspondente tenha k estados, fixados antes de qualquer entrada chegar. Faça o caso pequeno com k = 3 e apresente à máquina quatro entradas: uma abertura, duas, três, quatro.
| aberturas lidas | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| estado em que a leitura termina | q_1 | q_2 | q_0 | q_1 |
Repare no que acabou de acontecer. São quatro leituras e três estados. A quarta coluna repete o estado da primeira, e a partir dali a máquina não distingue mais uma abertura de quatro. Complete as duas entradas com um único fechamento: a primeira vira (), que é balanceada, e a segunda vira ((((), que não é. As duas continuam do mesmo estado, com o mesmo sufixo, e terminam no mesmo estado — recebendo a mesma resposta, e uma dessas respostas está errada.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
I["máquina de k estados,<br/>fixada antes de qualquer entrada"] --> A1["1 abertura"]
I --> A2["2 aberturas"]
I --> AK["até k+1 aberturas"]
A1 --> E["k+1 leituras<br/>para k estados"]
A2 --> E
AK --> E
E --> C["duas profundidades i e j<br/>param no mesmo estado"]
C --> S["mesmo sufixo:<br/>i fechamentos"]
S --> R["mesma resposta para as duas,<br/>e uma delas está errada"]
Uma objeção razoável aparece sempre aqui: e se a tabela de estados fosse maior? Ela seria maior, e o mesmo argumento se refaria com o novo número, porque a hipótese não pressupõe nada sobre a máquina além da quantidade de estados. Pois é. Com dez estados, a colisão acontece na décima primeira abertura.
Escreva mil aberturas seguidas de um único fechamento: são 1001 símbolos, e a cadeia não é balanceada. Para recusá-la, a máquina precisaria saber que sobraram 999 aberturas pendentes. O que ela tem, ao chegar ali, é um estado entre k. Quem só sabe em que estado está não sabe quantas vezes já entrou nele.
O terreno de fora não é homogêneo. Tome as cadeias da forma ww, um trecho qualquer seguido da repetição exata dele mesmo. Segundo Hopcroft, Motwani e Ullman, elas estão fora até da classe livre de contexto, num degrau ainda mais alto que os parênteses balanceados. Fica registrado como fato citado, e não como resultado demonstrado aqui.
O erro simétrico é tão comum quanto o otimista e custa mais caro, porque leva alguém a abandonar um requisito que estava ao alcance. Quem entendeu que o aninhamento sai da classe conclui que qualquer coisa com parênteses está fora, e a conclusão é falsa. Fixe a profundidade máxima em três níveis e o conjunto passa a ser finito: (), ()(), (()), (())(), (()()) e assim por diante, uma lista que termina. Toda linguagem finita é regular, e a alternância de todas as suas cadeias é a expressão que a denota. O que a cerca barra é o “sem profundidade máxima”, e não o parêntese.
O critério que fecha a seção. Escreva o requisito como uma pergunta que a máquina teria de responder ao chegar ao fim da entrada. Pergunte o que ela precisaria lembrar para responder aquilo. Verifique se o que ela precisa lembrar tem teto declarado. Casar letras, arroba e mais letras exige lembrar só em que trecho a leitura está: cabe. Casar parênteses balanceados sem limite exige lembrar quantas aberturas ficaram pendentes: não cabe. Casar parênteses até três níveis exige lembrar um número entre zero e três: cabe. O discriminador é a memória, e não o número de símbolos estranhos que o padrão exibe.
1.7 O que os motores de hoje acrescentam, e a única construção que sai da classe
Abra a documentação de qualquer biblioteca de expressões regulares e você encontra bem mais do que três operadores: grupos de captura, verificação adiante, quantificadores não gulosos, retrovisão, âncoras, classes nomeadas. Sobre cada uma cabe uma pergunta só, e o critério da seção anterior a responde.
A retrovisão permite que um padrão exija a repetição de um trecho que ele próprio já casou. Passe o requisito pelos três passos. A pergunta que a máquina teria de responder é se a segunda ocorrência repete a primeira. Para responder, ela precisa lembrar a primeira ocorrência inteira. E o trecho capturado não tem tamanho limitado, porque quem escreve o padrão não declarou teto nenhum. É o formato ww da seção anterior, e ele não pede um pouco mais de memória: pede memória proporcional à entrada, que é outro tipo de recurso.
O custo também está medido na literatura. Alfred Aho registrou, no Handbook of Theoretical Computer Science de 1990, que casar padrão com retrovisor é um problema NP-completo. A construção parece um acréscimo pequeno na notação. Do outro lado dela há uma classe de problemas para a qual ninguém conhece algoritmo eficiente, no lugar de um tempo proporcional ao comprimento da entrada.
Três outras extensões dão a impressão de estar fora da classe e não estão. A verificação adiante exige que, a partir de certa posição, o texto siga um padrão auxiliar, sem consumir aquele trecho. Parece exigir que a máquina espie o futuro, o que soa impossível para quem lê da esquerda para a direita numa passada. Não é: a condição é ela própria uma linguagem regular, e a classe é fechada sob interseção, mesmo que a notação não ofereça o operador. Convém separar duas afirmações aqui, porque elas se embaralham: dizer que a construção não sai da classe é dizer que existe uma expressão dos três operadores denotando o mesmo conjunto, e não que essa expressão seja curta.
O grupo de captura guarda qual trecho da entrada casou com qual parte do padrão. Isso muda o que se extrai do casamento, e não o conjunto de cadeias aceitas — a pergunta “esta cadeia pertence à linguagem?” recebe a mesma resposta com ou sem captura. O quantificador não guloso muda a preferência entre casamentos possíveis, escolhendo o mais curto onde o guloso escolheria o mais longo. O conjunto aceito continua idêntico, e o que muda é qual das divisões o motor devolve: decide tudo para quem extrai trechos, e nada para quem decide pertinência.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TB
R["a mesma expressão regular"] --> F1["família com retrocesso"]
R --> F2["família sem retrocesso"]
F1 --> C1["aceita retrovisão e captura"]
F1 --> C2["o tempo pode crescer muito<br/>além do comprimento da entrada"]
F2 --> D1["aceita só o que a classe<br/>regular alcança"]
F2 --> D2["tempo proporcional ao<br/>comprimento da entrada"]
Existem duas famílias de motor, e a diferença entre elas é a decisão de aceitar ou recusar o que sai da classe. O PCRE, escrito por Philip Hazel em Cambridge a partir de 1997, é o representante mais conhecido da primeira: aceita retrovisão e captura, e experimenta divisões uma a uma, voltando atrás quando uma falha. É o método que produziu a conta cúbica dos sete caracteres da primeira seção. O RE2, publicado pelo Google em 2010, é o representante da segunda: recusa a retrovisão e executa pelo método de 1968, com todos os pontos ativos avançando de uma vez.
No fim das contas, chamar uma delas de melhor é abandonar a análise cedo demais. Quem precisa de retrovisão não tem escolha, e aceita junto o método de execução que vem com ela. Quem precisa de garantia de tempo sobre entrada que não controla, como um serviço que recebe texto de fora, não pode aceitar um motor que retroceda. E há um pedido que costuma aparecer neste ponto: se a linguagem que você usa já traz uma biblioteca de expressões regulares pronta, por que não usá-la e pular tudo isto? Porque a biblioteca padrão da maioria das linguagens pertence à família com retrocesso, e o que este percurso constrói é uma máquina determinista que decide numa passada. São objetos diferentes, com garantias diferentes.
1.7.1 A árvore que o capítulo seguinte vai consumir
A Peneira tem agora a primeira das suas nove peças, e o que ela entrega é uma árvore reduzida ao núcleo. Nenhum padrão foi casado contra texto algum, e nenhuma entrada foi lida além da própria expressão. O objeto produzido é uma descrição, e descrições não decidem.
O capítulo seguinte consome exatamente esse objeto. A construção que ele apresenta percorre a árvore a partir da raiz e monta, para cada tipo de nó, um pedaço de máquina com uma entrada e uma saída — três casos internos, e não oito, porque a redução já aconteceu. É ali que a decisão do núcleo passa de argumento a economia medida, e é ali também que o clone da subárvore do fecho positivo prova por que precisava existir.
Antes de virar a página, faça uma conta com o seu próprio recorte. Pegue o padrão mais longo que a sua linguagem vai precisar aceitar e conte os símbolos escritos. Depois aplique as reduções deste capítulo, à mão, e conte os nós que sobrariam: cada faixa de n símbolos custa 2n-1, cada fecho positivo dobra a subárvore e acrescenta dois, cada opcional acrescenta dois. Escreva o resultado ao lado do número de símbolos. É a primeira medida do seu sistema, e ela vale mais do que parece — daqui em diante, toda vez que algo ficar grande demais, você vai querer saber se já estava grande aqui.
1.8 A expressão descreve, e ainda não reconhece
Cinco coisas passam a estar ao seu alcance daqui em diante. Decidir se um texto é ou não uma expressão regular, incluindo os casos de borda em que a resposta contraria o hábito. Calcular a linguagem denotada, de baixo para cima. Reduzir qualquer notação de conveniência a três operadores e duas folhas, com a equivalência escrita ao lado de cada redução. Decidir, pelo argumento da memória, se um requisito dado em prosa cabe na classe. E reconhecer os pares equivalentes que a comparação de estruturas não identifica.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
T["texto do padrão"] --> A["árvore reduzida ao núcleo"]
A --> Q{"e agora?"}
Q -->|"falta"| M1["construir a máquina<br/>a partir da árvore"]
Q -->|"falta"| M2["torná-la determinista e<br/>reduzi-la ao menor tamanho"]
Q -->|"falta"| M3["decidir equivalência plena<br/>comparando máquinas mínimas"]
Fica uma dívida de vocabulário, e ela é a mais antiga do capítulo. A palavra “regular” foi definida aqui por um critério de escrita: uma linguagem é regular quando existe uma expressão que a denote. Existe uma segunda definição, por máquina, que diz que uma linguagem é regular quando existe um autômato finito que a reconheça. As duas definem o mesmo conjunto de linguagens, e a demonstração das duas direções ocupa dois dos próximos capítulos.
O saldo deste ponto do percurso. A expressão denota um conjunto; a máquina reconhece cadeias. A árvore reduzida ao núcleo é a fronteira entre as duas coisas: ela é o último objeto que descreve, e o primeiro que uma máquina vai consumir.
A conta de nós também fica pendurada, com juros anunciados. Uma faixa de vinte e seis símbolos rendeu 51 nós de árvore, e é essa árvore que a construção da máquina vai consumir, nó a nó. O que aqui se mediu em estrutura se mede, no capítulo da máquina, em estados; e no da representação, em bytes de tabela. A moeda muda de capítulo para capítulo, e a conta desce sempre na mesma direção.
Volte, antes de virar a página, ao memorando de dezembro de 1951. Kleene escreveu três operadores para dizer que sequências de estímulos um arranjo de neurônios consegue separar das demais. A notação atravessou seis décadas, mudou de assunto duas vezes e chegou aqui inteira — os mesmos três operadores, o mesmo alcance, o mesmo limite. Quando o próximo padrão lento aparecer na sua frente, as duas perguntas já estão escritas: a classe alcança este requisito, e o motor entrega o que a classe promete? A garantia é da classe; a entrega é da implementação. O que mudou em seis décadas foi o outro lado da conversão — e é ele que o capítulo seguinte constrói.
O que vem abaixo é o que você vai construir com a notação que acabou de ganhar definição.
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.