Kann das CSV-Format durch eine Regex definiert werden?

Ein Kollege und ich haben kürzlich darüber gestritten, ob ein reiner regulärer Ausdruck das csv-Format vollständig kapseln kann, sodass alle Dateien mit einem bestimmten Escape-, Anführungszeichen und Trennzeichen analysiert werden können.

Der Regex muss nicht in der Lage sein, diese Zeichen nach der Erstellung zu ändern, darf jedoch in keinem anderen Edge-Fall fehlschlagen.

Ich habe argumentiert, dass dies nur für einen Tokenizer unmöglich ist. Der einzige Regex, der dies tun könnte, ist ein sehr komplexer PCRE-Stil, der über das reine Tokenisieren hinausgeht.

Ich suche etwas im Sinne von:

... das csv-Format ist eine kontextfreie Grammatik und als solche ist es unmöglich, nur mit Regex zu analysieren ...

Oder liege ich falsch? Ist es möglich, csv nur mit einer POSIX-Regex zu analysieren?

Wenn beispielsweise sowohl das Escape-Zeichen als auch das Anführungszeichen vorhanden sind ", sind diese beiden Zeilen gültig. 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..."

Nizza in der Theorie, schrecklich in der Praxis

Mit CSV meine ich die in RFC 4180 beschriebene Konvention .

Während der Abgleich grundlegender CSV-Daten trivial ist:

"data", "more data"

Hinweis: Übrigens ist die Verwendung der Funktion .split ('/ n') .split ('"') für sehr einfache und gut strukturierte Daten wie diese wesentlich effizienter. Reguläre Ausdrücke funktionieren als NDFSM (Non-Deterministic Finite) State Machine), die viel Zeit für das Zurückverfolgen verschwendet, sobald Sie Kantenfälle wie Escape-Zeichen hinzufügen.

Zum Beispiel ist hier die umfassendste Zeichenfolge für reguläre Ausdrücke, die ich gefunden habe:

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

Werte in einfachen und doppelten Anführungszeichen, aber keine Zeilenumbrüche in Werten, Anführungszeichen usw. werden angemessen behandelt.

Quelle: Stapelüberlauf - Wie kann ich einen String mit JavaScript analysieren?

Es wird ein Albtraum, sobald die gängigen Randfälle eingeführt werden wie ...

"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

Der Newline-as-Value-Edge-Fall allein reicht aus, um 99,9999% der in der Natur gefundenen RegEx-basierten Parser zu brechen. Die einzige "vernünftige" Alternative ist die Verwendung des RegEx-Abgleichs für die Tokenisierung von Basissteuerungs- / Nichtsteuerungszeichen (dh Terminal vs. Nicht-Terminal) in Kombination mit einer Zustandsmaschine, die für die Analyse auf höherer Ebene verwendet wird.

Quelle: Erfahrung, die sonst als starke Schmerzen und Leiden bekannt ist.

Ich bin der Autor von jquery-CSV , dem einzigen Javascript-basierten, vollständig RFC-konformen CSV-Parser der Welt. Ich habe Monate damit verbracht, dieses Problem anzugehen, mit vielen intelligenten Leuten zu sprechen und eine Menge verschiedener Implementierungen auszuprobieren, einschließlich dreier vollständiger Neuschreibungen der Core-Parser-Engine.

tl; dr - Moral der Geschichte, PCRE allein saugt für das Parsen alles andere als die einfachsten und strengsten regulären (dh Typ-III) Grammatiken. Es ist jedoch nützlich, um terminale und nicht terminale Zeichenfolgen zu kennzeichnen.

Regex kann jede reguläre Sprache analysieren und kann keine interessanten Dinge wie rekursive Grammatiken analysieren. Aber CSV scheint ziemlich regelmäßig zu sein und lässt sich mit einer Regex analysieren.

Gehen wir von der Definition aus : Erlaubt sind Reihenfolge, Wahl zwischen Alternativen ( |) und Wiederholung (Kleene star, the *).

• Ein Wert ohne Anführungszeichen ist normal: [^,]*# ein beliebiges Zeichen außer Komma
• Ein Wert in Anführungszeichen ist regulär: "([^\"]|\\\\|\\")*"# Folge von Werten , die nicht in Anführungszeichen "oder mit Escapezeichen \"oder mit Escapezeichen angegeben sind\\
  • Einige Formulare können Anführungszeichen mit Anführungszeichen enthalten, wodurch eine Variante ("")*"zum obigen Ausdruck hinzugefügt wird.
• Ein zulässiger Wert ist regulär: <Wert ohne |Anführungszeichen > <Wert mit Anführungszeichen>
• Eine einzelne CSV-Zeile ist normal: <Wert> (,<Wert>)*
• Auch eine durch getrennte Abfolge von Zeilen \nist offensichtlich regelmäßig.

Ich habe nicht jeden dieser Ausdrücke akribisch getestet und keine Fanggruppen definiert. Ich habe auch einige technische Details, wie die Varianten von Zeichen, die anstelle von verwendet werden ,können ", oder Zeilentrennzeichen, beschrieben: Diese verstoßen nicht gegen die Regelmäßigkeit, Sie erhalten nur einige leicht unterschiedliche Sprachen.

Wenn Sie ein Problem in diesem Beweis finden können, kommentieren Sie bitte! :)

Trotzdem kann das praktische Parsen von CSV-Dateien durch reine reguläre Ausdrücke problematisch sein. Sie müssen wissen, welche der Varianten dem Parser zugeführt wird, und es gibt keinen Standard dafür. Sie können mehrere Parser für jede Zeile ausführen, bis eine erfolgreich ist, oder das Format von Kommentaren unterscheiden. Dies kann jedoch andere Mittel als reguläre Ausdrücke erfordern, um effizient oder überhaupt zu arbeiten.

Einfache Antwort - wahrscheinlich nicht.

Das erste Problem ist das Fehlen eines Standards. Während man ihre csv auf eine streng definierte Weise beschreiben kann, kann man nicht erwarten, streng definierte csv-Dateien zu erhalten. "Sei konservativ in dem, was du tust, sei liberal in dem, was du von anderen akzeptierst" -Jon Postal

Unter der Annahme, dass man eine akzeptable Standardsprache hat, stellt sich die Frage nach Fluchtzeichen und ob diese ausgeglichen werden müssen.

Ein String in vielen CSV-Formaten ist definiert als string value 1,string value 2. Wenn diese Zeichenfolge jedoch ein Komma enthält, ist dies jetzt der Fall "string, value 1",string value 2. Wenn es ein Zitat enthält, wird es"string, ""value 1""",string value 2 .

An dieser Stelle halte ich es für unmöglich. Das Problem ist, dass Sie bestimmen müssen, wie viele Anführungszeichen Sie gelesen haben und ob ein Komma innerhalb oder außerhalb des Modus mit doppelten Anführungszeichen für den Wert steht. Das Ausbalancieren von Klammern ist ein unmögliches Regex-Problem. Einige Extended Regular Expression Engines (PCRE) können damit umgehen, aber es ist dann kein regulärer Ausdruck.

Du könntest finden /programming/8629763/csv-parsing-with-a-context-free-grammar nützlich.

Geändert:

Ich habe nach Formaten für Escape-Zeichen gesucht und keine gefunden, die willkürlich gezählt werden müssen - das ist wahrscheinlich nicht das Problem.

Es gibt jedoch Probleme mit dem Escape-Zeichen und dem Datensatztrennzeichen (um damit zu beginnen). http://www.csvreader.com/csv_format.php ist eine gute Lektüre der verschiedenen Formate in freier Wildbahn.

• Die Regeln für die Zeichenfolge in Anführungszeichen (wenn es sich um eine Zeichenfolge in einfachen oder doppelten Anführungszeichen handelt) unterscheiden sich.
  • 'This, is a value' vs "This, is a value"
• Die Regeln für Escape-Zeichen
  • "This ""is a value""" vs "This \"is a value\""
• Die Behandlung des eingebetteten Datensatztrennzeichens ({rd})
  • (roh eingebettet) "This {rd}is a value"vs (entkommen) "This \{rd}is a value"vs (übersetzt)"This {0x1C}is a value"

Der Schlüssel ist, dass es möglich ist, einen String zu haben, der immer mehrere gültige Interpretationen hat.

Die zugehörige Frage (für Kantenfälle) "Ist es möglich, dass eine ungültige Zeichenfolge akzeptiert wird?"

Ich bezweifle immer noch stark, dass es einen regulären Ausdruck gibt, der mit jeder gültigen CSV-Datei übereinstimmt, die von einer Anwendung erstellt wurde, und jede CSV-Datei ablehnt, die nicht analysiert werden kann.

Definieren Sie zuerst die Grammatik für Ihre CSV (werden die Feldbegrenzer maskiert oder codiert, wenn sie im Text erscheinen?) Und stellen Sie dann fest, ob sie mit Regex syntaktisch analysiert werden können. Grammatik zuerst: Parser zweitens: http://www.boyet.com/articles/csvparser.html Es sollte beachtet werden, dass diese Methode einen Tokenizer verwendet - aber ich kann keine POSIX-Regex erstellen, die mit allen Edge-Fällen übereinstimmt. Wenn Ihre Verwendung von CSV-Formaten nicht regelmäßig und kontextfrei ist ... dann ist Ihre Antwort Ihre Frage. Gute Übersicht hier: http://nikic.github.com/2012/06/15/The-true-power-of-regular-expressions.html

Dieser reguläre Ausdruck kann eine normale CSV-Datei wie im RFC beschrieben tokenisieren:

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

Erläuterung:

• ("(?:[^"]|"")*"|[^,"\n\r]*) - ein CSV-Feld, zitiert oder nicht
  • "(?:[^"]|"")*" - ein zitiertes Feld;
    • [^"]|""- Jedes Zeichen ist entweder nicht "oder "escape als""
  • [^,"\n\r]* - ein nicht zitiertes Feld, das möglicherweise nicht enthält , " \n \r
• (,|\r?\n|\r)- das folgende Trennzeichen, entweder ,oder eine neue Zeile
  • \r?\n|\r - eine Newline, eine von \r\n \n \r

Eine gesamte CSV-Datei kann durch wiederholte Verwendung dieses regulären Ausdrucks abgeglichen und validiert werden. Es ist dann notwendig, die angegebenen Felder zu korrigieren und sie auf der Grundlage der Trennzeichen in Zeilen aufzuteilen.

Hier ist Code für einen CSV-Parser in Javascript, basierend auf dem regulären Ausdruck:

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

Ob diese Antwort Ihnen hilft, Ihr Argument zu klären, müssen Sie selbst entscheiden. Ich bin einfach froh, einen kleinen, einfachen und korrekten CSV-Parser zu haben.

Meiner Meinung nach a lex Programm mehr oder weniger ein großer regulärer Ausdruck, und diese können viel komplexere Formate wie die Programmiersprache C symbolisieren.

In Bezug auf die RFC 4180- Definitionen:

1. Zeilenumbruch (CRLF) - Der reguläre Ausdruck ist flexibler und ermöglicht CRLF, LF oder CR.
2. Der letzte Datensatz in der Datei hat möglicherweise einen Zeilenumbruch am Ende oder nicht - Der reguläre Ausdruck erfordert einen letzten Zeilenumbruch, aber der Parser passt sich dem an.
3. Möglicherweise gibt es eine optionale Kopfzeile. Dies hat keine Auswirkungen auf den Parser.
4. Jede Zeile sollte die gleiche Anzahl von Feldern in der Datei enthalten - nicht erzwungene
   Leerzeichen werden als Teil eines Feldes betrachtet und sollten nicht ignoriert werden - okay
   Auf das letzte Feld im Datensatz darf kein Komma folgen. Nicht erzwungen
5. Jedes Feld kann in doppelte Anführungszeichen eingeschlossen sein oder nicht ... - okay
6. Felder, die Zeilenumbrüche (CRLF), doppelte Anführungszeichen und Kommas enthalten, sollten in doppelte Anführungszeichen eingeschlossen werden - okay
7. Ein doppeltes Anführungszeichen in einem Feld muss mit einem weiteren doppelten Anführungszeichen versehen werden - okay

Der reguläre Ausdruck selbst erfüllt die meisten RFC 4180-Anforderungen. Ich stimme den anderen nicht zu, aber es ist einfach, den Parser anzupassen, um sie zu implementieren.