Разбор QString

[alexis031182]

Истина познаётся в споре.

Да не, это философская отмазка, лишь бы не работать

А выбор между своим велосипедом и чужим решением - сравнением

PS эт уже каждый решает для себя, что выбрать. Споры тут неуместны.

Часто действительно интересно написать своё. У меня сейчас как раз такая ситуация с моим проектом веб-сервера.

[Igors]

Обсуждается ведь, как я понимаю, то, что следует предпочесть в ситуации, когда есть выбор, правильно?

А этот выбор часто бывает непростым. Ну конечно, если налицо json - обидеть велосипедиста может каждый . Но вот задача не имеет столь явных аналогий, напр http://www.prog.org.ru/index.php?topic=21746.msg151303#msg151303. И вот уже почему-то мы автоматически считаем что "готовое решение" = RegExp. Но так ли это? Я лично не уверен, во всяком случае мне это легче сделать просто на С++.

А в более сложных случаях все намного хуже. Увы, слишком поздно обнаруживается что "готовое решение" было ошибкой, и приходится начинать чуть ли не с нуля. с растраченными деньгами и временем    Использовать готовое конечно заманчиво, но здесь легко потерять "реализьм"

[alexis031182]

А этот выбор часто бывает непростым. Ну конечно, если налицо json - обидеть велосипедиста может каждый

А обидят потому, что хотя и не знают доподлинно возможностей велосипедиста, тем не менее в подавляющем большинстве случаев, в итоге, окажутся правы. Мол, да я! Да я этот json своим самописным парсером порву как болонка грелку! А на поверку оказывается... что ничего не оказывается. Видимо со временем таковые возгласы и сформировали устойчивое общественное мнение о подобных "грандиозных" начинаниях. Да Вы и сами где-то высказывали аналогичную мысль. Кажется в теме о Qt креаторе.

А вот здесь получилось иначе. Вы однозначно доказали, что Ваше решение эффективнее, нежели чем QRegExp (не регулярка как таковая, парсеров, её реализующих, довольно много, но именно кьютишный класс). Отсюда и результат: возгласов супротив нет. Вполне возможно, что кто-нибудь расстроится, если Ваш проект победит в эффективности и некоторых из специализированных парсеров (тех же json), но ломать стереотипы часто полезно. Здесь не могу с Вами не согласиться.

Но вот задача не имеет столь явных аналогий, напр http://www.prog.org.ru/index.php?topic=21746.msg151303#msg151303. И вот уже почему-то мы автоматически считаем что "готовое решение" = RegExp. Но так ли это? Я лично не уверен, во всяком случае мне это легче сделать просто на С++.

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

А в более сложных случаях все намного хуже. Увы, слишком поздно обнаруживается что "готовое решение" было ошибкой, и приходится начинать чуть ли не с нуля. с растраченными деньгами и временем    Использовать готовое конечно заманчиво, но здесь легко потерять "реализьм"

Тут уж наверное только опыт может помочь.

[Igors]

А обидят потому, что хотя и не знают доподлинно возможностей велосипедиста, тем не менее в подавляющем большинстве случаев, в итоге, окажутся правы. Мол, да я! Да я этот json своим самописным парсером порву как болонка грелку!

Вот именно такого задорного подхода я жду от молодых пацанов! (ну конечно подкрепленного кодом - хоть частично). Однако же - сами видите 

По правде сказать я вспомнил что это json только когда  Вы сказали. Заказчик попросил меня добавить чтение таких файлов и дал пару ссылок на имеющиеся парсеры. Ну я посидел вечерок, делал примерно как сейчас только на char * и ввод был просто "конкретные скобки". Все получилось, потом правда вылез один баг - не учел вложенные кавычки \". Ну и нафиг мне было связываться с чужим кодом?

А вот здесь получилось иначе. Вы однозначно доказали, что Ваше решение эффективнее, нежели чем QRegExp (не регулярка как таковая, ...

Ничего такого я не доказывал! Я считаю что RegExp попросту НЕ ПРЕДНАЗНАЧЕН для "контекстного" разбора, и нечего насиловать тул тыкая его куда не надо. О чем кстати есть вполне внятное упоминание в букваре.

[alexis031182]

Вот именно такого задорного подхода я жду от молодых пацанов! (ну конечно подкрепленного кодом - хоть частично). Однако же - сами видите  

Шаблонность мышления? Но это свойственно, наверное, абсолютному большинству. Невозможно же всё перепроверить/переписать самолично. Хоть какие-то блоки, пусть и самые минимальные, так или иначе всё равно будут исходить из чужих, кем-то уже реализованных мыслей. Другое дело конечно, когда шаблонность принимает вредный масштаб. Это навроде позиции, пытающейся оправдать использование кавалерии во Второй мировой войне.

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

Сказал kambala. А json в вэбе по популярности, похоже, уже давно оставил позади тот же xml. Практически стандарт де-факто.

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

Вы уверены в своих силах, от того и оправдан был Ваш шаг. Плюс, Вы сами себе хозяин в принятии решений о том, как поступать в этом и похожих случаях. Но представьте положение молодого исполнителя, что не имеет возможности для манёвра. В его ситуации отход от какого-либо постулата чреват срывом заказа. Зачем ему дополнительный риск? Как минимум он потеряет больше времени на разработку собственного решения. А как максимум - его начинание может закончиться признанием поражения. Другими словами, чтобы заняться своей собственной уникальной разработкой, необходимы соответствующие условия. Это, например, и относительная свобода в принятии решения, которая, по правде сказать, автоматически снизит долю ответственности (не может же быть так, что если где-нибудь прибыло, то нигде не убудет). Это и наличие большего количества знаний и опыта по сравнению с ожидаемым заказчиком уровнем исполнителя. Это и... да хотя бы просто наличие здорового авантюризма, поскольку не всегда представляется возможность адекватно оценить собственные силы для не шаблонного решения задачи.

Ничего такого я не доказывал! Я считаю что RegExp попросту НЕ ПРЕДНАЗНАЧЕН для "контекстного" разбора, и нечего насиловать тул тыкая его куда не надо. О чем кстати есть вполне внятное упоминание в букваре.

Как раз доказательство Вы и привели. Потребовалась разработка собственного решения, чтобы обстоятельно показать неэффективность применения регулярки, как Вы назвали, для "контекстного разбора". Иначе получился бы чистой воды холивар. Приводилось бы множество малосвязанных между собой примеров, противостоящих точке зрения оппонентов. А тут, раз, и в дамках. Супротив аргумента "скорость выполнения" мало что возможно возразить. Тем более, когда разница столь существенна.

[moskk]

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

[m_ax]

Столкнулся с аналогичной проблемой разбора определённых форматов документов.
И.. вспомнил про эту тему..

Если можно немного покритикую реализацию igors'а.

Во-первых, хотелось бы чтобы это не было завязано на Qt (пишу сейчас ядро и зависимости от такого монстра, как Qt там излишни)

Во-вторых, хотелось бы иметь возможность начинать разбор с определённого места, т.е. чтобы можно было задавать pos (position) с которой начинается разбор. Нечто подобное интерфейсу QRegExp, например..

В общем, первые два пункта, заставили меня написать нечто подобное. Концептуально, интерфейс я старался сохранить близким к реализации igors'а. (приатачено ниже)

И так два класса:
parse_param

Код

C++ (Qt)
class parse_param
{
public:
    parse_param();
    parse_param(const std::string &tokens, const std::string &delims);
 
    void add_quote(char bra, char ket);
    void set_delims(const std::string &delims);
    void set_tokens(const std::string &tokens);
 
    friend class string_parser;
 
private:
    std::string m_bra_list;
    std::string m_ket_list;
    std::string m_tokens;
    std::string m_delims;
};
 

С токенами и делимами здесь, думаю все знакомы. Метод add_quotes добавляет открывающий символ (bra) и закрывающий символ (ket) для цитаты. Всё остальное аналогично варианту igors'а, за исключением того, что в конструкторе вначале передаются токены, а затем делимы.

И интерфейс string_parser:

Код

C++ (Qt)
enum class split_behavior { keep_empty_parts, skip_empty_parts };
 
class string_parser
{
public:
    typedef std::string::size_type size_type;
 
    string_parser(const parse_param &param);
 
    size_type next_token(const std::string &str, size_type pos = 0, split_behavior behavior = split_behavior::skip_empty_parts) const;
    size_type next_quote(const std::string &str, size_type pos = 0, split_behavior behavior = split_behavior::skip_empty_parts) const;
    size_type matched_length() const;
    char token() const;
    std::string result() const;
 
    static std::string trim(const std::string &str, const std::string &delim = " \t\n");
    static size_type npos();
 
private:
    const parse_param &m_param;
    mutable char m_token;
    mutable size_type m_mathed_length;
    mutable std::string m_result;
 
    size_type find_first_token(const std::string &str, size_type pos = 0) const;
    static size_type skip_quote(const std::string &str, char bra, char ket, size_type pos = 0);
};
 

Здесь метод next_token возвращает позицию следующего токена, в противном случае std::string::npos, например:

Код

C++ (Qt)
std::string str = "a, b, , c , {d,e {f}}";
parse_param param(",.", " \t");
param.add_quote('{', '}');
 
string_parser parser(param);
size_t pos = 0;
while ((pos = parser.next_token(str, pos, mbib::split_behavior::skip_empty_parts)) != std::string::npos) {
    std::cout << std::left << parser.result()  << std::setw(10) << parser.token() << std::endl;
    pos += parser.matched_length();
}
 

вывод:

Код

Bash
"a"
","
"b"
","
"c"
","
"{d,e {f}}"
""        
 

Если установлен флаг split_behavior::keep_empty_parts, то будут также выведены все пустые строки между токенами:

Код

C++ (Qt)
std::string str = "a, b, , c , {d,e {f}}";
parse_param param(",.", " \t");
param.add_quote('{', '}');
 
string_parser parser(param);
size_t pos = 0;
while ((pos = parser.next_token(str, pos, mbib::split_behavior::keep_empty_parts)) != std::string::npos) {
    std::cout << std::left << parser.result()  << std::setw(10) << parser.token() << std::endl;
    pos += parser.matched_length();
}
 

вывод:

Код

Bash
"a"
","
"b"
","
""
","
"c"
","
"{d,e {f}}"
""
 

далее, метод next_quote возвращает позицию начала цитаты. Всё остальное аналогично next_token:

Код

C++ (Qt)
std::string str = "{a, b},{}{} , c , {d,e {f}}";
parse_param param(",.", " \t");
param.add_quote('{', '}');
 
string_parser parser(param);
size_t pos = 0;
while ((pos = parser.next_token(str, pos, mbib::split_behavior::skip_empty_parts)) != std::string::npos) {
    std::cout << std::left << parser.result() << std::endl;
    pos += parser.matched_length();
}
 

Вывод:

Код

Bash
"a, b"
"d,e {f}"
 

метод result возвращает строку с результатом,
метод token возвращает текущий символ токена (в противном случае -1)
метод matched_length - аналогичен QRegExp::matchedLength
trim удаляет в начале и в конце строки delims.
npos - аналогичен std::string::npos

Теперь о тестах и о производительности.
Сравнивались реализация igors и моя на следующем простом примере:

Код

C++ (Qt)
#include <iostream>
#include <ctime>
#include "string_parser.h"
#include "QStringParser.h"
#include <QDebug>
 
int main()
{
    QString src="Westerholt, K.  {and Sprungmann, D.}  and Zabel, H.  and Brucas, R.  and Hj\"orvarsson, B.  and Tikhonov, D. A. and Garifullin, I. A.";
    std::string std_src = src.toStdString();
    const long N = 1000000;
 
    parse_param param(",.", " \t");
    param.add_quote('{', '}');
 
    string_parser parser(param);
 
    clock_t tStart = clock();
    for (long i = 0; i < N; ++i) {
        size_t pos = 0;
        while ((pos = parser.next_token(std_src, pos, split_behavior::keep_empty_parts)) != std::string::npos) {
            //std::cout << parser.result() << std::endl << parser.token() << std::endl;
            pos += parser.matched_length();
        }
    }
    std::cout << "m_ax: time (sec) = " << (float)(clock() - tStart) / CLOCKS_PER_SEC << std::endl;
 
 
    CParseParam cparam(" \t", ",.");
    cparam.AddQuote(100, "{", "}");
 
    QStringRef temp;
    tStart = clock();
    for (long i = 0; i < N; ++i) {
        QStringParser cparser(src, cparam);
        while(cparser.NextToken(temp)) {}
    }
    std::cout << "igors: time (sec) = " << (float)(clock() - tStart) / CLOCKS_PER_SEC << std::endl;
 
    return 0;
}
 

Вывод на моей машине:

Код

Bash
m_ax: time (sec) = 11.72
igors: time (sec) = 8.93
 

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

Проект приатачен, спасибо за внимание).



 
       

[Igors]

Если можно немного покритикую реализацию igors'а.

Во-первых, хотелось бы чтобы это не было завязано на Qt (пишу сейчас ядро и зависимости от такого монстра, как Qt там излишни)

Во-вторых, хотелось бы иметь возможность начинать разбор с определённого места, т.е. чтобы можно было задавать pos (position) с которой начинается разбор. Нечто подобное интерфейсу QRegExp, например..

Критиковать можно и нужно 

1) С определенного места (или фрагмент) можно, ведь используется QStringRef - очень удобный утилитарный класс, и надо было просто передрать его для std::string реализации. Возвращение позиции (индекса) куда менее удобно, возникают заботы о конце.

2) Не понял (может просто невнимательно смотрел) как Вы обошлись без приоритетов quote. Напр

"test ("test)  // одна quote кавычки, другая скобки ()

Также если баланс quote нарушен (напр "test) то возвращаемым токеном должно быть все до конца строки (а не npos) 

Вообще самое трудное в этой задаче - не реализация, а придумать как этим удобно пользоваться. В связи с этим какая-я то обобщенная реализация (напр для QString и std::string) наверно была бы совершенно монструозной 

[m_ax]

Если можно немного покритикую реализацию igors'а.

Во-первых, хотелось бы чтобы это не было завязано на Qt (пишу сейчас ядро и зависимости от такого монстра, как Qt там излишни)

Во-вторых, хотелось бы иметь возможность начинать разбор с определённого места, т.е. чтобы можно было задавать pos (position) с которой начинается разбор. Нечто подобное интерфейсу QRegExp, например..

Критиковать можно и нужно 

1) С определенного места (или фрагмент) можно, ведь используется QStringRef - очень удобный утилитарный класс, и надо было просто передрать его для std::string реализации. Возвращение позиции (индекса) куда менее удобно, возникают заботы о конце.

2) Не понял (может просто невнимательно смотрел) как Вы обошлись без приоритетов quote. Напр

"test ("test)  // одна quote кавычки, другая скобки ()

Также если баланс quote нарушен (напр "test) то возвращаемым токеном должно быть все до конца строки (а не npos) 

Вообще самое трудное в этой задаче - не реализация, а придумать как этим удобно пользоваться. В связи с этим какая-я то обобщенная реализация (напр для QString и std::string) наверно была бы совершенно монструозной 

По-поводу п. 2
С приоритетами, имхо, это лишнее.. Это порождает неоднозначные ситуации, и скорее, свидетельствует о плохо определённом формате..
Позже поясню..

[Bepec]

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

[Old]

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

Из этой ситуации есть только один выход: завершить программу с сообщением об ошибке.

[Bepec]

Почему же? если ошибка находится в секции, которая не требуется обязательно для работы, то вполне можно и запуститься и сообщить об ошибке и, возможно, произвести работы по восстановлению ;P

[m_ax]

И так, по поводу приоритетов..

Меня, как пользователя, смутило следующее:

1) Неочевидность.. Казалось бы, чем выше приоритет для quote,  тем выше по иерархи она должна стоять (ну и обрабатываться).. У вас же всё наоборот..

2) Непонятное (?) поведение для такого простого примера:

Код

C++ (Qt)
    QString src = "\"test, (\",test)";
    CParseParam cparam(" \t", ",.");
    cparam.AddQuote(10, "(", ")");
    cparam.AddQuote(10, "\"", "\"");
 
    QStringRef temp;
    QStringParser cparser(src, cparam);
     while(cparser.NextToken(temp)) {
         qDebug() << temp;
     }
 

Почему вывод будет таким:

Код

Bash
""test, (",test)" 
 

Ведь приоритеты для обоих цитат одинаковы..
Логичнее было бы ожидать такого результата:

Код

Bash
""test, ("" 
"," 
"test)"
 

Это понятно почему логичнее?

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

Но всё это, конечно, наверное, больше дело личных предпочтений.. В конечном счёте вам решать.. Я лишь высказал личное впечатления и своё видение этого.

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

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

  
 
 

[Igors]

1) Неочевидность.. Казалось бы, чем выше приоритет для quote,  тем выше по иерархи она должна стоять (ну и обрабатываться).. У вас же всё наоборот..

Дело вкуса - можно напр вспомнить "0 = уровень ядра (наивысший)"

Логичнее было бы ожидать такого результата:

Не "логичнее" а "интуитивнее" т.к. в жизни приоритет кавычек выше. Так никто Вам не мешал дать такой приоритет как в жизни. Возьмем квадратные скобки вместо кавычек

Код

C++ (Qt)
QString src = "[test(],test)]";
 

С какой же стати первый токен должен быть [test, (]? Проблемы внутри круглых скобок, до этого должны выдаться нормальные токены test и (],test)

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

Это обычная лень и нежелание вникать в какие-то там тонкости  

Непонятно как Вы обойдетесь без приоритета здесь
test("some)thing")

Или даже здесь (не вижу как у Вас это отрабатывается)
test("something()")

[m_ax]

Не "логичнее" а "интуитивнее" т.к. в жизни приоритет кавычек выше. Так никто Вам не мешал дать такой приоритет как в жизни. Возьмем квадратные скобки вместо кавычек

Код

C++ (Qt)
QString src = "[test(],test)]";
 

С какой же стати первый токен должен быть [test, (]? Проблемы внутри круглых скобок, до этого должны выдаться нормальные токены test и (],test)

Ещё раз: Здесь у вас квадратные и круглые скобки имеют одинаковый приоритет, т.е. фактически, они равноправны. Почему вы делаете выбор в пользу круглых скобок, а не квадратных? Ведь первая цитата начинается именно с них (с квадратных). 

Непонятно как Вы обойдетесь без приоритета здесь
test("some)thing")

Или даже здесь (не вижу как у Вас это отрабатывается)
test("something()")

Да легко, в зависимости от того, что мне нужно будет получить.