Es & # 8220; regex & # 8221; en los lenguajes de programación modernos realmente & # 8220; gramática sensible al contexto & # 8221 ;?

Question

A lo largo de los años, " regex " la coincidencia de patrones se ha ido haciendo cada vez más poderosa hasta el punto en que me pregunto: ¿es realmente solo una comparación de gramática sensible al contexto? ¿Es una variación / extensión de la coincidencia de la gramática libre de contexto? ¿Dónde está ahora y por qué no lo llamamos así en lugar de la expresión regular y antigua " expresión regular " ;?

Answer 1

En particular, las referencias inversas a la captura de paréntesis hacen que las expresiones regulares sean más complejas que las gramáticas regulares, libres de contexto o sensibles al contexto. El nombre simplemente ha crecido históricamente (como muchas palabras). Consulte también esta sección en Wikipedia y este explicación con un ejemplo de Perl.

Answer 2

La forma en que lo veo:

• idiomas regulares:
  • emparejado por máquinas de estado. Solo se puede usar una variable para representar la corriente " ubicación " en la gramática que debe coincidir: no se puede implementar la recursión
• Idiomas sin contexto:
  • Emparejado por una máquina de pila. La ubicación " actual " " En la gramática se representa una pila en una u otra forma. No se puede " recordar " cualquier cosa que haya ocurrido antes
• Lenguajes sensibles al contexto:
  • La mayoría de los lenguajes de programación
  • Todos La mayoría de los idiomas humanos

Sé de analizadores de expresiones regulares que te permiten relacionarte con algo que el analizador ya ha encontrado, logrando algo así como una gramática sensible al contexto.

Aún así, los analizadores de expresiones regulares, por muy sofisticados que sean, no permiten la aplicación recursiva de reglas, lo que es un requisito definitivo para las gramáticas libres de contexto.

El término regex , en mi opinión, se refiere principalmente a la sintaxis utilizada para expresar esas gramáticas regulares (las estrellas y los signos de interrogación).

Answer 3

Hay implementaciones modernas de expresiones regulares que rompen las reglas de expresión regular clásica definición .

Por ejemplo, Microsoft & # 8217; s .NET Balancing Group < código> (? < name1 - name2 > & # 8230;) :

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

Este hace coincide con el idioma L & # 8320; & # 8321; = { & # 949; , 01, 0011, 000111, & # 8230; }. Pero este lenguaje no es regular según el Lema de bombeo .