Backtracking in Scala -Parser -Kombinatoren?
-
26-09-2019 - |
Frage
Es scheint, als würde Scalas Parser -Kombinators nicht zurückverfolgen. Ich habe eine Grammatik (siehe unten), die die folgenden "stmt" nicht richtig analysieren kann:
copy in to out .
Das sollte leicht mit Backtracking analysieren sein:
stmt: (to out(copy in))
Oder vermisst ich etwas?
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}
Lösung
Sie möchten verwenden PackratParsers
in 2,8. Ich denke, der Packrat -Parser ist der einzige Backtracking -Parser.
Bearbeiten: Ab Mitte des Jahres 2015 sollten Sie verwenden Fastparse stattdessen. Es ist nicht nur viel schneller, sondern auch einfacher zu bedienen (insbesondere beim Erstellen von Datenstrukturen durch Parsen).
Andere Tipps
Ihr Problem ist nicht zurückverfolgt. Der Standard |
Bediener in scala.util.parsing.combinator
wird Backtracking machen. Ihr Problem ist eine Rekursion (links) (expr
→ call
→ args
→ smplargs
→ expr
). Packrat -Parsen kann tatsächlich dabei helfen.