Backtracking in Scala-Parser-Kombinatoren?

Question

Es scheint, dass Scala Parser Kombinator nicht zurückverfolgen. Ich habe eine Grammatik (siehe unten), das folgende „Anw“ nicht analysieren kann richtig:

copy in to out . 

so einfach sein sollte mit Rückzieher zu analysieren:

stmt: (to out(copy in)) 

oder bin ich etwas fehlt?

Parser:

type ExprP = Parser[Expr] 
type ValueP = Parser[ValExpr] 
type CallP = Parser[Call] 
type ArgsP = Parser[Seq[Expr]] 

val ident  = "[a-zA-Z\\+\\-\\*/%><\\\\\\=]+".r 
val sqstart = "\\["       .r 
val sqend  = "\\]"       .r 
val del  = ","       .r 
val end  = "\\."       .r 

def stmt: ExprP  = expr <~ end 
def expr: ExprP  = ucall | call | value 
def value: ValueP = ident ^^ {str => IdentExpr(str)} 
def call: CallP  = (args ~ ident ~ expr) ^^ {case args ~ method ~ upon => Call(args, method, upon)} 
def ucall: CallP  = (ident ~ expr) ^^ {case method ~ upon => Call(Seq(), method, upon)} 
def args: ArgsP  = advargs | smplargs 
def smplargs: ArgsP = expr ^^ {e => Seq(e)} 
def advargs: ArgsP = (sqstart ~> repsep(expr, del) <~ sqend) ^^ {seq => seq} 

Answer 1

Sie wollen PackratParsers in 2.8 verwenden. Ich denke, der Packrat-Parser ist der einzige Backtracking-Parser.

Edit: ab Mitte des Jahres 2015 sollten Sie stattdessen verwenden. Es ist nicht nur viel schneller, sondern auch einfacher zu benutzen (besonders beim Aufbau von Datenstrukturen aus dem Parsing).

Answer 2

Ihr Problem ist kein Backtracking. Der Standard | Operator in scala.util.parsing.combinator wird Backtracking ausführen. Ihr Problem ist Links-Rekursion (expr → call → args → smplargs → expr). Packat-Parsing kann dabei helfen.