Czy format csv można zdefiniować za pomocą wyrażenia regularnego?

19

Współpracownik i ja ostatnio spieraliśmy się o to, czy czysty regex jest w stanie w pełni enkapsulować format csv, tak że jest w stanie parsować wszystkie pliki za pomocą dowolnego znaku zmiany znaczenia, znaku cytowania i znaku separatora.

Wyrażenie regularne nie musi być zdolne do zmiany tych znaków po utworzeniu, ale nie może zawieść w żadnym innym przypadku krawędzi.

Argumentowałem, że jest to niemożliwe tylko dla tokenizera. Jedynym wyrażeniem regularnym, które może to zrobić, jest bardzo złożony styl PCRE, który wykracza poza zwykłe tokenizowanie.

Szukam czegoś w stylu:

... format csv jest gramatyką bezkontekstową i dlatego niemożliwe jest parsowanie samego regexu ...

A może się mylę? Czy można parsować csv za pomocą wyrażenia regularnego POSIX?

Na przykład, jeśli zarówno znak zmiany znaczenia, jak i znak cudzysłowu są ", wtedy te dwie linie są poprawne 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
źródło
to nie jest CSV, ponieważ nigdzie nie ma zagnieżdżenia (IIRC)
maniak zapadkowy
1
ale jakie są przypadki brzegowe? może w CSV jest więcej niż kiedykolwiek myślałem?
69
1
@ c69 Co powiesz na ucieczkę i cytat char ". W takim przypadku obowiązuje:"""this is a test.""",""
Spencer Rathbun
Próbowałeś stąd wyrażenia regularnego ?
dasblinkenlight
1
Trzeba uważać na przypadki krawędzi, ale wyrażenie regularne powinno być w stanie tokenizować plik csv tak, jak to opisano. Wyrażenie regularne nie musi zliczać dowolnej liczby cudzysłowów - wystarczy policzyć do 3, co mogą zrobić wyrażenia regularne. Jak wspomnieli inni, powinieneś spróbować spisać dobrze zdefiniowaną reprezentację tego, czego oczekujesz od tokena csv ...
nadchodząca burza

Odpowiedzi:

20

Niezły w teorii, okropny w praktyce

Przez CSV założę , że masz na myśli konwencję opisaną w RFC 4180 .

Dopasowanie podstawowych danych CSV jest banalne:

"data", "more data"

Uwaga: BTW, o wiele bardziej wydajne jest korzystanie z funkcji .split ('/ n'). Split ('”) dla bardzo prostych i dobrze zorganizowanych danych takich jak ta. Wyrażenia regularne działają jako NDFSM (niedeterministyczny skończony State Machine), która marnuje dużo czasu na cofanie się, gdy zaczniesz dodawać przypadki krawędzi, takie jak znaki ucieczki.

Oto na przykład najbardziej wyczerpujący ciąg pasujący do wyrażeń regularnych, jaki znalazłem:

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

W rozsądny sposób obsługuje wartości pojedynczego i podwójnego cudzysłowu, ale nie nowe wartości w wartościach, cudzysłowy itp.

Źródło: Przepełnienie stosu - jak analizować ciąg za pomocą JavaScript

Staje się koszmarem po wprowadzeniu typowych skrzynek krawędziowych, takich jak ...

"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

Sam przypadek krawędzi nowej linii jako wartości jest wystarczający, aby złamać 99,9999% parserów opartych na RegEx znalezionych na wolności. Jedyną „rozsądną” alternatywą jest użycie dopasowania RegEx do podstawowego tokenizacji kontrolnej / niekontrolowanej (tj. Terminal vs nieterminalny) w połączeniu z maszyną stanu używaną do analizy wyższego poziomu.

Źródło: Doświadczenie znane również jako rozległy ból i cierpienie.

Jestem autorem jquery-CSV , jedynego na świecie parsera CSV opartego na javascript, w pełni zgodnego z RFC. Spędziłem miesiące zajmując się tym problemem, rozmawiając z wieloma inteligentnymi ludźmi i próbując tony, jeśli różne implementacje, w tym 3 pełne przeróbki silnika głównego parsera.

tl; dr - Morał tej historii, sam PCRE jest do bani, jeśli chodzi o parsowanie czegokolwiek poza najprostszymi i najściślejszymi zwykłymi gramatykami (tj. typ III). Mimo to jest przydatny do tokenizacji ciągów terminalowych i nieterminalnych.

Evan Plaice
źródło
1
Tak, to też było moje doświadczenie. Każda próba pełnego kapsułkowania czegoś więcej niż bardzo prostego wzorca CSV napotyka na te rzeczy, a następnie napotykasz zarówno problemy z wydajnością, jak i problemy z złożonością ogromnego wyrażenia regularnego. Czy przeglądałeś bibliotekę node-csv ? Wydaje się również, że ta teoria jest uzasadniona. Każda nietrywialna implementacja używa wewnętrznego analizatora składni.
Spencer Rathbun
@SpencerRathbun Yep. Jestem pewien, że wcześniej rzuciłem okiem na źródło node-csv. Wygląda na to, że do przetwarzania używa typowej maszyny stanu tokenizacji znaków. Parser jquery-csv działa na tej samej podstawowej koncepcji, z tym wyjątkiem, że używam wyrażenia regularnego do tokenizacji terminala / terminala. Zamiast oceniać i konkatenować na zasadzie char-by-char, regex jest w stanie dopasować wiele nieterminalnych znaków na raz i zwrócić je jako grupę (tj. Łańcuch). Minimalizuje to niepotrzebne konkatenacje i „powinno” zwiększyć wydajność.
Evan Plaice,
20

Regex może analizować dowolny zwykły język i nie może analizować wymyślnych rzeczy, takich jak gramatyki rekurencyjne. Ale CSV wydaje się być dość regularny, więc można go analizować za pomocą wyrażenia regularnego.

Przejdźmy do definicji : dozwolone są sekwencja, wybór formy alternatywnej ( |) i powtórzenie (gwiazda Kleene'a *).

  • Niecytowana wartość jest regularna: [^,]*# dowolny znak oprócz przecinka
  • Podana wartość jest regularna: "([^\"]|\\\\|\\")*"# sekwencja dowolnej wartości oprócz cytatu "lub ucieczki cytatu \"lub ucieczki\\
    • Niektóre formy mogą zawierać cytaty z cudzysłowami, co dodaje wariant ("")*"powyższemu wyrażeniu.
  • Dozwolona wartość jest regularna: <wartość niepotwierdzona> |<wartość podana>
  • Pojedyncza linia CSV jest regularna: <wartość> (,<wartość>)*
  • Sekwencja oddzielonych linii \njest również oczywiście regularna.

Nie skrupulatnie testowałem każde z tych wyrażeń i nigdy nie zdefiniowałem grup catch. Ja również pomijane pewne szczegóły techniczne, jak wariantów znaków, które mogą być wykorzystywane zamiast ,, "lub liniowych separatorów: to nie łamią prawidłowości, po prostu dostać kilka nieco różnych językach.

Jeśli zauważysz problem w tym dowodzie, prosimy o komentarz! :)

Ale mimo to praktyczne analizowanie plików CSV za pomocą czystych wyrażeń regularnych może być problematyczne. Musisz wiedzieć, który wariant jest podawany do parsera, i nie ma dla niego standardu. Możesz wypróbować kilka parserów dla każdej linii, aż jeden się powiedzie, lub w jakiś sposób rozróżnić format formularza od komentarzy. Ale może to wymagać środków innych niż wyrażenia regularne, aby działać wydajnie lub wcale.

9000
źródło
4
Absolutnie +1 za punkt praktyczny. Jest coś, co jestem pewien, gdzieś głęboko jest przykład (wymyślonej) wartości, która złamałaby wersję z cytowaną wartością Po prostu nie wiem, co to jest. „Zabawa” z wieloma parserami to „te dwie prace, ale dają różne odpowiedzi”
1
Będziesz oczywiście potrzebować różnych wyrażeń regularnych dla cudzysłowów odwróconego ukośnika w porównaniu z cudzysłowami cytowanymi. Wyrażenie regularne dla pierwszego typu pola csv powinno być podobne [^,"]*|"(\\(\\|")|[^\\"])*", a drugie powinno być podobne [^,"]*|"(""|[^"])*". (Uwaga, ponieważ nie testowałem żadnego z nich!)
nadchodząca burza
Polując na coś , co może być standardem, istnieje przypadek, który został pominięty - wartość z załączonym ogranicznikiem rekordu. To sprawia, że ​​praktyczna analiza jest jeszcze przyjemniejsza, gdy istnieje wiele różnych sposobów radzenia sobie z tym
Fajna odpowiedź, ale jeśli uruchomię perl -pi -e 's/"([^\"]|\\\\|\\")*"/yay/'i podłączę "I have here an item,\" that is a test\""się, wynikiem jest „tak, to test”. Uważa, że ​​wyrażenie regularne jest wadliwe.
Spencer Rathbun
@SpencerRathbun: kiedy będę miał więcej czasu, faktycznie przetestuję wyrażenia regularne i prawdopodobnie nawet wkleję kod sprawdzającej koncepcję, który przejdzie testy. Przepraszamy, dzień pracy trwa.
9000
5

Prosta odpowiedź - prawdopodobnie nie.

Pierwszym problemem jest brak standardu. Podczas gdy można opisać ich csv w ściśle określony sposób, nie można oczekiwać, że otrzymają ściśle określone pliki csv. „Bądź konserwatywny w tym, co robisz, bądź liberalny w tym, co akceptujesz od innych” - Jon Postal

Zakładając, że ktoś ma standardową akceptowalną, istnieje kwestia znaków ucieczki i czy trzeba je wyważyć.

Ciąg w wielu formatach csv jest zdefiniowany jako string value 1,string value 2. Jeśli jednak ten ciąg zawiera przecinek, jest teraz "string, value 1",string value 2. Jeśli zawiera cytat, staje się "string, ""value 1""",string value 2.

W tym momencie uważam, że to niemożliwe. Problem polega na tym, że musisz ustalić, ile cytatów przeczytałeś i czy przecinek znajduje się wewnątrz lub na zewnątrz trybu podwójnego cytowania wartości. Równoważenie nawiasów jest niemożliwym problemem wyrażenia regularnego. Niektóre rozszerzone mechanizmy wyrażeń regularnych (PCRE) mogą sobie z tym poradzić, ale wtedy nie jest to wyrażenie regularne.

Może się przydać /programming/8629763/csv-parsing-with-a-context-free-grammar przydatne.


Zmieniono:

Patrzyłem na formaty znaków specjalnych i nie znalazłem żadnych, które wymagałyby arbitralnego liczenia - więc prawdopodobnie nie o to chodzi.

Istnieją jednak problemy dotyczące tego, co jest znakiem ucieczki i ogranicznikiem zapisu (na początek). http://www.csvreader.com/csv_format.php to dobra lektura różnych formatów na wolności.

  • Reguły dla cytowanego łańcucha (jeśli jest to łańcuch pojedynczego lub podwójnego cudzysłowu) różnią się.
    • 'This, is a value' vs "This, is a value"
  • Zasady dotyczące znaków ucieczki
    • "This ""is a value""" vs "This \"is a value\""
  • Obsługa osadzonego ogranicznika rekordów ({rd})
    • (raw embeded) "This {rd}is a value"vs (escaped) "This \{rd}is a value"vs (przetłumaczone)"This {0x1C}is a value"

Kluczową kwestią jest to, że można mieć ciąg znaków, który zawsze będzie miał wiele poprawnych interpretacji.

Powiązane pytanie (w przypadkach skrajnych) „czy możliwe jest zaakceptowanie niepoprawnego ciągu?”

Nadal mocno wątpię, że istnieje wyrażenie regularne, które może pasować do każdego poprawnego pliku CSV utworzonego przez jakąś aplikację i odrzuca wszystkie pliki CSV, których nie można przeanalizować.

Społeczność
źródło
1
Cytaty w cudzysłowie nie muszą być wyważone. Zamiast tego, musi być numer nawet cytatów przed osadzonym cytat, który jest oczywiście regularna: ("")*". Jeśli cytaty wewnątrz wartości są niezrównoważone, to już nie nasza sprawa.
9000
Takie jest moje stanowisko, ponieważ w przeszłości spotkałem się z tymi okropnymi wymówkami dotyczącymi „transferu danych”. Jedyną rzeczą, która odpowiednio sobie z nimi poradziła, był parser, czysty regex łamał się co kilka tygodni.
Spencer Rathbun
2

Najpierw zdefiniuj gramatykę dla swojego pliku CSV (czy separatory pól są jakoś uciekane lub zakodowane, jeśli pojawiają się w tekście?), A następnie można ustalić, czy można je przetworzyć za pomocą wyrażenia regularnego. Gramatyka pierwsza: parser drugi: http://www.boyet.com/articles/csvparser.html Należy zauważyć, że ta metoda używa tokenizera - ale nie mogę utworzyć wyrażenia regularnego POSIX, które pasowałoby do wszystkich przypadków krawędzi. Jeśli korzystanie z formatów CSV jest nieregularne i pozbawione kontekstu ... to odpowiedź na twoje pytanie. Dobry przegląd tutaj: http://nikic.github.com/2012/06/15/The-true-power-of-regular-expressions.html

iivel
źródło
2

Ten wyrażenie regularne może tokenizować normalny CSV, jak opisano w RFC:

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

Wyjaśnienie:

  • ("(?:[^"]|"")*"|[^,"\n\r]*) - pole CSV, cytowane lub nie
    • "(?:[^"]|"")*" - cytowane pole;
      • [^"]|""- każda postać albo nie ", albo "ucieka jako""
    • [^,"\n\r]* - pole niecytowane, które nie może zawierać , " \n \r
  • (,|\r?\n|\r)- następujący separator, albo ,nowy wiersz
    • \r?\n|\r - nowa linia, jedna z \r\n \n \r

Cały plik CSV można dopasować i sprawdzić poprawność za pomocą tego wyrażenia regularnego wielokrotnie. Konieczne jest zatem poprawienie cytowanych pól i podzielenie ich na wiersze na podstawie separatorów.

Oto kod parsera CSV w JavaScript, na podstawie wyrażenia regularnego:

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

To, czy ta odpowiedź pomoże rozstrzygnąć spór, należy do ciebie; Cieszę się, że mam mały, prosty i poprawny parser CSV.

Moim zdaniem lexprogram jest mniej więcej dużym wyrażeniem regularnym, które mogą tokenizować znacznie bardziej złożone formaty, takie jak język programowania C.

W odniesieniu do definicji RFC 4180 :

  1. podział linii (CRLF) - Wyrażenie regularne jest bardziej elastyczne, umożliwiając CRLF, LF lub CR.
  2. Ostatni rekord w pliku może, ale nie musi, mieć kres linii końcowej - Ponowne wyrażenie regularne wymaga końca linii, ale parser się do tego dostosowuje.
  3. Może być opcjonalna linia nagłówka - Nie wpływa to na parser.
  4. Każda linia powinna zawierać tę samą liczbę pól w całym pliku - nie wymuszone
    Spacje są uważane za część pola i nie powinny być ignorowane - dobrze
    Ostatnie pole rekordu nie może być poprzedzone przecinkiem - nie wymuszone
  5. Każde pole może, ale nie musi być ujęte w podwójne cudzysłowy ... - w porządku
  6. Pola zawierające podział wiersza (CRLF), podwójne cudzysłowy i przecinki powinny być ujęte w cudzysłowy - dobrze
  7. podwójny cytat pojawiający się w polu musi być poprzedzony innym podwójnym cytatem - w porządku

Sam regexp spełnia większość wymagań RFC 4180. Nie zgadzam się z innymi, ale łatwo jest dostosować parser, aby je zaimplementować.

Sam Watkins
źródło
1
wygląda to bardziej na autopromocję niż na
gnat
1
@gnat, zredagowałem swoją odpowiedź, aby podać więcej wyjaśnień, sprawdzić wyrażenie regularne w stosunku do RFC 4180 i aby zmniejszyć autopromocję. Uważam, że ta odpowiedź ma wartość, ponieważ zawiera przetestowane wyrażenie regularne, które może tokenizować najpopularniejszą formę CSV używaną przez Excel i inne arkusze kalkulacyjne. Myślę, że to rozwiązuje pytanie. Mały parser CSV pokazuje, że łatwo jest parsować CSV za pomocą tego wyrażenia regularnego.
Sam Watkins
Nie chcąc nadmiernie się promować, oto moje kompletne małe biblioteki csv i tsv, których używam w ramach małej aplikacji do arkuszy kalkulacyjnych (arkusze Google są dla mnie zbyt ciężkie). To jest kod typu open source / public domain / CC0 jak wszystkie publikowane przeze mnie treści. Mam nadzieję, że może to być przydatne dla kogoś innego. sam.aiki.info/code/js
Sam Watkins