Здравствуйте, fddima, Вы писали: S>>Тем более, что буферизация должна быть строго ортогональна алгоритму, собственно, разбора. Ещё не хватало свой BufferedStream каждый раз писать. F> Понятие Stream в описанном случае вообще бесполезно. Не нужно никакого BufferedStream. Я лишь предложил работать в таком простом случае как CSV непосредственно с буфером символов, и не нужно его абстрагировать до потока символов.
Не очень понимаю, почему и что бесполезно.
Есть два способа работать с CSV:
1. Хардкорный.
Читаем весь файл в память как можно более крупными кусками, затем бежим по нему, заменяя запятые и CR/LF на \0, и расставляя указатели по мере необходимости. Этим любят заниматься старообрядные С++ программисты. На вопросы с подковыркой, типа "а если файл в UTF-16", "а если файл 16гиг, а непрерывного адресного пространства есть только 120кб" и т.п. они шипят и плюются.
2. Архитектурный.
Строится всё на минимально необходимом количестве абстракций, которые укладываются нужным количеством слоёв. Очевидно, что для парсинга CSV достаточно источника, умеющего выдавать по одному символу за раз. Это TextReader. Всё. Парсеру CSV больше никто не нужен. Вопросы наличия или отсутствия буфера его не касаются. Эти вопросы будут касаться только того, кто даст Stream StreamReader-у, который будет использоваться парсером.
Вы какой из способов имеете в виду? Первый?
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[8]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, fddima, Вы писали:
VD>>Возвращать. Делается две функции Peek() и Read(). Первая возвращает сивол не меняя позиции (заглядывание вперед на единицу), вторая сдвигая позицию на единицу. Реализуется все очень просто: F> Это всё понятно. Далее то куда их девать?
Что значит куда девать? Их достаточно для реализации разбора на базе, например, конечного автомата.
VD>>XML ни чуть сложнее, а намного сложнее, так как грамматика у него не регулярная. Тут уже одним конечным автоматом не обойтись. По любому нужен стек, а лучше полноценный построитель парсеров. F> Не особо нужен.
Ну, спорить с теорией можно, но глупо .
F>>> Как насчёт замерить скорость стандартного дотнетовского XML парсера с твоим пеговым? VD>>Мне просто в лом тратить время на пенесометрию, но на результаты взглянул бы с удовольствием. Если займешься, я буду тебе очень благодарен. F> Мне тоже в лом, но интересно. Я не знаю что где и как с твоим парсером. Где можно посмотреть?
Мой парсер не был предназначен для пенисометрии. Он был разработан в рамках макроса предоставляющего XML-литералы в виде DSL для Nemerle (весь проект можно посмотреть здесь, там же есть и тесты демонстрирующие использование). Но из него не сложно будет выдрать грамматику, убрать расширения и сделать тестовый парсер.
VD>>>>Ну, практика показывает, что грамотно сгенерированный парсер может быть и быстрее рукописного. Вот товарищ пишет
, что его ПЕГоский парсер JSON-а в полтора раза быстрее аналогичного рукописного написанного по всем канонам. При этом он писал парсер всего 3 часа. F>>> Тоже самое относится к рукописным. О чём тут спорить? VD>>Что относится? Ты внимательно прочитал написанное мной? F> Внимательно. Говорю, что тоже можно сказать о рукописных парсерах: грамотно написанный и т.д. может быть и т.д. F> Что касается Json — думаю это всё же недостаток самого newton. И преимущество вашей реализации PEG, если всё так просто получается делать как ты говоришь.
Я смотрел newton — это добротный рукопашный парсер в котором все хорошо кроме того, что в нем местами используются абстракции которые с одной стороны необходимы чтобы не превратить код парсера в ужасное говнище, но с другой не могут не влиять (негативно) на производительность.
Преимущество генерированного кода в том, что он может плевать на абстрации и быть сколь угодно ужасен. Более того. Генерируемый код может быть одновременно и ужасен, и приличным (пригодным для отладки). Например, наш PegGrammar генерирует весьма читабельный код в дебаг-версии проекта, и высокооптимизированный в релизе. В релизе производится ряд хардкорных оптимизаций (генерация ДКА, переписывание правил и т.п.), а дебаге наоборот делаются преобразования направленные на упрощение генерируемого кода.
Как ты понимаешь, рукописный парсер себе такого позволить не может.
Ну, и совершенно очевидно, что генерированный код может плевать на абстракции просто потому, что исходным кодом для парсера является грамматика и обработчики, а не сам парсер, как в случае рукописного парсера.
Лично я никогда не написал бы такого кода который генерирует PegGrammar, так как его было бы невозможно поддерживать. Но поддержка макроса сводится к поддержке алгоритмов оптимизации и генерации кода. А поддержка конечного парсера в правке грамматики. Посему можно допускать чудовищный с точки зрения рукописного кода код, но при этом высокопроизводительный.
Один факт. В Nemerle нет оператора goto, но внутри макросов такой код все же сгенерировать можно. И PegGrammar этим во всю пользуется при генерации конечных автоматов в релиз-версии. Применение goto дало где-то 10% прироста производительности конечного парсера. Такое применение goto вполне оправданно. Но в рукописном коде я бы ни в жизнь не допустил бы использования goto.
Я конечно не утверждаю, что невозможно создать рукописный парсер которые был бы эффективнее генерированного. Это не так. Но при прочих равных — это не такая уж простая задача.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, Neco, Вы писали:
N>И проблема с тем, что в общем случае надо читать несколько символов наперёд
Строго говоря, НЕ НАДО. Перепишите алгоритм, он наверняка хромает. У меня реализован разбор на конечном автомате — ничего "предзаглядывать" не понадобилось.
Re: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, Neco, Вы писали:
N>Здравствуйте, matumba, Вы писали:
M>>Строго говоря, НЕ НАДО. Перепишите алгоритм, он наверняка хромает. У меня реализован разбор на конечном автомате — ничего "предзаглядывать" не понадобилось. N>А как? Хоть намекните... N>Я так понимаю, что можно добавить новые состояния, когда парсер "съел" половину переноса строки и ожидает вторую.
Зачем?
Состояний у парсера очень немного.
1. BeforeData
2. WithinData
3. WithinQuotedData
4. RightAfterTheQuote
Переводы строк лучше склеивать, т.к. некоторые источники ограничиваются CR без LF. А "пустых строк" в CSV не бывает, поэтому CR CR = CR LF = LF LF = CR LF CR LF = "один перевод строки".
Схема переходов примитивна:
Здравствуйте, Sinclair, Вы писали:
S>Ну ты же знаешь — я от переднего края отстал на годы. Для меня всё ещё написать свой парсер CSV с нуля, потом поматериться и отладить, потом поматериться и ускорить, потом поматериться и снова отладить — проще, чем даже взять готовый.
Да Вы батенька не отсталис! Вы батенька стареете похожес.
S>А уж тем более чем взять готовый генератор парсеров. S>Можешь, кстати, показать, как правильные пацаны сейчас пишут парсер CSV? (Предположим, что все готовые парсеры — заведомое УГ).
Да я тоже уже постарел. В показательных выступлениях не участвую. Как грится — дорогу молодежи!
Скажу только, что парсер CSV пишется с использованием того же PegGrammar-а где-то за час. Без опыта за 3.
В качестве примера могу показать свой парсер XML-я с брэкджеком и шлюхами (со сплайсами и встроенными операторами foreach, when и unless) — здесь. Он правда по сложнее раз эдак в несколько, но за счет декларативности код грамматики влезает на один экран (сравнимый рукописный парсер на шарпе потянет строк эдак на 1000).
. Он правда (по его же словам), с ним не за час справился, а за три, но то в основном потому, что опыта мало было. Зато обошелся без вопросов в форумах.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: Чтение файла: заглянуть на несколько символов вперёд
Да нет никакой проблемы, тем более — с CSV Переносов, кстати, тоже, в CSV строка файла == строка таблицы. Просто читаете целиком одну строку в свой буфер и ходите по нему сколько угодно. Но необходимости в таком хождении в общем случае тоже нет. Даже читая посимвольно из однонаправленного потока, складываете символы в буфер, пока не обнаружите конец лексемы, а потом уже смотрите, что за лексема. Для кавычек и т.п. просто заведите ещё одно состояние, да и всё.
"Нормальные герои всегда идут в обход!"
Re[2]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, Neco, Вы писали:
N>Писал csv парсер и столкнулся с проблемой, когда стандартных библиотечных функций как будто бы не хватает.
Конечно нехватает. Парсеры писать вручную работа неблагодарная совсем.
Почему бы не использовать готовые парсеры (я не верю что нет доступных csv-парсеров)? Или же не сгенерировать его тем же Coco/R-ом? Хотя я бы Nemerle.Peg задействовал
/* иЗвиНите зА неРовнЫй поЧерК */
Re[3]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, Neco, Вы писали:
H>>Или же не сгенерировать его тем же Coco/R-ом? Хотя я бы Nemerle.Peg задействовал N>Знал бы, я б попробовал, конечно. Но сдаётся мне, что это поможет только по части ускорения написания (что не есть проблема). Мне-то судя по-всему надо правильно выделить состояния конечного автомата. N>Плюс нехватка времени на изучение новых горизнтов даёт о себе знать.
Когда я набросал на скорую руку парсер джейсона на Peg, был удивлен не столько скоростью написания (благо я уже юзал другие генераторы парсеров и в скорости написания peg не несет особых преимуществ, кроме тесной интеграции с .net), сколько скоростью самого парсера, он оказался быстрее рукописного Newton.Json в полтора раза. А автор джейсона вобщем-то обращает внимание на вопросы производительности.
Нехватка времени довольно смешная причина делать задачу вручную не пользуясь инструментами для этого созданными.
Re[4]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, VladD2, Вы писали:
VD>Раньше принято было считать, что быстрее все будет при заглядывании вперед на 0-1 символ, а чем больше заглядывание, тем медленнее разбор (в плоть до экспоненты).
Тем более, что буферизация должна быть строго ортогональна алгоритму, собственно, разбора. Ещё не хватало свой BufferedStream каждый раз писать.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[6]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, hardcase, Вы писали:
H>>Есть мнение, что PEG уместен везде где уместны регулярные выражения.
VD>Ну, в данном случае мы имеем дело с исключением. Дело в том, что CSV-файлы могут быть и очень больших размеров. А у пега есть одна проблема. В общем случае он требует чтобы все данные были загружены в память. Наша реализация не исключение. CSV-же спокойно парсится с 0-1 заглядыванием вперед.
Это понятно, но я что-то не увидел где ТС говорит об ограничениях.
/* иЗвиНите зА неРовнЫй поЧерК */
Re[13]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, samius, Вы писали:
S>Таки можно, если нужно. Еще раз напомню, что я не предлагал что-либо менять в текущей реализации. Просто упомянул о том, что необходимость загрузки всех данных в память — это специфика реализации, а не PEG-а как такового.
Теоретически — да. На практике при этом придется забить на производительность.
S>Если честно, я даже не могу высосать из пальца задачу с претензией на реальность, где бы данные для разбора не могли бы поместиться в памяти. Тот же бесконечный CSV выглядит по меньшей мере глупо, притом что гарантий его разбора парсер на ленивых списках дает не сильно больше.
Придумать пример элементарно. Например, разбор лога веб-сервера ведущегося в текстовом формате.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Чтение файла: заглянуть на несколько символов вперёд
Писал csv парсер и столкнулся с проблемой, когда стандартных библиотечных функций как будто бы не хватает.
Дело в том, что CsvParser это автомат, который читает файл посимвольно и переходит из одного состояния в другое. И проблема с тем, что в общем случае надо читать несколько символов наперёд, чтобы решить, что надо переходить в другое состояние (из-за кавычек и переносов строки). С кавычками хватает Peek у стандартного StreamReader'а. А с переносом строки сложнее. Самое простое, что придумал, это создать свой Reader, который перед каждым чтением буфера бэкапирует предыдущее состояние. А потом по специальному методу CancelLastReading он восстанавливает его. Но решение довольно ресурсозатратное.
Кто как решает эту проблему (если сталкивались)?
Пасиб.
P.S. Вот этот класс. Решение абсолютно черновое. Писал, лишь бы юнит тесты прогонялись.
public class ExStreamReader : IDisposable {
private Stream _stream;
private Encoding _encoding;
private Decoder _decoder;
private char[] _buffer;
private int _bufferSize;
private int _bufferPosition;
private char[] _newLine;
private bool _endOfStream;
private long _lastBaseStreamPosition;
private int _lastBufferPosition;
private int _lastBufferSize;
private char[] _lastBuffer;
public ExStreamReader(Stream stream, Encoding enconding)
: this(stream, enconding, 1024) {
}
public ExStreamReader(Stream stream, Encoding enconding, int bufferSize) {
_stream = stream;
_endOfStream = _stream.Length == 0;
_encoding = enconding;
_decoder = _encoding.GetDecoder();
NewLineSymbol = "\n";
ByteBufferSize = bufferSize;
_buffer = new char[ByteBufferSize];
}
public bool EndOfStream {
get {
return (_stream.Position == _stream.Length) && (_bufferPosition == _bufferSize);
}
}
public int Read() {
char[] ch = new char[1];
int rez = Read(ch, 0, 1);
if (rez > 0) {
return ch[0];
} else {
return -1;
}
}
public string ReadString(int charsToRead) {
return new string(Read(charsToRead));
}
public char[] Read(int charsToRead) {
char[] ch = new char[charsToRead];
int rez = Read(ch, 0, charsToRead);
if (rez != charsToRead) {
char[] n_rez = new char[rez];
Array.Copy(ch, n_rez, rez);
return n_rez;
} else {
return ch;
}
}
public int Read(char[] buffer, int startIndex, int charsToRead) {
SaveInformationForCancelling();
int charsReaded = 0;
int destArrayStartIndex = startIndex;
while (charsReaded < charsToRead && !EndOfStream) {
if (_bufferPosition >= _bufferSize) {
ReadBuffer(_stream, _decoder, ref _buffer, ref _bufferPosition, ref _bufferSize, ref _endOfStream);
}
int rlCharsToRead = (charsToRead - charsReaded);
if (rlCharsToRead > _bufferSize - _bufferPosition) {
rlCharsToRead = _bufferSize - _bufferPosition;
}
Array.Copy(_buffer, _bufferPosition, buffer, destArrayStartIndex, rlCharsToRead);
charsReaded += rlCharsToRead;
destArrayStartIndex += rlCharsToRead;
_bufferPosition += rlCharsToRead;
}
return charsReaded;
}
private void SaveInformationForCancelling() {
_lastBaseStreamPosition = _stream.Position;
_lastBufferPosition = _bufferPosition;
if (_lastBuffer == null || _lastBuffer.Length != _buffer.Length) {
_lastBuffer = new char[_buffer.Length];
}
_buffer.CopyTo(_lastBuffer, 0);
_lastBufferSize = _bufferSize;
}
public void CancelLastReading() {
_stream.Position = _lastBaseStreamPosition;
_bufferPosition = _lastBufferPosition;
_bufferSize = _lastBufferSize;
_buffer = new char[ByteBufferSize];
if (_lastBuffer != null) {
_lastBuffer.CopyTo(_buffer, 0);
}
}
private void ReadBufferTailed(Stream stream, Decoder decoder, int tailStart, int tailSize, ref char[] buffer, ref int bufferPosition, ref int bufferSize, ref bool endOfStream) {
var tail = new char[tailSize];
Array.Copy(buffer, bufferPosition, tail, 0, tailSize);
Array.Copy(tail, 0, buffer, 0, tailSize);
ReadBuffer(stream, decoder, ref buffer, ref bufferPosition, ref bufferSize, tailSize, ByteBufferSize - tailSize, ref endOfStream);
bufferPosition = 0;
bufferSize = bufferSize + tailSize;
}
private void ReadBuffer(Stream stream, Decoder decoder, ref char[] buffer, ref int bufferPosition, ref int bufferSize, ref bool endOfStream) {
ReadBuffer(stream, decoder, ref buffer, ref bufferPosition, ref bufferSize, 0, ByteBufferSize / 2, ref endOfStream);
}
private static void ReadBuffer(Stream stream, Decoder decoder, ref char[] buffer, ref int bufferPosition, ref int bufferSize, int startWritingFrom, int bytesToRead, ref bool endOfStream) {
var b_buffer = new byte[bytesToRead];
var cnt_read = stream.Read(b_buffer, 0, bytesToRead);
if (cnt_read == 0) {
bufferPosition = 0;
bufferSize = 0;
endOfStream = true;
} else {
bufferPosition = startWritingFrom;
var chars_read = decoder.GetChars(b_buffer, 0, cnt_read, buffer, startWritingFrom);
bufferSize = chars_read;
}
}
private int _byteBufferSize;
public int ByteBufferSize {
get { return _byteBufferSize; }
private set {
if (value < 6) {
throw new ArgumentException("You cannot set buffer size shorter than maximum symbol size (6 bytes)");
}
_byteBufferSize = value;
}
}
public string NewLineSymbol {
get {
return new string(_newLine);
}
set {
_newLine = value.ToCharArray();
}
}
public long Position {
get {
return _stream.Position - _bufferSize + _bufferPosition;
}
}
public void Dispose() {
}
}
всю ночь не ем, весь день не сплю — устаю
Re[2]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, matumba, Вы писали:
M>Строго говоря, НЕ НАДО. Перепишите алгоритм, он наверняка хромает. У меня реализован разбор на конечном автомате — ничего "предзаглядывать" не понадобилось.
А как? Хоть намекните...
Я так понимаю, что можно добавить новые состояния, когда парсер "съел" половину переноса строки и ожидает вторую. Но при этом надо запоминать уже съеденную часть, чтобы в случае, если перенос строки не состоялся поменять поведение — в общем какой-то головняк.
Вот мой алгоритм:
private string[] ReadCsvLine() {
var rez = new List<string>();
var state = ReadingState.ExpectDataStart;
bool end_of_line = false;
char[] extra_data = null;
StringBuilder current_data = null;
do {
if (_reader.EndOfStream) {
switch (state) {
case ReadingState.Data:
case ReadingState.ExpectDataStart: {
AddValue(rez, current_data);
break;
}
case ReadingState.QuotedData: {
throw new CsvParserException("Unexpected end of line!");
}
case ReadingState.ExpectSeparator: {
// do nothingbreak;
}
default: {
throw new CsvParserException(string.Format("Unknown state [{0}]", state));
}
}
end_of_line = true;
break;
}
char cur = (char)_reader.Read();
switch (state) {
case ReadingState.ExpectDataStart: {
if (cur == '"') {
current_data = new StringBuilder();
state = ReadingState.QuotedData;
} else if (cur == ',') {
AddValue(rez, current_data);
} else if (IsNewLine(cur, _reader)) {
AddValue(rez, current_data);
state = ReadingState.NoRead;
end_of_line = true;
} else {
current_data = new StringBuilder();
current_data.Append(cur);
state = ReadingState.Data;
}
break;
}
case ReadingState.Data: {
if (cur == '"') {
throw new CsvParserException(string.Format("Unexpected quota inside data! Position: [{0}]", _reader.Position));
} else if (cur == ',') {
AddValue(rez, current_data);
current_data = null;
state = ReadingState.ExpectDataStart;
} else if (IsNewLine(cur, _reader)) {
AddValue(rez, current_data);
current_data = null;
state = ReadingState.NoRead;
end_of_line = true;
} else {
current_data.Append(cur);
if (extra_data != null) {
current_data.Append(extra_data);
}
}
break;
}
case ReadingState.QuotedData: {
if (cur == '"') {
if (NextSymbolIsQuota(_reader)) {
current_data.Append(cur);
_reader.Read();
} else {
AddValue(rez, current_data);
current_data = null;
state = ReadingState.ExpectSeparator;
}
} else {
current_data.Append(cur);
}
break;
}
case ReadingState.ExpectSeparator: {
if (cur == ',') {
current_data = null;
state = ReadingState.ExpectDataStart;
} else if (IsNewLine(cur, _reader)) {
state = ReadingState.NoRead;
end_of_line = true;
} else {
throw new CsvParserException(string.Format("Expected separator! Position: [{0}]", _reader.Position));
}
break;
}
default: {
throw new CsvParserException(string.Format("Unknown state [{0}]", state));
}
}
} while (!end_of_line);
return rez.ToArray();
}
private void AddValue(List<string> data, StringBuilder sb) {
if (sb != null) {
data.Add(sb.ToString());
} else {
data.Add(null);
}
}
private bool NextSymbolIsQuota(ExStreamReader reader) {
if (reader.EndOfStream) {
return false;
} else {
char nc = (char)reader.Read();
reader.CancelLastReading();
return nc == '"';
}
}
private bool IsNewLine(char ch, ExStreamReader reader) {
if (ch == _newLine[0]) {
bool is_new_line = true;
var buf = new char[_newLine.Length - 1];
int bytes_read = reader.Read(buf, 0, buf.Length);
for (int i = 0; i < bytes_read; i++) {
char val_from_buf = buf[i];
char val_from_nl = _newLine[i + 1];
if (val_from_buf != val_from_nl) {
is_new_line = false;
break;
}
}
if (is_new_line) {
return true;
} else {
reader.CancelLastReading();
return false;
}
} else {
return false;
}
}
private enum ReadingState {
ExpectDataStart = 0, Data, QuotedData, ExpectSeparator, NoRead /* expected that reading will not be performed in this state */
}
строго говоря он даже не совсем мой. я его слизал откуда-то и доработал на предмет распознавания разных переносов строк и ещё какой-то мульки (уже не помню).
всю ночь не ем, весь день не сплю — устаю
Re[2]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, Jolly Roger, Вы писали:
JR> Даже читая посимвольно из однонаправленного потока, складываете символы в буфер, пока не обнаружите конец лексемы, а потом уже смотрите, что за лексема.
А кстати, может в этом и соль. Я ориентируюсь на начало лексемы, а возможно надо на конец. Надо обмозговать, когда время будет.
всю ночь не ем, весь день не сплю — устаю
Re[2]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, hardcase, Вы писали:
H>Конечно нехватает. Парсеры писать вручную работа неблагодарная совсем. H>Почему бы не использовать готовые парсеры (я не верю что нет доступных csv-парсеров)?
Всё начиналось с быстрого решения на MSJET. Потом оно оказалось неспособным что-то читать и пришлось уже думать над чем-то своим.
H>Или же не сгенерировать его тем же Coco/R-ом? Хотя я бы Nemerle.Peg задействовал
Знал бы, я б попробовал, конечно. Но сдаётся мне, что это поможет только по части ускорения написания (что не есть проблема). Мне-то судя по-всему надо правильно выделить состояния конечного автомата.
Плюс нехватка времени на изучение новых горизнтов даёт о себе знать.
В общем, сменил подглючноватый ExStreamReader на другую версию (сменив подход — теперь просто буферизую заранее прочитанные символы):
public class ExStreamReader : IDisposable {
private StreamReader _reader;
private InternalBuffer _buffer;
public ExStreamReader(Stream stream, Encoding enconding) {
_reader = new StreamReader(stream, enconding);
_buffer = new InternalBuffer(_reader);
}
public char Read() {
if (_buffer.IsEmpty) {
return (char)_reader.Read();
} else {
return _buffer.Read();
}
}
public int PreRead(ref char[] buffer, int index, int count) {
return _buffer.PreRead(ref buffer, index, count);
}
public void ConfirmPreRead() {
_buffer.Clear();
}
public bool EndOfStream {
get {
return _reader.EndOfStream;
}
}
public long Position {
get { return _reader.BaseStream.Position; }
}
public void Dispose() {
_reader.Dispose();
}
private class InternalBuffer {
private StreamReader _rdr;
private Queue<char> _buf = new Queue<char>();
public InternalBuffer(StreamReader rdr) {
_rdr = rdr;
}
public int PreRead(ref char[] buffer, int index, int count) {
int bytes = _rdr.Read(buffer, index, count);
for (int i = index; i < count + index; i++) {
_buf.Enqueue(buffer[i]);
}
return bytes;
}
public char Read() {
if (IsEmpty) {
throw new InvalidOperationException("You cannot read from InternalBuffer when it is empty");
}
return _buf.Dequeue();
}
public bool IsEmpty {
get {
return _buf.Count == 0;
}
}
public void Clear() {
_buf.Clear();
}
}
}
а сам парсер остался практически без изменений. Вроде работает и по скорости будет гораздо лучше, хотя исходный вопрос остаётся открытый.
всю ночь не ем, весь день не сплю — устаю
Re[4]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, Ziaw, Вы писали:
Z>Нехватка времени довольно смешная причина делать задачу вручную не пользуясь инструментами для этого созданными.
Ага. Я бы даже сказал — парадоксальная. Просто (видимо) народ настолько привык к тому, что внешние "тулы" очень трудно сконфигурированный и прикрутить к процессу сборки, что и отношение соответствующие.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[5]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, VladD2, Вы писали:
VD>А зачем такие задачи вообще вручную решать? Я вижу только одну причину — изучение ОК.
Ну ты же знаешь — я от переднего края отстал на годы. Для меня всё ещё написать свой парсер CSV с нуля, потом поматериться и отладить, потом поматериться и ускорить, потом поматериться и снова отладить — проще, чем даже взять готовый.
А уж тем более чем взять готовый генератор парсеров.
Можешь, кстати, показать, как правильные пацаны сейчас пишут парсер CSV? (Предположим, что все готовые парсеры — заведомое УГ).
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re: Чтение файла: заглянуть на несколько символов вперёд
Если хочется иметь look-a-head, тем более для такого простого парсера — избавляемся от посимвольных чтений вообще, работаем только с буфером. Это не сложно, и на порядок быстрее.
Re[2]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, fddima, Вы писали:
F>Если хочется иметь look-a-head, тем более для такого простого парсера — избавляемся от посимвольных чтений вообще, работаем только с буфером. Это не сложно, и на порядок быстрее.
Я пропустил что-то новое в теории парсеров?
Раньше принято было считать, что быстрее все будет при заглядывании вперед на 0-1 символ, а чем больше заглядывание, тем медленнее разбор (в плоть до экспоненты).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, Neco, Вы писали:
M>>Строго говоря, НЕ НАДО. Перепишите алгоритм, он наверняка хромает. У меня реализован разбор на конечном автомате — ничего "предзаглядывать" не понадобилось. N>А как? Хоть намекните... N>Я так понимаю, что можно добавить новые состояния, когда парсер "съел" половину переноса строки и ожидает вторую. Но при этом надо запоминать уже съеденную часть....
Ты сам себе намекнул.
Весь автомат укладывается в 3 состояния с сохранением промежуточного буфера:
0: читаем и запоминаем поля (обрабатывая запятую), пока не попадём на кавычки. Кавычки -> 1
1: Мы внутри строки — запоминаем символы или ждём очередную кавычку. Кавычки -> 2
2: Здесь ждём либо кавычки, либо запятую, обрабатываем соответственно (т.к. кавычки могут быть удвоенными внутри строки и просто окончание строки).
В конце проверяем состояние, если 1 — это ошибка. Не забываем про аккумулятор.
Для большей наглядности нарисуй этот автомат — что и в каком состоянии может быть — он не тривиален, но без трюков.
Re[3]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, VladD2, Вы писали:
VD>Я пропустил что-то новое в теории парсеров? VD>Раньше принято было считать, что быстрее все будет при заглядывании вперед на 0-1 символ, а чем больше заглядывание, тем медленнее разбор (в плоть до экспоненты).
Ну больше 0-1 и в крайних случаях 2-х символов и не нужно. Здесь csv-"парсер" больше похож на сканер, и здесь выгодно вычитать за раз как можно больше. Скорее всего чтение значения будет в 90% попадать в буфер, и считываться будет одним while(isValidChar(buf[pos]))pos++; После чего часть массива char — готовое значение, которое нигде не нужно "накапливать", как это произойдёт с посимвольным stream. А для XML-я именно тут происходит атомизация имён, не допуская создания лишних объектов строк, и это весьма актуально.
Я не знаю как там в теории — есть практика, и эта практика, насколько мне известно работает быстрее всех.
Сложные парсеры — это удел PEG/etc — где умом парсер объять сложно, а скоростью сканирования текста можно пренебречь.
Re[4]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, Sinclair, Вы писали:
VD>>Раньше принято было считать, что быстрее все будет при заглядывании вперед на 0-1 символ, а чем больше заглядывание, тем медленнее разбор (в плоть до экспоненты). S>Тем более, что буферизация должна быть строго ортогональна алгоритму, собственно, разбора. Ещё не хватало свой BufferedStream каждый раз писать.
Понятие Stream в описанном случае вообще бесполезно. Не нужно никакого BufferedStream. Я лишь предложил работать в таком простом случае как CSV непосредственно с буфером символов, и не нужно его абстрагировать до потока символов.
Re[4]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, fddima, Вы писали:
F> Сложные парсеры — это удел PEG/etc — где умом парсер объять сложно, а скоростью сканирования текста можно пренебречь.
Есть мнение, что PEG уместен везде где уместны регулярные выражения.
/* иЗвиНите зА неРовнЫй поЧерК */
Re[6]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, Sinclair, Вы писали:
S>Вы какой из способов имеете в виду? Первый?
Ты, лучше на ты.
Между 1 и 2 затрудняюсь выбрать. Имеем TextReader, читаем буфер, всё дальнейшее общение происходит с буфером.
Re[5]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, hardcase, Вы писали:
H>Есть мнение, что PEG уместен везде где уместны регулярные выражения.
Ну есть такое же мнение что пихать его всюду — не лучшая идея. Хотя ничего против PEG конечно не имею.
Re[4]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, fddima, Вы писали:
F>Ну больше 0-1 и в крайних случаях 2-х символов и не нужно.
Дык, а 1 символ легко кэшируется в отдельном поле.
F>Здесь csv-"парсер" больше похож на сканер,
Не похож, а он и есть. Регулярная грамматиках. Можно хоть регулярными выражениями парсить.
F>и здесь выгодно вычитать за раз как можно больше.
Особой выгоды нет. Стандартные стримы и так кэшировать чтение умеют.
F>Я не знаю как там в теории — есть практика, и эта практика, насколько мне известно работает быстрее всех.
В теории теория и практика одинаковы. На практике — нет. (с)
Но это не тот случай.
F> Сложные парсеры — это удел PEG/etc — где умом парсер объять сложно, а скоростью сканирования текста можно пренебречь.
Ну, практика показывает, что грамотно сгенерированный парсер может быть и быстрее рукописного. Вот товарищ пишет
Здравствуйте, VladD2, Вы писали:
F>>Ну больше 0-1 и в крайних случаях 2-х символов и не нужно. VD>Дык, а 1 символ легко кэшируется в отдельном поле.
Куда их потом девать эти символы?
F>>Здесь csv-"парсер" больше похож на сканер, VD>Не похож, а он и есть. Регулярная грамматиках. Можно хоть регулярными выражениями парсить.
Чуть сложнее — XML — и он уже будет парсером, похожим на сканер, как ни крути.
F>>и здесь выгодно вычитать за раз как можно больше.
VD>В теории теория и практика одинаковы. На практике — нет. (с) VD>Но это не тот случай.
Как насчёт замерить скорость стандартного дотнетовского XML парсера с твоим пеговым?
VD>Ну, практика показывает, что грамотно сгенерированный парсер может быть и быстрее рукописного. Вот товарищ пишет
, что его ПЕГоский парсер JSON-а в полтора раза быстрее аналогичного рукописного написанного по всем канонам. При этом он писал парсер всего 3 часа.
Тоже самое относится к рукописным. О чём тут спорить?
Re[5]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, hardcase, Вы писали:
H>Есть мнение, что PEG уместен везде где уместны регулярные выражения.
Ну, в данном случае мы имеем дело с исключением. Дело в том, что CSV-файлы могут быть и очень больших размеров. А у пега есть одна проблема. В общем случае он требует чтобы все данные были загружены в память. Наша реализация не исключение. CSV-же спокойно парсится с 0-1 заглядыванием вперед.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[6]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, fddima, Вы писали:
VD>>В теории теория и практика одинаковы. На практике — нет. (с) VD>>Но это не тот случай. F> Как насчёт замерить скорость стандартного дотнетовского XML парсера с твоим пеговым?
Они в сущности разные задачи решают (один для разбора XML документов, другой — для поддержки XML литералов в одном дотнетном языке), но на сравнение производительности и я бы посмотрел.
/* иЗвиНите зА неРовнЫй поЧерК */
Re[6]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, fddima, Вы писали:
VD>>Дык, а 1 символ легко кэшируется в отдельном поле. F> Куда их потом девать эти символы?
Возвращать. Делается две функции Peek() и Read(). Первая возвращает сивол не меняя позиции (заглядывание вперед на единицу), вторая сдвигая позицию на единицу. Реализуется все очень просто:
class LookaheadStream
{
...
char _lookahead;
public char Peek()
{
return _lookahead;
}
public char Read()
{
var current = _lookahead;
_lookahead = (char)_baseStream.Read();
return current;
}
}
F>>>Здесь csv-"парсер" больше похож на сканер, VD>>Не похож, а он и есть. Регулярная грамматиках. Можно хоть регулярными выражениями парсить. F> Чуть сложнее — XML — и он уже будет парсером, похожим на сканер, как ни крути.
XML ни чуть сложнее, а намного сложнее, так как грамматика у него не регулярная. Тут уже одним конечным автоматом не обойтись. По любому нужен стек, а лучше полноценный построитель парсеров.
VD>>В теории теория и практика одинаковы. На практике — нет. (с) VD>>Но это не тот случай. F> Как насчёт замерить скорость стандартного дотнетовского XML парсера с твоим пеговым?
Мне просто в лом тратить время на пенесометрию, но на результаты взглянул бы с удовольствием. Если займешься, я буду тебе очень благодарен.
VD>>Ну, практика показывает, что грамотно сгенерированный парсер может быть и быстрее рукописного. Вот товарищ пишет
, что его ПЕГоский парсер JSON-а в полтора раза быстрее аналогичного рукописного написанного по всем канонам. При этом он писал парсер всего 3 часа. F> Тоже самое относится к рукописным. О чём тут спорить?
Что относится? Ты внимательно прочитал написанное мной?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[7]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, hardcase, Вы писали:
H>Это понятно, но я что-то не увидел где ТС говорит об ограничениях.
Ага. Скажу больше. Дотнетный Regex так вообще кроме строки ничего не понимает, если я не ошибаюсь. Так что в рамках стандартной реализации регекспов твое утверждение вообще верно на 100%.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[6]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, hardcase, Вы писали:
H>>Есть мнение, что PEG уместен везде где уместны регулярные выражения.
VD>Ну, в данном случае мы имеем дело с исключением. Дело в том, что CSV-файлы могут быть и очень больших размеров. А у пега есть одна проблема. В общем случае он требует чтобы все данные были загружены в память. Наша реализация не исключение. CSV-же спокойно парсится с 0-1 заглядыванием вперед.
В общем случае ПЕГ-у достаточно ленивого списка символов, который легко посадить на поток данных. Лишь в худшем случае размер данных, необходимых парсеру, будет равен длине потока.
А вот его частные реализации как правило используют сразу все данные.
Re[7]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, VladD2, Вы писали:
VD>Возвращать. Делается две функции Peek() и Read(). Первая возвращает сивол не меняя позиции (заглядывание вперед на единицу), вторая сдвигая позицию на единицу. Реализуется все очень просто:
Это всё понятно. Далее то куда их девать?
VD>XML ни чуть сложнее, а намного сложнее, так как грамматика у него не регулярная. Тут уже одним конечным автоматом не обойтись. По любому нужен стек, а лучше полноценный построитель парсеров.
Не особо нужен.
F>> Как насчёт замерить скорость стандартного дотнетовского XML парсера с твоим пеговым? VD>Мне просто в лом тратить время на пенесометрию, но на результаты взглянул бы с удовольствием. Если займешься, я буду тебе очень благодарен.
Мне тоже в лом, но интересно. Я не знаю что где и как с твоим парсером. Где можно посмотреть?
VD>>>Ну, практика показывает, что грамотно сгенерированный парсер может быть и быстрее рукописного. Вот товарищ пишет
, что его ПЕГоский парсер JSON-а в полтора раза быстрее аналогичного рукописного написанного по всем канонам. При этом он писал парсер всего 3 часа. F>> Тоже самое относится к рукописным. О чём тут спорить? VD>Что относится? Ты внимательно прочитал написанное мной?
Внимательно. Говорю, что тоже можно сказать о рукописных парсерах: грамотно написанный и т.д. может быть и т.д.
Что касается Json — думаю это всё же недостаток самого newton. И преимущество вашей реализации PEG, если всё так просто получается делать как ты говоришь.
Re[4]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, Neco, Вы писали: S>Схема переходов примитивна:
ок, в таком случае (поскольку состояния такие же как у меня фактически) меня интересует механика.
вот здесь, например: S>
S>1. BeforeData:
S>CR, LF:; // nothing
S>
как вы определите пару символов "CR, LF" без упреждающего чтения? Правильно же я понимаю, что весь этот switch у вас происходит в цикле с посимвольным чтением?
А вот за состояние RightAfterTheQuote большое спасибо — его мне и не хватало.
всю ночь не ем, весь день не сплю — устаю
Re[7]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, fddima, Вы писали:
S>>Вы какой из способов имеете в виду? Первый? F> Ты, лучше на ты. F> Между 1 и 2 затрудняюсь выбрать. Имеем TextReader, читаем буфер, всё дальнейшее общение происходит с буфером.
Не очень понимаю, зачем это делать. Таким образом, мы всего лишь прокладываем между TextReader и CSVParser ещё одну абстракцию — некий буфер. Причём нужно ещё подгадывать с размером этого буфера, и склеивать элементы, попавшие на границу буферов. Имхо, овчинка выделки тово. Производительность тоже особо вряд ли изменится — StringBuilder внутри устроен и так достаточно хорошо. Я в том смысле, что достичь скорострельности C++-ного варианта с нулём копирований всё равно не удастся.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[5]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, Neco, Вы писали:
N>ок, в таком случае (поскольку состояния такие же как у меня фактически) меня интересует механика. N>вот здесь, например: S>>
S>>1. BeforeData:
S>>CR, LF:; // nothing
S>>
N>как вы определите пару символов "CR, LF" без упреждающего чтения? Правильно же я понимаю, что весь этот switch у вас происходит в цикле с посимвольным чтением?
Я имел в виду не пару, а любой из этих символов. Я же написал — в целях упрощения мы делаем два предположения:
1. Нам достаточно любого из символов для перевода строки.
2. Два (и более) любых перевода строки эквивалентны одному.
Для большинства практических случаев это приемлемо, т.к. мало кого интересуют строчки с нулём колонок. N>А вот за состояние RightAfterTheQuote большое спасибо — его мне и не хватало.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[8]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, Sinclair, Вы писали:
F>> Между 1 и 2 затрудняюсь выбрать. Имеем TextReader, читаем буфер, всё дальнейшее общение происходит с буфером. S>Не очень понимаю, зачем это делать. Таким образом, мы всего лишь прокладываем между TextReader и CSVParser ещё одну абстракцию — некий буфер. Причём нужно ещё подгадывать с размером этого буфера, и склеивать элементы, попавшие на границу буферов.
Этим мы избавляемся от необходимости использовать StringBuilder вообще (в большинстве случаев по крайней мере).
+ Это даёт возможность заглядывать вперёд. Подгадывать с размером буфера не надо — он должен уметь расширяться.
S> Имхо, овчинка выделки тово. Производительность тоже особо вряд ли изменится — StringBuilder внутри устроен и так достаточно хорошо. Я в том смысле, что достичь скорострельности C++-ного варианта с нулём копирований всё равно не удастся.
Тут помогут только замеры. По моим личным изыскам — овчинка того стоит. C++ скорострельности может и не достичь, но будет всё равно на высоте.
Я думаю мы врядли будем писать тесты, есть ведь более интересные задачи?
Re[6]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, Sinclair, Вы писали:
N>>как вы определите пару символов "CR, LF" без упреждающего чтения? Правильно же я понимаю, что весь этот switch у вас происходит в цикле с посимвольным чтением? S>Я имел в виду не пару, а любой из этих символов. Я же написал — в целях упрощения мы делаем два предположения: S>1. Нам достаточно любого из символов для перевода строки. S>2. Два (и более) любых перевода строки эквивалентны одному.
ааа, понятно — первый переводит строку, второй просто игнорится.
всю ночь не ем, весь день не сплю — устаю
Re[7]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, samius, Вы писали:
S>В общем случае ПЕГ-у достаточно ленивого списка символов, который легко посадить на поток данных. Лишь в худшем случае размер данных, необходимых парсеру, будет равен длине потока.
Вот только не надо мне рассказывать о том в чем я разобрался .
ПЕГ в общем-случае обеспечивает неограниченное заглядывание вперед с помощью предикатов и откат вплоть до начала разбираемого "файла". На практике, конечно заглядывание и откат редко бывает очень глубоким. Но на то он и общий случай, чтобы нельзя было делать предположений.
Потом алгоритмы лежащие под ПЕГом оперируют с позицией в тексте. Это куда эффективнее чем возня с абстракциями (не нужным в данном случае раз все равно работа идет с индексами).
S>А вот его частные реализации как правило используют сразу все данные.
Они потому и используют, что базовая концепция подталкивает. Попытка работать не индексируемым представлением, а с некоторой абстракцией списка (с последовательным чтением) резко усложнит реализацию парсера и мало что даст взамен (ведь возможность откатиться в начало разбираемого текста есть всегда). По сути любой неудачный разбор приводит к полному откату парсера (если нет дополнительных средств останова отката).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[8]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, samius, Вы писали:
S>>В общем случае ПЕГ-у достаточно ленивого списка символов, который легко посадить на поток данных. Лишь в худшем случае размер данных, необходимых парсеру, будет равен длине потока.
VD>Вот только не надо мне рассказывать о том в чем я разобрался .
Зато я не разобрался. Но я разбирался с парсер-комбинаторами, и не вижу здесь препятствий для работы с ленивой структурой данных, кроме разве что эффективности.
VD>ПЕГ в общем-случае обеспечивает неограниченное заглядывание вперед с помощью предикатов и откат вплоть до начала разбираемого "файла". На практике, конечно заглядывание и откат редко бывает очень глубоким. Но на то он и общий случай, чтобы нельзя было делать предположений.
нет возражений
VD>Потом алгоритмы лежащие под ПЕГом оперируют с позицией в тексте. Это куда эффективнее чем возня с абстракциями (не нужным в данном случае раз все равно работа идет с индексами).
да, эффективнее.
VD>Они потому и используют, что базовая концепция подталкивает. Попытка работать не индексируемым представлением, а с некоторой абстракцией списка (с последовательным чтением) резко усложнит реализацию парсера и мало что даст взамен (ведь возможность откатиться в начало разбираемого текста есть всегда). По сути любой неудачный разбор приводит к полному откату парсера (если нет дополнительных средств останова отката).
Позиция в буфере и есть та самая абстракция. Просто в каких-то реализациях она выражена как индекс, в других как char*, в третьих — узел ленивого списка.
Если PEG-у не требуется random-access к разбираемой строке, то он так же как и парсер-комбинатор сможет работать с другой абстракцией без увеличения алгоритмической сложности. То что вырастет кол-во тактов — не спорю. И даже с тем что это нафиг не надо — тоже не спорю.
Я докопался лишь с мыслью, что требование загрузки всех данных — лишь специфика реализации/большинства реализаций/быстрых реализаций, а не PEG-а как такового.
Впрочем, допускаю, что и ошибаюсь. Т.к. с PEG не знаком даже поверхностно.
Re[9]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, samius, Вы писали:
S>Зато я не разобрался. Но я разбирался с парсер-комбинаторами, и не вижу здесь препятствий для работы с ленивой структурой данных, кроме разве что эффективности.
С ленивыми структурами данных всегда так. Всем они хороши кроме медлительности и непредсказуемости .
Как я уже говорил проблема в откатах и заглядывании. Для эффективной самый лучший способ — это работа с индексами и соответственно массивами (строка в дотнете тоже массив своего рода). При этом откаты на начало текста стоят точно столько же сколько на пару символов.
Вообще было бы интересно посоревноваться с комбинаторными парсерами в скорости. Теоретически, на реальных задачах, мы (PegGrammar) должны порвать их как Тузик грелку. Но теория, есть теория. А хорошо бы это удивить на практике.
VD>>Они потому и используют, что базовая концепция подталкивает. Попытка работать не индексируемым представлением, а с некоторой абстракцией списка (с последовательным чтением) резко усложнит реализацию парсера и мало что даст взамен (ведь возможность откатиться в начало разбираемого текста есть всегда). По сути любой неудачный разбор приводит к полному откату парсера (если нет дополнительных средств останова отката). S>Позиция в буфере и есть та самая абстракция. Просто в каких-то реализациях она выражена как индекс, в других как char*, в третьих — узел ленивого списка.
Индекс и указатель (в сишном его понимании) эквивалентны. А вот "узел ленивого списка" — это извините лажа... с точки зрения скорости. Ведь эти узлы придется лепить на каждый символ. Даже при дико-эффективном GC эта операция очень дорогая. А в дотнете GC не так эффективен, так как рассчитан на императивные языки и на много поточный доступ (да и вообще далек от идела). Так что я не поставил бы на такую реализацию и трех рублей.
S>Если PEG-у не требуется random-access к разбираемой строке, то он так же как и парсер-комбинатор сможет работать с другой абстракцией без увеличения алгоритмической сложности.
На самом деле PEG — это не алгоритм, а нотация. Так что в принципе его можно разбирать и на основе парсер-комбинаторов с ленивыми списками под копотом. Просто когда код генерируется, то столь не эффективные реализации откидываются сами собой. Это на хаскеле другие пути слишком сложны, вот и лепят все в виде комбинаторов. Плюс хаскель все же не хилые оптимизации обеспечивает. А в дотнете их нет и появятся ли они ил нет неизвестно. Рассчитывать на них просто не серьезно. Зато мы можем использовать "грязную силу". Абстракция у нас обеспечивается декларативной грамматикой (которая хаскелям разным 100 очков форы даст) и генератором кода. Вот и падет выбор на массивы (строки), индексы и разные goto.
S>То что вырастет кол-во тактов — не спорю. И даже с тем что это нафиг не надо — тоже не спорю. S>Я докопался лишь с мыслью, что требование загрузки всех данных — лишь специфика реализации/большинства реализаций/быстрых реализаций, а не PEG-а как такового.
Ну, в общем — да. Конечно если представлять вычисления и данные в виде ленивых списков, то можно обойтись без массивов и индексов. Но такая реализация уже будет сильно уступать ручной реализации на основе конечных автоматов. Так что никакого выигрыша (кроме декларативности) от использования PEG-а не будет.
S>Впрочем, допускаю, что и ошибаюсь. Т.к. с PEG не знаком даже поверхностно.
PEG — это не более чем красивая нотация для описания рекурсивных парсеров с откатами. Так что если ты знаком с комбинаторными парсерами, то свитай, что знаком и с базовыми алгоритмами реализации PEG-а. А сама грамматика PEG-а очень похожа на скрещивание ужа с ежом, т.е. на скрещивание регулярных выражений и BNF. Основных новшеств два:
1. Оператор приоритетный выбора "/" вместо перечисления "|". Он как бы говорил, что если у нас есть правило А и Б перечисленные через этот оператор — "А / Б", то будет по очереди произведена попытка сопоставить оба этих правила. Причем если правило А сопоставится, то попытка сопоставлять Б даже не будет предприниматься. И соответственно, если попытка разобрать входную стоку по правилу А обломается, то будет предпринята попытка разобрать правило Б. Соответственно, если попытка будет успешным, то ОК, иначе разбор всего общего правила будет читаться проваленным.
2. Есть операторы предикатов "&" и "!". Они позволяют проверить сопоставиться ли в текущей позиции текст с правилом идущим за предикатом или нет. Первый позволит продолжить разбор текущего правила если идущее следом правило сопоставилось, второй наоборот. Например, с предикатом разобрать сишный комментарий можно очень простым правилом: "/*" (!"*/" any)* "*/"
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[10]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, VladD2, Вы писали:
VD>Как я уже говорил проблема в откатах и заглядывании. Для эффективной самый лучший способ — это работа с индексами и соответственно массивами (строка в дотнете тоже массив своего рода). При этом откаты на начало текста стоят точно столько же сколько на пару символов.
Да, и откат на узел списка будет стоить ровно столько же, пока не потребуется откат на позицию между (текущей и началом)/2. Но насколько я представляю себе кухню — не потребуется.
VD>Вообще было бы интересно посоревноваться с комбинаторными парсерами в скорости. Теоретически, на реальных задачах, мы (PegGrammar) должны порвать их как Тузик грелку. Но теория, есть теория. А хорошо бы это удивить на практике.
У меня под рукой парсер-генератор на C++, для которого я реализовал XML и еще кое-что, срезав пару углов из спеки для достижения скорейшего результата. Оптимизацией и замерами времени не занимался, но по ощущениям мегабайта 4 за секунду проглатывать должен. Кстати, поток данных у него на const wchar_t*.
Если хочется посорвеноваться — вот ссылка на тему
где комбинаторные парсеры фигурируют. Правда, бенчмарк не очень интересный — поток double-ов.
VD>Индекс и указатель (в сишном его понимании) эквивалентны. А вот "узел ленивого списка" — это извините лажа... с точки зрения скорости. Ведь эти узлы придется лепить на каждый символ. Даже при дико-эффективном GC эта операция очень дорогая. А в дотнете GC не так эффективен, так как рассчитан на императивные языки и на много поточный доступ (да и вообще далек от идела). Так что я не поставил бы на такую реализацию и трех рублей.
+1
VD>Ну, в общем — да. Конечно если представлять вычисления и данные в виде ленивых списков, то можно обойтись без массивов и индексов. Но такая реализация уже будет сильно уступать ручной реализации на основе конечных автоматов. Так что никакого выигрыша (кроме декларативности) от использования PEG-а не будет.
Согласен. Если упор на скорость, то индекс/указатель — оптимальное решение. Указатель на узел позволит читать потенциально бесконечные тексты, но значительно медленнее и лишь в случаях ограниченных откатов (все узлы между текущим и тем, на который откатываемся должны уложиться в памяти).
VD>PEG — это не более чем красивая нотация для описания рекурсивных парсеров с откатами. Так что если ты знаком с комбинаторными парсерами, то свитай, что знаком и с базовыми алгоритмами реализации PEG-а. А сама грамматика PEG-а очень похожа на скрещивание ужа с ежом, т.е. на скрещивание регулярных выражений и BNF. Основных новшеств два:
Т.е. похоже что отличие PEG от комбинаторного парсера можно сформулировать так: PEG генерит код на основе нотации, в то время когда комбинаторные парсеры комбинируются непосредственно кодом и красота нотации ограничена синтаксисом используемого языка. Так, в чистом C++ (не 0x) приходится сильно карячиться без лямбд, замыканий и т.п. Результат получается еще менее декларативный, чем в haskell.
Re[11]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, samius, Вы писали:
S>Да, и откат на узел списка будет стоить ровно столько же, пока не потребуется откат на позицию между (текущей и началом)/2. Но насколько я представляю себе кухню — не потребуется.
Можно реализовать все так, что и в случае списков откат на любой уровень будет стоить одинаково. Нельзя лишь сделать так, чтобы реализовав это не замедлить сам парсер. Еще раз повторюсь — список и тем более хранящий действия, а не только данные (ссылки на функции) — это очень не шустрый способ реализации. Да, скорость в нотации О будет та же, но реальная скорость будет низкой, так как выхлопу будет уходить в формирование списка для каждого символа.
VD>>Вообще было бы интересно посоревноваться с комбинаторными парсерами в скорости. Теоретически, на реальных задачах, мы (PegGrammar) должны порвать их как Тузик грелку. Но теория, есть теория. А хорошо бы это удивить на практике. S>У меня под рукой парсер-генератор на C++, для которого я реализовал XML и еще кое-что, срезав пару углов из спеки для достижения скорейшего результата. Оптимизацией и замерами времени не занимался, но по ощущениям мегабайта 4 за секунду проглатывать должен.
Все конечно зависит от процессора. Но на Core 2 сгенерированный нашим макросом парсер выдает 4 метра на грамматике C# 4.0. Так что думаю, как минимум, медленнее не будет. Хотя, конечно, нужно пробовать.
S>Кстати, поток данных у него на const wchar_t*. S>Если хочется посорвеноваться — вот ссылка на тему
где комбинаторные парсеры фигурируют. Правда, бенчмарк не очень интересный — поток double-ов.
Я бы сказал совсем не интересный. Примитивные тесты не показательны. Там и откаты то не нужны вовсе. ХМЛ еще может и потянет, но тоже весьма простой формат. А лучше какой-нить язык программирования. Вот в грамматике шарпа без откатов никуда. Там и без предикатов то не обойтись. Одни неоднозначности с приведением типов или операторами ? : что стоят?
S>Т.е. похоже что отличие PEG от комбинаторного парсера можно сформулировать так: PEG генерит код на основе нотации, в то время когда комбинаторные парсеры комбинируются непосредственно кодом и красота нотации ограничена синтаксисом используемого языка. Так, в чистом C++ (не 0x) приходится сильно карячиться без лямбд, замыканий и т.п. Результат получается еще менее декларативный, чем в haskell.
Не совсем так, так как от нечего делать можно генерить и комбинаторне парсеры по PEG-грамматике, но это конечно дурь. Прелесть и убогость комбинаторных парсеров в их динамичности. С одной стороны можно легко менять грамматику на лету, но с другой и производительности оптимальной добиться невозможно, и ошибки в грамматике выявлять сложно, и вообще — код не самый удобный способ представления грамматик (даже в лисе или немреле).
Но в общем — да. PEG позволяет описать грамматику декларативно и дальше уже генерироваться на ее основе такую реализацию парсера какая нужна. Это скорее всего (процентов эдак на 99) окажется рекурсивный парсер с откатами, но нюансов там получается море. Тут тебе и представление данных, и мемоизация промежуточных вычислений и генерация ДКА и многое другое.
Что же касается выразительности хаскеля и С++, то по мне так они примерно равный. В хаскеле ДСЛ-и (а мы имеем дело именно с ними) делаются за счет манипулирования функциями. В С++ того же эффекта достигают с помощью мета-программирования на шаблонах (см. boost::Spirit). Оба способы несовершенны и значительно уступают полноценным макросам Лиспа и Немерла (особенно последнего, так как в немерле макры мощнее). Выше я уже приводил грамматику шарпа. Как видишь — это полностью декларативный стиль. Причем без компромиссов (как в случае хаскеля и С++). Но это еще не все! Мы имеем и и другие бенефиты:
1. Мы не ограничены в выборе алгоритмов. Сгенерировать можно хоть черта лысого. Хаватило бы мозгов чтобы все решение понять.
2. Наше решение интегрируется в IDE. Мы получаем такие фишки как навигация по правилам, внятные сообщения об ошибках в грамматиках и т.п.
3. Мы можем так же генерировать документацию и сопутствующие вещи.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, Jolly Roger, Вы писали:
JR>Да нет никакой проблемы, тем более — с CSV Переносов, кстати, тоже, в CSV строка файла == строка таблицы. Просто читаете целиком одну строку в свой буфер и ходите по нему сколько угодно. Но необходимости в таком хождении в общем случае тоже нет. Даже читая посимвольно из однонаправленного потока, складываете символы в буфер, пока не обнаружите конец лексемы, а потом уже смотрите, что за лексема. Для кавычек и т.п. просто заведите ещё одно состояние, да и всё.
По поводу переносов строки уже сказали, но в остальном — так. Строка в кавычках — это один токен, то есть ещё одно состояние парсера (если делать его как FSM). Кстати парсеры на FSM не всегда хороши. Нас в универе учили писать рекурсивные лексеры — они обычно существенно проще. Например, с помощью флекса,бизона и файла описания грамматики простейший интерпретатор/компилятор языка С пишется за 3-4 часа (мы на лабах такое делали).
Здравствуйте, koandrew, Вы писали:
K>По поводу переносов строки уже сказали, но в остальном — так. Строка в кавычках — это один токен, то есть ещё одно состояние парсера (если делать его как FSM). Кстати парсеры на FSM не всегда хороши.
В данном случае парсер на ДКА прокатит.
У CSV грамматика регулярная.
K>Нас в универе учили писать рекурсивные лексеры — они обычно существенно проще.
Существенно проще чем что?
K>Например, с помощью флекса,бизона и файла описания грамматики простейший интерпретатор/компилятор языка С пишется за 3-4 часа (мы на лабах такое делали).
bottom-up parser тот еще геморой когда дело доходит до сообщений об ошибках.
Лучше использовать top-down parser. Особенно PEG. Ибо PEG умеет произвольные синтаксические предикаты что растягивает класс разбираемых языков аж до некоторого подмножества контекстно зависимых.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[9]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, VladD2, Вы писали:
F>> Это всё понятно. Далее то куда их девать? VD>Что значит куда девать? Их достаточно для реализации разбора на базе, например, конечного автомата.
Если это эээ литерал — каким образом мы его получим в виде строки?
F>> Не особо нужен. VD>Ну, спорить с теорией можно, но глупо .
Не особо нужен полноценный построить парсеров. Стёк нужен — но он достаточно прост.
VD>Мой парсер не был предназначен для пенисометрии. Он был разработан в рамках макроса предоставляющего XML-литералы в виде DSL для Nemerle (весь проект можно посмотреть здесь, там же есть и тесты демонстрирующие использование). Но из него не сложно будет выдрать грамматику, убрать расширения и сделать тестовый парсер.
Я обязательно посмотрю, но позже. Надо сначала посмотреть что к чему, разобраться. Тут ещё сложность в том что от немерле я запускал только инсталлятор в лучшем случае год назад. Поэтому буду смотреть на код коровьими глазами.
VD>Один факт. В Nemerle нет оператора goto, но внутри макросов такой код все же сгенерировать можно. И PegGrammar этим во всю пользуется при генерации конечных автоматов в релиз-версии. Применение goto дало где-то 10% прироста производительности конечного парсера. Такое применение goto вполне оправданно. Но в рукописном коде я бы ни в жизнь не допустил бы использования goto.
Да, goto — рулит. И ими можно много чего выжать, но соглашусь что писать руками их затея как минимум не простая, да и выглядит странной.
VD>Я конечно не утверждаю, что невозможно создать рукописный парсер которые был бы эффективнее генерированного. Это не так. Но при прочих равных — это не такая уж простая задача.
А я не утверждаю что можно успешно написать любой рукопашный парсер. Речь о достаточно простых. XML тот же — тоже можно, но уже не просто.
Re[11]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, samius, Вы писали:
S>У меня под рукой парсер-генератор на C++, для которого я реализовал XML и еще кое-что, срезав пару углов из спеки для достижения скорейшего результата. Оптимизацией и замерами времени не занимался, но по ощущениям мегабайта 4 за секунду проглатывать должен. Кстати, поток данных у него на const wchar_t*. S>Если хочется посорвеноваться — вот ссылка на тему
Так что рвем всех даже там где нет никаких причин это делать . Ну, а теперь сравни это дело со Штатным парсеком, что на тех самых списках на ленивых. Вот тебе и ответ на вопрос о том можно ли вместо индексов списки применять (ленивые).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[12]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, VladD2, Вы писали:
VD>Как я уже говрил даблы конечно лажа а не тест. Но вот вам наш ответ чемберленам: VD>http://rsdn.ru/forum/decl/4070931.1.aspx
VD>Так что рвем всех даже там где нет никаких причин это делать . Ну, а теперь сравни это дело со Штатным парсеком, что на тех самых списках на ленивых. Вот тебе и ответ на вопрос о том можно ли вместо индексов списки применять (ленивые).
Таки можно, если нужно. Еще раз напомню, что я не предлагал что-либо менять в текущей реализации. Просто упомянул о том, что необходимость загрузки всех данных в память — это специфика реализации, а не PEG-а как такового.
Если честно, я даже не могу высосать из пальца задачу с претензией на реальность, где бы данные для разбора не могли бы поместиться в памяти. Тот же бесконечный CSV выглядит по меньшей мере глупо, притом что гарантий его разбора парсер на ленивых списках дает не сильно больше.
Re[13]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, samius, Вы писали:
S>Таки можно, если нужно. Еще раз напомню, что я не предлагал что-либо менять в текущей реализации. Просто упомянул о том, что необходимость загрузки всех данных в память — это специфика реализации, а не PEG-а как такового.
Теоретически — да. На практике при этом придется забить на производительность.
S>Если честно, я даже не могу высосать из пальца задачу с претензией на реальность, где бы данные для разбора не могли бы поместиться в памяти. Тот же бесконечный CSV выглядит по меньшей мере глупо, притом что гарантий его разбора парсер на ленивых списках дает не сильно больше.
Придумать пример элементарно. Например, разбор лога веб-сервера ведущегося в текстовом формате.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[14]: Чтение файла: заглянуть на несколько символов вперёд
Здравствуйте, VladD2, Вы писали:
S>>Если честно, я даже не могу высосать из пальца задачу с претензией на реальность, где бы данные для разбора не могли бы поместиться в памяти. Тот же бесконечный CSV выглядит по меньшей мере глупо, притом что гарантий его разбора парсер на ленивых списках дает не сильно больше.
VD>Придумать пример элементарно. Например, разбор лога веб-сервера ведущегося в текстовом формате.
.
Ну и ладно, задачу всё равно это практически не усложняет.
"Нормальные герои всегда идут в обход!"
