Разбор грамматики с помощью Boost Spirit - PullRequest
9 голосов
/ 20 июня 2010

Я пытаюсь выполнить синтаксический анализ C-функции, такой как выражения дерева, как показано ниже (используя Spirit Parser Framework ):

F( A() , B( GREAT( SOME , NOT ) ) , C( YES ) )

Для этого я пытаюсь использовать триправила для следующей грамматики:

template< typename Iterator , typename ExpressionAST >
struct InputGrammar : qi::grammar<Iterator, ExpressionAST(), space_type> {

    InputGrammar() : InputGrammar::base_type( ) {
       tag = ( qi::char_("a-zA-Z_")  >> *qi::char_("a-zA-Z_0-9") )[ push_back( at_c<0>(qi::_val) , qi::_1 ) ];
       command =  tag [ at_c<0>(qi::_val) = at_c<0>(qi::_1) ] >> "(" >> (*instruction >> ",")
                                        [ push_back( at_c<1>(qi::_val) , qi::_1 ) ]  >> ")";
       instruction = ( command | tag ) [qi::_val = qi::_1];
    }
    qi::rule< Iterator , ExpressionAST() , space_type > tag;
    qi::rule< Iterator , ExpressionAST() , space_type > command;
    qi::rule< Iterator , ExpressionAST() , space_type > instruction;
};

Обратите внимание, что мое правило тега просто пытается захватить идентификаторы, используемые в выражениях (имена 'function').Также обратите внимание, что подпись правила тега возвращает ExpressionAST вместо std::string, как в большинстве примеров.Причина, по которой я хочу сделать это, на самом деле довольно проста: я ненавижу использовать варианты и буду избегать их, если это возможно.Я думаю, было бы здорово сохранить торт и съесть его.

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

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

Итак, вопрос в том, что я не знаю, что не так с приведенным выше кодом.Как бы вы определили вышеуказанную грамматику?

Используемый мной тип ExpressionAST:

struct MockExpressionNode {
    std::string name;
    std::vector< MockExpressionNode > operands;

    typedef std::vector< MockExpressionNode >::iterator iterator;
    typedef std::vector< MockExpressionNode >::const_iterator const_iterator;

    iterator begin() { return operands.begin(); }
    const_iterator begin() const { return operands.begin(); }
    iterator end() { return operands.end(); }
    const_iterator end() const { return operands.end(); }

    bool is_leaf() const {
        return ( operands.begin() == operands.end() );
    }
};

BOOST_FUSION_ADAPT_STRUCT(
    MockExpressionNode,
    (std::string, name)
    (std::vector<MockExpressionNode>, operands)
)

1 Ответ

12 голосов
/ 20 июня 2010

Что касается отладки, то можно использовать обычный подход к просмотру.Это затрудняется тем, как вы отформатировали правила.Если вы отформатируете по духу примеров (~ один синтаксический анализатор на строку, одно выражение феникса на строку), точки останова будут гораздо более информативными.

В вашей структуре данных нет способа отличить A() отSOME в том смысле, что они оба листья (дайте мне знать, если я что-то упустил).Из вашего варианта комментария я не думаю, что это было вашим намерением, поэтому, чтобы отличить эти два случая, я добавил переменную-член bool commandFlag в MockExpressionNode (true для A() и false для SOME) с соответствующим слияниемАдаптерная строка.

Специально для кода необходимо передать правило запуска базовому конструктору, например:

InputGrammar() : InputGrammar::base_type(instruction) {...}

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

Для правила tag на самом деле есть два синтаксических анализатора qi::char_("a-zA-Z_"), который является _1 с типом char и *qi::char_("a-zA-Z_0-9"), который равен _2 с типом (в основном) vector<char>.Невозможно привести их в строку без авторул, но это можно сделать, прикрепив правило к каждому разбираемому символу:

tag =   qi::char_("a-zA-Z_")
        [ at_c<0>(qi::_val) = qi::_1 ];
    >> *qi::char_("a-zA-Z_0-9")           //[] has precedence over *, so _1 is 
        [ at_c<0>(qi::_val) += qi::_1 ];  //  a char rather than a vector<char>

Однако, гораздо проще очистить духом это преобразование.Поэтому определите новое правило:

qi::rule< Iterator , std::string(void) , ascii::space_type > identifier;
identifier %= qi::char_("a-zA-Z_") >> *qi::char_("a-zA-Z_0-9");

И не беспокойтесь об этом;).Затем тег становится

tag = identifier
      [
          at_c<0>(qi::_val) = qi::_1,
          ph::at_c<2>(qi::_val) = false //commandFlag
      ]

Для команды первая часть в порядке, но есть пара проблем с (*instruction >> ",")[ push_back( at_c<1>(qi::_val) , qi::_1 ) ].Это будет анализировать ноль или несколько правил инструкций, сопровождаемых ",".Он также пытается push_back a vector<MockExpressionNode> (не уверен, почему это скомпилировано, может быть, не было создано из-за отсутствующего правила запуска?).Я думаю, вам нужно следующее (с модификацией идентификатора):

command =
        identifier
        [
           ph::at_c<0>(qi::_val) = qi::_1, 
           ph::at_c<2>(qi::_val) = true    //commandFlag
        ]
    >>  "("
    >> -(instruction % ",")
        [
           ph::at_c<1>(qi::_val) = qi::_1
        ]
    >>  ")";

При этом используется необязательный оператор - и оператор списка %, последний эквивалентен instruction >> *("," >> instruction).Затем выражение феникса просто присваивает вектор непосредственно члену структуры, но вы также можете прикрепить действие непосредственно к совпадению инструкции и использовать push_back.

Правило инструкции в порядке, я просто упомяну, что оноэквивалентно instruction %= (command|tag).

И последнее: если на самом деле нет различий между A() и SOME (т. е. исходной структурой без commandFlag), вы можете написать этот анализатор, используя только авторулы:

template< typename Iterator , typename ExpressionAST >
struct InputGrammar : qi::grammar<Iterator, ExpressionAST(), ascii::space_type> {
   InputGrammar() : InputGrammar::base_type( command ) {
      identifier %=
             qi::char_("a-zA-Z_")
         >> *qi::char_("a-zA-Z_0-9");
      command %=
            identifier
         >> -(
            "("
         >> -(command % ",")
         >>  ")");
    }
    qi::rule< Iterator , std::string(void) , ascii::space_type > identifier;
    qi::rule< Iterator , ExpressionAST(void) , ascii::space_type > command;
};

Это большое преимущество использования обернутой структуры, которая тщательно моделирует входные данные.

...