使用Boost Spirit X3解析Newick树语法失败求助

尝试用Boost Spirit X3解析Newick树格式，内部语法测试用例全部通过，但完整树解析器仅能通过第一个测试用例，其余均失败。

最小复现代码 #

namespace quetzal::newick::parser
{
  namespace x3 = boost::spirit::x3;

  using x3::alpha;
  using x3::alnum;
  using x3::double_;
  using x3::rule;
  using x3::lit;

  rule<struct branch> branch{"branch"};

  auto name    = alpha >> *alnum; // to be improved later
  auto length  = ':' >> double_;
  auto leaf    = -name;
  auto internal= '(' >> (branch % ',') >> ')' >> -name;
  auto subtree = leaf | internal;
  auto tree    = subtree >> ';';

  auto const branch_def = subtree >> -length;

  BOOST_SPIRIT_DEFINE(branch);
}

测试用例情况 #

内部语法测试（全部通过） #

BOOST_AUTO_TEST_CASE(internal_grammar)
{
  std::vector<std::string> inputs =
  {
    "(,)",
    "(A,B)F",
    "(A:10,B:10)F"
  };

  for(const auto& input : inputs)
  {
    auto iter = input.begin();
    auto iter_end = input.end();
    bool r = phrase_parse(iter, iter_end, quetzal::newick::parser::internal, x3::space );
    BOOST_CHECK(r && iter == iter_end);
  }
}

完整解析器测试（仅第一个用例通过） #

BOOST_AUTO_TEST_CASE(full_grammar)
{
  std::vector<std::string> inputs =
  {
    ";",
    "(,);",
    "(,,(,));",
    "(A,B,(C,D));",
    "(A,B,(C,D)E)F;",
    "(:0.1,:0.2,(:0.3,:0.4):0.5);",
    "(:0.1,:0.2,(:0.3,:0.4):0.5):0.0;",
    "(A:0.1,B:0.2,(C:0.3,D:0.4):0.5);",
    "(A:0.1,B:0.2,(C:0.3,D:0.4)E:0.5)F;",
    "((B:0.2,(C:0.3,D:0.4)E:0.5)F:0.1)A;"
  };

  for(const auto& input : inputs)
  {
    auto iter = input.begin();
    auto iter_end = input.end();
    bool r = phrase_parse(iter, iter_end, quetzal::newick::parser::tree, x3::space );
    BOOST_CHECK(r && iter == iter_end);
  }
}

问题根源 #

核心问题在于subtree规则的顺序：当前定义为leaf | internal，而leaf是-name（可选名称），这意味着leaf永远匹配成功（要么匹配名称，要么匹配空）。Spirit的顺序选择是优先尝试第一个规则，一旦leaf匹配成功，就不会再尝试internal规则。

比如解析(,);时，subtree先尝试leaf，匹配空后，tree规则期望匹配;，但此时输入指针仍停留在(位置，导致匹配失败。

解决方案 #

将subtree的规则顺序反转，优先尝试internal规则，只有当输入不是(开头时，才尝试leaf：

auto subtree = internal | leaf;

修改后的完整parser代码：

namespace quetzal::newick::parser
{
  namespace x3 = boost::spirit::x3;

  using x3::alpha;
  using x3::alnum;
  using x3::double_;
  using x3::rule;
  using x3::lit;

  rule<struct branch> branch{"branch"};

  auto name    = alpha >> *alnum; // to be improved later
  auto length  = ':' >> double_;
  auto leaf    = -name;
  auto internal= '(' >> (branch % ',') >> ')' >> -name;
  auto subtree = internal | leaf; // 反转规则顺序
  auto tree    = subtree >> ';';

  auto const branch_def = subtree >> -length;

  BOOST_SPIRIT_DEFINE(branch);
}

修改后所有测试用例均可正常通过：

• 遇到(开头的输入时，优先匹配internal规则，正确解析内部节点
• 遇到名称或空节点时，internal规则匹配失败，再尝试leaf规则
• 空输入;仍能正常匹配（internal失败后，leaf匹配空，再匹配;）

额外优化建议 #

1. 完善名称规则：当前name仅支持字母开头的字母数字组合，Newick格式允许名称包含除()、,、:、;外的任意字符，甚至带空格的名称（需用单/双引号包裹），可扩展规则：

auto quoted_name = x3::lexeme['"' >> *(x3::char_ - '"') >> '"' | '\'' >> *(x3::char_ - '\'') >> '\''];
auto unquoted_name = +(x3::char_ - x3::char_("(),:;"));
auto name = quoted_name | unquoted_name;

2. 明确固定字符匹配：建议将语法中的固定字符用x3::lit包裹，避免歧义：

auto internal= x3::lit('(') >> (branch % x3::lit(',')) >> x3::lit(')') >> -name;
auto length  = x3::lit(':') >> double_;
auto tree    = subtree >> x3::lit(';');

内容的提问来源于stack exchange，提问作者WaterFox