Quando um regexp não é uma expressão regular?

9

Como estou estudando para o meu curso formal de idiomas, me deparei com esses posts fascinantes ( Um Dois ) que descrevem como encontrar um número primo usando uma expressão regular . Como eu disse, um regexp , não uma expressão regular . Como uma expressão regular pode corresponder a seqüências de caracteres calculadas por um autômato de estado finito e a descoberta de um número primo não pode ser feita por uma FSA, a regexp mostrada na postagem do blog não é uma expressão inteiramente regular, pois faz o retrocesso para corresponder à sequência.

Desde que eu realmente nunca usei nenhuma expressão regular, agora, minha pergunta:

Como posso reconhecer imediatamente um regexp de uma expressão regular "verdadeira" apenas olhando para ele?

Definições: Por expressão regular, refiro-me à noção definida em linguagens formais. Por regexp, quero dizer a noção suportada pelas linguagens de programação modernas; a sintaxe regexp geralmente contém recursos adicionais, como referências posteriores. Os regexps, como vistos nas linguagens de programação, são estritamente mais poderosos do que as expressões regulares no estilo das linguagens formais.

peperunas
fonte
5
Regexp é apenas uma abreviação de expressão regular. O cálculo dos números primos é baseado em um hack Perl, não em expressões regulares.
11
É bem simples. Linguagens regulares empregam concatenação, repetição e alternância. Sempre que um mecanismo suporta algo que não seja equivalente a eles, isso não é regular.
Kilian Foth
11
Perguntas relacionadas: 1 , 2 , 3 .
Raphael
@ Yannis Se você pular a cerca para o CS, isso não é mais verdade. Os regexps, como vistos nas linguagens de programação, são estritamente mais poderosos que as expressões regulares (estilo de linguagens formais), e o formato abreviado "regexp" é por convenção (não sei o quão difundido é esse) usado para o primeiro, e não o último tipo.
Raphael
@KilianFoth Isso não é realmente uma descrição útil, no entanto. Por exemplo, você pode adicionar negação (ou, de fato, qualquer conjunto finito de conectivos booleanos) a expressões regulares sem aumentar seu poder.
precisa saber é o seguinte

Respostas:

13

tl; dr backrefs.

Assim que houver um \1(ou qualquer número que não seja usado para escapar do unicode) no regexp, não será uma expressão regular.

Backrefs permite combinar (a+)b\1quais correspondências n vezes aseguidas de b seguidas de n vezes apara qualquer n> 1. Este não é um idioma comum (é o filho de um idioma não comum).

É necessário e quase suficiente que o backref faça referência a um grupo que contenha uma regexp que corresponda a uma cadeia arbitrariamente longa ou que contenha um *ou +. A única exceção (que eu encontrei) de uma expressão regular da forma em (A)B\1que A é uma linguagem finita (pode ser substituída por uma enumeração de todas as palavras que as aceitam). Você pode convertê-lo paraword1+Bword1|word2+Bword2 etc. porque A é finito.

Grupos de pesquisa não removem a regularidade da regexp. A(?=B)Cé a seção transversal de expressões regulares AB.*e ACa seção transversal de 2 idiomas regulares é regular. A aparência negativa é semelhante, exceto usando o complemento de B.*(complementos de idiomas regulares sendo regulares). Lookbehind é exatamente o mesmo, assim como A(?<=B)Ca seção transversal de ACe .*BC.

catraca arrepiante
fonte
Isso é necessário e suficiente? Parece-me que (a)\1, ao usar um backref, é equivalente aae, portanto, trivialmente Regular. Também estou me perguntando se as asserções lookahead podem usar para reconhecer idiomas não regulares.
MSalters
11
@MSalters: Se você quer ser realmente técnico, (a)\1não é uma expressão regular, mas reconhece um idioma regular.
Jörg W Mittag