Scala - Combinator Parsing,替代品的顺序似乎很重要

Question

我是Scala的新手,我正在努力掌握组合器解析.所以我有一些代码可以解析逻辑原子(一阶逻辑中的谓词),如p(x,y,z)或p(x,1,q(a,b,c),z).我有这段小代码:

class Logic extends JavaTokenParsers {
    def functor: Parser[Any] = ident
    def term: Parser[Any] = predicate | ident | floatingPointNumber
    def predicate: Parser[Any] = functor~"("~repsep(term,",")~")"  
}

Functor是谓词符号,如pin p(x,y,z),term是一个常数或变量,如1或x,或a predicate,a predicate是一个复合词p(x,y,z).此代码可以正常工作,但如果我更改在term解析器中声明替代项的顺序,则会出现问题.也就是说,如果我写term解析器就好

def term: Parser[Any] = ident | floatingPointNumber | predicate

(这predicate是最后一个替代方案,虽然它是先前的),然后它无法解析"嵌套"表达式p(x,1,q(a,b,c),z)(虽然它仍适用于"平面"表达式p(x,y,z)).有人可以说明我在这里缺少什么吗？

非常感谢

Answer 1

订单事项

原因是A | B先尝试满足A,B只有A失败才会尝试.

这与|正则表达式(或一般的无上下文语法)不同.

在这种情况下"p(x,1,q(a,b,c),z)" p满足ident所以其他替代方案将不匹配(并且没有回溯).

出于这个原因,在具有冲突前缀的替代方案中,您可以将一个接受更长的字符串放在第一个(或者您知道的那个将导致满足更多短语的字符串).

最长的替代匹配

请注意,您可以使用|||组合器:

def term: Parser[Any] = ident ||| floatingPointNumber ||| predicate

根据Scala文档,|||解析器组合器匹配具有最长匹配组成的替代方案.