Адъ CSV

[metaclass]

А напишите кто-нибудь табличку состояний CSV парсера? Т.е. последовательность символов, разделенных запятыми, в строках, разделенных \r или \r\n разбить на список списков строк. Если в строке должны быть служебные символы (т.е. запятая или \r \n) - строка обрамляется в кавычки, если внутри такой строки нужна кавычка - ставится две кавычки подряд.
На самом деле там немного сложнее, типа допустимо незначимые пробелы возле запятых, а значимыми их делают тоже через кавычки, управляющие символы <32 вроде тоже обязательно в кавычки, но это пофиг.
Вроде блин простая задачка, а каждый раз когда ее приходится делать - получаются на пару страниц конечные автоматы.

Comments

[kkirsanov.livejournal.com]

Доктор!
Экспортирую из 2007 экселя в CSV. Он, зараза, и кавычки не ставит и служебные символы не эскейпит. С горя в XML начал экспортировать, а он угловые скобки html срезает.

Есть там кнопка "сделать чтоб работало" ?

[metaclass.livejournal.com]

Странно. У меня 2003 счас аккуратно поставил кавычки.

[vp.livejournal.com]

Что-то ты усложняешь.
Есть делиметер, допустим, запятая.
Поиск делиметера, по позициям - нарезка строки в список строк.
все, строка распаршена. Дальше по каждой подстроке уже убирание кавычек краевых, если они присутствуют, ну и байт стаффинг кавычек. Хотя на самом деле меня плющит, что вот делиметер внутри никаким байстаффингом не кодируется. То есть его просто тупо не может быть. Надо документ почитать про CSV, я не помню, как там по науке. Также и не помню как с \r\n быть по науке.

[metaclass.livejournal.com]

У меня нет строки целиком. Есть входные символы, из потока. Т.е. обрабатывать нужно классическим конечным автоматом :)
Поиск делимитера по позициям ломается на делимитерах внутри кавычек.
И обрабатываю я не одну строку а все строки подряд, потому что у меня может быть такое:
"test
test"
и это должно вернуться в виде одной строки внутри списка, с \r\n внутри

[lionet.livejournal.com]

Зачем "нужно" классическим? Можно BNF-based парсером. yacc/lex, no?

[metaclass.livejournal.com]

Можно и им, но мне быстрее обычный конечный автомат было сделать на дотнете, чем искать кодогенератор и придумывать грамматику.

[arush-damage.livejournal.com]

нафига там автомат?
там кроме одного флага и значения предыдущего символа ничего не нужно

[metaclass.livejournal.com]

Вот я до проверки значения предыдущего символа не додумался - вместо этого использовал состояние конечного автомата.

[lionet.livejournal.com]

Предыдущий символ будет пробел. И что получится?

[metaclass.livejournal.com]

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

[arush-damage.livejournal.com]

Стандарт ломало читать :)
Обработка пробелов - вообще не проблема.

[arush-damage.livejournal.com]

А вот про конец строки я забыл :(

[metaclass.livejournal.com]

Вот про это я и говорю - сколько не делаю, обязательно что нибудь забуду :)

[arush-damage.livejournal.com]

Как-то так :

quoted=0;
prev_char=0;
start_field();
while(c=getch()) {
  if (quoted) {
    if ('"' == c)) quoted = 0; 
    else field_append_char(ch);
  } else {
    if ('"' == ch) {
      if ('"' == prev_char) {
        field_append_char(ch);
        quoted = 1;
      } else if (',' == prev_char) {
        quoted = 1;
      } else {
        report_error();
        return;
      }
    } else if (',' == ch) {
      end_field();
      start_field()
    } else {
      if ('"' == prev_char) {
        report_error();
        return;
      } else {
        field_append_char(ch);
      }
    }
  }
  prev_char = ch;
}
if (quoted) {
  report_error();
  return;
}
end_field()

[lionet.livejournal.com]

Как-то так (парсинг "строки" CSV в точном соответствии с RFC4180):

extract_line(Data) -> extract_line(Data, []).
extract_line(Data, Accum) ->
        case extract_value(Data) of
                {Value, Rest} -> extract_line(Rest, [r(Value)|Accum]);
                {Rest} -> {r(Accum), Rest};
                novalue when Accum =/= [] -> {r(Accum), []};
                novalue -> noline
        end.

extract_value([]) -> novalue;
extract_value([$\r,$\n|Rest]) -> {Rest};
extract_value([$\n|Rest]) -> {Rest};
extract_value([$"|Rest]) -> extract_quoted(Rest, []);
extract_value(Rest) -> extract_nonquoted(Rest, []).

extract_nonquoted([$\n|_]=Rest, V) -> {V, Rest};
extract_nonquoted([$\r,$\n|_]=Rest, V) -> {V, Rest};
extract_nonquoted([$,|Rest], V) -> {V, Rest};
extract_nonquoted([C|Rest], V) -> extract_nonquoted(Rest, [C|V]);
extract_nonquoted([], V) -> {V, []}.

extract_quoted([$",$,|Rest], V) -> {V, Rest};
extract_quoted([$",$\r,$\n|Rest], V) -> {V, [$\n|Rest]};
extract_quoted([$",$\n|Rest], V) -> {V, [$\n|Rest]};
extract_quoted([$",$"|Rest], V) -> extract_quoted(Rest, [$"|V]);
extract_quoted([$"], V) -> {V, []};
extract_quoted([$\r,$\n|Rest], V) -> extract_quoted(Rest, [$\n|V]);
extract_quoted([C|Rest], V) -> extract_quoted(Rest, [C|V]);
extract_quoted([], V) -> {V, []}.

[lionet.livejournal.com]

incidentally, это табличка состояний. По вертикали идут состояния, по горизонтали — входные символы, меняющие состояния. После стрелки, соответственно, связанные действия.

[metaclass.livejournal.com]

Да, паттерн-матчинг спасает очень сильно. У меня была мысль его имитировать, но я забил :)

[lionet.livejournal.com]

Да ладно, на GNU C почти то же самое можно забубенить, если игнорировать \r\n/\n проблему :)

enum {
    ST_NOCHANGE,  /* Pseudo-state */
    ST_PLAIN,
    ST_QUOTED_VALUE,
    _ST_MAX
} stateTable[_ST_MAX][256] = {
    [ST_PLAIN] = {
        [ '"' ] = ST_QUOTED_VALUE,
        ...
    },
    [ST_QUOTED_VALUE] = { ... }
};

[184467440737095.livejournal.com]

пусть A - терминалы, {'"'}, {','}, {'eol'} - подмножества A.
тогда для значения столбца и для текста целиком получаются следующие регулярные языки
V = (A\{',', 'eol', '"'})* + "(A\{'"'}+"")*"
S =((V,)*Veol)* = (V(, + eol))*

регулярный язык сводится к автомату. этот, если не ошибаюсь, к такому:

  A\{',', 'eol', '"'}   {'"'}   {'eol', ','}
1         1               2           1
2         2               3           2
3        err              2           1

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

[enternet.livejournal.com]

На заметку, про CSV и Excel.

Разделитель не всегда запятая. Иногда - точка с запятой. Зависит от настройки системы "разделитель элементов списка".

[metaclass.livejournal.com]

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

[zamotivator.livejournal.com]

Символ	Текущее состояник	Новое состояние	Генерируемое событие
"	Start	First-Quote	None
"	First-Quote	Double-Quoted	None
not "	First-Quote	Single-Quoted	None
"	Single-Quote	Start	Single-Quoted String
"	Double-Quoted	Double-Quoted-End	None
not "	Double-Quoted	Double-Quoted	None
"	Double-Quoted-End	Start	Double-Quoted String
,	Start	Start	Field complete
\n	Start	Start	String complete

[vp.livejournal.com]

Я вот хоть ты тресни, но не понимаю, какой жизненный паттерн может заставить парсить CSV конечным автоматом? Дайте мне ну хоть один пример :)

[zamotivator.livejournal.com]

Твои предложения - чем парсить?
Как только ты сталкиваешься с ситуацией "быстро парсить поток байт" что льётся без остановки, спасают только автоматы (и то лишь в случае регулярных грамматик).
В остальных случаях нужны уже синтаксические анализаторы.

Рукописный лесосипед может требоваться в силу специфичности требований - таких как окружающий шум.

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

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

Но кодировать вручную иногда проще, чем искать хуй-пойми что.

[vp.livejournal.com]

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

[zamotivator.livejournal.com]

Простой пример - очень длинные поля, буферизация которых не выгодна.
Тогда состояния позволяют обрабатывать блок, сразу его пересылать дальше или писать на диск, и лишь затем аккумулировать следующий блок.
Или вообще построить конвейер из параллельного чтения данных по сети, обработке данных (парсингу) и записи блоков на диск.
Так что всё не так просто.

[vp.livejournal.com]

очень длинные поля, буферизация которых не выгодна.

Я ВЕРЮ!!!!!
Я прошу живой пример из жизни конкретно под CSV, плиз! Я мозгом скриплю - банально не могу представить где такое может произойти. Ну можалуйсто! :)
Про бинарные и т.п. потоковые протоколы - без вопросов.

[zamotivator.livejournal.com]

Представь, что между двумя запятыми 10 мегабайт.
И это ещё нормально, у нас вон в csv гигабайтные блобы экспортили из SyBase =)

[vp.livejournal.com]

А, ну вот в общем то ясно теперь, спасибо :) Паттерн сформировался :)

[zamotivator.livejournal.com]

Ну, это лишь в твоём понимании "таблички из экселя", отдельные индивидумы таскают в нём гигабайты.
Кстати, это ничем и никем не запрещено - таскать толстые табличные данные в этом формате - универсально, просто, минимум накладных расходов (escaping запятой и перевода строки - мелочи).

[metaclass.livejournal.com]

Приход CSV в стопицот мб длиной из последовательного потока.

[metaclass.livejournal.com]

А чем его еще парсить? В SetDelimiterText у TStrings, кстати, тот же самый конечный автомат, поверх указателя на символ в строке.

[metaclass.livejournal.com]

\r еще не обрабатывается вроде - виндовые переносы строк будут частично на выход попадать.
и последнее поле в строке по моему, не обработается корректно.

[zamotivator.livejournal.com]

Гм. Ну суть ты понял, допилишь сам =)