%%{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 — Resumo
Versão de revisão. Ela recupera o percurso inteiro depressa e não substitui a primeira leitura. As definições aparecem aqui na forma mais curta que ainda é correta. As contas longas e as demonstrações passo a passo ficam na versão completa deste capítulo e no capítulo do livro.
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.
O capítulo anterior parou aqui. Lá uma linguagem era guardada por extenso, como lista, e a lista quebrou na primeira operação que produz infinitos elementos. No lugar da lista entra um texto curto. E logo vem a pergunta: que conjunto, precisamente, um texto curto desses descreve?
Uma advertência de vocabulário vem antes de qualquer outra coisa. 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 aparece dois capítulos adiante.
1.1 Sete caracteres, e a notação que os escreveu já tinha 68 anos
A notação prometia decidir numa passada, e 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 sete caracteres de expressão regular: .*.*=.*. O fragmento não tem defeito nenhum enquanto notação. Ele descreve um conjunto banal: 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, e depois refaz o serviço inteiro na posição seguinte. É o cubo do comprimento da linha. Dobre a linha e o trabalho fica oito vezes maior.
Pois é: sete caracteres.
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 separa das demais. Para falar de conjuntos de sequências, 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: Regular Expression Search Algorithm. O programa lia uma expressão regular e escrevia, a partir dela, código de máquina do IBM 7094. Tome a*ab e a cadeia aaab. O fecho pode consumir nenhum a, um, dois ou três: quatro divisões, e só uma termina bem. O método de 1968 não escolhe entre elas. Ele carrega todas ao mesmo tempo, como um conjunto de pontos ativos dentro da expressão, e faz o conjunto inteiro avançar um caractere por vez. Em 1973, a pedido de Doug McIlroy, o mecanismo saiu de dentro do editor ed e virou programa próprio, o g/re/p.
A garantia é da classe; a entrega é da implementação. Essa 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.2 Que texto é uma expressão, e que encaixe ele esconde
Enquanto a resposta for “eu reconheço quando vejo”, não há como escrever o programa que lê o padrão. A resposta vem por indução, na forma de sempre: alguns objetos são expressões por decreto, umas poucas regras fabricam expressões novas, 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. Repare agora no 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, 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.
Escreva a|bc. O que foi escrito ali? Ou é a alternativa entre a e a concatenação bc, ou é a concatenação entre a alternativa a|b e o símbolo c. 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. Quem quiser a outra leitura escreve (a|b)c.
%%{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. A árvore sintática de uma expressão 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. Há duas maneiras de instalá-la: uma tabela de prioridades consultada a cada operador, ou a ordem em que as funções de leitura se chamam. Na segunda, 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, e a convenção fica escrita num lugar só.
| 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 |
A primeira linha é a mais informativa das quatro. O símbolo a atravessa quatro níveis de leitura e nenhum deles cria nó: um nó nasce quando há operador de verdade, e 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. A quarta linha responde a uma pergunta de custo: (a|b)*c tem sete caracteres, dois deles parênteses, e produz seis nós. Os parênteses orientaram a leitura e não deixaram vestígio.
A associatividade tem o mesmo destino. O laço de leitura começa pelo primeiro fator à esquerda e vai pendurando cada novo fator sobre o acumulado, e por isso abc sai como concat(concat('a', 'b'), 'c'). Essa decisão não está escrita em convenção alguma, em comentário algum, em tabela alguma. Ela é a forma da árvore, e essa é a única cópia da decisão dentro do sistema.
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, e a tentação é apontar as duas posições para o mesmo lugar. Dois pais apontando para o mesmo filho fazem um grafo, e a definição acima exige que todo nó seja filho de exatamente um outro. A consequência aparece no capítulo seguinte: a construção da máquina passará duas vezes pelos mesmos estados, e a máquina sairá errada longe da linha que causou o defeito.
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. Note que a posição a reportar é aquela em que o problema se constata, e nem sempre aquela em que ele nasceu. Em a(b|c, o cursor cai no fim do texto, porque é ali que a correção vai ser digitada. Já a** e a+* são apenas redundantes, e recusá-los exigiria uma regra a mais para proibir o inofensivo.
1.3 Que conjunto exatamente você acabou de escrever
Duas posições de texto descrevem um conjunto sem fim; dez posições descrevem um conjunto com um elemento só.
A definiçã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. As três operações que a semântica invoca chegam prontas do capítulo anterior: união, concatenação e fecho sobre conjuntos de cadeias.
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\}, e 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\}. 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 a conta sobre (a|b)* e veja o fecho entrar em ação. A subárvore da alternância denota \{a, b\}. 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. Quatro caracteres de texto, e um conjunto que a enumeração nunca alcança.
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. Zero elementos de um lado, um elemento do outro. A diferença aparece na concatenação: concatenar com \emptyset aniquila, porque para formar um par é preciso um elemento de cada lado, e concatenar com \varepsilon preserva. Um multiplica por zero e o outro multiplica por um, que é a 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.
O estrago é este. 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 caso mais sedutor é outro: 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. Há ainda uma terceira leitura errada, e ela vem de fora da notação. Em campos de busca de arquivos o asterisco significa “qualquer coisa”. Quem chega com esse hábito lê a* como “um a seguido de qualquer coisa”, e a convenção velha permanece ativa até alguém apontá-la.
NotaDefinição — Linguagem regular
Uma linguagem L \subseteq \Sigma^* é regular quando existe uma expressão regular r sobre \Sigma tal que L(r) = L.
Perceba o que ela pede e o que não pede. Pede existência, e não construção: a 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 ocupa a seção seguinte. Toda linguagem finita é regular, e a expressão sai escrevendo a alternância de todas as cadeias dela, uma a uma — um argumento sem graça que volta com juros mais adiante. 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.
1.4 Duas escritas, o mesmo conjunto
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 logo. 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 confere que o grupo não sobreviveu à leitura. Para comparar duas árvores como se comparam dois textos, escreva cada uma em forma prefixa: o rótulo da raiz, parêntese, o filho da esquerda, vírgula, o da direita, fecha parêntese. Duas árvores iguais produzem a mesma cadeia de caracteres, e comparar duas cadeias de caracteres 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 volta 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. Um segundo caso mostra o mesmo com menos disfarce: a|a e a denotam a mesma linguagem, com 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 e é inteiramente mecânico, e ele está a três capítulos daqui.
Guarde três pares como calibragem da intuição. (a^*)^* \equiv a^*, porque aplicar o fecho sobre algo já saturado não produz mais nada. a^*b^* e (a \mid b)^* não são equivalentes, e ba mostra isso em duas letras. Veja bem o terceiro: 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. O procedimento que resolve os três casos nunca é 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.
1.5 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 produzem 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. Sobra então uma pergunta de projeto: quantos desses operadores o programa que lê o padrão precisa tratar?
A primeira resposta tentadora é tratar todos. Funciona no primeiro dia e quebra no capítulo seguinte, porque cada tipo de nó reaparece em cada peça construída depois. Faça a aritmética. 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. Sem ele, cada uma trata oito, o que dá vinte e quatro — vinte e quatro lugares onde um defeito pode nascer.
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, e sim 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;
};
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;
}
Conte os rótulos possíveis de um nó e você encontra seis. 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. Observe também o que a redução do opcional faz aparecer: a folha da cadeia vazia não corresponde a nada que alguém digite, 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. À 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, e produz exatamente as mesmas cadeias. A redução do opcional se confere igual: L(x) \cup \{\varepsilon\} é o que x? significa em português. E repare em onde a redução acontece — dentro da mesma função que reconhece o sufixo, e não numa passada posterior. O que sai do leitor já não conhece fecho positivo, opcional nem classe de símbolos.
Agora a conta que dá nome a esta seção. Quantos nós você acha que [a-z] produz? 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], 51 nós a partir de três caracteres digitados. Dá dezessete nós de árvore para cada um dos caracteres que a pessoa escreveu no padrão.
| 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. 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 não duplica nada e acrescenta dois nós sobre os 51, chegando a 53. A última linha combina as duas operações: 18 caracteres digitados, 312 nós construídos. Quem escreveu o padrão acrescentou um par de parênteses e um sinal de mais, e dobrou a estrutura. Nada no texto indica isso, e nada no comportamento indica isso depois. Uma classe de um símbolo só, escrita [a], é o único ponto da tabela em que a conta some: três caracteres digitados, um nó construído.
Separe duas grandezas antes de concluir. Uma é o tamanho da árvore, medido em nós. A outra é o tamanho da linguagem denotada, que pode ser infinito com árvore minúscula. Quem as confunde acha 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 imprimíveis, que 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; o coringa tem custo fixo e máximo, todas as vezes. O inverso também acontece. O quantificador contado, do tipo x{3,5}, é redutível e caberia entre as reduções, e 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 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, 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. O que a máquina não faz, o tradutor faz por ela — e cobra em instruções.
1.6 O fechamento é cerca, e ela delimita por dentro
Compor especificações regulares nunca sai da classe — e é por isso mesmo 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.
Com L_1 = \{ab\} e L_2 = \{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. 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, e operador é decisão de projeto. 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ê escreve a especificação de um padrão complicado em pedaços, confere cada pedaço separadamente e compõe tudo depois, sem jamais perguntar se o resultado ainda pertence à classe. 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 “esta 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.
Tome os parênteses balanceados, com aninhamento sem profundidade máxima. 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. São quatro leituras e três estados, então duas delas terminam no mesmo estado. Complete essas duas com um único fechamento: uma vira (), que é balanceada, e a outra vira ((((), que não é. As duas continuam do mesmo estado, com o mesmo sufixo, e recebem 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"]
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. 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 fechamento é uma cerca, e ela delimita por dentro: todo o terreno cercado está disponível, a cerca não se move, e compor não a atravessa. O terreno de fora, porém, não é homogêneo. As cadeias da forma ww, um trecho qualquer seguido da repetição exata dele mesmo, estão fora até da classe livre de contexto, segundo Hopcroft, Motwani e Ullman. Fica registrado como fato citado, e não como resultado demonstrado aqui.
O erro simétrico é tão comum quanto o otimista, e cobra mais, 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. O que a cerca barra é o “sem profundidade máxima”.
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 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 pede memória proporcional à entrada, que é outro tipo de recurso. O custo 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.
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 pedir que a máquina espie o futuro. A condição, porém, é ela própria uma linguagem regular, e a classe é fechada sob interseção mesmo que a notação não ofereça o operador. Separe duas afirmações aqui: dizer que a construção não sai da classe é dizer que existe uma expressão dos três operadores denotando o mesmo conjunto, sem prometer 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 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. 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.
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 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.8 A expressão descreve, e ainda não reconhece
A árvore reduzida ao núcleo existe, e nenhuma máquina a percorre ainda.
Cinco coisas passam a estar ao seu alcance. 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. 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, 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. É a mesma medida que a Peneira, o sistema de referência destas páginas, começa a acumular na primeira das suas nove peças: o leitor de padrões que devolve a árvore já reduzida.
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 separa 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?