Scala Parser Combinators astuces pour bnf récursif?

Question

Im essayant de faire correspondre cette syntaxe:

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

Mon scala analyseur packrat Combinator ressemble à ceci:

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

Mais ce travail ne marche pas. Soit il "correspond gourmand" et me dit:

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

ou si je change le | à un ||| je reçois un 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) 
... 

Je kindoff comprends pourquoi je reçois les erreurs; Que puis-je faire pour analyser une syntaxe comme celle-ci? Il ne semble pas que ésotérique me

EDIT: Basé sur le papier référencé dans http://scala-programming-language.1934581.n4.nabble.com/Packrat-parser-guidance-td1956908.html j'ai découvert que mon didnt programme utilise en fait le nouvel analyseur de packrat.

Ie. changer Parser[Any]-PackratParser[Any] et utiliser lazy val au lieu de def

Je réécris ci-dessus à ceci:

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

Le problème est (au moins partiellement) que vous n'utilisez pas vraiment d'analyseurs Packrat. Consultez la documentation de trait de Scala PackratParsers, qui dit

L'utilisation PackratParsers est très similaire à l'aide Parsers:

• toute classe/trait qui étend Parsers (directement ou par une sous-classe ) peut mélanger PackratParsers. Exemple: objet MyGrammar étend StandardTokenParsers avec PackratParsers
• chaque production de grammaire précédemment déclarée comme def sans paramètres formels devient un val paresseux, et son type passe de Parser [Elem] pour PackratParser [Elem]. Ainsi, par exemple, la production def: Parser [Int] = {...} devient production val paresseux: PackratParser [Int] = {...}
• Important: L'utilisation PackratParsers est pas tout ou rien décision . Ils peuvent être mélangés librement avec les analyseurs syntaxiques en une seule grammaire.

Je ne sais pas assez sur l'analyseur de Scala 2.8 de combinateurs pour résoudre ce tout à fait, mais avec les modifications suivantes, j'ai pu l'obtenir pour analyser jusqu'à la virgule, ce qui est une amélioration sur ce que vous avez accompli.

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 production

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

est laissé récursive. Il s'étend à

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

où la récursion gauche se produit sur la deuxième ligne. C'est ce qui provoque le débordement de l'analyseur dans la pile.

Vous devez réécrire votre grammaire en évitant les productions récursives gauches.

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