ANTLR 4 - Как сократить время прогнозирования для операторов IF с помощью необязательного END-IF (грамматика COBOL)

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 )
.

Текст в скобках - это псевдокод. Ключевым моментом является то, что "END-IF" являются необязательными перед точкой, которая закрывает так называемое "предложение" в языке COBOL. Для того, чтобы "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 вариантов. Точно так же каждый END-IF перед DOT имеет альтернативы над "IF", ​​с которыми они соединяются, если их общее число не равно n.

Я попытался обрезать альтернативы, добавив семантические предикаты, как показано ниже:

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 и Statement_list. Более пристальный взгляд на среду выполнения antlr 4, кажется, показывает, что семантические предикаты вообще не используются во время прогнозирования.

Кто-нибудь знает хитрость, чтобы сделать этот "необязательный END-IF" однозначным, или заставить его быстро предсказывать?

На самом деле, существует также двусмысленность в заявлениях перед "ELSE", как и в "END-IF".

Примечание. Для сравнения образца с 30 уровнями вложенного ELSE-IF на моем компьютере требуется 3 секунды. И я сталкиваюсь с большими программами, которые часто встречаются в такой глубокой вложенности и используют для анализа более 10 минут. У одного из них даже происходит переполнение стека при прогнозировании.

Еще одно замечание: я использую antlr 4.2.