¿Cuál es la definición de una expresión regular?

10

Recientemente tuve una discusión amistosa con Ghoti sobre lo que constituye una expresión regular en los comentarios a mi respuesta a esta pregunta. Afirmé que lo siguiente es una expresión regular:

`[Rr]eading[Tt]est[Dd]ata`

Ghoti no estuvo de acuerdo, alegando que es un problema de archivo. La página global en wikipedia afirma que (el énfasis es mío):

Los globos no incluyen sintaxis para la estrella de Kleene que permite múltiples repeticiones de la parte anterior de la expresión; por lo tanto, no se consideran expresiones regulares, que pueden describir un conjunto más grande de idiomas regulares sobre cualquier alfabeto finito dado.

Sin embargo, no hay citas para esta afirmación, lo que indica que es solo la opinión de un editor de wikipedia en particular.

La especificación The Single UNIX ®, versión 2 , establece que una expresión regular básica (BRE) puede ser incluso un solo carácter:

Un carácter ordinario es un BRE que coincide: cualquier carácter del conjunto de caracteres admitido, excepto los caracteres especiales BRE enumerados en los caracteres especiales BRE.

Entonces, ¿cuál es la definición de una expresión regular en el mundo * nix, y esa definición excluye los globos de archivos?

terdon
fuente
66
En CS teórica, una expresión regular es una descripción de un lenguaje regular, que puede ser reconocido por un autómata finito. En el mundo de Unix, es mucho más complicado y no existe una definición única. Hay 2 dialectos de expresiones regulares en la especificación POSIX: extensión y básicos, que son utilizados por las herramientas como grep, sed, y awk. Vim usa su propia variedad, al igual que Perl.
jw013
Entonces, según esa definición, un archivo glob es un BRE ¿verdad?
terdon
2
No, un archivo glob NO es un BRE, ¿qué te hace pensar que es? Si lee la descripción POSIX de BRE y la descripción POSIX de globbing, notará que no son lo mismo. Por ejemplo, *tiene dos significados diferentes en BRE y globs. Nota: No creo que el término glob se use en ninguna parte de la especificación POSIX; en su lugar, se llama Pattern Matching y se describe en el capítulo del lenguaje de shell.
jw013
Consulte también ¿Por qué mi expresión regular funciona en X pero no en Y?
Gilles 'SO- deja de ser malvado'

Respuestas:

10

Como dijo lk-, la -nameopción de findtratará el argumento como un globo, no como una expresión regular.

El hecho de que una cadena se interprete como glob o regex o simplemente como una cadena simple depende de lo que se utilice para interpretar. Es una cuestión de contexto. La cadena en su ejemplo, [Rr]eading[Tt]est[Dd]atase puede evaluar en un número de maneras diferentes, pero lo que es depende de cómo se está utilizando. Úselo como un globo, es un globo. Úselo como una expresión regular, es una expresión regular. En el caso de la pregunta de dónde se originó esto , el OP describió la cadena como una expresión regular. Por lo tanto, podemos suponer que planeaba interpretarlo como una expresión regular.

Un solo personaje también puede ser una expresión regular, absolutamente. También puede ser una cadena, y también puede ser un globo. Podría ser interpretado como un byte o un tinyint, si lo desea. Todo depende del contexto.

Hay una serie de especificaciones para expresiones regulares en varias formas. BRE y ERE están bien documentados. PCRE agrega montones de funcionalidades. Muchos intérpretes de expresiones regulares implementarán, por ejemplo, "todo ERE y algunos de PCRE". O harán ERE menos alguna característica. Si sigue las especificaciones formales, muchas herramientas reclaman soporte de expresiones regulares que resulta ser incorrecto o incompleto. Conocer los detalles le permite adaptar sus soluciones a la colección de funcionalidades disponibles dentro de cualquier herramienta que esté evaluando su expresión regular.

Entonces ... si está buscando definiciones que "excluyan" los globos, lo está viendo desde una perspectiva incorrecta. Lo que se determina depende de cómo lo use .

ghoti
fuente
7

[Rr]eading[Tt]est[Dd]ataparece ser válido tanto como una expresión global y regular, y creo que tiene el mismo "significado" en ambas interpretaciones. Sin embargo, la -nameopción de findtratará el argumento como un globo, no como una expresión regular.

Esta distinción será importante si proporciona un argumento como foo*, que es a la vez un glob válido y una expresión regular válida, pero tiene un significado diferente según la interpretación:

Si se interpreta como un patrón global, esto va a coincidir foo, foobar, foo123, etc.

Si se interpreta como una expresión regular, esto va a coincidir fo, foo, foooooo, etc.

lk-
fuente
Gracias, veo la diferencia entre un patrón glob y una expresión regular. Sin embargo, ¿cuál es la definición formal de una expresión regular?
terdon
1
No sé si hay una definición única para "expresiones regulares", ya que el término se usa comúnmente. Existen diferentes especificaciones de sintaxis, como las expresiones regulares POSIX o las expresiones regulares de Perl, que incluyen otras "características" como referencias o lookaheads. Es posible que ya no se trate de expresiones regulares en el sentido más estricto (en el contexto de los lenguajes formales regulares), pero todavía se las conoce como tales.
lk-