1

我正在从 flex/bison 移植语法，并且大部分似乎都已启动并运行（特别是，我的令牌流似乎很好，并且我的解析器语法正在编译和运行），但似乎遇到了失控的问题即使对我的语法输入非常小/中等大小的堆栈/内存使用。将相同非末端的无界序列链接在一​​起的首选结构是什么？在我的 Bison 语法中，我有以下形式的产生规则：

statements: statement | statement statements
words: | word words

在 ANTLR 中，如果我保持相同的规则设置，这似乎在小输入（大约 4kB）上表现出色，但会导致较大输入（大约 100kB）的堆栈溢出。在这两种情况下，生成的自动解析树也相当笨拙。

我尝试将这些生产规则更改为具有显式加法（而不是递归形式）：

statements: statement+
words: word*

然而，即使是非常小的输入，这似乎也会导致内存使用量（超过 1GB）绝对可怕的爆炸，并且解析器在运行 20 分钟后还没有设法返回解析树。

任何指针将不胜感激。

4

2 回答 2

2

您重写的语句是您描述的两条规则（最高性能和最低内存使用）的最佳 ANTLR 4 形式。以下是关于您描述的问题的一些一般性反馈。

  1. 我为许多潜在的性能问题开发了一些非常先进的诊断代码。大部分代码都包含在 中TestPerformance，但它面向专家用户，需要对 ANTLR 4 的新 ALL(*) 算法有相当深入的了解才能解释结果。

  2. 特伦斯和我有兴趣将上述内容变成用户可以使用的工具。如果您提供完整的语法和示例输入，我可能会提供帮助（运行和解释测试），以便我可以使用该语法和输入对作为进一步评估自动化分析工具可用性的一部分.

  3. 确保您使用的是书中的两阶段解析策略。在许多情况下，这将极大地提高正确输入的解析性能（不正确的输入不会更快）。

  4. 我们不喜欢使用比必要更多的内存，但您应该知道，我们正在使用非常不同的“过度”定义 - 例如，我们使用 to 运行我们的测试应用程序-Xmx4g，-Xmx12g具体取决于测试。

于 2013-09-15T18:32:41.093 回答
1

好的，所以我已经通过以下方式让它工作了。我的 YACC 语法有以下结构：

lines: lines | line lines;
words: | word words;

但是，这并没有使递归解析变得快乐，所以我将其重写为：

lines: line+;
words: word*;

这符合@280Z28 的反馈（以及我最初的猜测）。这会挂起解析器，这就是我首先发布问题的原因，但我在对@280Z28 的回答的评论中概述的调试过程表明，实际上只有lines导致问题的解析（words）很好。一时兴起，我尝试了以下重写：

lines   : stmt (EOL stmt)+ EOL*;

（line最初定义为：

line : stmt (EOL | EOF);

)

即使对于大量输入，这似乎也很有效。然而，我完全不清楚为什么这是正确的事情（tm），或者为什么它与引发这个问题的修订版相比有所不同。对此事的任何反馈仍将不胜感激。

于 2013-09-20T17:57:16.810 回答