Boost Spirit 2 - 符号扩展和回溯

Question

我在指定和解析相当简单的语法时遇到了一些问题。

vertex = char+
edge = vertex " -> " vertex
start = ((vertex | edge) eol)*

input = "a\nb\na -> b\n"

Spirit 正在执行以下操作：

"a" -> vertex
"\n" -> eol
-> start

"b" -> vertex
"\n" -> eol
-> start

和

"a" -> vertex
terminate

而不是最后识别边缘并解析整个输入。也就是说，它可以解析整个输入，但事实并非如此。它不应该回溯并尝试使用替代规则进行解析吗？从而完成启动规则。

是因为Spirit用的是PEG吗？ (http://www.boost.org/doc/libs/1_57_0/libs/spirit/doc/html/spirit/abstracts/parsing_expression_grammar.html#spirit.abstracts.parsing_expression_grammar.alternatives)

最小工作示例：

#include <cstdio>
#include <string>
#include <boost/spirit/include/qi.hpp>

namespace qi = boost::spirit::qi;

void print(const std::string & str) {
  printf("%s\n", str.c_str());
}

void print_eol() {
  printf("eol\n");
}

int main() {
  std::string str = "a\nb\na -> b\n";
  std::string::iterator it = str.begin(), begin = str.begin(), end = str.end();

  qi::rule<std::string::iterator, std::string()> vertex = +qi::alnum;
  qi::rule<std::string::iterator, std::string()> edge = vertex >> " -> " >> vertex;
  qi::rule<std::string::iterator> start = (vertex[&print] | edge[&print]) % qi::eol[&print_eol];

  bool matched = parse(it, end, start);

  if (matched) {
    printf("matched\n");
  }
  if (it == end) {
    printf("all\n");
  } else if (it != begin) {
    printf("some\n");
  } else {
    printf("none\n");
  }

  return 0;
}

输出：

$ ./a.out
a
eol
b
eol
a
matched
some

我在 MSYS2 上使用 Boost 1.57.0 和 Clang 3.5.1。

Answer 1

看来你回答了你自己的问题：是的，这是因为 PEG 语法本质上是贪婪的，从左到右的匹配。

注释

从语义动作打印不是一个公平的测试，因为即使解析器确实回溯（它可以在单个表达式失败时继续下一个替代分支）副作用已经被触发。这是使用语义操作的主要缺点 - 除非你小心 (Boost Spirit: "Semantic actions are evil"?)
BOOST_SPIRIT_DEBUG 和 BOOST_SPIRIT_DEBUG_NODES 宏就是为了这个目的而提供的，并提供了更多信息

这里显而易见的解决方案是

重新排序分支：

start = (edge[&print] | vertex[&print]) % qi::eol[&print_eol];

Live On Coliru

a
eol
b
eol
a -> b
matched all

左 - 因式分解：

start = (vertex[print] >> -(" -> " >> vertex)[print]) % qi::eol[&print_eol];

Live On Coliru

a
eol
b
eol
a
b
matched all

如果除了满足您对 PEG 语法的好奇心之外，您还想要一些现实生活中的想法，您可以在 SO 答案中搜索关于如何在大约十几个 boost-spirit 答案中解析成 vertices/edges 单独集合的想法所以，我记得。

Boost Spirit 2 - 符号扩展和回溯

Boost Spirit 2 - Symbol expansion and backtracking

c++

boost

boost-spirit

boost-spirit-qi