Que tipo de linguagens formais os motores de regex modernos podem analisar?

Aqui no SO as pessoas às vezes dizem algo como “você não pode analisar o X com expressões regulares, porque o X não é uma linguagem regular”. Pelo que entendi, os mecanismos modernos de expressões regulares podem combinar mais do que apenas linguagens regulares no sentido de Chomsky . Minhas perguntas:

dado um mecanismo de expressão regular que suporta

  • backreferences
  • asserções lookaround de largura ilimitada
  • recursion, como (?R)

que tipo de linguas pode analisar? Pode analisar qualquer linguagem livre de contexto e, se não, qual seria o contraexemplo?

(Para ser preciso, por “parse” quero dizer “construir uma única expressão regular que aceitaria todas as strings geradas pela gramática X e rejeitar todas as outras strings”).

Adicionar: Estou particularmente interessado em ver um exemplo de uma linguagem livre de contexto que os mecanismos de regex modernos (Perl, Net, módulo regex python) não seriam capazes de analisar.

Recentemente, escrevi um longo artigo sobre esse tópico: O verdadeiro poder das expressões regulares .

Para resumir:

  • Expressões regulares com suporte para referências de subpadrão recursivas podem corresponder a todas as linguagens livres de contexto (por exemplo, a^nb^n ).
  • Expressões regulares com asserções de lookaround e referências de subpadrão podem corresponder a pelo menos algumas linguagens sensíveis ao contexto (por exemplo, ww e a^nb^nc^n ).
  • Se as asserções tiverem largura ilimitada (como você diz), todas as gramáticas sensíveis ao contexto poderão ser correspondidas. Eu não conheço nenhum sabor de regex que não tenha restrições de largura fixa em lookbehind (e ao mesmo tempo suporta referências de subpadrão).
  • Expressões regulares com backreferences são NP-completas, então qualquer outro problema NP pode ser resolvido usando expressões regulares (depois de aplicar uma transformação em tempo polinomial).

Alguns exemplos:

  • Correspondendo à linguagem livre de contexto {a^nb^n, n>0} :

     /^(a(?1)?b)$/ # or /^ (?: a (?= a* (\1?+ b) ) )+ \1 $/x 
  • Correspondendo a linguagem contextual {a^nb^nc^n, n>0} :

     /^ (?=(a(?-1)?b)c) a+(b(?-1)?c) $/x # or /^ (?: a (?= a* (\1?+ b) b* (\2?+ c) ) )+ \1 \2 $/x 

Os modernos mecanismos de regex podem certamente analisar um conjunto maior de idiomas do que os idiomas comuns. Assim, nenhum dos quatro conjuntos clássicos de Chomsky é exatamente reconhecido pelos regexes. Todos os idiomas regulares são claramente reconhecidos por expressões regulares. Existem algumas linguagens clássicas livres de contexto que não podem ser reconhecidas por expressões regulares, como a linguagem parêntese balanceada, a menos que haja backreferences com contagem disponíveis. No entanto, um regex pode analisar o idioma ww que é sensível ao contexto.

Na verdade, as expressões regulares na teoria formal da linguagem são apenas levemente relacionadas a regexes. Regexes correspondentes com backreference ilimitado são NP-Complete no caso mais geral, portanto, todos os algoritmos de correspondência de padrões para expressões regulares poderosas são exponenciais, pelo menos no caso geral. No entanto, na maioria das vezes, a maioria das inputs é bastante rápida. Sabe-se que a correspondência de linguagens livres de contexto é no máximo algo mais rápido que n^3 , então existem algumas linguagens em regexes que não são livres de contexto (como ww ) mas nem todas as linguagens livres de contexto podem ser interpretadas por expressões regulares. Os idiomas do tipo 0 não são decidíveis em geral, os regexes do filho não chegam lá.

Então, como uma conclusão não muito conclusiva, os regexes podem analisar um amplo conjunto de linguagens que incluem todas as linguagens regulares, e algumas sem contexto e sensíveis ao contexto, mas não exatamente iguais a qualquer um desses conjuntos. Existem outras categorias de idiomas e outras taxonomias, onde você pode encontrar uma resposta mais precisa, mas nenhuma taxonomia que inclua linguagens livres de contexto como um subconjunto apropriado em uma hierarquia de idiomas pode fornecer uma única linguagem reconhecida por regexes, porque regexes somente se cruzam em alguma parte com linguagens livres de contexto, e nenhum é um subconjunto apropriado do outro.

Você pode ler sobre regexes em Introdução à Linguagem e Linguística por Ralph W. Fasold, Jeff Connor-Linton

Hierarquia de Chomsky :

Type0> = Type1> = Type2> = Type3

A Linguística Computacional apresenta principalmente Gramáticas Tipo 2 e 3

gramáticas de tipo 3 :

–Inclui expressões regulares e autômatos de estados finitos (também conhecidos como máquinas de estados finitos)

–O ponto focal do resto desta palestra

Gramáticas do tipo 2 :

– Comumente usado para analisadores de linguagem natural

–Usado para modelar a estrutura sintática em muitas teorias lingüísticas (freqüentemente complementadas por outros mecanismos)

–Nós vamos jogar um papel chave na próxima palestra sobre análise.


A maioria dos XMLs, como o Microsoft DGML (Directed Graph Markup Language), que possui links inter-relacionais, são exemplos de que o Regex é inútil.


e estas três respostas podem ser úteis:

1 – lookaround-affect-which-languages-pode-ser-correspondido-por-expressões-regulares

2 – expressões regulares – arent

3 – onde-mais-regex-implementações-queda-na-complexidade-escala