"Regex" é nas linguagens de programação modernas realmente "gramática sensível ao contexto"?

Question

Ao longo dos anos, a correspondência de padrões "Regex" está ficando cada vez mais poderosa a ponto de me perguntar: é realmente apenas uma correspondência de gramática sensível ao contexto? É uma variação/extensão da correspondência de gramática livre de contexto? Onde está agora e por que não chamamos de que, em vez da antiga e restritiva "expressão regular"?

Answer 1

Em referências específicas, para capturar parênteses tornam as expressões regulares mais complexas que as gramáticas regulares, livres de contexto ou sensíveis ao contexto. O nome é simplesmente cultivado historicamente (tantas palavras). Veja também esta seção na Wikipedia e este Explicação com um exemplo de Perl.

Answer 2

A maneira como eu vejo:

• Idiomas regulares:
  • Combinado por máquinas de estado. Apenas uma variável pode ser usada para representar o "local" atual na gramática a ser correspondente: a recursão não pode ser implementada
• Idiomas livres de contexto:
  • Combinado por uma máquina de pilha. O "local" atual na gramática é representado por uma pilha de uma ou outra forma. Não consigo "lembrar" nada que ocorreu antes
• Idiomas sensíveis ao contexto:
  • A maioria das linguagens de programação
  • Tudo A maioria das línguas humanas

Conheço os analisadores de expressão regular que permitem que você combine contra algo que o analisador já encontrou, alcançando algo como uma gramática sensível ao contexto.

Ainda assim, os analistas regulares de expressão, por mais sofisticados que sejam, não permitem a aplicação recursiva de regras, o que é um requisito definitivo para gramáticas sem contexto.

O termo regex, na minha opinião, refere -se principalmente ao sintaxe usado para expressar essas gramáticas regulares (as estrelas e pontos de interrogação).

Answer 3

Existem recursos nas implementações modernas de expressão regular que quebram as regras do Definição de expressão regular clássica.

Por exemplo Microsoft .NET Grupo de equilíbrio (?<name1-name2> … ):

^(?:0(?<L>)|1(?<-L>))*(?(L)(?!))$

este faz corresponder ao idioma eu₀₁ = {ε, 01, 0011, 000111,…}. Mas esse idioma não é regular de acordo com o Lema de bombeamento.