Tornando indietro nel combinatori scala parser?
-
26-09-2019 - |
Domanda
Sembra combinatori parser di Scala Non backtrack. Ho una grammatica (vedi in basso) che non può analizzare il seguente "stmt" correttamente:
copy in to out .
Questo 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}
Soluzione
Si desidera utilizzare PackratParsers
in 2.8. Credo che il parser packrat è il parser unico backtracking.
Edit: a partire da metà 2015, è necessario utilizzare fastparse . Non è solo molto più veloce, ma anche più facile da usare (in particolare per la costruzione di strutture di dati da analisi).
Altri suggerimenti
Il problema non è facendo marcia indietro. L'operatore |
standard scala.util.parsing.combinator
farà backtracking. Il tuo problema è ricorsione sinistra (expr
→ → call
args
→ → smplargs
expr
). Packrat analisi può davvero aiutare in questo.