Expressões regulares não são

36

Pergunte até a alguém com experiência em ciência da computação o que é uma expressão regular e é provável que a resposta ultrapasse a restrição de estar ao alcance de um autômato de estado finito.

Por exemplo, a "expressão regular"

/^1?$|^(11+?)\1+$/

criado pela notável personalidade do Perl, Abigail (e parte do conjunto de testes do Perl desde 2002) descreve uma máquina que aceita apenas números unários compostos, mas o exercício 4.5 (b) da terceira edição de Uma Introdução às Linguagens Formais e Autômatos de Peter Linz, faz com que o leitor use o lema de bombeamento para provar que

L={an:n is not a prime number}

não é uma linguagem comum.

Em contextos em que a distinção é importante, como devemos chamar expressões estritamente mais poderosas?

Greg Bacon
fonte

Respostas:

46

Larry Wall propôs que usássemos "expressão regular" para o formalismo proposto por Kleene e "regex" para expressões para as extensões amplamente usadas. É uma convenção bastante amplamente seguida. Se você quiser deixar claro que está falando sobre expressões regulares no sentido de idiomas formais, geralmente não é difícil traduzir para falar de idiomas regulares.

O poder das regexes vem do backtracking, e tem havido trabalho feito em autômatos para idiomas regulares com backtracking. Veja, em particular, Becchi & Crowley, 2008, Estendendo os autômatos finitos para corresponder com eficiência às expressões regulares compatíveis com Perl .

Charles Stewart
fonte
5
Concordo que algo como "Perl regex" ("POSIX regex" etc.) versus "linguagem comum" deve ser claro o suficiente para evitar qualquer possibilidade de má interpretação.
Jukka Suomela
As regexes Perl têm muito mais recursos adicionais do que apenas voltar atrás.
Reinierpost
@reinierpost É verdade, mas acho que o retorno é o mais importante do ponto de vista das línguas formais. As regexes Perl têm recursos como a execução de código Perl arbitrário, mas acho que as regexes devem ser interpretadas livremente como abrangendo PCREs. Os PCREs contêm esquisitices como padrões recursivos, mas essas são artes das trevas, levando você muito além do domínio das linguagens comuns. Eu poderia atualizar minha resposta para cobrir isso, no entanto.
Charles Stewart
18

Essas expressões foram examinadas por Aho (Manual de Ciência da Computação Teórica, Vol. A, Cap. 5) e Campeanu, Salomaa, Yu ("Um estudo formal de expressões regulares práticas", International Journal of Foundations of Computer Science, 14: 1007 –1018, 2003), bem como alguns documentos de acompanhamento.

Aho chama as expressões mais poderosas de "rewbr" (expressão regular com referências anteriores), Campeanu et al. use "expressão regular estendida" e "expressão regular prática". Como parece, "expressão regular estendida" é o termo mais comumente usado na literatura recente.

Com base no termo "expressão racional" da escola francesa, e considerando o fato de que essas expressões são usadas no mundo real, eu próprio gosto de "expressão real".

Adendo: Um capítulo da minha tese de doutorado lida com essa classe de linguagens formais (o trabalho correspondente deve aparecer no STACS 2011). Enquanto escrevia esse capítulo e o artigo, experimentei vários termos. Finalmente, decidi usar expressões regulares estendidas para o modelo com referências anteriores e expressões regulares apropriadas para as expressões regulares agradáveis ​​e normais. Como é bastante irritante mudar a terminologia em um artigo que já está completamente (ou quase todo) escrito, acho que alguns podem estar interessados ​​nas experiências que levaram à minha escolha:

Primeiro, regex e rewbr realmente não rolam a língua, e usá-los repetidamente no decorrer de um artigo inteiro ficou realmente cansativo de escrever e ler, principalmente quando se usa qualquer uma das formas plurais possíveis. Expressões regulares semelhantes a PERL também eram bastante difíceis de manejar. Claro, eu não sou falante nativo, então YMMV.

Segundo, assim que alguém quiser falar sobre os dois modelos, é conveniente usar termos que são uma variação da expressão regular , pois isso permite enfatizar semelhanças ou diferenças conforme necessário (por exemplo, "uma expressão regular, seja apropriada ou não"). estendido "). Além disso, isso permite enfatizar facilmente o caso especial de "expressões regulares estendidas sem referências anteriores", quando se fala de casos especiais em toda a classe, em vez de comparar modelos diferentes.

Terceiro, preferi usar um termo que já é usado na literatura em vez de um termo recém-cunhado, o que me deixou a escolha entre expressões regulares estendidas e expressões regulares práticas . A segunda opção implicava (pelo menos implicitamente) que expressões regulares apropriadas são de alguma forma impraticáveis, o que parecia bastante estranho (especialmente porque o RE2 do Google não usa refexs e parece ser bastante prático).

Obviamente, essa escolha é apenas o meu "máximo local pessoal" e, dependendo das necessidades, outras opções podem ser mais apropriadas.

Dominik D. Freydenberger
fonte
7
Infelizmente, o termo expressão regular estendida já é adotado pelo POSIX, que distingue entre expressão regular básica (BRE) e expressão regular estendida (ERE) , ambas expressões regulares estendidas de acordo com sua definição.
Jörg W Mittag
@ Jörg: Na verdade, de acordo com isso, nem as expressões regulares POSIX estendidas nem básicas são mais poderosas que as expressões regulares regulares. E o BRE puro (não GNU) parece realmente menos poderoso do que as expressões regulares (sem um operador de alternância).
Sepp2k em 07/10
Veja "Em expressões regulares estendidas" de Carle e Narendran (2009) para obter resultados mais recentes sobre esse "rewbr": portal.acm.org/citation.cfm?id=1533235
Jakob
Resultados mais recentes sobre essa classe de idiomas: "Na interseção de idiomas regex com idiomas regulares", de Campeanu e Santean (TCS 410, 2009) "Um teste de correspondência de tempo polinomial para grandes classes de expressões regulares estendidas" de Reidenbach e Schmid (CIAA 2010 ) e "Expressões regulares estendidas: sucintibilidade e decidibilidade" (por mim, que devem aparecer no STACS 2011).
Dominik D. Freydenberger
6

Sabe-se que o chamado regexp do perl é poderoso o suficiente para ser Turing completo; existe até um compilador do programa usual para o perl regexp.

Por isso, duvido que faça sentido procurar um nome para esse tipo de "regexps".

Veja, por exemplo, http://search.cpan.org/~asavige/Acme-EyeDrops-1.62/lib/Acme/EyeDrops.pm

Arthur MILCHIOR
fonte
Você tem algumas dicas?
András Salamon
5
@ András: Eu acho que Arthur está falando sobre a ?{CODE}diretiva de Perl , que permite que expressões padrão intercalem o código do programa em expressões regulares. Entendo que os PCREs são usualmente definidos como sendo a parte "declarativa" da linguagem, sendo a linguagem inteira chamada de linguagem padrão. De acordo com WP, Aho, 1990, "Algoritmos para encontrar padrões em strings" mostra que o problema de associação para idiomas regulares com backtracking é NP completo. Não há outros recursos para PCREs declarativos.
Charles Stewart
Eu adicionei o link; Eu não olhei para o código-fonte, então realmente não sei como ele funciona e se há alguma prova de que a compilação esteja realmente correta.
Arthur MILCHIOR
11
Desculpe, mas de acordo com seu argumento, como o cálculo lambda é Turing completo, não fazia sentido procurar um nome para ele. O mesmo para todos os outros formalismos e linguagens de computação completos de Turing. Mais precisamente, a integralidade de Turing não descreve o quão expressiva é uma linguagem, portanto, não faz sentido identificá-las apenas porque são completas em Turing. Meu exemplo sobre o cálculo lambda foi extremo, é claro.
Blaisorblade 10/09/10
2

Penso que o melhor termo para "expressão regular no contexto de autômatos" é "expressão racional", como é usado, por exemplo, na Teoria dos Elementos de Automação de Sakarovitch, ou no Manual de Autômatos Ponderados.

Michaël Cadilhac
fonte
11
Não é muito comumente usado, IMHO.
Blaisorblade 10/09/10
Ele é amplamente utilizado na teoria dos autômatos ponderados, consulte en.wikipedia.org/wiki/Rational_language . Eu já vi isso muitas vezes no campo das línguas em relação aos grupos também.
Michaël Cadilhac
1

Dadas as outras respostas, eu sugeriria que "linguagens regulares" são seguras e, depois de observar brevemente a diferença, falar sobre "expressões regulares práticas" para regexs (com retorno).

Observe também que o mesmo regexp, como expressões regulares e práticas, pode ter semântica diferente, porque neste último caso a semântica é definida em termos de retrocesso, com resultados diferentes. Os detalhes estariam fora do tópico, mas responderei se você fizer outra pergunta sobre isso (talvez no SO, e não aqui, não sei) e me notificará através de um comentário.

Blaisorblade
fonte
0

Poderíamos chamá-los de expressões padrão . Isso pode introduzir confusões com linguagens de padrões, mas pelo menos essas são menos comuns.

Rafael
fonte
2
Em princípio, eu concordo com o seu raciocínio, mas Campeanu, Santean e Yu já usaram o termo expressões padrão para denotar uma classe similar de linguagens com uma definição "mais limpa" (consulte "Expressões padrão e autômatos padrão", IPL 92 (2004). )
Dominik D. Freydenberger,