Scala Parser Combinators Tricks für rekursive bnf?

Question

Im Versuch, diese Syntax zu entsprechen:

import scala.util.parsing.combinator.PackratParsers 
import scala.util.parsing.combinator.syntactical._ 

object Dotter extends StandardTokenParsers with PackratParsers { 
    lexical.delimiters ++= List(".",";") 
    def pgm = repsep(expr,";") 
    def expr :Parser[Any]= ident | expr~"."~num 
    def num = numericLit 

     def parse(input: String) = 
    phrase(pgm)(new PackratReader(new lexical.Scanner(input))) match { 
     case Success(result, _) => println("Success!"); Some(result) 
     case n @ _ => println(n);println("bla"); None 
    } 

    def main(args: Array[String]) { 
     val prg = "x.1.2.3;" + 
      "y.4.1.1;" + 
      "z;" + 
      "n.1.10.30" 


      parse(prg); 
    } 
} 

Aber das funktioniert nicht:

pgm ::= exprs 
exprs ::= expr [; exprs] 
expr ::= ID | expr . [0-9]+ 

wie Meine scala packrat Parser combinator aussieht. Entweder es „passt gierig“ und sagt mir:

[1.2] failure: end of input expected 
x.1.2.3;y.4.1.1;z;n.1.10.30 

oder wenn ich die | zu einem ||| ändern bekomme ich einen Stackoverflow:

Exception in thread "main" java.lang.StackOverflowError 
at java.lang.Character.isLetter(Unknown Source) 
at java.lang.Character.isLetter(Unknown Source) 
at scala.util.parsing.combinator.lexical.Lexical$$anonfun$letter$1.apply(Lexical.scala:32) 
at scala.util.parsing.combinator.lexical.Lexical$$anonfun$letter$1.apply(Lexical.scala:32) 
... 

ich kindoff verstehen, warum ich die Fehler bekommen; Was kann ich tun, um eine Syntax wie oben zu analysieren? Dabei spielt es keine mir scheinen, dass esoterische

EDIT: Basierend auf dem Papier in http://scala-programming-language.1934581.n4.nabble.com/Packrat-parser-guidance-td1956908.html verwiesen ich, dass eigentlich mein Programm nur knapp sein Ziel die neue packrat Parser herausgefunden.

Ie. ändern Parser[Any]-PackratParser[Any] und verwenden lazy val statt def

ich die oben diese neu geschrieben:

import scala.util.parsing.combinator.PackratParsers 
import scala.util.parsing.combinator.syntactical._ 

object Dotter extends StandardTokenParsers with PackratParsers { 
    lexical.delimiters ++= List(".",";") 
    lazy val pgm : PackratParser[Any] = repsep(expr,";") 
    lazy val expr :PackratParser[Any]= expr~"."~num | ident 
    lazy val num = numericLit 

    def parse(input: String) = 
    phrase(pgm)(new PackratReader(new lexical.Scanner(input))) match { 
     case Success(result, _) => println("Success!"); Some(result) 
     case n @ _ => println(n);println("bla"); None 
    } 

    def main(args: Array[String]) { 
     val prg = "x.1.2.3 ;" + 
      "y.4.1.1;" + 
      "z;" + 
      "n.1.10.30" 


      parse(prg); 
    } 
} 

Answer 1

Das Problem ist (zumindest teilweise), dass Sie nicht tatsächlich Packrat-Parser verwenden. Lesen Sie die Dokumentation für PackratParsers Merkmal der Scala, die

Mit PackratParsers sagt, ist sehr ähnlich zur Verwendung von Parser:

• jede Klasse/Merkmal, das Parser (direkt oder über eine Unterklasse) erstreckt, kann in mischen PackratParser. Beispiel Objekt MyGrammar erstreckt StandardTokenParsers mit PackratParsers
• jede Grammatik Produktion zuvor als def ohne deklarierten formalen Parameter wird ein fauler val, und dessen Typ von Parser [Elem] zu PackratParser [Elem] geändert wird. So zum Beispiel def Produktion: Parser [Int] = {...} wird faul val Produktion: PackratParser [Int] = {...}
• Wichtig: mit PackratParsers ist keine Entscheidung alles oder nichts . Sie können in einer einzigen Grammatik mit regelmäßigem Parser gemischt werden.

Ich weiß nicht genug über Parser Kombinatoren Scala 2.8 dies völlig zu beheben, aber mit den folgenden Modifikationen konnte ich es bis zum Semikolon zu analysieren, um bekommen, was eine Verbesserung ist über das, was du erreicht hast.

object Dotter extends StandardTokenParsers with PackratParsers { 
    lexical.delimiters ++= List(".",";") 
    lazy val pgm:PackratParser[Any] = repsep(expr,";") 
    lazy val expr:PackratParser[Any]= ident ||| (expr~"."~numericLit) 

    def parse(input: String) = phrase(expr)(lex(input)) match { 
     case Success(result, _) => println("Success!"); Some(result) 
     case n @ _ => println(n);println("bla"); None 
    } 

    def lex(input:String) = new PackratReader(new lexical.Scanner(input)) 
} 

Answer 2

Die Produktion

expr ::= ID | expr . [0-9]+ 

linksrekursiv wird. Es erweitert sich zu

expr ::= ID 
expr ::= expr . [0-9]+ 

wo die linke Rekursion in der 2. Zeile auftritt. Dies bewirkt, dass der Parser den Stapel überläuft.

Sie sollten Ihre Grammatik umschreiben, indem Sie links rekursive Produktionen vermeiden.