java - 解析器组合器中的递归耗尽堆栈空间

Question

我一直在用 Java 创建一个简单的解析器组合器库，并且第一次尝试使用编程结构来定义标记和解析器语法，请参见下文:

final Combinator c2 = new CombinatorBuilder()
    /*
    .addParser("SEXPRESSION", of(Option.of(new Terminal("LPAREN"), zeroOrMore(new ParserPlaceholder("EXPRESSION")), new Terminal("RPAREN"))))
    .addParser("QEXPRESSION", of(Option.of(new Terminal("LBRACE"), zeroOrMore(new ParserPlaceholder("EXPRESSION")), new Terminal("RBRACE"))))
    */
    .addParser("SEXPRESSION", of(Option.of(new Terminal("LPAREN"), new ParserPlaceholder("EXPRESSION"), new Terminal("RPAREN"))))
    .addParser("QEXPRESSION", of(Option.of(new Terminal("LBRACE"), new ParserPlaceholder("EXPRESSION"), new Terminal("RBRACE"))))
    .addParser("EXPRESSION", of(
        Option.of(new Terminal("NUMBER")),
        Option.of(new Terminal("SYMBOL")),
        Option.of(new Terminal("STRING")),
        Option.of(new Terminal("COMMENT")),
        Option.of(new ParserPlaceholder("SEXPRESSION")),
        Option.of(new ParserPlaceholder("QEXPRESSION"))
)).build()

如果我采用使用构建器定义的第一个解析器“SEXPRESSION”，我可以解释结构:

addParser 的参数:

1. 解析器名称
2. 析取Option的ImmutableList

Option.of 的参数:

1. Element 数组，其中每个元素都是 Terminal 或 ParserPlaceholder，稍后将替换实际的 名称匹配的解析器。

这个想法是能够从一个解析器引用另一个解析器，从而表达更复杂的语法。

我遇到的问题是，在将 RPAREN ')' 解析为“SEXPRESSIONS”和“时，使用上面的语法来解析诸如“(+ 1 2)”之类的字符串值会陷入无限递归调用中。 EXPRESSION”解析器有“一个或多个”基数。

我确信我可以发挥创意并想出一些限制递归调用深度的方法，也许可以通过确保当“SEXPRESSION”解析器移交给“EXPRESSION”解析器时，然后再移交给“EXPRESSION”解析器“SEXPRESSION”解析器，并且没有获取 token ，然后退出？但如果存在标准解决方案，我不想要一个黑客解决方案。

有什么想法吗？

谢谢

Answer 1

并不是要回避这个问题，但我认为使用 VM 参数调用应用程序来增加堆栈大小没有任何问题。

这可以在 Java 中通过添加标志 -XssNm 来完成，其中 N 是调用应用程序所使用的内存量。

默认的 Java 堆栈大小是 512 KB，坦率地说，它几乎没有任何内存。除了小的优化之外，我觉得用这么小的内存来实现复杂的递归解决方案即使不是不可能，也是很困难的，特别是因为 Java 在递归方面效率很低。

那么，这个标志的一些例子，如下:

• -Xss4M 4 MB
• -Xss2G 2 GB

它也会在您调用 java 启动应用程序后立即执行，或者如果您使用的是 Eclipse 等 IDE，您可以进入并在运行配置中手动设置命令行参数。

希望这有帮助!