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

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不能inter the name，name进入了function_call，试了name，进入了funciton call。您如何解决此类情况？

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

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

但我不想这样做，因为 name ::= identifier | function_call 在 VHDL 规范中是 BNF-ed 并且 function_call 可能在其他地方共享。由于同样的原因

，左递归消除 found here 是不可取的

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

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

Stack overflow when using parser combinators

scala

parsing

parser-combinators

left-recursion