Derivadas de expressões regulares explicadas usando o Pac-Man

Nov 25 2022

Um tutorial explicando o algoritmo de correspondência de expressão regular funcional

Comer cerejas vermelhas dá a você a habilidade de comer fantasmas azuis. A ideia de que derivados podem ser usados para criar um algoritmo de correspondência de expressão regular é quase tão ridícula.

imagens por autor | fantasma e cerejas de Pac-Man

Em 1964, Brzozowski publicou o primeiro artigo sobre Derivadas de Expressões Regulares . Este é de longe um dos meus algoritmos favoritos. Usando derivadas de expressões regulares, podemos implementar um algoritmo para fazer correspondência de expressão regular. Este algoritmo é muito:

simples
funcional
facilmente extensível com seus próprios operadores

Neste artigo, mostrarei como podemos combinar uma string com uma expressão regular usando apenas duas funções puras e algumas analogias do Pac-Man. Se preferir, você pode assistir ao vídeo a seguir em vez de ler o artigo, pois ele aborda o mesmo material:

Recapitulação de Expressões Regulares

Primeiro, vamos fazer uma revisão rápida das expressões regulares para garantir que estamos na mesma página. A expressão a(a|b)*corresponde a uma string que começa com um a, que é seguida por qualquer número de a' se b'.

A string abcorresponderá a(a|b)*. Vamos indicar isso com um fantasma comestível azul.
A string aabbbatambém corresponde a(a|b)*, pois começa com um ae é seguida por vários a's e b's.
Em seguida, a string acnão corresponde a(a|b)*, pois o regex não corresponde ca nenhum e nosso regex não faz nenhuma correspondência de substring. Indicaremos isso usando um fantasma vermelho que está perseguindo o Pac-Man.
Por fim, a string batambém não corresponde a(a|b)*porque não começa com um a.

Visão geral do algoritmo

Antes de nos aprofundarmos nos detalhes, vamos obter uma visão geral de como esse algoritmo funciona. Eu criei um jogo estranho de Pac-Man onde você só come os fantasmas se comer a fruta em uma sequência que corresponda ao regex. Nosso Pac-Man representa o regex aba*. Tem a seguinte sequência de frutas para comer: uma maçã, depois uma banana e depois uma maçã: aba.

Quando começamos, o fantasma está nos perseguindo e a expressão regular que resta para corresponder é aba*.
Comemos a primeira maçã, e a expressão regular que resta para corresponder é ba*. O fantasma ainda está nos perseguindo, pois a fruta que comemos até agora, a maçã, não corresponde ao regex.
Em seguida, comemos a banana. O regex que resta para corresponder é a*. Agora o fantasma começa a fugir porque, tecnicamente, abjá combina aba*.
Podemos tentar comer o fantasma ou comer outra maçã, caso em que a expressão regular que falta corresponder ainda é a*. O fantasma ainda está fugindo, pois abatambém corresponde à expressão regular aba*.

Animação do Pac-Main comendo uma maçã, uma banana e outra maçã

Há mais uma função em ação aqui. A função verifica se o fantasma está perseguindo o Pac-Man ou se o Pac-Man já correspondeu ao regex e está perseguindo o fantasma. Essa função é chamada de função anulável; ele verifica se o regex que falta corresponder corresponde à string vazia. Ele pode fazer isso porque, se o regex restante corresponder à string vazia, a fruta que comeu já deve ter sido suficiente para satisfazer o regex.

nullable: corresponde à string vazia

não anulável: não corresponde à string vazia

Algoritmo de Combinação de Derivadas

Isso significa que precisamos apenas de duas funções para escrever o algoritmo de correspondência derivada:

a função derivada
a função anulável

Um em Golang para os programadores imperativos:

e outro em Haskell para programadores funcionais:

Essas duas funções são equivalentes e apenas escritas em diferentes estilos de programação. No código Haskell, foldltambém chamado de dobrar à esquerda ou reduzir em outras linguagens, faz o trabalho do loop for para você. Além disso, em Haskell, não precisamos de vírgulas para passar parâmetros para funções; como a aplicação de função é a operação mais comum em uma linguagem de programação funcional, usamos espaço para delimitar os parâmetros.

Agora, vamos nos aprofundar em como implementar as funções anuláveis e derivadas.

Digressão da história da origem do Pac-Man

Mas antes de fazermos isso, não sei se você já se perguntou sobre a história da origem do Pac-Man. Eu afirmo que não houve barril de lixo nuclear no qual Pac-Man caiu, resultando em Pac-Man ganhando o poder de comer fantasmas. A lógica é bem mais simples.

Pac-Man é uma fruta! Quando Pac-Man come outra fruta, Pac-Man está sendo um canibal. Portanto, se você for perseguido por um fantasma, terá que comer um pouco de carne humana, e o fantasma deve, pelo menos temporariamente, começar a fugir de você. Agora, eu não tentei isso sozinho, mas a lógica parece sólida.

Isso explica por que os zumbis estão sempre perseguindo os humanos. Como David Attenborough disse uma vez:

“Os zumbis que estão nos perseguindo estão sendo perseguidos por fantasmas que não podemos ver. Depois que os zumbis comerem um pouco de nossa carne humana, você os verá exibindo o estranho comportamento de mastigar o ar, este é o zumbi comendo o fantasma que o perseguia antes.

Operadores Básicos

A implementação das funções anuláveis e derivadas requer que primeiro definamos os operadores básicos disponíveis em nossas expressões regulares.

Podemos pensar em uma expressão regular como descrevendo um conjunto de strings.

Isso significa que o conjunto vazio representa um operador que não corresponde a strings.
A string vazia representa um conjunto singleton de uma única string que corresponde apenas à string vazia.
O caractere também representa um conjunto singleton que corresponde apenas ao caractere único a.
Podemos então combinar essas expressões regulares de base usando operadores como: or, concatenatione Kleene star, onde re srepresenta as duas expressões de expressão regular que estamos combinando.

Função anulável

Podemos começar com a função anulável. Vamos ver alguns exemplos e descobrir qual dessas expressões regulares corresponde à string vazia para entender como essa função é implementada.

a*corresponde à string vazia, pois zero ou mais inclui zero.
(a*|b)corresponde à string vazia, pois o lado esquerdo de or corresponde à string vazia.
abnão corresponde à string vazia, pois corresponde apenas à stringab
ab*também não corresponde à string vazia, pois ab*requer uma string que comece com uma
(a|b)não corresponde à string vazia, pois nem o lado esquerdo nem o direito de orcorrespondem à string vazia.

exemplos anuláveis

Aqui está a implementação da função anulável. O lado esquerdo representa os valores que são passados para a função e o lado direito representa a implementação da função nesse caso. Os fantasmas vermelhos representam falsos e os fantasmas azuis representam verdadeiros:

implementação da função anulável

O conjunto vazio não corresponde à string vazia, pois não corresponde a nenhuma string.
A string vazia corresponde à string vazia porque corresponde apenas à string vazia.
O caractere anão corresponde à string vazia porque corresponde apenas ao caractere a.
Se tivermos um lógico or, temos que verificar os dois lados. Se qualquer um corresponder à string vazia, o lógico orcorresponderá à string vazia.
Para concatenationque duas expressões regulares correspondam à string vazia, ambas devem corresponder à string vazia.
E, finalmente, se tivermos zero or morealgo, isso inclui zero, o que significa que sempre corresponde à string vazia.

Nosso operador superior é o ormeio que temos para verificar a nulidade dos lados esquerdo e direito: be a*.
Verificamos e vemos que o caractere bdo lado esquerdo não é anulável: false.
Em seguida, verificamos e vemos que o a*do lado direito é anulável: true.
Agora voltamos falsee truepodemos orpegá-los true.

exercícios anuláveis

Tente percorrer a implementação e verifique se as expressões regulares a seguir são anuláveis. Você pode clicar neles para verificar sua resposta:

uma
a*(b*|∅)
εa
∅*
(∅|b)*(abc|ε)

Antes de examinarmos a implementação da função, vejamos exemplos de uma derivada. Aqui vamos obter a derivada de algumas expressões regulares, todas em relação ao caractere a:

A expressão regular que resta para corresponder depois a*de comer uma amaçã ainda é a*.
A derivada de ab*em relação a aé b*, pois já combinamos o prefixo a.
A derivada de (a|b)bem relação a aé b.
A derivada de b|(a*b)em relação a aé a*b. A esquerda bnão combinava, então poderíamos jogá-la fora e afoi consumida pela zero or more adireita.
Em seguida, temos ab*, este é um pouco complicado. Depois que ele come a maçã, a expressão regular que falta corresponder é b(ab)*. Como só combinamos o a, esperamos ver pelo menos mais um b.

A derivada do conjunto vazio é sempre o conjunto vazio. Não há como recuperar, pois o conjunto vazio não corresponde a nada.
A derivada da string vazia referente a qualquer caractere é o conjunto vazio. Não esperava corresponder a um personagem. Ele corresponderá apenas à string vazia.
A derivada de um único caractere para um caractere semelhante (neste caso, o apple) é a string vazia, pois depois que ela corresponde a si mesma, tudo o que resta para corresponder é a string vazia.
A derivada de um caractere em relação a um caractere diferente que não é igual, neste caso, o banana, é o conjunto vazio, pois não combinamos o caractere específico.
A derivada de uma orexpressão é a ordas derivadas. Ele simplesmente empurra o problema para seus filhos.
A derivada da concatexpressão deve considerar se pode pular a primeira expressão. Ele só pode ignorar a primeira expressão se a primeira expressão corresponder à string vazia e for anulável. Então, a primeira coisa que fazemos é verificar isso. Vamos pensar no caso em que não é possível pular a primeira expressão quando a expressão rnão é anulável. Então a derivada é a derivada da primeira expressão concatenatedcom a segunda expressão s. Se pudermos pular a primeira regex, teremos que considerar uma alternativa que seja apenas a derivada da segunda expressão. Podemos, então, oras duas alternativas de pular re não pular re retornar isso como resultado.
Finalmente, temos o staroperador. Corresponde a uma expressão zero ou mais vezes. Como estamos passando um caractere, esse não é o caso zero. Portanto, temos que considerar o one or morecaso. Isso significa que temos que derivar a expressão dentro de stare concatenatenovamente com a zero or moreexpressão.

Exemplo de derivada 1

Vamos calcular a derivada de (ab)*em relação a a.

(ab)*é uma zero or moreexpressão, então olhamos para a zero or moreregra. Vemos que isso requer a derivada da expressão dentro de star.

Este é o concatenationde ae b. Portanto, verificamos se o lado esquerdo é anulável e o caractere anão é anulável. Isso significa que não podemos ignorá-lo. Temos que calcular a derivada de aem relação a a. Mas essa é a string vazia, então se nós concatenatea string vazia com o lado direito, que era b, obtemos b.

Agora, recursamos de volta para zero or more, lembre-se de que tiramos a derivada de abem relação a ae retornamos a b. Agora podemos concatenar isso com (ab)*novamente e obtemos b(ab)*.

Exemplo de derivada 2

Vamos calcular a derivada de (a*ba)em relação a b.

a*é concatenado ba, então vamos dar uma olhada na regra de concatenação.
Verificamos se o lado esquerdo a*é anulável, o que é. Isso significa que podemos ignorá-lo, o que também significa que temos que criar uma orde duas derivadas.
O lado esquerdo acaba não combinando, já a*que não combina b.
Felizmente, temos uma alternativa, o arquivo ba. A derivada de baem relação a bé e a.

Eu pulei alguns detalhes aqui. Considere um exercício verificar meu trabalho percorrendo você mesmo a função.

exercícios derivados

Tente percorrer a implementação e verifique quais são as derivadas das seguintes expressões regulares em relação a b. Você pode clicar neles para verificar sua resposta:

εb
b*(b|c)
a*(b|c)
bεb
∅*b

Espero que agora você entenda por que comer cerejas vermelhas lhe dá a capacidade de comer fantasmas azuis e como implementar um correspondente de expressão regular usando o algoritmo derivado.

Cobrimos o algoritmo de trabalho básico aqui, mas há muitas maneiras de tornar esse algoritmo ainda melhor com pequenos ajustes. Nós trapaceamos e encobrimos as regras de simplificação neste post, usando-as sem explicá-las, o que se tornará especialmente óbvio se você percorrer os exercícios. Também não discutimos como você pode usar memoização para construir preguiçosamente um autômato eficiente.

Também podemos facilmente estender o algoritmo para incluir novos operadores como, note interleaveaté mesmo suportar gramáticas livres de contexto. Vou discutir alguns desses tópicos no próximo artigo .

Enquanto isso, eu adoraria ver sua implementação desse algoritmo em uma linguagem de programação com a qual você se sinta mais confortável. Por favor, envie-me um link nos comentários.