Scala 解析器组合器递归 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

或者如果我将 | 更改为 ||| 我会得到一个 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 解析器。

IE。将 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 扩展
  标准令牌解析器
  Packrat解析器
• 之前声明为 def 的每个语法产生式没有
  形式参数变成惰性值，
  它的类型从
  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))
}

Answer 2

产生式

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

是递归的。它扩展到

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

第二行发生左递归的位置。这就是导致解析器溢出堆栈的原因。

您应该重写语法，避免左递归产生式。

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