как разобрать и проверить упорядоченный список целых чисел с помощью ци - PullRequest
Новая
       16

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

5 голосов
/ 22 июня 2011

Я анализирую текстовый файл, возможно, размером несколько ГБ, состоящий из следующих строк: 

11 0.1
14 0.78
532 -3.5

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

#include <iostream>
#include <string>

#include <boost/spirit/include/phoenix.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/fusion/include/std_pair.hpp>

namespace px = boost::phoenix;
namespace qi = boost::spirit::qi;

namespace my_parsers
{
using namespace qi;
using px::at_c;
using px::val;
template <typename Iterator>
struct verify_data : grammar<Iterator, locals<int>, std::pair<int, int>()>
{
    verify_data() : verify_data::base_type(section)
    {
        section
            =  line(val(0))    [ at_c<0>(_val) = _1]
            >> +line(_a)       [ _a = _1]
            >> eps             [ at_c<1>(_val) = _a]
            ;

        line
            %= (int_ >> other) [
                                   if_(_r1 >= _1)
                                   [
                                       std::cout << _r1 << " and "
                                       << _1 << val(" out of order\n")
                                   ]
                               ]
            ;

        other
            = omit[(lit(' ') | '\t') >> float_ >> eol];
    }
    rule<Iterator, locals<int>, std::pair<int, int>() > section;
    rule<Iterator, int(int)> line;
    rule<Iterator> other;
};
}

using namespace std;
int main(int argc, char** argv)
{
    string input("11 0.1\n"
                 "14 0.78\n"
                 "532 -3.6\n");

    my_parsers::verify_data<string::iterator> verifier;
    pair<int, int> p;
    std::string::iterator begin(input.begin()), end(input.end());
    cout << "parse result: " << boolalpha
         << qi::parse(begin, end, verifier, p) << endl; 
    cout << "p.first: " << p.first << "\np.second: " << p.second << endl;
    return 0;
}

Что я хотел бы знать, это следующее:

  • Есть ли лучший способ сделать это?Я использовал унаследованные и синтезированные атрибуты, локальные переменные и немного феникса вуду.Это замечательно;изучение инструментов - это хорошо, но я не могу не думать, что может быть гораздо более простой способ достичь того же: / (в PEG-парсере, который ...)
  • Как это можно сделать без локальной переменной дляпример?

Дополнительная информация: У меня есть другие форматы данных, которые анализируются одновременно, и поэтому я хотел бы сохранить возвращаемое значение в качестве атрибута синтаксического анализатора.На данный момент это std :: pair, другие форматы данных при анализе разбираются, например, со своими собственными std :: pair, и именно эти я хотел бы вставить в std :: vector.

Ответы [ 2 ]

2 голосов
/ 23 июня 2011

Это как минимум уже намного короче:

  • до 28 LOC
  • не больше местных жителей
  • не более вектор слияния at<> волшебство
  • не более унаследованных атрибутов
  • не более класс грамматики
  • больше нет ручной итерации
  • использование точек ожидания (см. other) для улучшения отчетов об ошибках анализа
  • выражения этого синтаксического анализатора аккуратно синтезируются в vector<int>, если вы решите назначить его с %= (но это будет стоить производительности, помимо возможного выделения большого массива)

. 

#include <boost/spirit/include/phoenix.hpp>
#include <boost/spirit/include/qi.hpp>

namespace px = boost::phoenix;
namespace qi = boost::spirit::qi;

typedef std::string::iterator It;

int main(int argc, char** argv)
{
    std::string input("11 0.1\n"
            "14 0.78\n"
            "532 -3.6\n");

    int min=-1, max=0;
    {
        using namespace qi;
        using px::val;
        using px::ref;

        It begin(input.begin()), end(input.end());
        rule<It> index = int_ 
            [
                if_(ref(max) < _1)  [ ref(max) = _1 ] .else_ [ std::cout << _1 << val(" out of order\n") ],
                if_(ref(min) <  0)  [ ref(min) = _1 ]
            ] ;

        rule<It> other = char_(" \t") > float_ > eol;

        std::cout << "parse result: " << std::boolalpha 
                  << qi::parse(begin, end, index % other) << std::endl; 
    }
    std::cout << "min: " << min << "\nmax: " << max << std::endl;
    return 0;
}

Бонус

Я мог бы предложить исключить проверку из выражения и сделать ее автономной функцией; конечно, это делает вещи более многословными (и ... разборчивыми), и мой образец braindead использует глобальные переменные ... - , но я надеюсь, вы знаете, как использовать boost::bind или px::bind, чтобы сделать его более реальным -Жизнь

В дополнение к вышесказанному

  • до 27 LOC даже с функцией free
  • больше нет Phoenix, больше нет Phoenix включает (yay раз компиляции)
  • больше нет типов выражений феникса в сборках отладки, которые раздувают двоичный файл и замедляют его
  • не более var, ref, if_, .else_ и убогий operator, (которые имели большой риск ошибки ( в некоторое время ) из-за не включенной перегрузки с phoenix.hpp)
  • ( легко портируется на c ++ 0x лямбда-выражения - немедленно устраняется необходимость в глобальных переменных )

. 

#include <boost/spirit/include/phoenix.hpp>
#include <boost/spirit/include/qi.hpp>
namespace px = boost::phoenix;
namespace qi = boost::spirit::qi;
typedef std::string::iterator It;

int min=-1, max=0, linenumber=0;
void validate_index(int index)
{
    linenumber++;
    if (min < 0)     min = index;
    if (max < index) max = index;
    else             std::cout << index << " out of order at line " << linenumber << std::endl;
}

int main(int argc, char** argv)
{
    std::string input("11 0.1\n"
            "14 0.78\n"
            "532 -3.6\n");
    It begin(input.begin()), end(input.end());

    {
        using namespace qi;

        rule<It> index = int_ [ validate_index ] ;
        rule<It> other = char_(" \t") > float_ > eol;
        std::cout << "parse result: " << std::boolalpha 
                  << qi::parse(begin, end, index % other) << std::endl; 
    }
    std::cout << "min: " << min << "\nmax: " << max << std::endl;
    return 0;
}
2 голосов
/ 23 июня 2011

Полагаю, гораздо проще было бы проанализировать файл с использованием стандартных потоковых операций, а затем проверить порядок в цикле.Во-первых, ввод: 

typedef std::pair<int, float> value_pair;

bool greater(const value_pair & left, const value_pair & right) {
    return left.first > right.first;
}

std::istream & operator>>(std::istream & stream, value_pair & value) {
    stream >> value.first >> value.second;
    return stream;
}

Использование это так: 

std::ifstream file("your_file.txt");
std::istream_iterator<value_pair> it(file);
std::istream_iterator<value_pair> eof;

if(std::adjacent_find(it, eof, greater) != eof) {
    std::cout << "The values are not ordered" << std::endl;
}

Я считаю это намного проще.

...