Backtracking in scala parser combinatori?

Question

Sembra che i combinatori di parser di scala non tornino indietro. Ho una grammatica (vedi in basso) che non può analizzare il seguente "stmt" correttamente:

copy in to out . 

che dovrebbe essere facile da analizzare con backtracking:

stmt: (to out(copy in)) 

o mi sto perdendo qualcosa?

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

Si desidera utilizzare PackratParsers in 2.8. Penso che il parser Packrat è l'unico parser backtracking.

Modifica: a partire dalla metà dell'anno 2015, invece, è necessario utilizzare fastparse. Non è solo molto più veloce, ma anche più facile da usare (specialmente quando si costruiscono strutture dati dall'analisi).

Answer 2

Il tuo problema non è il backtracking. L'operatore standard | in scala.util.parsing.combinator eseguirà il backtracking. Il tuo problema è ricorsione sinistra (expr → → args → smplargs → expr). L'analisi di Packrat può davvero aiutare in questo.