Scala Parser Combinators trucos para bnf recursivo?

Question

Im tratando de coincidir con esta sintaxis:

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

Mi Scala packrat analizador combinador se ve así:

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); 
    } 
} 

Pero esto no funciona. O bien "coincide codiciosos" y me dice:

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

o si cambio de la | a un ||| recibo una 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) 
... 

I kindoff entender por qué consigo los errores; ¿Qué puedo hacer para analizar una sintaxis como la anterior? Eso no parece que esotérica me

EDIT: Basado en el documento de referencia en http://scala-programming-language.1934581.n4.nabble.com/Packrat-parser-guidance-td1956908.html descubrí que mi programa realmente aún no ha utilizar el nuevo analizador de roedor.

Ie. Parser[Any] cambiar a PackratParser[Any] y uso lazy val en lugar de def

Reescribí lo anterior a esto:

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

El problema es (al menos parcialmente) que no está realmente utilizando analizadores de Packrat. Consulte la documentación de PackratParsers rasgo de Scala, que dice

Usando PackratParsers es muy similar que utilizan analizadores:

• cualquier clase/rasgo que se extiende analizadores (directamente oa través de una subclase ) puede mezclar en PackratParsers. Ejemplo: objeto MyGrammar extiende StandardTokenParsers con PackratParsers
• cada producción gramática declarado previamente como def sin parámetros formales se convierte en un val perezoso, y su tipo se cambia de Analizador [Elem] para PackratParser [Elem]. Así, por ejemplo, la producción def: Analizador [Int] = {...} se convierte en val perezoso producción: PackratParser [Int] = {...}
• Importante: el uso de PackratParsers no es una decisión de todo o nada . Se pueden mezclar libremente con los analizadores regulares en una sola gramática.

No sé lo suficiente sobre Scala 2.8 combinadores analizador para solucionar este problema en su totalidad, pero con las siguientes modificaciones, que era capaz de conseguir que se analiza en lo que el punto y coma, que es una mejora sobre lo que has logrado

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

La producción

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

queda recursiva. Se expande a

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

donde la recursividad a la izquierda ocurre en la 2da línea. Esto es lo que hace que el analizador desborde la pila.

Debe volver a escribir su gramática evitando producciones recursivas a la izquierda.

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