如何简化令牌预测DFA？

Question

Lexer DFA导致“代码太大”错误

我正在尝试使用ANTLR3解析Java服务器页面。

Java对单个方法的字节码有64k的限制，在编译由ANTLR生成的Java源代码时，我总是遇到“代码太大”的错误。

在某些情况下，我可以通过破坏我的词法分析器来修复它。例如，JSP使用XML "Name“标记，它可以包括各种字符。我决定在我的"Name“令牌中只接受ASCII字符，这极大地简化了一些测试，并且lexer允许它进行编译。

然而，我已经到了不能再偷工减料的地步，但是DFA仍然太复杂了。

我该怎么做呢？

是否存在导致复杂DFA的常见错误？

有没有一种方法可以抑制DFA的生成，也许依赖于语义谓词或固定的前视来帮助预测？

手工编写这个lexer将会很容易，但在我放弃使用ANTLR之前，我想确保我没有忽略一些显而易见的东西。

背景

ANTLR3词法分析器使用DFA来决定如何标记化输入。在生成的DFA中，有一个名为specialStateTransition()的方法。此方法包含一条switch语句，其中DFA中的每个状态都有一个case。在每种情况下，都有一系列if语句，每个语句对应于从状态开始的每个转换。每条if语句的条件都会测试一个输入字符，以查看它是否与转换匹配。

这些字符测试条件可能非常复杂。它们通常具有以下形式：

int ch = … ; /* "ch" is the next character in the input stream. */
switch(s) { /* "s" is the current state. */
  …
  case 13 :
    if ((('a' <= ch) && (ch <= 'z')) || (('A' <= ch) && (ch <= 'Z')) || … )
      s = 24; /* If the character matches, move to the next state. */
    else if …

对我的词法分析器进行一个看似很小的更改，就可能导致对单个转换进行数十次比较，对每个状态进行多个转换，以及对几十个状态进行比较。我认为，由于我的语义谓词，正在考虑的一些状态是不可能达到的，但似乎语义谓词被DFA忽略了。(我可能读错了--这段代码绝对不是我能手工写的！)

我在Jsp2x工具中找到了一个ANTLR2语法，但是我对它的解析树不满意，我想更新一下我的ANTLR2语法，所以我想我可以尝试自己写一个ANTLR2语法。我正在使用ANTLRWorks，并且我试图为DFA生成图形，但是ANTLRWorks中似乎有一些bug阻止了它。

Answer 1

不幸的是，非常大的语法(许多不同的标记)就有这个问题(SQL语法也有这个问题)。

有时，这可以通过使某些词法分析器规则fragments而不是生成令牌的“完整”词法分析器规则和/或重新安排规则中字符匹配的方式来解决，但通过查看您已经尝试的方式，我怀疑在您的情况下能获得多少好处。但是，如果您愿意在SO上发布您的lexer语法，我或其他人可能会看到一些可以改变的东西。

通常，通过将词法分析器语法拆分为2个或更多独立的词法分析器语法，然后在一个“主”语法中导入这些语法，可以解决此问题。在ANTLR术语中，这些被称为复合语法。请参阅有关它们的ANTLR维基页面：http://www.antlr.org/wiki/display/ANTLR3/Composite+Grammars

编辑

正如@Gunther在OP下面的注释中正确地提到的那样，请参阅Q&A：Why my antlr lexer java class is "code too large"?，其中一个小的更改(删除了某个谓词)会导致这个“代码太大”的-error消失。

Answer 2

实际上，制作一个复合语法并不总是那么容易。在许多情况下，this AntTask可以帮助解决这个问题(每次重新编译语法后都必须运行它，但这个过程并不是很无聊)。

不幸的是，即使是这个神奇的脚本在一些复杂的情况下也没有帮助。编译器可能会开始抱怨DFA转换(静态String[]字段)的块太大。

我找到了一个简单的解决方法，通过将(使用集成开发环境重构特性)这样的字段转移到另一个具有任意生成名称的类中。当以这种方式仅移动一个或多个字段时，这总是有帮助的。