Scala Parser Sztuczki kombinatory dla rekurencyjnego bnf?

Question

Im próbuje dopasować tę składnię:

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

Mój scala packrat parser syntezatora wygląda następująco:

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

Ale to nie robi praca. Albo "pasuje chciwy" i mówi mi:

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

czy zmienić | do ||| dostaję 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) 
... 

kindoff rozumiem dlaczego dostaję błędy; co mogę zrobić, aby parsować składnię jak wyżej? Wydaje się, że robi mi ezoteryczny

EDIT: podstawie artykułu odwołuje się http://scala-programming-language.1934581.n4.nabble.com/Packrat-parser-guidance-td1956908.html okazało się, że mój program nie zrobił właściwie używać nowego packrat parsera.

Tzn. zmienić Parser[Any] do PackratParser[Any] i używać lazy val zamiast def

przepisałem wyżej do tego:

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

Problem polega (przynajmniej częściowo) na tym, że faktycznie nie używasz parserów Packrat. Zapoznać się z dokumentacją Scala PackratParsers cecha, która mówi

Korzystanie PackratParsers jest bardzo podobna do korzystających parserami:

• każda klasa/cecha, która rozciąga Parsery (bezpośrednio lub za pośrednictwem podklasy) można mieszać w PackratParsers. Przykład: obiekt MyGrammar rozciąga StandardTokenParsers z PackratParsers
• każdy produkt gramatyki wcześniej uznane za def bez parametrów formalnych się leniwe Val oraz typ zmienia Parser [Elem] do PackratParser [Elem]. Tak więc, na przykład, produkcja def: Parser [Int] = {...} staje się leniwy Val produkcji: PackratParser [Int] = {...}
• Ważne: przy użyciu PackratParsers nie jest wszystko albo nic decyzję . Można je dowolnie mieszać ze zwykłymi analizatorami w jednej gramatyce.

nie wiem wystarczająco dużo o Scala 2.8 za parser kombinatorów, aby rozwiązać ten problem całkowicie, ale z następującymi modyfikacjami, udało mi się dostać do analizowania miarę średnikiem, który jest poprawa nad tym, co osiągnąłeś.

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

Produkcja

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

pozostało rekurencyjnych. Rozwija się do

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

gdzie pojawia się lewostronna rekursja w drugiej linii. To powoduje, że parser przepełnia stos.

Powinieneś przepisać swoją gramatykę, unikając lewicowych produkcji rekursywnych.

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