Backtracking in scala parser combinators?
-
26-09-2019 - |
Question
It seems like scala's parser combinators don't backtrack. I have a grammar (see bottom) which can't parse the following "stmt" correctly:
copy in to out .
That should be easy to parse with backtracking:
stmt: (to out(copy in))
or am I missing something?
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}
Solution
You want to use PackratParsers
in 2.8. I think the packrat parser is the only backtracking parser.
Edit: as of mid-year 2015, you should use fastparse instead. It's not only much faster, but also easier to use (especially when building data structures from parsing).
OTHER TIPS
Your problem is not backtracking. The standard |
operator in scala.util.parsing.combinator
will do backtracking. Your problem is left-recursion (expr
→ call
→ args
→ smplargs
→ expr
). Packrat parsing may indeed help with that.