解析器组合器:repsep是否允许反向跟踪？

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",在这种情况下会更有帮助

当语法中有选择,并且没有分支成功时,解析器返回最远位置的错误,这通常是正确的策略.假设你的语法允许a "if"或a "for",输入是"if !!!".在if分支上,错误就像是"(" expected, "!" found.在for分支上,消息将是"for expected, if found".显然,来自if分支的消息(出现在第二个令牌上)比来自for分支的消息在第一个令牌上更好,而根本不相关.

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

• 分隔符(;在Pascal中):repsep(item, separator)
• 终结者(;在C中):rep(item <~ terminator)
• 灵活: repsep(item, separator) <~ separator?

在没有任何项目之后,最后一个将允许单个分隔符.如果这是不合需要的,也许吧(rep1sep(item, separator) <~ separator?)?.