Antlr 解析器 StackOverflowException（用于解析正则表达式）

Question

我做了一个简单的解析正则表达式的语法。不幸的是，当我尝试在大型表达式上测试我的正则表达式编译器时，我遇到了 WhosebugException。这个问题类似于除了他们的解决方案不再适用于我的场景。这是我的语法：

union: concat | concat '|' union ;
concat: kleene_closure concat | kleene_closure;
kleene_closure: atomic '*' | atomic ;
atomic : '(' union ')' | LETTER ;

现在的问题是我有一个非常大的文件，看起来像

something1 | something2 | something3 | .... | something1000

我使用 ANTLR 的 Visitor class 进行解析。我知道我可以像这样使用 +/* 来进行一些优化

union: (concat '|')* concat ;
concat: kleene_closure+;
kleene_closure: atomic '*' | atomic ;
atomic : '(' union ')' | LETTER ;

但是，由于此语法的递归性质，它并没有真正解决问题。例如，它现在会在以下显然需要递归的示例中失败：

(...(((something1) | something2) | something3) | .... ) | something1000

如何避免 WhosebugExcpetion？其他编译器（例如 C 编译器）如何处理具有数千行代码的大型文本？

Answer 1

如果您要使用递归下降解析器，那么您将不可避免地运行进入超过调用堆栈深度的输入。这个问题可以通过像 Java 这样的语言得到改善，它们能够控制自己的堆栈深度，因此会有一个像 WhosebugException 这样的可控结果。但这仍然是一个真正的问题。

像 Yacc/Bison 和 Java Cup 这样的解析器生成器使用 bottom-up LALR(1) 算法，该算法使用显式堆栈进行临时存储，而不是为此目的使用调用堆栈.这意味着解析器必须管理解析器堆栈的存储（或者使用宿主语言标准库中的容器 ADT，如果有的话），这稍微复杂一些。但是您不必处理这种复杂性；它内置于解析器生成器中。

解析器生成器的显式堆栈有几个优点：

更容易控制最大堆栈大小；
最大堆栈大小（通常）仅受可用内存限制；
它的内存效率可能更高，因为控制流信息不需要保存在堆栈帧中。

不过，这不是万灵药。一个足够复杂的表达式将超过任何固定的堆栈大小，这可能导致某些程序无法解析。此外，如果您利用上面第二点中提到的灵活性（“仅受可用内存限制”），您可能会发现您的编译器被 OOM 进程（或段错误）毫不客气地终止，而不是能够响应更礼貌的 out-of-memory 异常（当然取决于 OS 和配置）。

至于：

How do other compilers, like for instance C compiler deal with really large texts that have thousands lines of code?

如果您在语法中使用重复运算符（或者，在您使用 LALR(1) 解析器的情况下，您的语法是 left-recursive，那么拥有数千行代码不是问题).正如您在问题中指出的那样，当您的文本包含数千个嵌套块时，就会出现问题。答案是许多 C 编译器无法优雅地处理此类文本。这是一个简单的 gcc 实验：

$ # A function which generates deeply-nested C programs
$ type deep
deep is a function
deep () { 
    n=;
    printf "%s\n%s\n %s\n" '#include <stdio.h>' 'int main(void) {' 'int a0 = 0;';
    for ((i=0; i<n; ++i))
    do
        printf '%*s{ int a%d = a%d + 1;\n' $((i+1)) '' $((i+1)) $i;
    done;
    printf '%*sprintf("%%d\n", a%d);\n' $n '' $n;
    for ((i=0; i<n; ++i))
    do
        printf "%s" '}';
    done;
    printf "%s\n" '}'
}
$ deep 3
#include <stdio.h>
int main(void) {
 int a0 = 0;
 { int a1 = a0 + 1;
  { int a2 = a1 + 1;
   { int a3 = a2 + 1;
   printf("%d\n", a3);
}}}}
$ # For small depths, GCC is OK with that.
$ deep 3 | gcc -x c - && ./a.out
3
$ # Let's go deeper:
$ deep 10 | gcc -x c - && ./a.out
10
$ deep 100 | gcc -x c - && ./a.out
100
$ deep 1000 | gcc -x c - && ./a.out
1000
$ deep 10000 | gcc -x c - && ./a.out
10000
$ # Ka-bang. (Took quite a long time, too.)
$ deep 100000 | gcc -x c - && ./a.out
gcc: internal compiler error: Segmentation fault (program cc1)
Please submit a full bug report,
with preprocessed source if appropriate.
See <file:///usr/share/doc/gcc-7/README.Bugs> for instructions.

没有嵌套块，gcc 仍然很慢但可以处理程序：

$ type big
big is a function
big () 
{ 
    n=;
    printf "%s\n%s\n %s\n" '#include <stdio.h>' 'int main(void) {' 'int a0 = 0;';
    for ((i=0; i<n; ++i))
    do
        printf ' int a%d = a%d + 1;\n' $((i+1)) $i;
    done;
    printf ' printf("%%d\n", a%d);\n' $n;
    printf "%s\n" '}'
}
$ big 3
#include <stdio.h>
int main(void) {
 int a0 = 0;
 int a1 = a0 + 1;
 int a2 = a1 + 1;
 int a3 = a2 + 1;
 printf("%d\n", a3);
}
$ $ big 3|gcc -x c - && ./a.out
3
$ big 10000|gcc -x c - && ./a.out
10000
$ big 100000|gcc -x c - && ./a.out
100000

Answer 2

您可以用 ABNF 语法定义语法并将其提供给 TGS* 以迭代地 解析它 - 无需使用线程专用堆栈进行递归。解析器生成器生成的解析器运行迭代地用于所有它的操作：词法分析、解析、树构造、树到字符串的转换、树迭代和树销毁。

解析器在运行时，也可以仅通过事件为您提供树构建信息，然后您可以根据需要构建树（或执行任何操作没有任何树的计算）。在这种情况下，当您使用事件（没有显式树构建的确定性解析器语法）进行解析时，如果您有足够的操作内存来保存解析规则的深度，您实际上可以“流式传输”任何输入 regardless 的大小。

ABNF (RFC 5234) 中的确定性语法是这样的：

alternative     = concatenation *('|' concatenation)
concatenation   = 1* kleene-closure
kleene-closure  = atomic 0*1 '*'
atomic          = '(' alternative ')' / letter
letter          = 'a'-'z' / 'A'-'Z'

然而，此语法每个项目一个字母，对于输入“ab”，您将得到两个原子节点，每个节点一个字母。如果你想要更多的字母，那么也许这个语法就可以了：

alternative     = concatenation *('|' *ws concatenation)
concatenation   = element *(ws 0*1 element)
element         = primary 0*1 '*'
primary         = '(' *ws alternative ')' / identifier
identifier      = 1*('a'-'z' / 'A'-'Z')
ws              = %x20 / %x9 / %xA / %xD

你可以理解为：备选方案由一个或多个 concatenations 组成，由 | 分隔。 concatenation 是一个或多个 elements，由至少一个 white space 字符分隔。 element 可能以 * 结尾，并且可以是范围内的 alternative 或 identifier，后者又是一个或多个字母。白色 space 是 space、tab、new line 或 carriage return。如果你想要更复杂的标识符，你可以使用这个：

identifier      = (letter / '_') *(letter / '_' / digit)
letter          = 'a'-'z' / 'A'-'Z'
digit           = '0'-'9'

*我在那个项目上工作。

Antlr 解析器 StackOverflowException（用于解析正则表达式）

Antlr parser StackOverflowException (for parsing regular expressions)

stack-overflow

parsing

antlr

antlr4