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

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

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.

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.

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

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

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