Уловки Scala Parser Combinators для рекурсивного bnf?

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

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

или если я изменю | на |||, я получу 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)
...

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

РЕДАКТИРОВАТЬ: на основе статьи, указанной в 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);
    }
}

scala ebnf parser-combinators
person svrist    schedule 27.07.2010    source источник

Ответы (2)


arrow_upward
10
arrow_downward

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

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

  • любой класс/черта, расширяющая парсеры (напрямую или через подкласс), может смешиваться с PackratParsers. Пример: объект MyGrammar расширяет StandardTokenParsers с помощью PackratParsers.
  • каждая продукция грамматики, ранее объявленная как def без формальных параметров, становится lazy val, и ее тип изменяется с Parser[Elem] на PackratParser[Elem]. Так, например, производство def: 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))
}
person Ken Bloom    schedule 27.07.2010
comment
Точно! Я перечитал документацию и понял это. Последнее, что нужно, это опечатка в методе разбора: phrase(expr) должно быть phrase(pgm). Ваше здоровье! - person svrist; 27.07.2010

arrow_upward
1
arrow_downward

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

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

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

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

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

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

expr ::= ID {. [0-9]+}
person michid    schedule 27.07.2010
comment
Разве синтаксический анализатор packrat не должен был позволять мне выполнять левую рекурсию? - person svrist; 27.07.2010