Est-ce que «regex» dans les langages de programmation modernes est vraiment une «grammaire sensible au contexte»?

Question

Au fil des ans, "regex". la correspondance des motifs est devenue de plus en plus puissante au point de me demander: s'agit-il vraiment d'une correspondance grammaticale contextuelle? Est-ce une variante / extension de la correspondance grammaire sans contexte? Où est-il en ce moment et pourquoi n'appelons-nous pas simplement cela à la place de l'ancienne "expression régulière" restrictive?

Answer 1

En particulier, les références arrière à la capture des parenthèses rendent les expressions rationnelles plus complexes que les grammaires régulières, sans contexte ou sensibles au contexte. Le nom est simplement historiquement développé (autant de mots). Voir aussi cette section sur Wikipedia et ceci explication avec un exemple de Perl.

Answer 2

La façon dont je vois les choses:

• Langues régulières:
  • Correspondant aux machines d'état. Une seule variable peut être utilisée pour représenter le courant " emplacement " dans la grammaire à apparier: la récursivité ne peut pas être implémentée
• Langues sans contexte:
  • Adapté par une machine à pile. Le " emplacement " actuel dans la grammaire est représenté par une pile sous une forme ou une autre. Je ne peux pas "me souvenir" tout ce qui s'est passé avant
• Langages contextuels:
  • La plupart des langages de programmation
  • Tous La plupart des langues humaines

Je connais des analyseurs syntaxiques d’expressions régulières qui vous permettent de faire une comparaison avec quelque chose que l’analyseur a déjà rencontré, en réalisant quelque chose comme une grammaire contextuelle.

Néanmoins, les analyseurs d’expressions régulières, aussi sophistiqués soient-ils, ne permettent pas l’application récursive de règles, ce qui est une exigence absolue pour les grammaires sans contexte.

À mon avis, le terme regex fait principalement référence à la syntaxe utilisée pour exprimer ces grammaires régulières (les étoiles et les points d'interrogation).

Answer 3

Les implémentations modernes d’expressions régulières comportent des fonctionnalités qui enfreignent les expressions régulières classiques. définition .

Par exemple, Microsoft .NET Groupe d'équilibrage (? < nom1 - nom2 >… ) :

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

Cette ne correspond pas à la langue L = { e , 01, 0011, 000111,…}. Mais cette langue n’est pas régulière selon la Lemma de pompage .