Expresividad de lenguaje formal de patrones Perl

Question

Las expresiones regulares clásicas son equivalentes a autómatas finitos. La mayoría de las implementaciones actuales de "expresiones regulares" no son estrictamente expresiones regulares, pero son más poderosas. Algunas personas han comenzado a usar el término "patrón" en lugar de "expresión regular" para ser más precisos.

¿Cuál es la clasificación de lenguaje formal de lo que se puede describir con una "expresión regular" moderna como los patrones admitidos en Perl 5?

Actualización: Por "Perl 5" me refiero a la funcionalidad de coincidencia de patrones implementada en Perl 5 y adoptada por muchos otros lenguajes (C#, JavaScript, etc.) y no nada específico de Perl. No quiero considerar, por ejemplo, los trucos para incrustar el código Perl en un patrón.

Answer 1

Hubo un debate reciente sobre este tema una Perlmonks: Turing completeness and regular expressions

Answer 2

Siempre he escuchado la implementación de expresiones regulares de perl descrita como NFA con retroceso. Wikipedia parece tener una pequeña sección sobre esto:

Ésta es posiblemente un poco demasiado difusa pero es no informativa menos:

From Wikipedia:

Hay por lo menos tres diferentes algoritmos que deciden si y cómo una expresión regular dada coincide con una cadena .

El más antiguo y más rápido de dos confían en consecuencia en la teoría del lenguaje formal que permite cada máquina de estado finito no determinista (NFA) para transformarse en una máquina de estados finitos determinista (DFA). El DFA puede ser construido explícitamente y luego ejecutar en la cadena de entrada resultante un símbolo a la vez. La construcción de DFA para una expresión regular de tamaño m tiene costo de tiempo y memoria de O (2m), pero se puede ejecutar en una cadena de tamaño n en tiempo O (n). Un enfoque alternativo es para simular directamente el NFA, construyendo esencialmente cada estado DFA en la demanda y luego descartándolo en el siguiente paso de , posiblemente con almacenamiento en caché. Este mantiene implícito el DFA y evita el costo de construcción exponencial de , pero el costo de funcionamiento de aumenta a O (nm). El enfoque explícito se denomina algoritmo DFA y el enfoque implícito es el algoritmo NFA. Como ambos se pueden ver como formas diferentes de ejecutar el mismo DFA , también se les suele llamar el algoritmo DFA sin hacer una distinción . Estos algoritmos son rápidos, pero usarlos para recordar las subexpresiones agrupadas , la cuantificación diferida de y las características similares es complicado. [12] [13]

El tercer algoritmo es hacer coincidir el patrón con la cadena de entrada por retrocediendo. Este algoritmo es comúnmente llamado NFA, pero esta terminología puede ser confusa.Su tiempo de ejecución puede ser exponencial, que implementaciones sencillas exhibición cuando juego contra las expresiones como (a | aa) * b que contiene tanto la alternancia y cuantificación sin límites y la fuerza el algoritmo para considerar un exponencialmente creciente número de sub -casos. Las implementaciones más complejas de a menudo identifican y aceleran o abortan casos comunes donde de lo contrario funcionarían lentamente.

Aunque las implementaciones de rastreo hasta la sólo dan una garantía exponencial de el peor de los casos, proporcionan mucha mayor flexibilidad y expresivo poder. Por ejemplo, cualquier implementación que permita el uso de las referencias , o implemente las diversas extensiones introducidas por Perl, , debe usar una implementación de retroceso de .

Algunas implementaciones intentan proporcionar lo mejor de ambos algoritmos por primera funcionamiento de un partido de DFA rápida para ver si la cadena coincide con la expresión regular en absoluto, y sólo en ese caso realizan potencialmente más lento retroceso partido .

Answer 3

Perl regexps, como los de cualquier lenguaje de patrones, donde se permiten "referencias", no son realmente "regulares".

Backreferences es el mecanismo de que coincide con la misma cadena que coincidía con un subpatrón anterior al. Por ejemplo, /^(a*)\1$/ solo coincide con cadenas con número par de a s, porque después de algunos a s debe seguir el mismo número de ellos.

Es fácil probar que, por ejemplo, el patrón /^((a|b)*)\1$/ coincide con las palabras de un idioma no habitual (*), por lo que es más expresivo que el autómata finito hormiga. Las expresiones regulares no pueden "recordar" una cadena de longitud arbitraria y luego volver a unirla (la longitud puede ser muy larga, mientras que la máquina de estado finito solo puede simular la cantidad finita de "memoria").

Una prueba formal usaría el pumping lemma. (Por cierto, este lenguaje tampoco puede describirse mediante la gramática libre de contexto.)

Ni hablar del tricks that allow to use perl code in perl regexps (lenguaje no regular de paréntesis equilibrados).

---

(*) Los "idiomas regulares" son conjuntos de palabras que combinan con autómatas finitos. Ya escribí an answer sobre eso.