使用解析器组合器时堆栈溢出

Question

import scala.util.parsing.combinator._
object ExprParser extends JavaTokenParsers {
    lazy val name: Parser[_] = "a" ~ rep("a" | "1") | function_call
    lazy val function_call = name ~ "(" ~> name <~ ")"
}

无限

期地重复function_call.parseAll("aaa(1)") .显然，这是因为 1 不能将名称与名称之间，而 name 进入 function_call ，这会尝试名称，从而进入函数调用。您如何解决这种情况？

有一个解决方案可以将名称简化为简单的标识符

def name = rep1("a" | "1") 
def function_call = name ~ "(" ~ (function_call | name) ~ ")"

但我不想这样做，因为name ::= identifier | function_call VHDL 规范中是 BNF ed，function_call可能在其他地方共享。出于同样的原因，此处发现的左递归消除是不可取

的

def name: Parser[_] = "a" ~ rep("a" | "1") ~ pared_name
def pared_name: Parser[_] = "(" ~> name <~ ")" | ""

顺便说一句，我也想知道，如果我修复错误，name.parseAll 将"aaa"仅作为名称规则中的第一个替代方案还是采用整个"aaa(1("？在仅消耗 aaa 之前，如何命名为消耗整个 aaa(1(？我想我应该在名称中function_call第一个选择，但在这种情况下它会更急切地堆叠溢出？

Answer 1

一个简单的解决方案是使用 packrat 解析器：

object ExprParser extends JavaTokenParsers with PackratParsers {
  lazy val name: PackratParser[_] = "a" ~ rep("a" | "1") | function_call
  lazy val function_call: PackratParser[_] = name ~ "(" ~> name <~ ")"
}

输出：

scala> ExprParser.parseAll(ExprParser.function_call, "aaa(1)")
res0: ExprParser.ParseResult[Any] =
[1.5] failure: Base Failure
aaa(1)
    ^