Como o REGEXP é implementado nas linguagens de programação?

7

Existe um bom artigo geral sobre a interpretação ou compilação do REGEXP em linguagens de programação para correspondência de padrões, com ou sem variáveis? Não estou procurando uma explicação rápida sobre a construção de DFAs, mas um artigo real sobre como isso é realmente feito na implementação de linguagens de programação e o que é considerado simples ou difícil. Espero que as diferenças entre os idiomas possam ter um impacto. Um documento formal sobre como a implementação do REGEXP deve ser realizada também é útil :-)

programming-languages compilers regular-expressions matching interpreters babou
fonte
Obviamente, essa é uma pergunta antiga, mas pensei em acrescentar que, como alternativa à construção de Thompson, gosto bastante da idéia da construção de Berry-Sethi, que usa exatamente mais um estado do que o regex possui símbolos terminais . Ver como a correspondência entre os NFAs é feita ao encontrar os estados alcançáveis ​​em tempo real, porém, isso é quase um ponto mudo. Talvez a falta de transições ϵ seja atraente. A única referência que posso dar são esses slides .
G. Bach
@ G.Bach Não existe uma pergunta antiga, a menos que os avanços técnicos tenham tornado o tópico obsoleto. AFAIK, isso também pode ser uma resposta, se você realmente puder relacioná-lo à implementação do REGEXP nas linguagens de programação. Pode ser usos existentes ou usos sugeridos. As versões de linguagens de programação do REGEXP possuem uma variedade de sinos e assobios que podem ou não ser compatíveis com o método Berry-Sethi. Eu acho que a construção Berry-Sethi é usada na implementação da linguagem Esterel, mas não para o REGEXP, AFAIK.
babou 30/07/2014
Eu realmente não acho que uma resposta separada seja merecida, foi mais um comentário que "existem outras construções além da Thompson que são igualmente eficientes"; Eu realmente não sei onde ele é usado em nenhuma ferramenta, só gostei da idéia quando soube disso, que estava de fato no contexto da criação de um NFA free, aceitando o idioma de uma expressão regular. ϵ
G. Bach
@ G.Bach Eu pensei que poderia ser útil lembrar as pessoas de variantes interessantes. Mas transformá-lo em uma resposta adequada para a pergunta, como de fato pode ser um pouco de trabalho. Obrigado mesmo assim.
babou 30/07/2014

Respostas:

5

Acredito que a maioria dos correspondentes de expressão regular interpretada começa com o algoritmo de construção de Thompson para transformar a expressão regular em um autômato finito não determinístico. O artigo que os descreveu pela primeira vez é: Ken Thompson, "Técnicas de programação: algoritmo de busca por expressão regular", Communications of the ACM , 11 (6): 419-422, junho de 1968. Mas esse trabalho é um pouco difícil de ler, pois ele estava compilando para o código da máquina.

Meu tutorial favorito sobre implementação de expressões regulares é esta série de posts de Russ Cox , autor da biblioteca de expressões regulares RE2. Ele dá muita discussão histórica. Ele argumenta que a abordagem mais eficiente para simular o NFA é converter o DFA em tempo real com o cache apenas dos estados do DFA que você realmente alcança. (Em contraste com, por exemplo, a implementação de expressões regulares no Perl, que usam backtracking.) Há casos (por exemplo, quando você obtém expressões regulares estendidas com referências), em que você precisa usar o backtracking, mas Cox sugere que você deve use o retorno sempre que precisar.

O outro lugar que você pode procurar é a biblioteca de expressões regulares de Henry Spencer . De acordo com esse site, isso foi descrito no livro: Dale Schumacher (ed), Software Solutions In C , Academic Press, 1994.

Lógica Errante
fonte