ti-enxame.com

Escrevendo um analisador para expressões regulares

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 regex, 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 regulares corretamente , 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 estendida 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.

EDIT: Eu devo esclarecer que, enquanto vou implementar o analisador de expressões regulares em Python, não estou muito preocupado sobre em qual linguagem de programação os exemplos ou artigos estão escritos. Enquanto não estiver em Brainfuck, provavelmente vou entender o suficiente para fazer valer a pena.

66
Chinmay Kanchi

Escrever uma implementação de um mecanismo de expressão regular é realmente uma tarefa bastante complexa.

Mas se você estiver interessado em fazê-lo, mesmo que não consiga entender o suficiente dos detalhes para implementá-lo, eu recomendaria que você olhasse para este artigo:

A correspondência de expressões regulares pode ser simples e rápida (mas é lenta em Java, Perl, PHP, Python, Ruby, ...)

Ele explica quantas das linguagens de programação populares implementam expressões regulares de uma maneira que pode ser muito lenta para algumas expressões regulares e explica um método ligeiramente diferente que é mais rápido. O artigo inclui alguns detalhes de como a implementação proposta funciona, incluindo algum código-fonte em C. Pode ser uma leitura um pouco pesada se você está apenas começando a aprender expressões regulares, mas acho que vale a pena conhecer a diferença entre os dois abordagens.

37
Mark Byers

Eu já dei +1 a Mark Byers - mas, pelo que me lembro, o artigo não diz muito sobre como a correspondência de expressões regulares funciona além de explicar por que um algoritmo é ruim e outro muito melhor. Talvez algo nos links?

Vou me concentrar na boa abordagem - criando autômatos finitos. Se você se limitar a autômatos determinísticos sem minimização, isso não é realmente muito difícil.

O que descreverei (muito rapidamente) é a abordagem adotada em Design Moderno do Compilador .

Imagine que você tem a seguinte expressão regular ...

a (b c)* d

As letras representam caracteres literais para corresponder. O * é a correspondência usual de zero ou mais repetições. A idéia básica é derivar estados com base em regras pontilhadas. O estado zero tomaremos como o estado em que nada foi correspondido ainda, então o ponto fica na frente ...

0 : .a (b c)* d

A única correspondência possível é 'a', então o próximo estado que derivamos é ...

1 : a.(b c)* d

Agora temos duas possibilidades - corresponder ao 'b' (se houver pelo menos uma repetição de 'b c') ou corresponder ao 'd' caso contrário. Nota - estamos basicamente fazendo uma pesquisa de dígrafos aqui (primeiro a profundidade ou a largura primeiro ou o que for), mas estamos descobrindo o dígrafo à medida que o pesquisamos. Supondo uma estratégia abrangente, precisaremos enfileirar um de nossos casos para consideração posterior, mas ignorarei esse problema daqui em diante. Enfim, descobrimos dois novos estados ...

2 : a (b.c)* d
3 : a (b c)* d.

O estado 3 é um estado final (pode haver mais de um). Para o estado 2, podemos apenas corresponder ao 'c', mas precisamos ter cuidado com a posição do ponto posteriormente. Temos "a. (B c) * d" - que é o mesmo que o estado 1, portanto não precisamos de um novo estado.

IIRC, a abordagem no Design moderno do compilador é traduzir uma regra quando você atinge um operador, a fim de simplificar o manuseio do ponto. O estado 1 seria transformado em ...

1 : a.b c (b c)* d
    a.d

Ou seja, sua próxima opção é corresponder à primeira repetição ou pular a repetição. Os próximos estados são equivalentes aos estados 2 e 3. Uma vantagem dessa abordagem é que você pode descartar todas as suas correspondências anteriores (tudo antes do '.'), Pois só se importa com futuras correspondências. Isso normalmente fornece um modelo de estado menor (mas não necessariamente mínimo).

[~ # ~] editar [~ # ~] Se você descartar os detalhes já correspondentes, a descrição do seu estado é uma representação do conjunto de cadeias que pode ocorrer a partir deste ponto.

Em termos de álgebra abstrata, esse é um tipo de fechamento de conjunto. Uma álgebra é basicamente um conjunto com um (ou mais) operadores. Nosso conjunto é de descrições de estado e nossos operadores são nossas transições (correspondências de caracteres). Um conjunto fechado é aquele em que a aplicação de qualquer operador a qualquer membro do conjunto sempre produz outro membro que está no conjunto. O fechamento de um conjunto é o conjunto maior que é fechado. Então, basicamente, começando com o estado inicial óbvio, estamos construindo o conjunto mínimo de estados que é fechado em relação ao nosso conjunto de operadores de transição - o conjunto mínimo de estados alcançáveis.

Mínimo aqui refere-se ao processo de fechamento - pode haver um autômato equivalente menor que normalmente é chamado de mínimo.

Com essa idéia básica em mente, não é muito difícil dizer "se eu tenho duas máquinas de estados representando dois conjuntos de cadeias, como derivar um terço representando a união" (ou interseção ou diferença de conjunto ...). Em vez de regras pontilhadas, suas representações de estado serão um estado atual (ou conjunto de estados atuais) de cada autômato de entrada e talvez detalhes adicionais.

Se suas gramáticas regulares estão ficando complexas, você pode minimizar. A idéia básica aqui é relativamente simples. Você agrupa todos os seus estados em uma classe de equivalência ou "bloco". Em seguida, você testa repetidamente se precisa dividir os blocos (os estados não são realmente equivalentes) com relação a um tipo de transição específico. Se todos os estados de um bloco específico puderem aceitar uma correspondência do mesmo caractere e, ao fazê-lo, atingir o mesmo bloco seguinte, eles serão equivalentes.

O algoritmo Hopcrofts é uma maneira eficiente de lidar com essa ideia básica.

Uma coisa particularmente interessante sobre minimização é que todo autômato finito determinístico tem precisamente uma forma mínima. Além disso, o algoritmo Hopcrofts produzirá a mesma representação dessa forma mínima, independentemente da representação de qual caso maior ele começou. Ou seja, essa é uma representação "canônica" que pode ser usada para derivar um hash ou para pedidos arbitrários, mas consistentes. O que isso significa é que você pode usar autômatos mínimos como chaves em contêineres.

O exposto acima é provavelmente um pouco desleixado das definições de WRT, portanto, verifique todos os termos antes de usá-los, mas com um pouco de sorte, isso dará uma rápida introdução às idéias básicas.

BTW - dê uma olhada no resto de site de Dick Grunes - ele tem um livro gratuito PDF sobre técnicas de análise. A primeira edição do Modern Compiler Design é muito boa IMO , mas como você verá, há uma segunda edição iminente.

21
Steve314

Este artigo adota uma abordagem interessante. A implementação é dada em Haskell, mas foi reimplementada em Python pelo menos uma vez.

7
dhaffey

Há um capítulo interessante (embora um pouco curto) em Beautiful Code de Brian Kernighan, apropriadamente chamado "A Regular Expression Matcher". Nele, ele discute um comparador simples que pode corresponder a caracteres literais e o .^$* símbolos.

6
Richard Fearn

Concordo que escrever um mecanismo de regex melhorará a compreensão, mas você deu uma olhada no ANTLR ??. Ele gera os analisadores automaticamente para qualquer tipo de idioma. Então, talvez você possa tentar pegar uma das gramáticas de idiomas listadas em exemplos de gramática e percorrer o AST e o analisador que ele gera. código, mas você terá um bom entendimento de como um analisador funciona.

1
A_Var