parsing - Antlr parser StackOverflowException（用于解析正则表达式）

Question

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

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

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

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

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

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

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

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

如何避免 StackOverflowExcpetion？其他编译器，例如 C 编译器如何处理具有数千行代码的非常大的文本？

标签： parsingstack-overflowantlrantlr4

Answer 1

如果您要使用递归下降解析器，那么您将不可避免地遇到超出调用堆栈深度的输入。像 Java 这样能够控制自己的堆栈深度的语言可以改善这个问题，从而产生像 StackOverflowException 这样的可控结果。但这仍然是一个真正的问题。

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

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

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

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

至于：

其他编译器，例如 C 编译器如何处理具有数千行代码的非常大的文本？

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

$ # A function which generates deeply-nested C programs
$ type deep
deep is a function
deep () { 
    n=$1;
    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=$1;
    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