¿Se puede definir el formato csv mediante una expresión regular?

19

Un colega y yo hemos discutido recientemente si una expresión regular pura es capaz de encapsular completamente el formato csv, de modo que sea capaz de analizar todos los archivos con cualquier carácter de escape, carácter de comillas y carácter de separador.

La expresión regular no necesita ser capaz de cambiar estos caracteres después de la creación, pero no debe fallar en ningún otro caso de borde.

He argumentado que esto es imposible solo para un tokenizador. La única expresión regular que podría hacer esto es un estilo PCRE muy complejo que va más allá de la tokenización.

Estoy buscando algo en la línea de:

... el formato csv es una gramática libre de contexto y, como tal, es imposible analizar solo con expresiones regulares ...

¿O estoy equivocado? ¿Es posible analizar csv con solo una expresión regular POSIX?

Por ejemplo, si tanto el carácter de escape como el carácter de cotización son ", entonces estas dos líneas son válidas csv:

"""this is a test.""",""
"and he said,""What will be, will be."", to which I replied, ""Surely not!""","moving on to the next field here..."
Spencer Rathbun
fuente
que no es un CSV ya que no hay ninguna parte de anidación (IIRC)
trinquete monstruo
1
¿Pero cuáles son los casos límite? tal vez hay más en CSV, de lo que alguna vez pensé?
c69
1
@ c69 ¿Qué tal escapar y citar char son ambos "? Entonces lo siguiente es válido:"""this is a test.""",""
Spencer Rathbun
¿Intentaste regexp desde aquí ?
dasblinkenlight
1
Es necesario tener cuidado con los casos límite, pero una expresión regular debería ser capaz de tokenizar csv como lo ha descrito. La expresión regular no necesita contar un número arbitrario de comillas, solo necesita contar hasta 3, lo que pueden hacer las expresiones regulares. Como otros han mencionado, usted debe tratar de anotar una representación bien definida de lo que se espera un csv contadores a ser ...
comingstorm

Respuestas:

20

Agradable en teoría, terrible en la práctica.

Por CSV voy a asumir que te refieres a la convención como se describe en RFC 4180 .

Si bien la coincidencia de datos CSV básicos es trivial:

"data", "more data"

Nota: Por cierto, es mucho más eficiente usar una función .split ('/ n'). Split ('"') para datos muy simples y bien estructurados como este. Las expresiones regulares funcionan como un NDFSM (finito no determinista) State Machine) que pierde mucho tiempo retrocediendo una vez que comienza a agregar casos extremos como caracteres de escape.

Por ejemplo, aquí está la cadena de coincidencia de expresiones regulares más completa que he encontrado:

re_valid = r"""
# Validate a CSV string having single, double or un-quoted values.
^                                   # Anchor to start of string.
\s*                                 # Allow whitespace before value.
(?:                                 # Group for value alternatives.
  '[^'\\]*(?:\\[\S\s][^'\\]*)*'     # Either Single quoted string,
| "[^"\\]*(?:\\[\S\s][^"\\]*)*"     # or Double quoted string,
| [^,'"\s\\]*(?:\s+[^,'"\s\\]+)*    # or Non-comma, non-quote stuff.
)                                   # End group of value alternatives.
\s*                                 # Allow whitespace after value.
(?:                                 # Zero or more additional values
  ,                                 # Values separated by a comma.
  \s*                               # Allow whitespace before value.
  (?:                               # Group for value alternatives.
    '[^'\\]*(?:\\[\S\s][^'\\]*)*'   # Either Single quoted string,
  | "[^"\\]*(?:\\[\S\s][^"\\]*)*"   # or Double quoted string,
  | [^,'"\s\\]*(?:\s+[^,'"\s\\]+)*  # or Non-comma, non-quote stuff.
  )                                 # End group of value alternatives.
  \s*                               # Allow whitespace after value.
)*                                  # Zero or more additional values
$                                   # Anchor to end of string.
"""

Maneja razonablemente valores de comillas simples y dobles, pero no líneas nuevas en valores, comillas escapadas, etc.

Fuente: Desbordamiento de pila: ¿cómo puedo analizar una cadena con JavaScript?

Se convierte en una pesadilla una vez que se introducen los casos límite comunes como ...

"such as ""escaped""","data"
"values that contain /n newline chars",""
"escaped, commas, like",",these"
"un-delimited data like", this
"","empty values"
"empty trailing values",        // <- this is completely valid
                                // <- trailing newline, may or may not be included

El caso de borde de nueva línea como valor solo es suficiente para romper el 99.9999% de los analizadores basados ​​en RegEx encontrados en la naturaleza. La única alternativa "razonable" es utilizar la coincidencia RegEx para la tokenización básica de caracteres de control / sin control (es decir, terminal versus no terminal) combinada con una máquina de estado utilizada para análisis de nivel superior.

Fuente: Experiencia conocida también como dolor y sufrimiento extensos.

Soy el autor de jquery-CSV , el único analizador CSV basado en javascript, totalmente compatible con RFC en el mundo. He pasado meses abordando este problema, hablando con muchas personas inteligentes y probando un montón si diferentes implementaciones incluyen 3 reescrituras completas del motor del analizador principal.

tl; dr - Moraleja de la historia, PCRE solo apesta para analizar cualquier cosa menos las gramáticas regulares más simples y estrictas (es decir, Tipo III). Aunque, es útil para tokenizar cadenas terminales y no terminales.

Evan Plaice
fuente
1
Sí, esa ha sido mi experiencia también. Cualquier intento de encapsular completamente más que un patrón CSV muy simple se topa con estas cosas, y luego se enfrenta tanto a los problemas de eficiencia como a los problemas de complejidad de una expresión regular masiva. ¿Has mirado en la biblioteca node-csv ? Parece validar esta teoría también. Toda implementación no trivial utiliza un analizador interno.
Spencer Rathbun
@SpencerRathbun Sí. Estoy seguro de que he echado un vistazo a la fuente node-csv antes. Parece utilizar una máquina de estado de tokenización de caracteres típica para el procesamiento. El analizador jquery-csv funciona en el mismo concepto fundamental, excepto que uso regex para la tokenización terminal / no terminal. En lugar de evaluar y concatenar char-by-char, regex puede hacer coincidir varios caracteres no terminales a la vez y devolverlos como un grupo (es decir, una cadena). Esto minimiza la concatenación innecesaria y 'debería' aumentar la eficiencia.
Evan Plaice
20

Regex puede analizar cualquier lenguaje regular y no puede analizar cosas elegantes como las gramáticas recursivas. Pero CSV parece ser bastante regular, tan analizable con una expresión regular.

Trabajemos desde la definición : se permiten secuencias, alternativas de forma de elección ( |) y repetición (estrella de Kleene, la *).

  • Un valor sin comillas es regular: [^,]*# cualquier carácter menos coma
  • Un valor entre comillas es regular: "([^\"]|\\\\|\\")*"# secuencia de cualquier cosa menos comillas "o comillas \"escapadas o escapadas escapadas\\
    • Algunas formas pueden incluir comillas de escape con comillas, lo que agrega una variante ("")*"a la expresión anterior.
  • Un valor permitido es regular: <unquoted-value> |<quoted-value>
  • Una sola línea CSV es regular: <valor> (,<valor>)*
  • Una secuencia de líneas separadas por \ntambién es obviamente regular.

No probé meticulosamente cada una de estas expresiones, y nunca definí grupos de captura. También he pasado por alto algunos detalles técnicos, como las variantes de caracteres que se pueden utilizar en lugar de ,, "o la línea de separadores: éstas no se rompen la regularidad, que acaba de obtener varios idiomas ligeramente diferentes.

Si puede detectar un problema en esta prueba, ¡por favor comente! :)

Pero a pesar de esto, el análisis práctico de archivos CSV mediante expresiones regulares puras puede ser problemático. Debe saber cuál de las variantes se está enviando al analizador, y no hay un estándar para ello. Puede probar varios analizadores en cada línea hasta que uno tenga éxito, o de alguna manera dividir el formato de los comentarios. Pero esto puede requerir medios distintos de las expresiones regulares para hacerlo de manera eficiente, o en absoluto.

9000
fuente
44
Absolutamente un +1 para el punto práctico. Hay algo de lo que estoy seguro, en algún lugar profundo es un ejemplo de un valor (artificial) que rompería la versión del valor citado. Simplemente no sé qué es. La 'diversión' con múltiples analizadores sería "estos dos funcionan, pero dan respuestas diferentes"
1
Obviamente, necesitará diferentes expresiones regulares para las comillas invertidas con comillas invertidas y comillas dobles. Una expresión regular para el primer tipo de campo csv debería ser algo así [^,"]*|"(\\(\\|")|[^\\"])*", y el último debería ser algo así [^,"]*|"(""|[^"])*". (¡Cuidado, ya que no he probado ninguno de estos!)
tormenta que viene el
Al buscar algo que podría ser un estándar, hay un caso que se pierde: un valor con un delimitador de registro incluido. Esto también hace que el análisis práctico sea aún más divertido cuando hay varias formas diferentes de manejarlo
Buena respuesta, pero si ejecuto perl -pi -e 's/"([^\"]|\\\\|\\")*"/yay/'y canalizo "I have here an item,\" that is a test\"", el resultado es 'yay eso es una prueba \ "". Creo que tu expresión regular es defectuosa.
Spencer Rathbun
@SpencerRathbun: cuando tenga más tiempo, probaré las expresiones regulares y probablemente incluso pegue un código de prueba de concepto que pase las pruebas. Lo siento, el día de trabajo continúa.
9000
5

Respuesta simple, probablemente no.

El primer problema es la falta de un estándar. Si bien se puede describir su csv de una manera estrictamente definida, no se puede esperar obtener archivos csv estrictamente definidos. "Sé conservador en lo que haces, sé liberal en lo que aceptas de los demás" -Jon Postal

Asumiendo que uno tiene un estándar estándar aceptable, está la cuestión de los caracteres de escape y si es necesario equilibrarlos.

Una cadena en muchos formatos csv se define como string value 1,string value 2. Sin embargo, si esa cadena contiene una coma, es ahora "string, value 1",string value 2. Si contiene una cita se convierte en "string, ""value 1""",string value 2.

En este punto, creo que es imposible. El problema es que necesita determinar cuántas comillas ha leído y si una coma está dentro o fuera del modo de doble comilla del valor. El equilibrio entre paréntesis es un problema imposible de expresiones regulares. Algunos motores de expresiones regulares extendidas (PCRE) pueden manejarlo, pero entonces no es una expresión regular.

Puede encontrar /programming/8629763/csv-parsing-with-a-context-free-grammar útil.


Modificado:

He estado buscando formatos para caracteres de escape y no he encontrado ninguno que necesite un recuento arbitrario, por lo que probablemente ese no sea el problema.

Sin embargo, existen problemas sobre cuál es el carácter de escape y el delimitador de registro (para empezar). http://www.csvreader.com/csv_format.php es una buena lectura sobre los diferentes formatos en la naturaleza.

  • Las reglas para la cadena entre comillas (si es una cadena entre comillas simples o una cadena entre comillas dobles) difieren.
    • 'This, is a value' vs "This, is a value"
  • Las reglas para los personajes de escape
    • "This ""is a value""" vs "This \"is a value\""
  • El manejo del delimitador de registro incrustado ({rd})
    • (sin procesar embebido) "This {rd}is a value"vs (escapado) "This \{rd}is a value"vs (traducido)"This {0x1C}is a value"

La clave aquí es que es posible tener una cadena que siempre tendrá múltiples interpretaciones válidas.

La pregunta relacionada (para casos extremos) "¿es posible tener una cadena no válida que sea aceptada?"

Todavía dudo mucho que haya una expresión regular que pueda coincidir con cada CSV válido creado por alguna aplicación y rechazar cada csv que no se pueda analizar.

Comunidad
fuente
1
Las citas entre comillas no necesitan ser equilibradas. En su lugar, debe haber un número par de cotizaciones antes de un presupuesto integrado, lo que obviamente es normal: ("")*". Si las cotizaciones dentro del valor están fuera de balance, ya no es asunto nuestro.
9000
Esta es mi posición, habiéndome encontrado con estas horribles excusas para la "transferencia de datos" en el pasado. Lo único que los manejó adecuadamente fue un analizador sintáctico, la expresión regular pura se rompía cada pocas semanas.
Spencer Rathbun
2

Primero defina la gramática para su CSV (¿los delimitadores de campo se escapan o codifican de alguna manera si aparecen en el texto?) Y luego se puede determinar si es analizable con regex. Primero la gramática: segundo analizador: http://www.boyet.com/articles/csvparser.html Cabe señalar que este método usa un tokenizador, pero no puedo construir una expresión regular POSIX que coincida con todos los casos límite. Si su uso de formatos CSV no es regular y está libre de contexto ... entonces su respuesta está en su pregunta. Buena descripción general aquí: http://nikic.github.com/2012/06/15/The-true-power-of-regular-expressions.html

iivel
fuente
2

Esta expresión regular puede simular CSV normal, como se describe en el RFC:

/("(?:[^"]|"")*"|[^,"\n\r]*)(,|\r?\n|\r)/

Explicación:

  • ("(?:[^"]|"")*"|[^,"\n\r]*) - un campo CSV, citado o no
    • "(?:[^"]|"")*" - un campo citado;
      • [^"]|""- cada personaje no es ", o "escapó como""
    • [^,"\n\r]* - un campo sin comillas, que puede no contener , " \n \r
  • (,|\r?\n|\r)- el siguiente separador, ya sea ,o una nueva línea
    • \r?\n|\r - una nueva línea, una de \r\n \n \r

Se puede hacer coincidir y validar un archivo CSV completo mediante el uso repetido de esta expresión regular. Luego es necesario arreglar los campos entre comillas y dividirlos en filas según los separadores.

Aquí hay un código para un analizador CSV en Javascript, basado en la expresión regular:

var csv_tokens_rx = /("(?:[^"]|"")*"|[^,"\n\r]*)(,|\r?\n|\r)/y;
var csv_unescape_quote_rx = /""/g;
function csv_parse(s) {
    if (s && s.slice(-1) != '\n')
        s += '\n';
    var ok;
    var rows = [];
    var row = [];
    csv_tokens_rx.lastIndex = 0;
    while (true) {
        ok = csv_tokens_rx.lastIndex == s.length;
        var m = s.match(csv_tokens_rx);
        if (!m)
            break;
        var v = m[1], d = m[2];
        if (v[0] == '"') {
            v = v.slice(1, -1);
            v = v.replace(csv_unescape_quote_rx, '"');
        }
        if (d == ',' || v)
            row.push(v);
        if (d != ',') {
            rows.push(row)
            row = [];
        }
    }
    return ok ? rows : null;
}

Si esta respuesta ayuda a resolver su argumento es para que usted decida; Estoy feliz de tener un analizador CSV pequeño, simple y correcto.

En mi opinión, un lexprograma es más o menos una expresión regular grande, y esos pueden tokenizar formatos mucho más complejos, como el lenguaje de programación C.

Con referencia a las definiciones RFC 4180 :

  1. salto de línea (CRLF): la expresión regular es más flexible y permite CRLF, LF o CR.
  2. El último registro en el archivo puede tener o no un salto de línea final: la expresión regular tal como es requiere un salto de línea final, pero el analizador se ajusta a eso.
  3. Puede haber una línea de encabezado opcional: esto no afecta al analizador.
  4. Cada línea debe contener el mismo número de campos en todo el archivo: no se aplican Los
    espacios se consideran parte de un campo y no se deben ignorar: está bien
    El último campo del registro no debe ir seguido de una coma, no se aplica
  5. Cada campo puede estar o no encerrado entre comillas dobles ... - está bien
  6. Los campos que contienen saltos de línea (CRLF), comillas dobles y comas deben estar entre comillas dobles: está bien
  7. una comilla doble que aparece dentro de un campo debe escaparse precediéndola con otra comilla doble - está bien

La expresión regular en sí misma satisface la mayoría de los requisitos de RFC 4180. No estoy de acuerdo con los demás, pero es fácil ajustar el analizador para implementarlos.

Sam Watkins
fuente
1
esto se parece más a la autopromoción que a responder la pregunta que se hace, consulte Cómo responder
mosquito el
1
@gnat, edité mi respuesta para dar más explicaciones, verificar la expresión regular contra RFC 4180 y hacer que sea menos autopromocional. Creo que esta respuesta tiene valor, ya que contiene una expresión regular probada que puede simular la forma más común de CSV utilizada por Excel y otras hojas de cálculo. Creo que esto resuelve la pregunta. El pequeño analizador CSV demuestra que es fácil analizar CSV usando esta expresión regular.
Sam Watkins
Sin desear promocionarme en exceso, aquí están mis pequeñas bibliotecas completas de csv y tsv que estoy usando como parte de una pequeña aplicación de hoja de cálculo (las hojas de Google me parecen demasiado pesadas). Este es un código de código abierto / dominio público / CC0 como todas las cosas que publico. Espero que esto pueda ser útil para alguien más. sam.aiki.info/code/js
Sam Watkins