Backtracking в компиляторах scala parser?

Question

Кажется, что комбайны Scars's parser не возвращаются. У меня есть грамматики (см снизу), которые не могут разобрать следующее «STMT» правильно:

copy in to out . 

Это должно быть легко разобрать с откатами:

stmt: (to out(copy in)) 

или я что-то отсутствует?

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

Вы хотите использовать PackratParsers в 2.8. Я думаю, что парсер parrat является единственным парсером обратного отслеживания.

Редактировать: начиная с середины 2015 года вместо этого вы должны использовать fastparse. Это не только намного быстрее, но и проще в использовании (особенно при построении структур данных при разборе).

Answer 2

Ваша проблема не в обратном направлении. Стандартный оператор | в scala.util.parsing.combinator выполнит откат. Ваша проблема - левая рекурсия (expr → call → args → smplargs → expr). Анализ Packrat действительно может помочь в этом.