Подтвердить что ты не робот

Минимизация boost:: spirit compile раз

Любые идеи для сокращения времени boost:: spirit compile?

Я просто портировал синтаксический анализатор, чтобы повысить:: дух. EBNF имеет около 25 правил.

Результат хорошо работает, и производительность исполнения прекрасна.

Проблема в том, что компиляция берет навсегда! Это занимает около десяти минут и требует почти гигабайта памяти. Исходный синтаксический анализатор, скомпилированный за несколько секунд.

Я использую boost версии 1.44.0 и Visual Studio 2008.

В статье Джоэля де Гузмана "Лучшие практики" говорится

Правила со сложными определениями сильно вредят компилятору. Мы видели правила, превышающие сто линии и возьмите пару минут для компиляции

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

Вот самая сложная часть моей грамматики. Является ли он кандидатом на то, чтобы быть разбитым на более мелкие части, каким-то образом?

    rule
        =   (   tok.if_ >> condition  >> tok.then_ >> *sequel  )                            [ bind( &cRuleKit::AddRule, &myRulekit ) ]
        |   (   tok.if_ >> condition  >> tok.and_ >> condition >> tok.then_ >> *sequel  )   [ bind( &cRuleKit::AddRule, &myRulekit ) ]
        ;

    condition
        =   ( tok.identifier >> tok.oper_ >> tok.value )                                    [ bind( &cRuleKit::AddCondition, &myRulekit, _pass, _1, _2, _3 ) ]
        |   ( tok.identifier >> tok.between_ >> tok.value >> "," >> tok.value )             [ bind( &cRuleKit::AddConditionBetween, &myRulekit, _pass, _1, _3, _4 ) ]
        ;

    sequel
        =   ( tok.priority_ >> tok.high_ )      [ bind( &cRuleKit::setPriority, &myRulekit, 3 ) ]
        |   ( tok.priority_  )                  [ bind( &cRuleKit::setPriority, &myRulekit, 2 ) ]
        |   ( tok.interval_ >> tok.value )      [ bind( &cRuleKit::setInterval, &myRulekit, _2 ) ]
        |   ( tok.mp3_ >> tok.identifier )      [ bind( &cRuleKit::setMP3, &myRulekit, _2 ) ]
        |   ( tok.disable_ )                    [ bind( &cRuleKit::setNextRuleEnable, &myRulekit, false ) ]
        ;

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

        set_reading
            =   tok.set_reading >> +attribute_reading
            ;

        attribute_reading
            =   ( tok.name_ >> tok.identifier )
                [
                                                bind( &cPackage::Add, &myReadings, _pass, _2 )
                ]
            |   ( tok.nmea_ >> tok.identifier )
                [
                                                bind( &cPackage::setNextNMEA, &myReadings, _2 )
                ]
            |   ( tok.column_ >> tok.integer )
                [
                                                bind( &cPackage::setNextColumn, &myReadings, _2 )
                ]
            |   ( tok.precision_ >> tok.value )
                [
                                                bind( &cPackage::setNextPrecision, &myReadings, _2 )
                ]
            |   ( tok.unit_ >> tok.identifier )
                [
                                                bind( &cPackage::setNextUnit, &myReadings, _2 )
                ]
            |   ( tok.value_ >> tok.identifier )
                [
                                                bind( &cPackage::setNextValue, &myReadings, _2 )
                ]
            |   ( tok.qualifier_ >> tok.identifier >> tok.qual_col_ >> tok.integer )
                [
                                                bind( &cPackage::setNextQualifier, &myReadings, _2, _4 )
                ]
            ;

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

    set_reading
        =   tok.set_reading >> +attribute_reading
        ;

    attribute_reading
        =   attribute_reading_name
        |   attribute_reading_nmea
        |   attribute_reading_col
        |   attribute_reading_precision
        |   attribute_reading_unit
        |   attribute_reading_value
        |   attribute_reading_qualifier
        ;



    attribute_reading_name
        =   ( tok.name_ >> tok.identifier )     [ bind( &cPackage::Add, &myReadings, _pass, _2 ) ]
        ;
    attribute_reading_nmea
        =   ( tok.nmea_ >> tok.identifier )     [ bind( &cPackage::setNextNMEA, &myReadings, _2 ) ]
        ;
    attribute_reading_col
        =   ( tok.column_ >> tok.integer )      [ bind( &cPackage::setNextColumn, &myReadings, _2 ) ]
        ;
    attribute_reading_precision
        =   ( tok.precision_ >> tok.value )     [ bind( &cPackage::setNextPrecision, &myReadings, _2 ) ]
        ;
    attribute_reading_unit
        =   ( tok.unit_ >> tok.identifier )     [ bind( &cPackage::setNextUnit, &myReadings, _2 ) ]
        ;
    attribute_reading_value
        =   ( tok.value_ >> tok.identifier )    [ bind( &cPackage::setNextValue, &myReadings, _2 ) ]
        ;
    attribute_reading_qualifier
        =   ( tok.qualifier_ >> tok.identifier >> tok.qual_col_ >> tok.integer ) [ bind( &cPackage::setNextQualifier, &myReadings, _2, _4 ) ]

        ;

Это экономит несколько минут от общего времени компиляции!!!

Как ни странно, потребность в пиковой памяти остается неизменной, она требуется только за меньшее время

Итак, я чувствую себя немного более надежно, что все мои усилия по обучению boost:: spirit будут полезными.

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

Я потратил большую часть семидневного обучения boost:: spirit и портировал небольшой, но реальный мир, парсер из flex. Я пришел к выводу, что он работает, и код очень изящный. К сожалению, наивное использование путем простого расширения кода примера учебника для реального приложения быстро перегружает компилятор - память и время, затраченное на компиляцию, становятся совершенно непрактичными. По-видимому, есть методы для решения этой проблемы, но они требуют тайного знания, которое у меня нет времени, чтобы учиться. Думаю, я буду придерживаться гибкости, которая может быть уродливой и старомодной, но относительно простой и молниеносной.

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

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

enter image description here

Ответ 2

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

grammar.hpp:

template <typename Iterator>
struct grammar : qi::grammar<Iterator>
{
    grammar();   // declaration only
    // ...
};

grammar_def.hpp:

// This file should not contain anything else.
#include "grammar.hpp"

// Definition of constructor.
template <typename Iterator>
grammar<Iterator>::grammar()
{
    // initialize your rules here
}

grammar.cpp:

// This file should not contain anything else.
#include "grammar_def.hpp"

// Explicitly instantiate the constructor for the iterator type
// you use to invoke the grammar (here, as an example I use 
// std::string::const_iterator).
typedef std::string::const_iterator iterator_type;
template grammar<iterator_type>::grammar();

Сделайте то же самое для объекта lexer.

Этот подход требует немного больше работы, чем прямой метод, но позволяет распределять требования к памяти и времени для общей компиляции. Другим преимуществом этого подхода является то, что любое изменение в конструкторе грамматики не требует перекомпиляции ничего, кроме файла grammar.cpp.

Еще один совет для lexer: старайтесь как можно больше минимизировать использование экземпляров token_def<>. Вам нужно использовать token_def<>, только если вы хотите получить доступ к значению маркера в качестве атрибута во время разбора. Во всех остальных случаях вы можете уйти с lex::string или lex::char_, чтобы определить свои токены.