ANTLR 4 - 如何使用可选的 END-IF（COBOL 语法）减少 IF 语句的预测时间

Question

我一直在研究 COBOL 语法，发现对于具有深度嵌套 IF 语句的程序，生成的解析器运行速度非常慢。

我认为最好先看一下示例代码，以解释 COBOL 的一个“烦人”功能 - 一个 DOT（句号）可以关闭任何级别的未封闭嵌套 IF 语句。在这里：

IF condition-1
    S1
    IF condition-2
        S2
        (more nested IF conditions)
           IF condition-n
               Sn
  (0~n "END-IF"s )
.

括号内的文字是伪代码。关键点是，在 COBOL 中结束所谓“句子”的点之前，“END-IF”是可选的。为了允许“END-IF”是可选的，我这样编写了语法：

sentence:
  statement_list DOT
  ;
statement_list:
  statement+
  ;
statement:
  if_statement
  | ...   //other statements
  ;
if_statement:
  IF condition THEN? statement_list
  (ELSE statement_list)?
  END_IF?
  ;

对于像上面的示例这样的代码风格来说，这个语法是很慢的。调试时我发现解析器正忙于预测 if_statement 内部。这是预料之中的，因为语法中存在歧义。对于示例代码，“IF 条件-2 ...”可以被识别为“IF 条件-1 ...”的子项或兄弟，因为 S1 后面可以省略“END-IF”。最里面的“IF条件-n”最多可以有n个选择。类似地，如果它们的总数不是 n，则 DOT 之前的每个 END-IF 都可以替代它们配对的“IF”。

我尝试通过添加语义谓词来切断替代方案，如下所示：

statement_list:
  statement+  {_input.LA(1)==END_IF || _input.LA(1)==ELSE || _input.LA(1)==DOT}?
  ;  
if_statement:
  IF condition THEN? statement_list
   ( {_input.LA(1)!=ELSE}? | ELSE statement_list)
   ( {_input.LA(1)!=END-IF}? | END_IF) 
   ;

这将大型程序的解析时间减少了 2/3，但并未将其减少为线性时间，因为仍然观察到对 if_statement 和 statements_list 的深度预测。仔细研究 antlr 4 运行时似乎表明在预测期间根本不使用语义谓词。

有谁知道有什么技巧可以让这个“可选的 END-IF”明确，或者让它快速预测吗？

其实“ELSE”之前的语句也存在歧义，就像END-IF之前的语句一样。

注意：在我的机器上将示例与 30 层嵌套 ELSE-IF 进行配对需要 3 秒。我面临的大型程序经常出现这种深度嵌套，并且需要 10 分钟以上的时间来解析。其中之一甚至在预测时出现堆栈溢出。

另一个注意事项：我使用的是antlr 4.2。

Answer 1

我知道这个问题是 10 年前（或大约 10 年前）提出的。 但是...，我们在 Antlr 4.16（最新版本）中仍然面临这个问题。 足够深的嵌套 Cobol if-then-else 语句以及可选的尾随 end-if 在解析器中可能需要长达 7 分钟的时间 - 从开始规则... 我们已经对其进行了分析，我们看到所有的时间都花在 if then else 上。

欢迎任何想法或建议。