Может ли формат csv быть определен регулярным выражением?

Мы с коллегой недавно спорили о том, способен ли чистый регулярный код полностью инкапсулировать формат csv, так что он способен анализировать все файлы с любым заданным escape-символом, символом кавычек и символом-разделителем.

Регулярное выражение не должно быть способно изменять эти символы после создания, но оно не должно терпеть неудачу в любом другом граничном случае.

Я утверждал, что это невозможно только для токенизатора. Единственное регулярное выражение, которое может это сделать, - это очень сложный стиль PCRE, который выходит за рамки простого токенизации.

Я ищу что-то вроде:

... формат csv - это контекстно-свободная грамматика, и поэтому ее невозможно проанализировать с помощью одного регулярного выражения ...

Или я не прав? Можно ли проанализировать CSV с помощью регулярного выражения POSIX?

Например, если и escape-символ, и char в кавычках ", то эти две строки являются действительными 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..."

Хороший в теории, ужасный на практике

Под CSV я предполагаю, что вы имеете в виду соглашение, описанное в RFC 4180 .

Хотя сопоставление базовых данных CSV тривиально:

"data", "more data"

Примечание: Кстати, намного эффективнее использовать функцию .split ('/ n'). Split ('"') для очень простых и хорошо структурированных данных, подобных этой. Регулярные выражения работают как NDFSM (недетерминированный конечный State Machine), который тратит много времени на возврат, когда вы начинаете добавлять крайние случаи, такие как escape-символы.

Например, вот наиболее полная строка соответствия регулярного выражения, которую я нашел:

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

Он разумно обрабатывает одинарные и двойные кавычки, но не переводит строки в новые значения, экранированные кавычки и т. Д.

Источник: Переполнение стека - Как я могу разобрать строку с помощью JavaScript

Это становится кошмаром, когда общие крайние случаи введены как ...

"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

Одного краевого случая новой строки как значения достаточно, чтобы сломать 99,9999% анализаторов на основе RegEx, найденных в дикой природе. Единственная «разумная» альтернатива - использовать сопоставление RegEx для базового токенизации управляющих / неконтрольных символов (т. Е. Терминал против нетерминала) в сочетании с конечным автоматом, используемым для анализа более высокого уровня.

Источник: опыт, иначе известный как сильная боль и страдание.

Я являюсь автором jquery-CSV , единственного в мире полностью совместимого с RFC парсера CSV на основе javascript. Я потратил месяцы на решение этой проблемы, общаясь со многими умными людьми и пробуя кучу разных реализаций, включая 3 полных переписывания ядра парсера.

tl; dr - Мораль истории, один только PCRE - отстой для анализа чего угодно, кроме самых простых и строгих регулярных (т. е. Type-III) грамматик. Хотя это полезно для токенизации терминальных и нетерминальных строк.

Regex может анализировать любой обычный язык и не может анализировать такие сложные вещи, как рекурсивные грамматики. Но CSV, кажется, довольно регулярный, так что разбирается с регулярным выражением.

Давайте поработаем с определением : допустимы последовательность, выбор альтернативных форм ( |) и повторение (звезда Клини, the *).

• Обычное значение без кавычек: [^,]*# любой символ, кроме запятой
• Значение в кавычках является обычным: "([^\"]|\\\\|\\")*"# последовательность чего-либо, кроме кавычки "или экранированной кавычки \"или экранированной escape\\
  • Некоторые формы могут включать экранирование кавычек с кавычками, что добавляет вариант ("")*"к выражению выше.
• Допустимое значение является регулярным: <unquoted-value> |<quoted-value>
• Одна строка CSV является регулярной: <значение> (,<значение>)*
• Последовательность линий, разделенных \nтакже, очевидно, правильна.

Я не тщательно проверял каждое из этих выражений и никогда не определял группы перехвата. Я также умалчивается некоторых тонкостей, как варианты символов , которые могут быть использованы вместо ,, "или разделители строк: они не нарушают регулярность, вы просто получите несколько несколько различных языков.

Если вы можете обнаружить проблему в этом доказательстве, пожалуйста, прокомментируйте! :)

Но, несмотря на это, практический анализ файлов CSV с помощью чисто регулярных выражений может быть проблематичным. Вам нужно знать, какой из вариантов подается на анализатор, и для него нет стандарта. Вы можете попробовать несколько синтаксических анализаторов для каждой строки, пока одна из них не преуспеет, или каким-либо образом угадайте комментарии формы формата. Но для этого могут потребоваться другие средства, кроме регулярных выражений, для эффективной работы или вообще.

Простой ответ - вероятно, нет.

Первая проблема - это отсутствие стандарта. Хотя можно описать их CSV строго определенным образом, нельзя ожидать получения строго определенных CSV-файлов. «Будьте консервативны в том, что вы делаете, будьте либеральными в том, что вы принимаете от других» - Джон Посталь

Если предположить, что у человека действительно есть приемлемый стандарт, возникает вопрос об экранирующих символах, и нужно ли их сбалансировать.

Строка во многих форматах CSV определяется как string value 1,string value 2. Однако, если эта строка содержит запятую, это сейчас "string, value 1",string value 2. Если он содержит цитату, он становится "string, ""value 1""",string value 2.

На данный момент я считаю, что это невозможно. Проблема в том, что вам нужно определить, сколько кавычек вы прочитали и находится ли запятая внутри или вне режима двойных кавычек значения. Балансировка скобок - это невозможная проблема регулярных выражений. Некоторые расширенные механизмы регулярных выражений (PCRE) могут справиться с этим, но тогда это не регулярное выражение.

Вы можете найти /programming/8629763/csv-parsing-with-a-context-free-grammar полезным.

Измененный:

Я искал форматы для escape-символов и не нашел ни одного, требующего произвольного подсчета - так что, вероятно, это не проблема.

Тем не менее, существуют проблемы с символом escape и разделителем записей (для начала). http://www.csvreader.com/csv_format.php хорошо читается в различных форматах в дикой природе.

• Правила для строки в кавычках (если это строка в одинарных кавычках или строка в двойных кавычках) различаются.
  • 'This, is a value' против "This, is a value"
• Правила побега персонажей
  • "This ""is a value""" против "This \"is a value\""
• Обработка встроенного разделителя записей ({rd})
  • (необработанный врезанный) "This {rd}is a value"против (сбежавший) "This \{rd}is a value"против (переведенный)"This {0x1C}is a value"

Ключевым моментом здесь является то, что возможно иметь строку, которая всегда будет иметь несколько допустимых интерпретаций.

Связанный вопрос (для крайних случаев) "возможно ли иметь недопустимую строку, которая принята?"

Я все еще сильно сомневаюсь, что существует регулярное выражение, которое может соответствовать каждому действительному CSV, созданному некоторым приложением, и отклонять каждый CSV, который не может быть проанализирован.

Сначала определите грамматику для вашего CSV (экранированные или закодированные как-то поля-разделители полей, если они появляются в тексте?), А затем можно определить, является ли он анализируемым с помощью регулярных выражений. Первая грамматика: вторая парсер: http://www.boyet.com/articles/csvparser.html Следует отметить, что этот метод использует токенизатор - но я не могу создать регулярное выражение POSIX, которое бы соответствовало всем крайним случаям. Если вы используете форматы CSV нерегулярно и не зависят от контекста ... тогда ваш ответ на ваш вопрос. Хороший обзор здесь: http://nikic.github.com/2012/06/15/The-true-power-of-regular-expressions.html

Это регулярное выражение может маркировать нормальный CSV, как описано в RFC:

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

Объяснение:

• ("(?:[^"]|"")*"|[^,"\n\r]*) - поле CSV, указано или нет
  • "(?:[^"]|"")*" - цитируемое поле;
    • [^"]|""- каждый персонаж либо нет ", либо "экранирован как""
  • [^,"\n\r]* - поле без кавычек, которое может не содержать , " \n \r
• (,|\r?\n|\r)- следующий разделитель, либо ,перевод строки
  • \r?\n|\r - перевод строки, один из \r\n \n \r

Весь CSV-файл можно сопоставить и проверить с помощью этого регулярного выражения. Затем необходимо исправить поля в кавычках и разбить их на строки на основе разделителей.

Вот код для анализатора CSV в Javascript, основанный на регулярном выражении:

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

Помогает ли этот ответ урегулировать ваши аргументы, решать вам; Я просто счастлив иметь небольшой, простой и правильный парсер CSV.

На мой взгляд, lexпрограмма представляет собой более или менее большое регулярное выражение, и они могут маркировать гораздо более сложные форматы, такие как язык программирования Си.

Со ссылкой на определения RFC 4180 :

1. разрыв строки (CRLF) - регулярное выражение является более гибким, позволяя использовать CRLF, LF или CR.
2. Последняя запись в файле может иметь или не иметь разрыв конца строки - Регулярное выражение в том виде, в каком оно есть, требует окончательного перевода строки, но анализатор подстраивается под это.
3. Там может быть необязательная строка заголовка - это не влияет на синтаксический анализатор.
4. Каждая строка должна содержать одинаковое количество полей в файле - неиспользуемые
   пробелы считаются частью поля и не должны игнорироваться - хорошо
   . Последнее поле в записи не должно сопровождаться запятой - не обязательно
5. Каждое поле может быть или не быть заключено в двойные кавычки ... - хорошо
6. Поля, содержащие разрывы строк (CRLF), двойные кавычки и запятые, должны быть заключены в двойные кавычки - хорошо
7. двойная кавычка, появляющаяся внутри поля, должна быть экранирована, предшествуя другой двойной кавычке - хорошо

Само регулярное выражение удовлетворяет большинству требований RFC 4180. Я не согласен с другими, но легко настроить парсер для их реализации.