使用 Boost::Spirit 解析前提条件和递归

Question

我正在尝试使用 Boost::Spirit 解析 PDDL 文件，但在将前提条件解析为结构时遇到了一些问题。我很难理解关于如何将条件放入我的结构和递归的 Boost 手册。

我在下面给出了一段代码，应该可以很好地说明问题。必须解析如下所示的字符串：

:precondition
(and
  (at-pos ?r ?pos)
  (not (has-pos ?m ?pos))
)

到目前为止我的代码看起来像这样，但我几乎可以肯定我不明白 at_c 是如何工作的，因为我还没有使用 Boost::Phoenix 的经验。

predi_param = '?' >> name_type;
predi = '(' 
    >> name_type
    >> +predi_param
    >> ')';
literal = ( 
    ( '(' >> lit("not") >>
      predi       [at_c<0>(_val) = false]
      >> ')'
    )
    | predi       [at_c<0>(_val) = true]
  )
  >> ')';
pred_list = ( '(' >> lit("and") >> (*pred_list) >> ')')
  | literal;
preconditions = lit(":precondition") >> pred_list;

qi::rule<Iterator, std::string(), ascii::space_type> predi_param;
qi::rule<Iterator, Predicate(), ascii::space_type> predi;
qi::rule<Iterator, Literal(), ascii::space_type> literal;
qi::rule<Iterator, std::vector<Literal>(), ascii::space_type> preconditions, pred_list;

我的 AST 看起来像这样：

struct Predicate
{
  std::string name;
  std::vector<std::string> predicate_params;
};  
struct Literal
{
  bool condition;
  Predicate predicate;
};

BOOST_FUSION_ADAPT_STRUCT(
    pddl_parser::Literal,
    (bool, condition)
    (pddl_parser::Predicate, predicate)
)

BOOST_FUSION_ADAPT_STRUCT(
    pddl_parser::Predicate,
    (std::string, name)
    (std::vector<std::string>, predicate_params)
)

编译会导致编译错误：

parser.cpp:67:17:   required from ‘pddl_parser::domain_parser<Iterator>::domain_parser() [with Iterator = __gnu_cxx::__normal_iterator<const char*, std::__cxx11::basic_string<char> >]’
parser.cpp:136:10:   required from here
/usr/include/boost/spirit/home/qi/detail/assign_to.hpp:153:20: error: no matching function for call to ‘pddl_parser::Literal::Literal(const std::vector<pddl_parser::Literal>&)’
             attr = static_cast<Attribute>(val);
                    ^~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from parser.cpp:11:0:
./pddlast.h:23:10: note: candidate: pddl_parser::Literal::Literal()
   struct Literal
          ^~~~~~~
./pddlast.h:23:10: note:   candidate expects 0 arguments, 1 provided
./pddlast.h:23:10: note: candidate: pddl_parser::Literal::Literal(const pddl_parser::Literal&)
./pddlast.h:23:10: note:   no known conversion for argument 1 from ‘const std::vector<pddl_parser::Literal>’ to ‘const pddl_parser::Literal&’
./pddlast.h:23:10: note: candidate: pddl_parser::Literal::Literal(pddl_parser::Literal&&)
./pddlast.h:23:10: note:   no known conversion for argument 1 from ‘const std::vector<pddl_parser::Literal>’ to ‘pddl_parser::Literal&&’

如果我出于测试目的将 pred_list 重新格式化为 pred_list = ( '(' >> *literal) >> ')'); 代码编译但仍然没有成功，尽管我将 (and ) 取出。我的印象是我完全错了，但找不到任何东西。这是我第一次尝试使用 Boost::Spirit.

Answer 1

嗯，你说

pred_list = ( '(' >> *literal) >> ')');

编译，但以下不编译：

pred_list = ( '(' >> lit("and") >> (*pred_list) >> ')') | literal;

仔细一看，还真有道理。由于 pred_list 的声明属性类型为 std::vector<Literal>，显然重复文字 (*literal) 可能与自动属性传播兼容。

现在，查看第二个规则定义。它解析了一堆无属性文字（'('、"and"、')'），然后……*pred_list。如果 pred_list 声明了一个 std::vector<Literal> 属性，那么 *pred_list 肯定会合成一个 std::vector<std::vector<Literal> >。更糟糕的是，"after-thought" | literal 使合成属性等同于 variant<vector<vector<Literal>>, Literal>.

是的。这有点乱。您的 AST 根本不反映规则，反之亦然。

前方的道路

您或许应该重述您的问题，删除失败的实施部分并描述目标。如果我们能知道真正的语法要求，/那么/我们就可以推导出一个与之匹配的正确的 AST。

插曲

在中场休息期间，让我简化 literal 的规则。（有关背景资料，请参阅 Boost spirit semantic actions on qi::rule）：

literal = 
    '(' >> matches("not") >> predi >> ')'
    | qi::attr(false) >> predi
    ;

PS It appears that a stray cat also typed an extra unbalanced
    >> ')';
at the end there?

有建设性的猜测

仅从示例输入来看，我打赌您只想解析 scheme-like function applications 形式的

(function_name arguments)

应用程序可以嵌套的位置。因此，参数要么是原子，要么是函数应用程序。

好吧，让我们快速地在上面放一个 AST：

namespace AST {
    using Atom = std::string;

    struct Application;

    using Expression = boost::variant<Atom, Application>;

    struct Application {
        Atom function;
        std::vector<Expression> arguments;
    };
}

这很简单，对吧。这是解析前提条件的最简单语法：

template <typename Iterator>
struct Precondition : qi::grammar<Iterator, AST::Expression()> {
    Precondition() : Precondition::base_type(precondition) {
        using namespace qi;

        atom         = +(graph - '(' - ')');
        application  = '(' >> atom >> *expression >> ')';
        expression   = atom | application;

        precondition = skip(ascii::space) [":precondition" >> expression];

        BOOST_SPIRIT_DEBUG_NODES((precondition)(expression)(application)(atom))
    }

  private:
    using Skipper = qi::ascii::space_type;
    qi::rule<Iterator, AST::Application(), Skipper> application;
    qi::rule<Iterator, AST::Expression(), Skipper>  expression;

    // lexemes
    qi::rule<Iterator, AST::Expression()> precondition;
    qi::rule<Iterator, AST::Atom()> atom;
};

请注意每条规则如何仅重述相应的 AST 节点。 precondition 也对外界隐藏船长。

输出：Live On Coliru

版画

Parsed (and (at-pos ?r ?pos) (not (has-pos ?m ?pos)))

并启用 BOOST_SPIRIT_DEBUG：

<precondition>
  <try>:precondition\n      </try>
  <expression>
    <try>\n                   </try>
    <atom>
      <try>(and\n               </try>
      <fail/>
    </atom>
    <application>
      <try>(and\n               </try>
      <atom>
        <try>and\n                </try>
        <success>\n                   </success>
        <attributes>[[a, n, d]]</attributes>
      </atom>
      <expression>
        <try>\n                   </try>
        <atom>
          <try>(at-pos ?r ?pos)\n   </try>
          <fail/>
        </atom>
        <application>
          <try>(at-pos ?r ?pos)\n   </try>
          <atom>
            <try>at-pos ?r ?pos)\n    </try>
            <success> ?r ?pos)\n          </success>
            <attributes>[[a, t, -, p, o, s]]</attributes>
          </atom>
          <expression>
            <try> ?r ?pos)\n          </try>
            <atom>
              <try>?r ?pos)\n           </try>
              <success> ?pos)\n             </success>
              <attributes>[[?, r]]</attributes>
            </atom>
            <success> ?pos)\n             </success>
            <attributes>[[?, r]]</attributes>
          </expression>
          <expression>
            <try> ?pos)\n             </try>
            <atom>
              <try>?pos)\n              </try>
              <success>)\n                  </success>
              <attributes>[[?, p, o, s]]</attributes>
            </atom>
            <success>)\n                  </success>
            <attributes>[[?, p, o, s]]</attributes>
          </expression>
          <expression>
            <try>)\n                  </try>
            <atom>
              <try>)\n                  </try>
              <fail/>
            </atom>
            <application>
              <try>)\n                  </try>
              <fail/>
            </application>
            <fail/>
          </expression>
          <success>\n                   </success>
          <attributes>[[[a, t, -, p, o, s], [[?, r], [?, p, o, s]]]]</attributes>
        </application>
        <success>\n                   </success>
        <attributes>[[[a, t, -, p, o, s], [[?, r], [?, p, o, s]]]]</attributes>
      </expression>
      <expression>
        <try>\n                   </try>
        <atom>
          <try>(not (has-pos ?m ?po</try>
          <fail/>
        </atom>
        <application>
          <try>(not (has-pos ?m ?po</try>
          <atom>
            <try>not (has-pos ?m ?pos</try>
            <success> (has-pos ?m ?pos))\n</success>
            <attributes>[[n, o, t]]</attributes>
          </atom>
          <expression>
            <try> (has-pos ?m ?pos))\n</try>
            <atom>
              <try>(has-pos ?m ?pos))\n </try>
              <fail/>
            </atom>
            <application>
              <try>(has-pos ?m ?pos))\n </try>
              <atom>
                <try>has-pos ?m ?pos))\n  </try>
                <success> ?m ?pos))\n         </success>
                <attributes>[[h, a, s, -, p, o, s]]</attributes>
              </atom>
              <expression>
                <try> ?m ?pos))\n         </try>
                <atom>
                  <try>?m ?pos))\n          </try>
                  <success> ?pos))\n            </success>
                  <attributes>[[?, m]]</attributes>
                </atom>
                <success> ?pos))\n            </success>
                <attributes>[[?, m]]</attributes>
              </expression>
              <expression>
                <try> ?pos))\n            </try>
                <atom>
                  <try>?pos))\n             </try>
                  <success>))\n                 </success>
                  <attributes>[[?, p, o, s]]</attributes>
                </atom>
                <success>))\n                 </success>
                <attributes>[[?, p, o, s]]</attributes>
              </expression>
              <expression>
                <try>))\n                 </try>
                <atom>
                  <try>))\n                 </try>
                  <fail/>
                </atom>
                <application>
                  <try>))\n                 </try>
                  <fail/>
                </application>
                <fail/>
              </expression>
              <success>)\n                  </success>
              <attributes>[[[h, a, s, -, p, o, s], [[?, m], [?, p, o, s]]]]</attributes>
            </application>
            <success>)\n                  </success>
            <attributes>[[[h, a, s, -, p, o, s], [[?, m], [?, p, o, s]]]]</attributes>
          </expression>
          <expression>
            <try>)\n                  </try>
            <atom>
              <try>)\n                  </try>
              <fail/>
            </atom>
            <application>
              <try>)\n                  </try>
              <fail/>
            </application>
            <fail/>
          </expression>
          <success>\n                   </success>
          <attributes>[[[n, o, t], [[[h, a, s, -, p, o, s], [[?, m], [?, p, o, s]]]]]]</attributes>
        </application>
        <success>\n                   </success>
        <attributes>[[[n, o, t], [[[h, a, s, -, p, o, s], [[?, m], [?, p, o, s]]]]]]</attributes>
      </expression>
      <expression>
        <try>\n                   </try>
        <atom>
          <try>)</try>
          <fail/>
        </atom>
        <application>
          <try>)</try>
          <fail/>
        </application>
        <fail/>
      </expression>
      <success></success>
      <attributes>[[[a, n, d], [[[a, t, -, p, o, s], [[?, r], [?, p, o, s]]], [[n, o, t], [[[h, a, s, -, p, o, s], [[?, m], [?, p, o, s]]]]]]]]</attributes>
    </application>
    <success></success>
    <attributes>[[[a, n, d], [[[a, t, -, p, o, s], [[?, r], [?, p, o, s]]], [[n, o, t], [[[h, a, s, -, p, o, s], [[?, m], [?, p, o, s]]]]]]]]</attributes>
  </expression>
  <success></success>
  <attributes>[[[a, n, d], [[[a, t, -, p, o, s], [[?, r], [?, p, o, s]]], [[n, o, t], [[[h, a, s, -, p, o, s], [[?, m], [?, p, o, s]]]]]]]]</attributes>
</precondition>

这个例子告诉你的是：

如何在 AST 中表示变体数据类型
如何通过它实现递归（更多高级信息另见documentation）

它不会立即根据 PDDL 规范验证 AST。我完全不确定你打算实施多少，所以我认为更通用的启动器可能会有帮助。

完整列表

Live On Coliru

#define BOOST_SPIRIT_DEBUG
#include <boost/fusion/adapted/struct.hpp>
#include <boost/spirit/include/qi.hpp>

namespace AST {
    using Atom = std::string;

    struct Application;

    using Expression = boost::variant<Atom, Application>;

    struct Application {
        Atom function;
        std::vector<Expression> arguments;

        friend std::ostream& operator<<(std::ostream& os, Application const& a) {
            os << "(" << a.function;
            for (auto& arg : a.arguments)
                os << " " << arg;
            return os << ")";
        }
    };
}

BOOST_FUSION_ADAPT_STRUCT(AST::Application, function, arguments)

namespace pddl_parser {

    namespace qi    = boost::spirit::qi;

    template <typename Iterator>
    struct Precondition : qi::grammar<Iterator, AST::Expression()> {
        Precondition() : Precondition::base_type(precondition) {
            using namespace qi;

            atom         = +(graph - '(' - ')');
            application  = '(' >> atom >> *expression >> ')';
            expression   = atom | application;

            precondition = skip(ascii::space) [":precondition" >> expression];

            BOOST_SPIRIT_DEBUG_NODES((precondition)(expression)(application)(atom))
        }

      private:
        using Skipper = qi::ascii::space_type;
        qi::rule<Iterator, AST::Application(), Skipper> application;
        qi::rule<Iterator, AST::Expression(), Skipper>  expression;

        // lexemes
        qi::rule<Iterator, AST::Expression()> precondition;
        qi::rule<Iterator, AST::Atom()> atom;
    };
}

int main() {
    using It = std::string::const_iterator;

    for (std::string const& input : {
            R"--(:precondition
                    (and
                      (at-pos ?r ?pos)
                      (not (has-pos ?m ?pos))
                    ))--"
            })
    {
        std::cout << "-----\n";
        It f = input.begin(), l = input.end();

        AST::Expression precondition;
        bool ok = parse(f, l, pddl_parser::Precondition<It>{}, precondition);

        if (ok) {
            std::cout << "Parsed " << precondition << "\n";
        } else {
            std::cout << "Parse Failed\n";
        }

        if (f != l) {
            std::cout << "Remaining unparsed input: '" << std::string(f, l) << "'\n";
        }
    }
}

使用 Boost::Spirit 解析前提条件和递归

Parsing preconditions and recursion with Boost::Spirit

c++

boost

boost-spirit

boost-spirit-qi

前方的道路

插曲

有建设性的猜测

完整列表