使用解析器组合器时堆栈溢出 [英] Stack overflow when using parser combinators
问题描述
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,name进入function_call
,它尝试name,进入funciton调用.您如何解决此类情况?
recurs indefinitely for function_call.parseAll("aaa(1)")
. Obviously, it is because 1 cannot inter the name and name enters the function_call
, which tries the name, which enters the funciton call. How do you resolve such situations?
有一个将名称简化为简单标识符的解决方案
There was a solution to reduce name to simple identifier
def name = rep1("a" | "1")
def function_call = name ~ "(" ~ (function_call | name) ~ ")"
但我不想这样做,因为 name ::= identifier |function_call
在 VHDL 规范中是 BNF 化的,function_call
可能在其他地方共享.左递归消除在这里找到是出于同样的原因不受欢迎
but I prefer not to do this because name ::= identifier | function_call
is BNF-ed in VHDL specification and function_call
is probably shared elsewhere. The left recursion elimination found here is undesirable for the same reason
def name: Parser[_] = "a" ~ rep("a" | "1") ~ pared_name
def pared_name: Parser[_] = "(" ~> name <~ ")" | ""
顺便说一句,我也想知道,如果我修复了这个错误,name.parseAll 是只将aaa"作为名称规则中的第一个选项还是使用整个aaa(1)"?在只消耗 aaa 之前,如何命名以消耗整个 aaa(1)?我想我应该将 function_call 作为名称中的第一个选项,但在这种情况下它会更急切地堆栈溢出?
BTW, I also wonder, if I fix the error, will name.parseAll consume "aaa" only as first alternative in the name rule or take whole "aaa(1)"? How can I make name to consume the whole aaa(1) before consuming only aaa? I guess that I should put function_call a first alternative in the name but it will stack overflow even more eagerly in this case?
推荐答案
一个简单的解决方案是使用 Packrat 解析器:
An easy solution is use the packrat parser:
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)
^
这篇关于使用解析器组合器时堆栈溢出的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!