Scala Parser Комбинированные трюки для рекурсивного bnf?

Question

Im пытается сопоставить этот синтаксис:

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

Мой Packrat анализатор Scala комбинатор выглядит следующим образом:

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

Но это не работает. Либо это «соответствует жадный» и говорит мне:

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

или изменить | к ||| я получаю 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 понять, почему я получаю ошибки; что я могу сделать, чтобы разобрать синтаксис, как указано выше? Это не кажется, что эзотерический мне

EDIT: на основе бумаги, указанного в http://scala-programming-language.1934581.n4.nabble.com/Packrat-parser-guidance-td1956908.html я узнал, что моя программа на самом деле использовать техника его подводит новый Packrat анализатор.

Т.е. изменить Parser[Any] к PackratParser[Any] и использовать lazy val вместо def

Я переписал выше этого:

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

Проблема заключается (по крайней мере частично) в том, что вы фактически не используете парсер Packrat. Обратитесь к документации по PackratParsers черты Scala, который говорит

Использование PackratParsers очень похож с использованием Парсеры:

• любой класс/черта, которая простирается парсеры (непосредственно или через подкласса) могут смешиваться в PackratParsers. Пример: Объект MyGrammar расширяет StandardTokenParsers с PackratParsers
• каждой грамматика производство ранее объявленное как опр без формальных параметров, становится ленивым Валом, и ее тип изменяется от Parser [Эль] для PackratParser [Эль]. Так, например, производство Защиту: Parser [Int] = {...} становится ленив VAL производства: PackratParser [Int] = {...}
• Важно: использование PackratParsers не является решение все или ничего , Они могут быть свободно перемешаны с регулярными Парсеры в одной грамматике.

Я не знаю достаточно о Scala 2.8 в комбинаторы синтаксического анализа, чтобы это исправить полностью, но со следующими изменениями, я смог его разобрать, насколько точка с запятой, что является улучшением над тем, что вы достигли.

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

Производство

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

является леворекурсивным. Он расширяется до

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

, где левая рекурсия происходит во второй строке. Именно это заставляет парсер переполнять стек.

Вы должны переписать свою грамматику, избегая левых рекурсивных постановок.

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