flowchart LR
A["Símbolo<br/>objeto primitivo do alfabeto"] --> B["Cadeia<br/>sequência finita de símbolos"]
B --> C["Todas as cadeias sobre o alfabeto<br/>infinito, mas enumerável"]
C --> D["Linguagem<br/>qualquer subconjunto desse universo"]
D --> E["Linguagem regular<br/>a que alguma expressão descreve"]
1 Módulo 02: Alfabetos, Linguagens e Expressões Regulares
Bem-vindo ao segundo módulo. O anterior lhe deu um mapa; este lhe dá as ferramentas do andar mais baixo dele. E tenho uma boa notícia: a teoria por baixo das expressões regulares é menor do que a bagunça das ferramentas faz supor. São seis construtores. Seis. Tudo o mais que você já viu numa busca ou é abreviação escrita em cima desses seis, ou não é expressão regular coisa nenhuma — e essa segunda possibilidade é a parte mais interessante da história.
1.1 O problema: o padrão que você copiou e não funcionou
Imagina a cena, porque quase certamente ela já aconteceu com você. Precisava validar um campo de texto, foi buscar na internet, achou um padrão numa resposta com muitos votos, colou no código e funcionou. Duas semanas depois apareceu um caso que o padrão rejeita e não deveria. Você abriu aquela sequência de colchetes, barras e asteriscos e fez a única coisa que sabia fazer: mudou um caractere, testou, mudou outro, testou de novo. Não faltou esforço nem inteligência ali; faltou modelo. Quem aprendeu por imitação não tem raciocínio disponível quando a imitação falha, porque nunca houve nada por baixo do padrão além do padrão.
Este módulo constrói o modelo que faltava, e o constrói pelo fundo, por objetos tão simples que parecem não merecer definição — símbolo, cadeia, conjunto de cadeias —, porque é ali que a intuição erra e o erro se propaga amplificado. Aviso desde já qual é o inimigo do módulo inteiro: a cadeia vazia. Ela responde sozinha pela maioria dos tropeços que vou ver nas suas demonstrações, e reaparece disfarçada nos próximos módulos como transição vazia, produção que deriva o nada e conjunto de anulabilidade.
O tom muda a partir daqui: o módulo anterior queria que você situasse, este quer que você opere.
Uma palavra sobre o ponto de partida que este capítulo assume, porque ele é menor do que o assunto sugere.
Não pressuponho estudo anterior de teoria de linguagens formais, nem contato prévio com autômatos, nem uso de qualquer ferramenta de geração de analisadores. Pressuponho apenas o que praticamente toda pessoa que programa já traz: ter usado, alguma vez, um padrão de busca em um editor de texto ou em uma ferramenta de linha de comando, provavelmente sem saber o que estava escrevendo. Esse é exatamente o ponto de partida deste capítulo, e uma das suas funções é mostrar que havia uma teoria por baixo daquela prática — teoria menor e mais bem comportada do que a notação fazia supor.
Do lado matemático, pressuponho o vocabulário elementar de conjuntos e de funções: união, interseção, diferença, produto cartesiano, subconjunto, cardinalidade e a noção de conjunto enumerável. Pressuponho também familiaridade com demonstração por indução sobre os números naturais, porque a técnica que usaremos aqui — indução sobre a estrutura de um objeto construído por regras — é uma variação dela, e a primeira vez que ela aparece neste capítulo eu a exibo por extenso justamente para que a analogia fique visível.
1.2 Os objetos elementares: símbolo, alfabeto, cadeia
Vamos por partes. Um alfabeto, que escrevemos \Sigma, é um conjunto finito e não vazio cujos elementos chamamos de símbolos. A definição não diz o que é um símbolo, e isso não é preguiça: o símbolo é primitivo, indivisível por decreto, e a teoria não precisa saber nada sobre a natureza dele. Podem ser letras, dígitos, pontuação ou categorias léxicas produzidas por uma fase anterior de um compilador — a teoria funciona igual nos quatro casos, e é essa indiferença que permite reaproveitar o mesmo aparato em níveis de abstração bem diferentes do mesmo sistema. Já a finitude sustenta praticamente todos os resultados deste andar, porque os algoritmos dos próximos módulos precisam examinar os símbolos um a um e indexar tabelas por símbolo: um alfabeto infinito não quebra a implementação, quebra os teoremas.
Uma cadeia sobre \Sigma é uma sequência finita de símbolos de \Sigma, e o seu comprimento \lvert w \rvert é o número de símbolos, contadas as repetições. A cadeia de comprimento zero é a cadeia vazia, escrita \varepsilon.
Escrevendo \Sigma^n para o conjunto das cadeias de comprimento exatamente n, definimos o universo em que tudo acontece:
\Sigma^* = \bigcup_{n \ge 0} \Sigma^n \qquad\text{e}\qquad \Sigma^+ = \bigcup_{n \ge 1} \Sigma^n .
Olha só o detalhe que decide tudo: \Sigma^0 = \{\varepsilon\}, e não o conjunto vazio. Existe exatamente uma maneira de não escrever nada, logo o conjunto das cadeias de comprimento zero tem um elemento. Escreva os dois objetos lado a lado até a diferença ficar automática: \emptyset não tem elementos, \{\varepsilon\} tem um.
A operação que sustenta o módulo inteiro é a concatenação: se u tem m símbolos e v tem n, então uv é a cadeia com os símbolos de u seguidos dos de v, de comprimento m+n. Ela é associativa, o que autoriza escrever uvw sem parênteses; tem \varepsilon como neutro, porque concatenar zero símbolos não acrescenta nada; e não é comutativa, porque sobre \Sigma = \{a,b\} já temos ab \ne ba. Guarde essa última: a álgebra que vamos montar tem soma comutativa e produto não comutativo, e trocar dois fatores de lugar por analogia com a aritmética da escola é o erro que mais aparece.
Pare e pense. Toda cadeia elevada a zero devolve a cadeia vazia — inclusive a própria cadeia vazia. Por que isso é forçado pela definição, e não uma convenção escolhida por comodidade? Se a resposta não vier logo, escreva a recursão da potência e veja o que acontece no primeiro passo.
Ainda no nível das cadeias, três relações merecem nome: x é prefixo de w quando w = xv, é sufixo quando w = ux e é subcadeia quando w = uxv. As consequências que somem quando alguém enumera à mão são sempre as mesmas — a cadeia vazia é as três coisas de qualquer cadeia, toda cadeia é as três coisas de si mesma, e uma cadeia de comprimento n tem n+1 prefixos, um por ponto de corte, incluindo os das pontas. Com subcadeias há um cuidado extra: em aaa, o pedaço aa ocorre em duas posições e é um só, e a maneira segura de não confundir ocorrências com objetos distintos é coletar os resultados em um conjunto. Sobre abc as subcadeias distintas são sete, e ac não está entre elas, porque subcadeia exige contiguidade — sem contiguidade o nome muda para subsequência, e trocar as duas noções produz não só resposta errada em exercício, mas especificação errada de categoria léxica.
Encerro a seção com uma observação que não é matemática e custa caro se ficar para depois: a escolha do alfabeto é decisão de projeto. Com os valores de um byte você tem duzentos e cinquenta e seis símbolos, número já grande o bastante para que uma tabela de transição indexada densamente desperdice memória; com todos os pontos de código de um sistema de escrita universal, nenhuma tabela indexada diretamente serve, e as estruturas dos próximos módulos passam a indexar por faixas. É barato decidir agora e caro reverter depois. Note ainda que, em compiladores, o formalismo é aplicado duas vezes em alfabetos diferentes: na análise léxica os símbolos são caracteres e as cadeias são lexemas; num nível acima, os símbolos são categorias léxicas e as cadeias são sequências de tokens.
1.3 Linguagens: conjuntos de cadeias
Subo um degrau. Uma linguagem sobre \Sigma é um subconjunto qualquer de \Sigma^* — qualquer um mesmo, e é essa generosidade quase escandalosa que dá alcance ao aparato. O conjunto dos identificadores válidos de uma linguagem de programação é uma linguagem; o dos programas sintaticamente corretos é uma linguagem sobre outro alfabeto; o dos programas que terminam também é. A única diferença que a teoria enxerga entre elas é a dificuldade de decidir a pertinência.
Agora o ponto que mais gera confusão no módulo.
flowchart TB
Q["A entrada vazia deve ser aceita"] --> V["Linguagem vazia<br/>nenhuma cadeia dentro<br/>cardinalidade zero"]
Q --> E["Linguagem que contém só a cadeia vazia<br/>uma cadeia dentro<br/>cardinalidade um"]
V --> RV["O reconhecedor rejeita tudo<br/>inclusive a entrada vazia"]
E --> RE["O reconhecedor rejeita tudo<br/>exceto a entrada vazia"]
RV --> C["Comportamentos diferentes<br/>de objetos que se parecem no papel"]
RE --> C
A imagem que ajuda: a linguagem vazia é uma caixa fechada e vazia; a linguagem que contém apenas a cadeia vazia é uma caixa com uma folha em branco dentro. A folha em branco é uma coisa; a ausência de folha é outra.
Como linguagens são conjuntos, união, interseção e diferença se aplicam sem novidade. O complemento pede cuidado, porque depende do alfabeto: a mesma L = \{a\} tem complementos diferentes conforme \Sigma seja \{a\} ou \{a,b\}. Escrever “o complemento de L” sem ter fixado \Sigma é escrever algo indefinido, e na implementação vira um defeito traiçoeiro — sai certo para os símbolos considerados e errado para os demais, em silêncio, até aparecer uma cadeia com o símbolo esquecido.
A primeira operação genuinamente nova estende a concatenação ao nível dos conjuntos:
L_1 L_2 = \{\, uv \mid u \in L_1 \ \text{e} \ v \in L_2 \,\}.
Toda cadeia de L_1 seguida de toda cadeia de L_2. Aqui reaparece o fenômeno de contar ocorrências contra contar objetos: com L_1 = \{a, ab\} e L_2 = \{b, \varepsilon\} há quatro pares e só três cadeias no resultado, porque (a,b) e (ab,\varepsilon) produzem ambos ab. A operação é associativa, não é comutativa, tem \{\varepsilon\} como neutro e \emptyset como absorvente.
As duas identidades que todo mundo troca. Concatenar a linguagem que contém só a cadeia vazia com uma linguagem devolve essa linguagem inteira; concatenar a linguagem vazia com ela devolve a linguagem vazia, porque não existe cadeia alguma para começar o par. O neutro é a caixa com a folha em branco; o absorvente é a caixa vazia. Trocar os dois papéis é a origem da maioria das “demonstrações” de que duas expressões diferentes são equivalentes.
A concatenação distribui sobre a união pelos dois lados. Sobre a interseção, porém, a distributividade falha: com L = \{a, aa\}, L_1 = \{a\} e L_2 = \{aa\}, o lado esquerdo é vazio e o direito contém aaa. A razão do fracasso vale carregar, porque reaparece na ambiguidade de gramáticas — a cadeia aaa é produzida de um lado pela quebra aa \cdot a e do outro pela quebra a \cdot aa, e a concatenação perde a informação de onde estava a fronteira.
Definidas a potência L^{n+1} = L^n L e a base L^0 = \{\varepsilon\}, chegamos ao fecho de Kleene e ao fecho positivo:
L^* = \bigcup_{n \ge 0} L^n \qquad\text{e}\qquad L^+ = \bigcup_{n \ge 1} L^n .
A operação leva o nome de Stephen Kleene, que a introduziu no trabalho em que caracterizou os eventos representáveis em redes de autômatos finitos, publicado em 1956 no volume Automata Studies. É ela que dá poder à notação inteira: sem fecho, tudo o que se descreve a partir de conjuntos finitos continua finito.
Duas consequências para memorizar por derivação, nunca por decoreba. Primeiro, L^* sempre contém a cadeia vazia, porque a potência zero está na união; já L^+ só a contém quando L já a continha. Segundo, os casos de borda: o fecho de Kleene do conjunto vazio é o conjunto com a cadeia vazia, enquanto o fecho positivo do conjunto vazio é vazio. O primeiro incomoda todo mundo na primeira leitura e é forçado pela álgebra — se tivéssemos L^0 = \emptyset, então L^1 = L^0 L = \emptyset para toda linguagem, absurdo, já que L^1 deve ser L. Ou, pela leitura combinatória: há exatamente uma maneira de concatenar zero cadeias, que é não fazer nada, e o resultado dela é a cadeia vazia.
Fecho a seção com a dificuldade que motiva a segunda metade do módulo. Linguagens interessantes são infinitas e não podem ser representadas por extensão — e há um argumento de contagem que fixa um limite absoluto: as linguagens sobre um alfabeto formam uma coleção não enumerável, ao passo que as descrições finitas formam uma coleção enumerável, de modo que, para qualquer sistema de descrição que se invente, quase todas as linguagens ficam sem descrição. Isso reorganiza a pergunta: não “como descrever qualquer linguagem?”, e sim “que classe vale a pena poder descrever, e com que notação?”.
1.4 Expressões regulares: seis construtores e nada mais
A resposta deste andar é uma classe pequena, de notação minúscula e reconhecimento barato. Fixado o alfabeto, o conjunto das expressões regulares é o menor conjunto tal que: o vazio é expressão; a cadeia vazia é expressão; cada símbolo do alfabeto é expressão; e, se r e s são expressões, então (r \mid s), (rs) e (r^*) também são. Três casos-base, três construtores, fim.
Uma advertência de notação que causa confusão real. Os desenhos \emptyset e \varepsilon aparecem aqui como elementos da sintaxe e apareceram antes como objetos semânticos. A diferença entre eles é a diferença entre a palavra e a coisa; diga “a expressão \varepsilon” ou “a cadeia \varepsilon” quando o contexto puder confundir, porque misturar sintaxe com semântica é a fonte da maior parte das dificuldades neste tópico.
Escrever todos os parênteses deixa a expressão ilegível, então adotamos precedência: estrela liga mais forte, depois concatenação, depois união. Assim ab^* é a seguido do fecho de b, e não o fecho de ab.
A semântica se define pela mesma indução que definiu a sintaxe, um caso por construtor:
L(\emptyset) = \emptyset, \qquad L(\varepsilon) = \{\varepsilon\}, \qquad L(a) = \{a\}, L(r \mid s) = L(r) \cup L(s), \qquad L(rs) = L(r)\,L(s), \qquad L(r^*) = L(r)^* .
flowchart LR
subgraph SIN["Sintaxe - texto que se escreve"]
A0["expressão do vazio"]
A1["expressão da cadeia vazia"]
A2["um símbolo do alfabeto"]
A3["alternação de duas expressões"]
A4["justaposição de duas expressões"]
A5["estrela sobre uma expressão"]
end
subgraph SEM["Semântica - conjunto denotado"]
B0["conjunto vazio"]
B1["conjunto com a cadeia vazia"]
B2["conjunto com uma cadeia de um símbolo"]
B3["união dos dois conjuntos"]
B4["concatenação dos dois conjuntos"]
B5["fecho de Kleene do conjunto"]
end
A0 --> B0
A1 --> B1
A2 --> B2
A3 --> B3
A4 --> B4
A5 --> B5
Olhe essas seis igualdades com atenção, porque elas contêm a ideia central do módulo. À esquerda, operações sobre texto; à direita, operações sobre conjuntos; e a correspondência é composicional, isto é, o significado do todo depende apenas do significado das partes. É ela que dá forma a todos os algoritmos dos próximos módulos: um caso por construtor, cada caso combinando os resultados dos filhos.
Vale exercitar uma vez. Tome r = (a \mid b)^* a sobre \Sigma = \{a,b\}: pela precedência é a concatenação de (a\mid b)^* com a, e então L(r) = \{a,b\}^*\{a\}, o conjunto das cadeias que terminam em a. A cadeia vazia não está nele, mas a cadeia a está — obtida tomando a cadeia vazia do fecho seguida do a. É aqui que a distinção do início do módulo paga: se o fecho não contivesse a cadeia vazia, a expressão descreveria outra coisa.
Agora, se a notação tem só seis construtores, de onde vem tudo aquilo que você já viu? De açúcar sintático. O sinal de mais é a expressão concatenada com o próprio fecho; a interrogação é a união com a cadeia vazia; um contador é a repetição escrita por extenso; uma classe entre colchetes é a união dos símbolos listados; o ponto é a união de todos os símbolos do alfabeto. Todas são elimináveis mecanicamente, e o preço é o tamanho — uma classe de vinte e seis letras vira vinte e cinco uniões, e o tamanho do autômato acompanha o da expressão expandida. Mas é só preço: não há ganho de poder expressivo.
Daí uma recomendação de projeto para o seu compilador: represente apenas os seis construtores na estrutura de dados e monte as formas derivadas em cima deles. Acrescentar um caso para o sinal de mais parece economizar trabalho e custa caro no módulo seguinte, quando o algoritmo que converte expressão em máquina tiver de tratar doze casos em vez de seis.
Fecho a seção com um hábito que quero incutir: ao ler uma expressão, não a leia como texto da esquerda para a direita. Leia-a como árvore.
flowchart TB
CAT["concatenação"] --> OP1["opcional"]
CAT --> POS["fecho positivo"]
CAT --> OP2["opcional"]
OP1 --> S["sinal de menos"]
POS --> D1["classe de dígitos"]
OP2 --> CAT2["concatenação"]
CAT2 --> P["ponto separador"]
CAT2 --> POS2["fecho positivo"]
POS2 --> D2["classe de dígitos"]
Vista assim, quase toda pergunta sobre a expressão tem resposta imediata. Ela aceita a cadeia vazia? Só se os três fatores da concatenação puderem produzi-la; o primeiro e o terceiro podem, por serem opcionais, mas o do meio é um fecho positivo e exige pelo menos uma ocorrência — logo não. Esse raciocínio, que parece trivial aqui, é o cálculo que faremos algoritmicamente adiante sob o nome de anulabilidade, e sem ele não há analisador sintático preditivo. As cadeias de fronteira também respondem sozinhas: com parte inteira obrigatória, um separador decimal sem dígito antes é rejeitado; já zeros à esquerda são aceitos, porque nada os proíbe — decisão de quem escreveu, não descuido, desde que esteja registrada.
Isso me leva ao erro de método que vou combater o semestre inteiro: especificar por exemplo em vez de especificar por expressão. Dizer que “números são coisas como 42 ou 3.14” não é especificação, é ilustração, porque os exemplos não dizem se zero à esquerda vale, nem se notação científica vale, nem se um ponto sem dígitos vale. A expressão responde às três perguntas sem que ninguém precise decidir nada de novo, e responde igual para todo mundo que a leia. O teste de qualidade: escolha uma cadeia esquisita e pergunte se ela é aceita. Se a resposta sai sem hesitação, está boa; se você precisa deliberar, ela está frouxa, e a frouxidão vai ser resolvida sem discussão e sem registro no momento em que o código for escrito — decisão tomada por acidente.
1.5 A álgebra dessas expressões
Expressões diferentes podem denotar a mesma linguagem, e escrevemos r \equiv s quando L(r) = L(s). A definição desloca uma pergunta sobre texto para uma pergunta sobre conjuntos, e essa é a chave de tudo aqui: para demonstrar uma equivalência, demonstra-se uma igualdade de conjuntos, tipicamente por dupla inclusão.
| Identidade | Nome |
|---|---|
| r \mid s \equiv s \mid r | comutatividade da união |
| r \mid r \equiv r | idempotência da união |
| r \mid \emptyset \equiv r | neutro da união |
| \varepsilon r \equiv r \varepsilon \equiv r | neutro da concatenação |
| \emptyset r \equiv r \emptyset \equiv \emptyset | absorvente da concatenação |
| r(s \mid t) \equiv rs \mid rt | distributividade à esquerda |
| \emptyset^* \equiv \varepsilon | fecho do vazio |
| r^{**} \equiv r^* | idempotência do fecho |
| r^* \equiv \varepsilon \mid r r^* | desdobramento do fecho |
| (r \mid s)^* \equiv (r^* s^*)^* | fecho da união |
Três delas se usam para raciocinar, e não apenas para encolher expressão. O desdobramento do fecho diz que uma cadeia do fecho ou é vazia, ou começa com uma cadeia da base seguida de outra cadeia do fecho: é a forma recursiva do fecho, base do algoritmo que constrói autômatos e da forma como as gramáticas expressam repetição. A idempotência do fecho sai direto da caracterização de menor conjunto. E o fecho da união é a melhor identidade para exercitar dupla inclusão — faça essa, e repare em que ponto a distinção do início do módulo trabalha: para enxergar uma cadeia da primeira base como elemento do produto dos dois fechos, é preciso que a cadeia vazia esteja no segundo. É o que faz as demonstrações fecharem.
Agora o ponto mais importante da seção, e ele é uma limitação.
flowchart TB
P["Duas expressões denotam a mesma linguagem"] --> D["Suspeita de que sim"]
P --> R["Suspeita de que não"]
D --> DA["Cadeia de identidades da tabela<br/>cada passo justificado"]
DA --> OK["Equivalência demonstrada"]
DA -.-> NADA["Não achei o caminho<br/>isso não conclui coisa alguma"]
R --> RT["Exibir uma cadeia que está em uma<br/>e não está na outra"]
RT --> NO["Equivalência refutada pela testemunha"]
A manipulação algébrica é excelente para demonstrar e péssima para refutar. Se você manipulou por meia hora e não transformou r em s, isso não demonstra que são diferentes — demonstra que você não achou o caminho. Para refutar, o instrumento é outro: exiba uma cadeia que está em uma linguagem e não está na outra. Uma cadeia é uma testemunha, e uma testemunha encerra a questão.
Concordância não é demonstração. Dá para comparar duas expressões gerando as cadeias das duas linguagens até um comprimento dado. É útil e pega quase todos os erros que você cometerá na prática, mas não demonstra equivalência: duas expressões podem coincidir até o comprimento dez e divergir no onze, e o programa diria que conferem. Concordância até um comprimento é evidência, não prova — e um programa que funciona induz justamente a esquecer essa diferença.
Três resultados delimitam o método. Redko demonstrou, em 1964, que nenhum conjunto finito de identidades puramente equacionais é completo para a equivalência de expressões regulares: qualquer catálogo como o da tabela deixa de fora alguma equivalência verdadeira. Salomaa obteve, em 1966, sistemas completos ao acrescentar uma regra de inferência com hipótese. E decidir equivalência, embora decidível — propriedade que se perde nos andares superiores da hierarquia —, é PSPACE-completo, resultado de Stockmeyer e Meyer publicado em 1973.
Vale ainda a regra de Arden, apresentada por Dean Arden em 1961, ponte entre a álgebra e a conversão de autômatos de volta em expressões: se a cadeia vazia não pertence a A, a equação X = AX \cup B tem solução única, dada por X = A^*B. Com A = \{\varepsilon\} e B = \emptyset, qualquer conjunto a satisfaz e a unicidade evapora — de novo a cadeia vazia decidindo tudo.
1.6 A fronteira com as notações de biblioteca
Chego ao ponto que mais muda a prática de quem programa, e a afirmação é forte: boa parte do que as bibliotecas chamam de “expressão regular” não é expressão regular.
A história explica a bagunça. Ken Thompson publicou em 1968, nas Communications of the ACM, um algoritmo que construía, a partir de uma expressão regular, um reconhecedor executável, e o incorporou ao editor de texto em que trabalhava; dessa linhagem saiu a ferramenta de busca por padrões distribuída com o Unix, e daí a notação se espalhou. No caminho, cada ferramenta acrescentou o que lhe convinha — parte açúcar inofensivo, parte construções novas, que aumentavam o poder expressivo para além da classe regular e, com ele, o custo de reconhecimento.
flowchart TB
N["Construção oferecida por uma notação de biblioteca"] --> Q{"Pode ser reescrita<br/>usando só os seis construtores"}
Q -->|sim| DENTRO["Açúcar sintático<br/>quantificadores, classes, faixas, ponto"]
Q -->|não| FORA["Fora da classe regular<br/>retrovisores, olhares gerais, recursão"]
DENTRO --> LIN["Máquina de memória finita<br/>tempo proporcional à entrada"]
FORA --> EXP["Retrocesso<br/>risco de custo exponencial"]
Quantificadores, contadores, classes de caracteres com faixas e com negação, classes nomeadas, o ponto que casa qualquer símbolo, agrupamento e alternação: tudo açúcar, expandível nos seis construtores, desde que o alfabeto seja finito e fixado. A pergunta operacional é sempre a mesma — isto pode ser expandido?
As âncoras de início e de fim de texto não são expressões regulares pela definição, porque falam de posição e não de cadeia; mas o que expressam continua dentro da classe. Existem porque a maioria das bibliotecas resolve o problema de busca e não o de reconhecimento. Num compilador, onde se reconhece um lexema completo a partir de uma posição, elas não fazem falta.
Retrovisores, que exigem que um trecho já casado reapareça idêntico adiante; olhares gerais, sobretudo os de comprimento variável; e construções recursivas, que nem fingem — são um mecanismo de pilha dentro da notação de padrões. Se encontrar uma dessas em uso, o que está sendo escrito é um analisador sintático disfarçado de padrão.
O caso dos retrovisores é o mais limpo de argumentar. Reconhecer “um trecho qualquer, seguido de qualquer coisa, seguido do mesmo trecho” exige lembrar conteúdo de comprimento ilimitado, e a memória de um reconhecedor da classe regular é finita e fixada antes de a entrada ser vista. A linguagem correspondente não é regular — e, o que talvez surpreenda, não é sequer livre de contexto. O custo não é só teórico: Alfred Aho registrou, no capítulo sobre algoritmos de busca de padrões do Handbook of Theoretical Computer Science, publicado em 1990, que decidir se uma cadeia casa com um padrão contendo retrovisores é NP-completo. A construção que a biblioteca oferece com dois caracteres a mais muda a classe de complexidade do problema que ela resolve.
Isso aparece na fatura de tempo de execução, e é a resposta à pergunta “por que a minha busca travou”. A primeira estratégia de reconhecimento, que estudaremos a partir do próximo módulo, converte o padrão em máquina e passa a entrada por ela sem nunca voltar atrás, em tempo proporcional ao comprimento da entrada. A segunda é o retrocesso — tentar uma alternativa e, se falhar adiante, voltar e tentar a próxima —, mais fácil de implementar, capaz de suportar retrovisores e olhares, e adotada por praticamente toda biblioteca de propósito geral. O problema é que o número de alternativas pode crescer exponencialmente: no caso canônico, um fecho dentro de outro aplicado a uma entrada longa que não casa, cada partição é uma alternativa e o reconhecedor as tenta todas antes de desistir — sendo que, pela álgebra da seção anterior, aquele padrão equivale a um bem mais simples, que roda em tempo linear.
E não é curiosidade acadêmica. Em 2 de julho de 2019 a Cloudflare publicou um relatório atribuindo uma interrupção global do seu serviço exatamente a esse fenômeno: uma regra recém-implantada continha um padrão com retrocesso catastrófico, e o consumo de processamento derrubou o serviço em escala mundial. O defeito não estava no código nem na entrada; estava na combinação de uma notação que permite construções fora da classe com uma estratégia que paga caro por certas formas.
O critério prático, numa frase. Se, para reconhecer o padrão, é preciso lembrar algo de tamanho ilimitado — um trecho já casado, uma contagem de aninhamento —, ele não é regular e a implementação vai pagar por isso. Se tudo o que é preciso lembrar cabe numa quantidade fixada antes de a entrada ser lida, ele é regular e existe reconhecimento em tempo linear.
Para quem projeta uma notação de padrões, e não apenas a consome, a consequência é confortável: inclua o que é açúcar, exclua o que muda a classe. Aceitar as construções excluídas significaria abandonar a garantia de tempo linear que é a razão de ser do formalismo. Aqui a teoria não apenas explica a decisão, ela a toma.
1.7 O caso conduzido: da teoria à especificação
Toda a teoria deste módulo converge para uma tarefa concreta: descrever, com precisão total, as categorias de símbolos léxicos de uma linguagem. Vale antecipar o que essa entrega não é. Não é código de compilador, e não é ilustração: não são exemplos do que se pretende reconhecer, são expressões que decidem, sem consultar a intenção de ninguém, se cada cadeia pertence à categoria. É contrato escrito antes da implementação, e de propósito antes dela.
1.7.1 6.1 O vocabulário elementar, tornado executável
A linguagem que este livro constrói chama-se Peneira, e o capítulo anterior já apresentou a sua forma: um programa declara padrões, escreve regras que reagem ao que for encontrado no texto de entrada e emite resultados rotulados. Antes de especificar as suas categorias léxicas, porém, vale dar corpo executável ao vocabulário deste capítulo — e vale porque a teoria elementar de cadeias e linguagens parece simples demais para merecer código exatamente enquanto não se tenta escrevê-lo.
Começo pelas cadeias. As operações são as da seção 1: concatenação, potência, reverso, prefixos, sufixos e subcadeias.
02_cadeia.h
#ifndef PENEIRA_02_CADEIA_H
#define PENEIRA_02_CADEIA_H
#include <cstddef>
#include <string>
#include <vector>
namespace peneira {
// Uma cadeia é uma sequência finita de símbolos sobre um alfabeto. Usamos
// std::string como representação: os símbolos são caracteres, e a cadeia vazia
// é a string de comprimento zero.
using Cadeia = std::string;
// A cadeia vazia, que a teoria escreve como épsilon. Existe como função
// nomeada para que o código se leia como a definição formal.
const Cadeia& vazia();
Cadeia concatenar(const Cadeia& a, const Cadeia& b);
// Potência: a cadeia concatenada com ela mesma n vezes. Por definição,
// qualquer cadeia elevada a zero é a cadeia vazia — inclusive a própria
// cadeia vazia.
Cadeia potencia(const Cadeia& s, std::size_t n);
Cadeia reverso(const Cadeia& s);
// Prefixos, sufixos e subcadeias incluem a cadeia vazia e a própria cadeia,
// como manda a definição. Esquecer os extremos é o erro mais comum ao
// enumerá-los à mão.
std::vector<Cadeia> prefixos(const Cadeia& s);
std::vector<Cadeia> sufixos(const Cadeia& s);
std::vector<Cadeia> subcadeias(const Cadeia& s);
bool ehPrefixoDe(const Cadeia& possivel, const Cadeia& s);
bool ehSufixoDe(const Cadeia& possivel, const Cadeia& s);
} // namespace peneira
#endif // PENEIRA_02_CADEIA_H
Duas decisões merecem comentário, e as duas são pedagógicas antes de serem técnicas.
A cadeia vazia recebe uma função nomeada em vez de aparecer como texto literal vazio espalhado pelo código. Escrever aspas vazias funcionaria igualmente bem e é o que se faz por reflexo. Nomeei porque, com o nome, o código passa a se ler como a definição formal, e porque a cadeia vazia é a origem da maioria dos erros deste tópico — dar nome a ela obriga quem lê a notar que ela está ali.
As subcadeias são coletadas em um conjunto ordenado, e não em uma lista. É a Definição 1.7 aplicada literalmente: em aaa, a subcadeia aa ocorre em duas posições e é uma só. Enumerar por posição e devolver duplicatas é o erro clássico, e escolher a estrutura de dados que o impede por construção é mais confiável do que lembrar de filtrar depois. O efeito colateral bom é que a saída sai ordenada e idêntica em toda execução, o que importa quando ela vai parar em um livro.
Subindo um nível, as linguagens. Aqui a implementação encontra o limite discutido na seção 2.6, e o encontra de frente.
02_linguagem.h
#ifndef PENEIRA_02_LINGUAGEM_H
#define PENEIRA_02_LINGUAGEM_H
#include <cstddef>
#include <set>
#include <string>
#include "02_cadeia.h"
namespace peneira {
// Uma linguagem é um conjunto de cadeias. Representamos com std::set por dois
// motivos: elimina repetições, como manda a definição de conjunto, e mantém
// ordem determinística, o que faz as demonstrações imprimirem sempre igual.
//
// Limitação assumida: só conseguimos representar linguagens FINITAS. As
// operações que produzem conjuntos infinitos (fecho) recebem um limite de
// comprimento e devolvem a fatia até ali. Isso é aproximação de demonstração,
// não implementação do conceito — o objeto infinito só ganha representação
// finita no módulo 3, quando o autômato entra.
using Linguagem = std::set<Cadeia>;
Linguagem uniao(const Linguagem& a, const Linguagem& b);
Linguagem intersecao(const Linguagem& a, const Linguagem& b);
Linguagem diferenca(const Linguagem& a, const Linguagem& b);
// Concatenação de linguagens: toda cadeia de `a` seguida de toda cadeia de
// `b`. O número de resultados é o produto dos tamanhos, e é por isso que o
// limite de comprimento existe.
Linguagem concatenacao(const Linguagem& a, const Linguagem& b,
std::size_t comprimentoMaximo);
Linguagem potencia(const Linguagem& a, std::size_t n,
std::size_t comprimentoMaximo);
// Fecho de Kleene: união de todas as potências, da zero em diante. Contém
// sempre a cadeia vazia — inclusive quando a linguagem de partida é vazia.
Linguagem fechoKleene(const Linguagem& a, std::size_t comprimentoMaximo);
// Fecho positivo: idem, mas a partir da potência um. Só contém a cadeia vazia
// se a linguagem de partida já a contiver.
Linguagem fechoPositivo(const Linguagem& a, std::size_t comprimentoMaximo);
// Formatação em notação de conjunto, com reticências quando há mais itens do
// que o limite pedido.
std::string formatar(const Linguagem& a, std::size_t maximoDeItens);
} // namespace peneira
#endif // PENEIRA_02_LINGUAGEM_H
Repare no parâmetro de comprimento máximo que aparece na concatenação, na potência e nos dois fechos. Ele não é detalhe de implementação nem otimização: é o que garante a terminação. Sem ele, o cálculo de ponto fixo do fecho não pararia para nenhuma linguagem que contenha uma cadeia não vazia, porque sempre haveria uma cadeia mais longa a produzir. O que o código calcula, portanto, não é o fecho — é a fatia do fecho até um comprimento dado, que é uma janela sobre o objeto e não o objeto.
Deixo essa insuficiência exposta de propósito, porque é exatamente ela que o capítulo seguinte resolve. Quando o autômato aparecer, um conjunto infinito passará a ter representação finita e exata, e a pergunta de pertinência passará a ser respondida sem enumerar nada. Ter sentido a falta é o que faz do autômato uma resposta.
Duas verificações que o código imprime valem mais que meia hora de quadro, e são as duas que a seção 2.5 anunciou. A potência zero de uma linguagem vale o conjunto contendo a cadeia vazia, e não o conjunto vazio. E o fecho de Kleene do conjunto vazio contém a cadeia vazia, enquanto o fecho positivo do conjunto vazio é, esse sim, vazio. Ver as duas linhas saírem impressas convence de um jeito que a demonstração no papel não convence, e recomendo que você reproduza as duas antes de seguir.
1.7.2 6.2 A expressão regular como estrutura de dados
A Definição 3.1 tem três casos-base e três construtores. A representação segue exatamente isso, sem acrescentar caso algum.
02_regex.h
#ifndef PENEIRA_02_REGEX_H
#define PENEIRA_02_REGEX_H
#include <cstddef>
#include <cstdint>
#include <memory>
#include <string>
#include "02_linguagem.h"
namespace peneira {
// Sintaxe abstrata de uma expressão regular, na definição indutiva da teoria:
// os três casos-base (linguagem vazia, cadeia vazia, símbolo) e os três
// construtores (união, concatenação, estrela). Tudo o mais é açúcar sobre
// esses seis.
enum class TipoRegex : std::uint8_t {
Vazio, // denota a linguagem { }
Epsilon, // denota a linguagem { cadeia vazia }
Simbolo, // denota a linguagem { "c" }
Uniao,
Concatenacao,
Estrela,
};
struct Regex;
// Ponteiro compartilhado, e não exclusivo, porque as formas derivadas
// reaproveitam a mesma subárvore: `r+` é montado como `r` concatenado com
// `r*`, e o mesmo `r` aparece nos dois lados.
using RegexPtr = std::shared_ptr<const Regex>;
struct Regex {
TipoRegex tipo;
char simbolo; // significativo quando tipo == Simbolo
RegexPtr esquerda; // subexpressão; nula nos casos-base
RegexPtr direita; // segunda subexpressão; nula fora de União/Concatenação
};
RegexPtr vazioRegex();
RegexPtr epsilonRegex();
RegexPtr simboloRegex(char c);
RegexPtr uniaoRegex(RegexPtr a, RegexPtr b);
RegexPtr concatRegex(RegexPtr a, RegexPtr b);
RegexPtr estrelaRegex(RegexPtr a);
// Formas derivadas, definidas em termos das seis primitivas.
RegexPtr maisUmRegex(RegexPtr a); // r+ = r r*
RegexPtr opcionalRegex(RegexPtr a); // r? = r | epsilon
// Uma classe de caracteres é união de símbolos. Escrevemos assim para deixar
// explícito que `[a-z]` não é um construtor novo da teoria: é notação para
// vinte e seis uniões.
RegexPtr faixaRegex(char de, char ate);
RegexPtr conjuntoRegex(const std::string& simbolos);
// Notação textual da expressão, com parênteses apenas onde a precedência
// exige (estrela liga mais forte que concatenação, que liga mais forte que
// união).
std::string formatarRegex(const Regex& r);
// Semântica: a linguagem denotada pela expressão, calculada por indução sobre
// a estrutura — um caso para cada construtor, exatamente como a definição.
// Limitada por comprimento porque a linguagem pode ser infinita.
Linguagem linguagemDe(const Regex& r, std::size_t comprimentoMaximo);
// Compara duas expressões pelas linguagens que denotam, até o comprimento
// dado. Serve para exercitar as identidades algébricas.
//
// Atenção ao que isto é e ao que não é: concordar até um comprimento é
// evidência, não demonstração. Duas expressões podem coincidir até o
// comprimento dez e divergir no onze. A prova de equivalência vem no módulo 5,
// com a unicidade do autômato mínimo.
bool mesmaLinguagemAte(const Regex& a, const Regex& b,
std::size_t comprimentoMaximo);
} // namespace peneira
#endif // PENEIRA_02_REGEX_H
Três pontos da implementação correspondem, um a um, a decisões discutidas na teoria.
Só existem seis construtores no tipo enumerado. As formas derivadas da Definição 3.3 são montadas em termos das primitivas: o fecho positivo é a expressão concatenada com o seu próprio fecho, o opcional é a união com a cadeia vazia, e uma faixa de caracteres é a união dos símbolos que ela abrange. É a recomendação da seção 3.3 aplicada, e o motivo dela aparece no capítulo seguinte: o algoritmo que converte expressão em máquina terá de tratar seis casos, e não doze.
O ponteiro para as subexpressões é compartilhado, e não exclusivo. A razão é estrutural e não de conveniência: ao montar o fecho positivo como a expressão seguida do seu próprio fecho, a mesma subárvore aparece nos dois lados. Com posse exclusiva seria preciso duplicá-la; com posse compartilhada, aponta-se duas vezes para a mesma. É uma das poucas situações em que o compartilhamento é a escolha correta por razão de modelo.
A função que calcula a linguagem denotada é a Definição 3.2 transcrita. Um caso para cada construtor, cada um devolvendo exatamente o que a definição manda: o conjunto vazio, o conjunto com a cadeia vazia, o conjunto com um símbolo, a união, a concatenação, o fecho. Ler essa função lado a lado com a definição do capítulo é o exercício mais curto e mais útil desta seção — são a mesma coisa em duas notações.
A comparação de expressões merece a ressalva que a seção 4.4 estabeleceu, e ela está escrita no próprio cabeçalho do código, e não apenas aqui. Comparar as linguagens denotadas até um comprimento dado é evidência, não demonstração: duas expressões podem coincidir até o comprimento dez e divergir no onze. Um verificador que responde “confere” a todas as identidades da tabela da seção 4.2 é útil e não prova nada. Aliás, vale a disciplina de incluir sempre, na bateria de verificações, um caso que deve divergir — a concatenação em ordens trocadas serve bem —, porque uma bateria em que tudo passa não distingue um verificador que funciona de um que sempre responde que sim.
1.7.3 6.3 A especificação léxica da Peneira
Chego à entrega propriamente dita. A pergunta que ela responde é: quais são os tipos de “palavra” que um programa Peneira contém, e como descrever cada um com precisão total?
Olhando o programa de exemplo do capítulo anterior, encontro nomes, números, textos entre aspas, padrões entre barras, sinais de pontuação e espaços. São seis categorias, e cada uma recebe quatro coisas: o nome, a expressão que a descreve, uma observação que registra a decisão de projeto por trás dela, e os dois corpora — o de cadeias que devem ser aceitas e o de cadeias que devem ser rejeitadas.
02_lexico.h
#ifndef PENEIRA_02_LEXICO_H
#define PENEIRA_02_LEXICO_H
#include <string>
#include <vector>
#include "02_cadeia.h"
#include "02_regex.h"
namespace peneira {
// Uma categoria léxica da linguagem Peneira: o nome, a expressão regular que
// a descreve (em notação textual) e os dois corpora de verificação.
//
// A especificação vive aqui, em código, e não apenas em prosa, porque a
// partir do módulo 7 é ela que o analisador léxico consome. Documento e
// implementação passam a ser a mesma coisa, e não podem divergir.
struct CategoriaLexica {
std::string nome;
std::string notacao;
std::string observacao;
std::vector<Cadeia> aceitas;
std::vector<Cadeia> rejeitadas;
};
// A especificação léxica completa da Peneira.
std::vector<CategoriaLexica> especificacaoLexica();
// Palavras reservadas: casam com a mesma forma de um identificador e precisam
// de desempate por prioridade. O tratamento é do módulo 7; a lista é fixada
// aqui, junto com o resto da especificação.
const std::vector<std::string>& palavrasReservadas();
// Duas categorias ganham também a árvore da expressão regular, e não só a
// notação textual: são as que servem de exemplo de trabalho nos módulos 3 a 5,
// quando a expressão vira autômato. As demais só ganham árvore no módulo 4,
// quando o analisador da notação existir e puder construí-las a partir do
// texto, em vez de à mão.
RegexPtr regexIdentificador();
RegexPtr regexNumero();
} // namespace peneira
#endif // PENEIRA_02_LEXICO_H
02_lexico.cpp
#include "02_lexico.h"
#include <utility>
namespace peneira {
const std::vector<std::string>& palavrasReservadas() {
static const std::vector<std::string> lista{
"pattern", "rule", "on", "where", "emit", "value", "and", "or",
};
return lista;
}
RegexPtr regexIdentificador() {
// letra ( letra | digito | _ )*
RegexPtr letra = faixaRegex('a', 'z');
RegexPtr digito = faixaRegex('0', '9');
RegexPtr sublinhado = simboloRegex('_');
RegexPtr corpo = uniaoRegex(uniaoRegex(letra, digito), std::move(sublinhado));
return concatRegex(faixaRegex('a', 'z'), estrelaRegex(std::move(corpo)));
}
RegexPtr regexNumero() {
// -? digito+ ( . digito+ )?
RegexPtr digito = faixaRegex('0', '9');
RegexPtr sinal = opcionalRegex(simboloRegex('-'));
RegexPtr inteiro = maisUmRegex(digito);
RegexPtr fracao = opcionalRegex(
concatRegex(simboloRegex('.'), maisUmRegex(faixaRegex('0', '9'))));
return concatRegex(concatRegex(std::move(sinal), std::move(inteiro)),
std::move(fracao));
}
std::vector<CategoriaLexica> especificacaoLexica() {
return std::vector<CategoriaLexica>{
CategoriaLexica{
"IDENTIFICADOR",
"[a-z][a-z0-9_]*",
"Começa por letra minúscula. Nomes de padrão e variáveis de "
"ligação. Casa também com as palavras reservadas, que são "
"desempatadas por prioridade no módulo 7.",
{"email", "numero", "e", "n2", "valor_alto", "pattern"},
{"", "2fast", "_oculto", "Email", "com-traco"},
},
CategoriaLexica{
"NUMERO",
"-?[0-9]+(\\.[0-9]+)?",
"Sinal opcional, parte inteira obrigatória, parte fracionária "
"opcional mas com pelo menos um dígito quando presente. Zeros à "
"esquerda são aceitos: rejeitá-los exigiria uma expressão bem "
"maior sem ganho para a linguagem.",
{"0", "100", "-5", "3.14", "-0.5", "007"},
{"", "-", ".5", "5.", "1.2.3", "1e10", "+3"},
},
CategoriaLexica{
"TEXTO",
"\"[^\"]*\"",
"Delimitado por aspas duplas, sem sequências de escape e sem "
"quebra de linha no interior. A ausência de escape é decisão de "
"projeto: evita um subanalisador dentro do analisador léxico.",
{"\"contato\"", "\"\"", "\"valor grande\""},
{"\"", "\"sem fim", "'aspas simples'"},
},
CategoriaLexica{
"PADRAO",
"/[^/]*/",
"O literal de padrão do usuário, delimitado por barras. O texto "
"interno é a mini-expressão regular que o módulo 4 vai analisar; "
"aqui ele é apenas reconhecido como um bloco opaco.",
{"/[a-z]+/", "//", "/-?[0-9]+/"},
{"/", "/sem fim", "[a-z]+"},
},
CategoriaLexica{
"PONTUACAO",
"\\(|\\)|\\{|\\}|;|,|=>|==|!=|>=|<=|=|>|<",
"Inclui os operadores de comparação. Os de dois caracteres criam "
"a necessidade do casamento mais longo: sem ele, \">=\" seria "
"lido como \">\" seguido de \"=\". Os parênteses vão escapados "
"porque na notação eles são agrupamento, não símbolo — a versão "
"anterior desta linha estava escrita como prosa legível, com "
"espaços entre as alternativas, e reconhecia a linguagem errada "
"em silêncio. O defeito só apareceu no módulo 7, quando o "
"analisador léxico passou a usar este autômato de verdade.",
{"=", "=>", ">=", "!=", ";", "{"},
{"", "=>>", "=!", "%"},
},
CategoriaLexica{
"ESPACO",
"[ \\t\\r\\n]+",
"Separa símbolos e é descartado pelo analisador léxico, sem virar "
"símbolo. Precisa existir na especificação mesmo sendo descartado: "
"é o que permite ao analisador saber onde um identificador termina.",
{" ", " ", "\t"},
{"", "a "},
},
};
}
} // namespace peneira
A decisão de forma vem da seção 3.5 e é a mais consequente deste bloco: a especificação está escrita como dado executável, e não como prosa em um documento à parte. A partir do capítulo sobre análise léxica, é esta mesma estrutura que o analisador vai consumir. Documento e implementação passam a ser o mesmo objeto, e por construção não podem divergir.
Vale percorrer as decisões que a especificação registra, porque cada uma ilustra um ponto da teoria.
Os identificadores começam por letra minúscula e admitem dígitos e sublinhado depois. Não aceitam maiúsculas, o que é restrição deliberada da linguagem: reduz o alfabeto e dispensa decidir se dois nomes que diferem só na caixa são o mesmo nome. Repare que a categoria casa também com as palavras reservadas — a palavra que introduz uma declaração de padrão é um identificador perfeitamente válido segundo a expressão. Isso não é defeito, é a situação normal em qualquer linguagem, e o desempate por prioridade é assunto de um capítulo adiante. Está anotado para não parecer descuido a quem releia.
Os números aceitam zeros à esquerda, e a cadeia correspondente aparece no corpus de aceitação de propósito. Rejeitá-los exigiria uma expressão bem maior — um dígito não nulo seguido de dígitos, ou um zero isolado — sem ganho para esta linguagem. É decisão consciente de manter a expressão pequena, e ela está registrada. Os quatro casos de fronteira analisados na seção 3.4 são exatamente os que aparecem aqui nos corpora.
Os textos não têm sequências de escape, e essa é a decisão de escopo mais importante do capítulo. Admitir uma aspa escapada dentro de um texto significa um pequeno analisador dentro do analisador léxico, com estado próprio. A linguagem fica menos expressiva e o percurso do livro fica viável.
O literal de padrão é reconhecido como bloco opaco: o conteúdo entre barras é a mini-expressão regular escrita por quem usa a linguagem, e o analisador léxico não olha para dentro dele — apenas reconhece que vai de barra a barra. Quem analisa o interior é outro componente, dois capítulos adiante. Separar as duas coisas é o que impede que o analisador da linguagem e o analisador da notação de padrões virem um emaranhado só.
A pontuação inclui operadores de dois caracteres, e é isso que cria a necessidade de uma regra de desempate por comprimento no reconhecimento. Sem ela, o operador de maior ou igual seria lido como dois símbolos separados, e uma condição perfeitamente escrita seria analisada errado sem que nada acusasse. É o exemplo mais concreto disponível para justificar, no capítulo sobre análise léxica, uma regra que de outro modo pareceria detalhe arbitrário.
Os espaços são categoria de primeira classe, ainda que descartados. Costumam ser esquecidos da especificação porque não viram símbolo na saída, e é justamente o espaço que informa onde um identificador termina — sem ele descrito, não há como o analisador saber onde cortar.
Vale notar, por fim, o que a notação da especificação não contém: nenhum retrovisor, nenhum olhar adiante, nenhuma construção recursiva. A exclusão segue o critério da seção 5.5, e a razão cabe em uma linha — essas construções não pertencem à classe que o motor desta linguagem reconhece. Aqui a teoria não apenas explicou a decisão de escopo; ela a tomou.
1.7.4 6.4 O que esta entrega ainda não pode fazer
Registro a limitação honesta desta etapa, porque ela é informativa e porque escondê-la daria a impressão errada de completude.
Os corpora de aceitação e de rejeição ainda não são executáveis. Não existe reconhecedor: tudo o que este capítulo produziu foi notação e a função que calcula, por enumeração limitada, a linguagem que uma expressão denota. Os corpora são contrato, escrito antes da implementação e de propósito antes dela. No capítulo seguinte, quando o primeiro reconhecedor aparecer, eles deixam de ser texto e passam a ser teste; alguns capítulos depois, quando a construção automática de máquinas a partir de expressões estiver pronta, passam a ser verificados por completo, para todas as seis categorias.
Escrever o teste antes do código não é formalidade neste caso: é o que permitirá, mais adiante, saber se o que foi construído está certo — em vez de apenas observar que ele roda sem falhar.
1.8 Síntese
Recapitulo a linha do argumento, simples apesar da densidade. Partimos de três primitivos: um alfabeto finito e não vazio, uma cadeia como sequência finita de símbolos e a concatenação, associativa, com a cadeia vazia como neutro e sem comutatividade. Subimos para as linguagens, subconjuntos quaisquer do universo das cadeias, com as operações booleanas mais a concatenação e o fecho — e é o fecho que produz infinitude a partir de descrição finita. Sobre essa base entraram as expressões regulares, com sintaxe indutiva de três casos-base e três construtores e semântica definida pela mesma indução. Tudo o que a notação prática oferece além disso ou é açúcar eliminável ao custo de tamanho, ou está fora da classe e muda o problema — e a fatura dessa mudança tem nome, data e serviço derrubado.
Falta a este módulo, propositalmente, uma coisa: aprendemos a descrever linguagens e não sabemos reconhecê-las. A única implementação que esta teoria permite, enumerar as cadeias e procurar na lista, não termina para nenhuma linguagem infinita. Essa insuficiência é o motivo de o próximo módulo existir. Ele apresenta a máquina: um dispositivo com quantidade finita de memória, que lê a entrada símbolo por símbolo, da esquerda para a direita, sem nunca voltar atrás, e ao final responde sim ou não. Parece fraco demais para servir a alguma coisa; e é exatamente ele que reconhece as linguagens descritas pela notação deste módulo.
Se de tudo isto você retiver uma coisa só, que seja a diferença entre a linguagem vazia e a linguagem que contém a cadeia vazia, com o que dela decorre: a potência zero de qualquer linguagem, o fecho de Kleene do conjunto vazio, o neutro contra o absorvente da concatenação. Não é a ideia mais profunda do módulo; é a que mais volta disfarçada nos próximos.