Il formato csv può essere definito da un'espressione regolare?

18

Recentemente un collega e io abbiamo discusso se una regex pura sia in grado di incapsulare completamente il formato csv, in modo tale che sia in grado di analizzare tutti i file con qualsiasi escape char, preventivo e char separatore.

L'espressione regolare non deve essere in grado di modificare questi caratteri dopo la creazione, ma non deve fallire in nessun altro caso limite.

Ho sostenuto che questo è impossibile solo per un tokenizer. L'unica regex che potrebbe essere in grado di farlo è uno stile PCRE molto complesso che va oltre la semplice tokenizzazione.

Sto cercando qualcosa sulla falsariga di:

... the csv format is a context free grammar and as such, it is impossible to parse with regex alone ...

O mi sbaglio? È possibile analizzare csv solo con un'espressione regolare POSIX?

Ad esempio, se sia il carattere di escape che il carattere di citazione sono " , allora queste due righe sono csv validi:

"""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..."
    
posta Spencer Rathbun 27.09.2012 - 18:37
fonte

5 risposte

18

Bello in teoria, terribile nella pratica

Per CSV assumerò che intendi la convenzione come descritto in RFC 4180 .

Mentre abbinare i dati CSV di base è banale:

"data", "more data"

Nota: BTW, è molto più efficiente usare una funzione .split ('/ n'). split ('"') per dati molto semplici e ben strutturati come questo. NDFSM (Macchina a stati finiti non deterministica) che spreca un sacco di tempo indietro nel backtracking una volta che inizi ad aggiungere casi limite come escape char.

Ad esempio, ecco la stringa di corrispondenza delle espressioni regolari più completa che ho trovato:

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.
"""

Gestisce ragionevolmente valori con quotazioni singole e doppie, ma non con ritorni a capo in valori, citazioni con escape, ecc.

Fonte: Overflow dello stack - Come posso analizzare una stringa con JavaScript

Diventa un incubo una volta che i casi limite comuni vengono introdotti come ...

"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

Il caso limite newline-as-value da solo è sufficiente a rompere il 99,9999% dei parser basati su RegEx trovati in natura. L'unica alternativa "ragionevole" consiste nell'utilizzare la corrispondenza di RegEx per la tokenizzazione di controllo di base / non di controllo (ad esempio terminale vs non terminale) associata a una macchina a stati utilizzata per l'analisi di livello superiore.

Fonte: esperienza altrimenti nota come intenso dolore e sofferenza.

Sono l'autore di jquery-CSV , l'unico basato su javascript, completamente RFC- parser compatibile con CSV nel mondo. Ho trascorso mesi ad affrontare questo problema, parlando con molte persone intelligenti e provando un sacco di diverse implementazioni, tra cui 3 riscritture complete del motore parser principale.

tl; dr - Morale della trama, PCRE da solo fa schifo per analizzare tutto tranne le grammatiche più semplici e rigide (Ie tipo III). Anche se, è utile per tokenizzare le stringhe terminale e non-terminale.

    
risposta data 22.10.2013 - 00:31
fonte
20

Regex può analizzare qualsiasi linguaggio normale e non può analizzare cose di fantasia come le grammatiche ricorsive. Ma CSV sembra essere abbastanza regolare, così parseable con un'espressione regolare.

Lavoriamo dalla definizione : consentiti sono la sequenza, le alternative del modulo di scelta ( | ) e la ripetizione ( Stella Kleene, * ).

  • Un valore non quotato è regolare: [^,]* # qualsiasi carattere ma virgola
  • Un valore quotato è regolare: "([^\"]|\\|\")*" # sequenza di tutto tranne citazione " o citazione di escape \" o escape escape \
    • Alcuni moduli possono includere citazioni di escape con virgolette, che aggiungono una variante ("")*" all'espressione sopra.
  • Un valore consentito è regolare: < valore non quotato > | < valore-quotato >
  • Una singola riga CSV è regolare: < value > (, < value > )*
  • Anche una sequenza di linee separate da \n è ovviamente regolare.

Non ho testato meticolosamente ciascuna di queste espressioni e non ho mai definito gruppi di cattura. Ho anche tralasciato alcuni aspetti tecnici, come le varianti di caratteri che possono essere utilizzati al posto di , , " o separatori di riga: questi non infrangono la regolarità, ma solo alcune lingue leggermente diverse.

Se riesci a individuare un problema in questa dimostrazione, ti preghiamo di commentare! :)

Ma nonostante ciò, l'analisi pratica dei file CSV mediante espressioni regolari pure può essere problematica. È necessario sapere quale delle varianti viene inviata al parser e non esiste uno standard per questo. Puoi provare diversi parser su ogni riga fino a quando uno riesce, o in qualche modo divinare i commenti del modulo di formato. Ma questo può richiedere mezzi diversi dalle espressioni regolari per fare in modo efficiente, o del tutto.

    
risposta data 27.09.2012 - 19:35
fonte
5

Risposta semplice - probabilmente no.

Il primo problema è la mancanza di uno standard. Mentre uno può descrivere il proprio csv in modo rigorosamente definito, non ci si può aspettare di ottenere file csv rigorosamente definiti. "Sii prudente in ciò che fai, sii liberale in ciò che accetti agli altri" -Jon Postal

Supponendo che uno abbia uno standard che è accettabile, c'è la questione dei caratteri di escape e se questi devono essere bilanciati.

Una stringa in molti formati csv è definita come string value 1,string value 2 . Tuttavia, se quella stringa contiene una virgola, ora è "string, value 1",string value 2 . Se contiene una citazione diventa "string, ""value 1""",string value 2 .

A questo punto credo sia impossibile. Il problema è che devi determinare quante virgolette hai letto e se una virgola è all'interno o all'esterno della modalità doppia quotata del valore. Le parentesi di bilanciamento sono un problema di regex impossibile. Alcuni motori di espressioni regolari (PCRE) estesi possono gestirli, ma non è un'espressione regolare allora.

Potresti trovare utile link .

Nuovo testo:

Ho esaminato i formati per i caratteri di escape e non ho trovato nessuno che necessiti di un conteggio arbitrario, quindi probabilmente non è questo il problema.

Tuttavia, ci sono problemi su quale sia il carattere di escape e il delimitatore di record (per iniziare). link è una buona lettura sui diversi formati in natura.

  • Le regole per la stringa quotata (se si tratta di una singola stringa quotata o una stringa doppia citata) differiscono.
    • 'This, is a value' vs "This, is a value"
  • Le regole per i caratteri di escape
    • "This ""is a value""" vs "This \"is a value\""
  • La gestione del delimitatore di record incorporato ({rd})
    • (raw embeded) "This {rd}is a value" vs (escape) "This \{rd}is a value" vs (tradotto) "This {0x1C}is a value"

La cosa fondamentale qui è che è possibile avere una stringa che avrà sempre più interpretazioni valide.

La domanda correlata (per i casi limite) "è possibile avere una stringa non valida che è accettata?"

Dubito strongmente che esista un'espressione regolare che possa corrispondere a tutti i CSV validi creati da alcune applicazioni e rifiutare ogni csv che non può essere analizzato.

    
risposta data 27.09.2012 - 19:23
fonte
2

Prima definisci la grammatica per il tuo CSV (i delimitatori di campo sono sfuggiti o codificati in qualche modo se compaiono nel testo?) e quindi può essere determinato se è analizzabile con espressioni regolari. Prima la grammatica: secondo parser: link Va notato che questo metodo usa un tokenizer - ma non posso costruirlo una regex POSIX che corrisponderebbe a tutti i casi limite. Se il tuo uso dei formati CSV è non regolare e privo di contesto ... allora la tua risposta è nella tua domanda. Buona panoramica qui: link

    
risposta data 27.09.2012 - 19:20
fonte
1

Questa espressione regolare può tokenize normale CSV, come descritto nella RFC:

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

Spiegazione:

  • ("(?:[^"]|"")*"|[^,"\n\r]*) - un campo CSV, quotato o meno
    • "(?:[^"]|"")*" - un campo quotato;
      • [^"]|"" - ogni carattere non è " , o " scappa come ""
    • [^,"\n\r]* - un campo non quotato, che non può contenere , " \n \r
  • (,|\r?\n|\r) : il seguente separatore, , o newline
    • \r?\n|\r - una nuova riga, una di \r\n \n \r

Un intero file CSV può essere abbinato e convalidato usando ripetutamente questa regexp. È quindi necessario correggere i campi citati e dividerli in righe in base ai separatori.

Questo è il codice per un parser CSV in Javascript, basato sul regexp:

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;
}

Se questa risposta ti aiuta a stabilire la tua argomentazione devi decidere; Sono contento di avere un parser CSV piccolo, semplice e corretto.

A mio parere, un programma lex è più o meno una grande espressione regolare, e quelli possono tokenizzare formati molto più complessi, come il linguaggio di programmazione C.

In riferimento alle RFC 4180 definizioni:

  1. interruzione di riga (CRLF) - Il regexp è più flessibile, consentendo CRLF, LF o CR.
  2. L'ultimo record nel file può o non può avere un'interruzione di riga finale - L'espressione regolare in quanto richiede un'interruzione di riga finale, ma il parser si adatta per questo.
  3. Esiste forse una riga di intestazione facoltativa, che non influisce sul parser.
  4. Ogni riga deve contenere lo stesso numero di campi in tutto il file - non applicata
    Gli spazi sono considerati parte di un campo e non dovrebbero essere ignorati - okay L'ultimo campo nel record non deve essere seguito da una virgola - non applicata
  5. Ogni campo può o non può essere racchiuso tra virgolette ... - ok
  6. I campi contenenti interruzioni di riga (CRLF), virgolette doppie e virgole devono essere racchiusi tra virgolette doppie - okay
  7. una virgoletta che appare all'interno di un campo deve essere preceduta da un altro doppio apice - okay

Lo stesso regexp soddisfa la maggior parte dei requisiti RFC 4180. Non sono d'accordo con gli altri, ma è facile regolare il parser per implementarli.

    
risposta data 22.03.2018 - 19:22
fonte

Leggi altre domande sui tag