Scala Parser Combinators трюки для рекурсивного BNF?

Question

Я пытаюсь соответствовать этому синтаксису:

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

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

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

, либо, если я заменяю | на |||, я получаю переполнение стека:

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)
...

Я понимаю, почемуЯ получаю ошибки;Что я могу сделать, чтобы разобрать синтаксис, как указано выше?Это не кажется мне эзотерическим

РЕДАКТИРОВАТЬ: На основе статьи, на которую ссылаются в http://scala -programming-language.1934581.n4.nabble.com / Packrat-parser-guide-td1956908.html Я обнаружил, что моя программа на самом деле не использует новый синтаксический анализатор пакетов.

Т.е.измените 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.См. Документацию по признаку Scala PackratParsers , в котором говорится, что

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

• любой класс / признак, расширяющий парсеры(напрямую или через подкласс) можно смешивать в PackratParsers.Пример: объект MyGrammar расширяет StandardTokenParsers с помощью PackratParsers
• . Каждое производство грамматики, ранее объявленное как def без формальных параметров, становится отложенным значением, а его тип изменяется с Parser [Elem] на PackratParser [Elem].Так, например, def production: Parser [Int] = {...} превращается в lazy val production: 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]+

, где левая рекурсия происходит во 2-й строке.Это то, что заставляет парсер переполнять стек.

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

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