scala - 解析器组合器 : Does repsep allows back-tracking?

Question

考虑这样的解析器示例:

object TestParser extends RegexParsers {
    override protected val whiteSpace = """[ \t]*""".r  

    def eol = """(\r?\n)+""".r
    def item = "[a-zA-Z][a-zA-Z0-9-]*".r
    def list = "items:" ~> rep1sep(item,",") 
    def constraints = "exclude:" ~> item

    def itemsDefinition = (rep1sep(list, eol) ~ repsep(constraints,eol))
}

如果我尝试解析此输入(没有两行包含排除工作正常):

items: item1, item2, item3, item3, item4
items: item2, item3, item3, item5, item4    
items: item4, item5, item6, item10      
items: item1, item2, item3
exclude: item1
exclude: item2

我收到以下错误:

[5.5] failure: `items:' expected but `e' found

       exclude: item1

       ^

问题很明显这一行:

def itemsDefinition = (rep1sep(list, eol) ~ repsep(constraints,eol))

它不起作用的原因是什么。它与回溯有关吗？我必须有哪些替代方法才能使其发挥作用？

Answer 1

您需要在列表和约束之间使用 eol

(rep1sep(list, eol) <~ eol) ~ repsep(constraint,eol)

完成答案:

您的语法将 eol 指定为列表之间的分隔符，而不是终止符。它会接受一个输入，其中第一个 exclude出现在最后一个 item3 之后(带有空格，但不是新行)。

在您的解析器到达不需要的 eol 之后，它寻找 items ，并找到 excludes反而。这给出了显示的错误消息。然后，解析器确实回溯到上一个新行。它考虑了列表部分停在那里的可能性，并寻找排除。但是如果找到一个 eol 代替。所以另一个可能的错误信息是 "excludes expected, eol found" ，在这种情况下会更有帮助

当语法中有选择，并且没有分支成功时，解析器返回最远位置的错误，这通常是正确的策略。假设您的语法允许 "if"或 "for" ，输入为 "if !!!" .关于 if分支，错误将类似于 "(" expected, "!" found .关于 for分支，消息将是 "for expected, if found" .显然，来自 if 的消息出现在第二个 token 上的分支比来自 for 的消息要好得多。分支，在第一个标记上，根本不相关。

关于分隔符/终止符的问题，您可以考虑:

分隔符(; 帕斯卡):repsep(item, separator)

终止符(; 在 C 中):rep(item <~ terminator)

灵活:repsep(item, separator) <~ separator?

最后一个将允许在没有任何项目之后使用单个分隔符。如果这是不可取的，也许 (rep1sep(item, separator) <~ separator?)? .