1

我读过的所有内容都表明 Treetop 会像正则表达式一样回溯，但我很难做到这一点。

假设我有以下语法：

grammar TestGrammar
  rule open_close
    '{' .+ '}'
  end
end

这与字符串不匹配{abc}。我怀疑那是因为从这封信开始.+就消耗了一切。a即abc}当我只希望它消费时它正在消费abc。

这似乎与类似的正则表达式不同。正则表达式/{.+}/将匹配{abc}。据我了解，这是可能的，因为正则表达式引擎在将关闭}作为 的一部分使用后回溯.+，然后无法匹配。

那么 Treetop 可以这样回溯吗？如果是这样，怎么做？

我知道您可以使用否定来匹配“除 a 之外的任何内容}”。但这不是我的本意。假设我希望能够匹配字符串{ab}c}。在这种情况下，我想要的标记是开头{、中间字符串ab}c和结尾}。这是一个人为的示例，但在使用嵌套表达式（如{a b {c d}}.

4

1 回答 1

2

Treetop 是Parsing Expression Grammar解析器的一个实现。PEG 的优点之一是它们结合了灵活性、速度和内存要求。然而，这种平衡行为有一些权衡。

引用维基百科文章：

零个或多个、一个或多个和可选运算符分别消耗其子表达式 e 的零个或多个、一个或多个或零个或一个连续重复。然而，与上下文无关文法和正则表达式不同的是，这些运算符总是表现得很贪婪，尽可能多地消耗输入并且从不回溯。[...] 表达式(a* a)总是会失败，因为第一部分(a*)永远不会留下任何 a 供第二部分匹配。

（强调我的。）

简而言之：虽然某些 PEG 运营商可以回溯以尝试采取另一条路线，但+运营商不能。

相反，为了匹配嵌套的子表达式，您希望在分隔的子表达式（首先检查）后跟非表达式字符之间创建一个交替。类似（未经测试）：

grammar TestGrammar
  rule open_close
    '{' contents '}'
  end
  rule contents
    open_close / non_brackets
  end
  rule non_brackets
    # …
  end
end
于 2012-10-17T05:04:49.690 回答