Mesmo depois de anos de programação, tenho vergonha de dizer que nunca compreendi totalmente expressões regulares. Em geral, quando um problema exige uma expressão regular, geralmente (após várias referências à sintaxe) é possível encontrar uma apropriada, mas é uma técnica que me vejo usando cada vez mais.

Então, para me ensinar e entender expressões regularesdevidamente, Decidi fazer o que sempre faço ao tentar aprender alguma coisa; ou seja, tente escrever algo ambicioso que provavelmente abandonarei assim que sentir que aprendi o suficiente.

Para esse fim, quero escrever um analisador de expressões regulares em Python. Nesse caso, "aprenda o suficiente" significa que quero implementar um analisador que possa entender completamente a sintaxe de regex extendida do Perl. No entanto, ele não precisa ser o analisador mais eficiente ou mesmo necessariamente utilizável no mundo real. Ele apenas precisa corresponder corretamente ou falhar ao corresponder a um padrão em uma sequência.

A questão é: por onde começo? Não sei quase nada sobre como as expressões regulares são analisadas e interpretadas, exceto pelo fato de envolver de algum modo um autômato de estado finito. Qualquer sugestão de como abordar esse problema bastante assustador seria muito apreciada.

EDITAR: Eu deveria esclarecer que enquanto eu vouimplemento o analisador de expressões regulares em Python, não estou muito preocupado com a linguagem de programação em que os exemplos ou artigos são escritos. Enquanto não estiver em Brainfuck, provavelmente vou entender o suficiente para fazer valer a pena.