On computing all patterns matched by a regular expression

[Code/código: regexPrinter]

A regular expression, without much rigor, is a very compact way of representing several different strings. One common use of regular expressions is to look for strings that have a certain structure in a bigger string (say a text). As an example, the regular expression abc(d|e) can be used to look for the strings "abcd" and "abce", where the character | denotes we have to make a choice. Thus cat|dog would match the strings "cat" and "dog". There are other special symbols that have meanings and purposes.

One very interesting question that arises is: given a regular expression, what are the strings matched by it? To answer that question I wrote a small Python program, that I called regexPrinter, that prints all strings matched by a given regular expression! In order to manage that task, I chose a subset of the regex syntax that I wanted to be able to print and also decided that whenever a piece of a pattern was infinite, at a given point the program would just print "..." to denote that infinity. This way, for any regex given, the program always stops.

The regexPrinter supports:

1. The * operator, that denotes that 0 or more repetitions are to be matched. For example, ah* matches "a", "ah", "ahh", ...;
2. The + operator that denotes that 1 or more repetitions are to be matched. For example, (hue)+ matches "hue", "huehue", "huehuehue", ...;
3. The ? operator that denotes either 0 or 1 occurrences of the preceding pattern. For example, woo(hoo)? matches "woo" and "woohoo";
4. The {$min$:$max$} operator that matches no less than $min$ and no more than $max$ repetitions of the preceding pattern. As an example, su{1:3}re matches the strings "sure", "suure" and "suuure";
5. The | operator that denotes a choice. cat|kat matches "cat" and "kat" and thank(s| you) matches "thanks" and "thank you";
6. The [] denote that only one pattern from the ones given are to be matched. For example [abc] matches "a", "b" and "c";
7. The parenthesis () that are used to group things. One thing to note is that the quantifiers *,+,?,{:} all have higher precedence than string concatenation e.g., ab? is interpreted as a(b?) and not (ab)?.

Please bear in mind that any character with no special meaning is interpreted literally, except inside the grouping operator [], where every character is interpreted literally. That is, [ab*] matches "a", "b" and "*", while b\&=' will match the string "b\&='".

The code for the program can be found here on GitHub and all it takes is vanilla Python3 to run. Just run the script and you will be prompted to insert regular expressions. The techniques I used were very, very similar to the ones I used to create my toy programming language, as I saw in this blog series. The way I went about writing this program was by implementing a parser for a subset of the grammar used by regular expressions, generating a tree representation for the regex, and then visiting all nodes of the tree, where each node knows how to print itself.

[Pt] Expressões regulares são uma maneira compacta de representar várias sequências de caracteres com alguma estrutura em comum. Estas podem ser usadas, por exemplo, para encontrar várias ocorrências de um certo padrão num texto, e substituí-lo por outro padrão (semelhante ou não). Um exemplo de uma expressão regular é cao|gato, que pode ser usada para encontrar as sequências "cao" e "gato". Assim, vemos que o | significa que devemos escolher apenas um dos padrões.

Uma pergunta interessante que surge é: dada uma expressão regular, quais são as sequências de caracteres que podem ser encontradas por ela? Para responder a essa pergunta, criei um pequeno programa em Python, a que chamei regexPrinter, que recebe uma expressão regular e imprime no ecrã todas as sequências que poderiam ser encontradas pela expressão. Para fazer isto, fiz com que, nos padrões infinitos, o programa imprimisse os casos mais pequenos e depois pusesse "..." para indicar essa infinitude, e escolhi também uma parte da sintaxe das expressões regulares que queria implementar.

Escolhi implementar os operadores *,+,? e {n:m}, que definem o número de repetições que um certo padrão pode ter: * repete 0 ou mais vezes, + repete 1 ou mais vezes, ? repete 0 ou 1 vezes, e {$n$:$m$} repete não menos do que $n$ e não mais do que $m$ vezes um padrão. Assim, ah* captura "a", "ah", "ahh", "ah...", etc; (hue)+ captura "hue", "huehue", "huehuehue", etc; woo(hoo)? captura "woo" e "woohoo" e po{1:3}is captura "pois", "poois" e "pooois". Implementei também o operador de escolha |, os parêntesis curvos () para se poderem agrupar padrões e alterar as prioridades dos operadores, e implementei os parêntesis retos, [], que definem que apenas um caracter do grupo deve ser capturado. Por exemplo [abc] captura as sequências "a", "b" e "c".

Qualquer caracter que não tenha um significado especial é interpretado literalmente, exceto dentro dos parêntesis retos [], onde todos os caracteres são interpretados literalmente.

O código pode ser encontrado aqui no GitHub e está em Python3. Para usar o regexPrinter basta correr o script e escrever expressões regulares no prompt. A técnica que usei para isto foi escrever uma gramática para o pedaço da sintaxe das expressões regulares que eu queria saber imprimir, escrevi um parser para essa gramática, e dada uma expressão regular uso o parser para a transformar numa árvore, onde cada nó se sabe imprimir. Em particular, foi algo parecido com o que fiz na minha linguagem de programação a fingir, aprendido nesta série de posts.

Let me know what you think!

-RGS