Kann das CSV-Format durch eine Regex definiert werden?

19

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..."
Spencer Rathbun
quelle
Es ist kein CSV, da es nirgendwo ein Nest gibt (IIRC)
Ratschenfreak
1
aber was sind die Randfälle? Vielleicht steckt mehr in CSV, als ich je gedacht habe?
c69
1
@ c69 Wie über Flucht- und Gänsefüsschen beide sind ". Dann gilt:"""this is a test.""",""
Spencer Rathbun
Hast du regexp von hier aus versucht ?
dasblinkenlight
1
Sie müssen auf Randfälle achten, aber ein regulärer Ausdruck sollte in der Lage sein, csv so zu tokenisieren, wie Sie es beschrieben haben. Der reguläre Ausdruck muss nicht beliebig viele Anführungszeichen hochzählen, sondern muss nur bis 3 zählen, was reguläre Ausdrücke können. Wie andere erwähnt haben, sollten Sie versuchen , eine gut definierte Darstellung aufschreiben , was man einen csv erwarten Token zu sein ...
comingstorm

Antworten:

20

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.

Evan Scholle
quelle
1
Ja, das war auch meine Erfahrung. Jeder Versuch, mehr als ein sehr einfaches CSV-Muster vollständig zu kapseln, führt zu diesen Problemen, und dann stoßen Sie sowohl auf die Effizienzprobleme als auch auf die Komplexitätsprobleme eines massiven regulären Ausdrucks. Haben Sie sich die node-csv- Bibliothek angesehen? Es scheint auch diese Theorie zu bestätigen. Jede nicht triviale Implementierung verwendet intern einen Parser.
Spencer Rathbun
@SpencerRathbun Ja. Ich bin mir sicher, dass ich mir vorher die node-csv-Quelle angesehen habe. Es scheint eine typische Zeichen-Tokenisierungs-Zustandsmaschine für die Verarbeitung zu verwenden. Der jquery-csv-Parser arbeitet nach dem gleichen Grundkonzept, außer dass ich Regex für die Terminal- / Nicht-Terminal-Tokenisierung verwende. Anstatt Zeichen für Zeichen auszuwerten und zu verketten, kann regex mehrere nicht-terminale Zeichen gleichzeitig abgleichen und als Gruppe (dh als Zeichenfolge) zurückgeben. Dies minimiert unnötige Verkettungen und sollte die Effizienz steigern.
Evan Plaice
20

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.

9000
quelle
4
Absolut eine +1 für den praktischen Punkt. Es gibt etwas, von dem ich sicher bin, dass es irgendwo in der Tiefe ein Beispiel für einen (erfundenen) Wert gibt, der die zitierte Werteversion sprengen würde. Ich weiß einfach nicht, was es ist. Der "Spaß" mit mehreren Parsern wäre "diese beiden arbeiten, aber geben unterschiedliche Antworten"
1
Offensichtlich benötigen Sie für Anführungszeichen mit umgekehrten Schrägstrichen andere reguläre Ausdrücke als für Anführungszeichen mit doppelten Schrägstrichen. Ein regulärer Ausdruck für den ersteren Typ eines CSV-Feldes sollte ungefähr so ​​aussehen [^,"]*|"(\\(\\|")|[^\\"])*", und der letztere sollte ungefähr so ​​aussehen [^,"]*|"(""|[^"])*". (Vorsicht, da ich keines von beiden getestet habe!)
Comingstorm
Auf der Suche nach etwas , das vielleicht ein Standard ist, fehlt ein Fall - ein Wert mit einem eingeschlossenen Datensatzbegrenzer. Dies macht auch das praktische Parsen noch mehr Spaß, wenn es mehrere verschiedene Möglichkeiten gibt, damit
Schöne Antwort, aber wenn ich renne perl -pi -e 's/"([^\"]|\\\\|\\")*"/yay/'und "I have here an item,\" that is a test\""einpfeife, ist das Ergebnis "yay, das ist ein Test". Meint, deine Regex ist fehlerhaft.
Spencer Rathbun
@SpencerRathbun: Wenn ich mehr Zeit habe, teste ich die regulären Ausdrücke und füge wahrscheinlich sogar einen Proof-of-Concept-Code ein, der die Tests besteht. Entschuldigung, der Arbeitstag geht weiter.
9000
5

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.

Gemeinschaft
quelle
1
Anführungszeichen in Anführungszeichen müssen nicht ausgeglichen sein. Stattdessen muss eine gerade Anzahl von Zitaten vor einem eingebetteten Zitat sein, die offensichtlich regelmäßig ist: ("")*". Wenn die Quotes innerhalb des Wertes aus dem Gleichgewicht geraten, ist dies bereits nicht unsere Sache.
9000
Dies ist meine Position, nachdem ich in der Vergangenheit auf diese schrecklichen Ausreden für "Datenübertragung" gestoßen bin. Das einzige, was sie richtig handhabte, war ein Parser, reiner Regex, der alle paar Wochen kaputt ging.
Spencer Rathbun
2

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

Iivel
quelle
2

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.

Sam Watkins
quelle
1
Das sieht eher wie Eigenwerbung als die Frage Adressierung gefragt, sehen wie man Antwort
gnat
1
@gnat, ich habe meine Antwort bearbeitet, um mehr Erklärungen zu geben, den regulären Ausdruck gegen RFC 4180 zu prüfen und ihn weniger selbstfördernd zu machen. Ich glaube, dass diese Antwort einen Wert hat, da sie einen getesteten regulären Ausdruck enthält, der die häufigste Form von CSV-Dateien, wie sie von Excel und anderen Tabellenkalkulationen verwendet werden, symbolisieren kann. Ich denke, dass dies die Frage regelt. Der kleine CSV-Parser zeigt, dass es einfach ist, CSV mit diesem regulären Ausdruck zu analysieren.
Sam Watkins
Ohne übermäßig für mich werben zu wollen, hier sind meine vollständigen kleinen CSV- und TSV-Bibliotheken, die ich als Teil einer kleinen Tabellenkalkulations-App verwende (Google Sheets fühlen sich zu schwer für mich an). Dies ist Open Source- / Public Domain- / CC0-Code wie alles, was ich veröffentliche. Ich hoffe, dass dies für jemand anderen nützlich sein kann. sam.aiki.info/code/js
Sam Watkins