ANTLR4 проблемы с левой рекурсией

Question

Я написал грамматику для ANTLR v4 с целью C#, которая использует некоторые леворекурсивные правила синтаксического анализа, и каждый раз, когда я пытаюсь проанализировать некоторый пример кода, который должен использовать эти правила, механизм синтаксического анализа выбирает неправильное правило.

правила синтаксического анализа:

expr 
    : expr COR term 
    | expr CAND term 
    | term 
    ; 

код Я пытаюсь разобрать:

... 
print("Testing Program p00csx\n"); 
... 

Посетитель, используя информацию из разбора двигателя:

public override Int32 VisitExpr(CSXParser.ExprContext context) 
    { 
     if (context == null) return 0; 
     switch (context.altNum) 
     { 
      case 1: //expr COR term 
       VisitExpr(context.expr()); 
       Console.Write(context.COR()); 
       VisitTerm(context.term()); 
       break; 
      case 2: //expr CAND term 
       VisitExpr(context.expr()); 
       Console.Write(context.CAND()); 
       VisitTerm(context.term()); 
       break; 
      case 3: //term 
       VisitTerm(context.term()); 
       break; 
     } 
     return 0; 
    } 

В этом Например, строковый литерал внутри вызова print() должен быть разрешен к 'expr', который разрешает «термин» и т. д., et c, пока у нас не будет 'stringLit'. Это пример 3 в приведенном выше примере. Вместо этого, однако, парсер выбирает случай 1, даже считает, что в тексте программы нет COR ('||').

Сайт ANTLR говорит, что v4 может обрабатывать леворекурсивные выражения, такие как эти, что заставляет меня поверить, что я должен что-то делать неправильно. Я новичок в ANTLR, и, может быть, проблема в том, что я просто забыл. Любая помощь приветствуется; Я читаю документацию и запускаю отладчик в течение нескольких дней и пытаюсь понять это.

Спасибо!

Answer 1

Нельзя использовать поле ParserRuleContext.altNum по следующим причинам.

• Это не инициализировано для леворекурсивных правил, поэтому оно ненадежно.
• Это огромная трата памяти, и я надеюсь удалить ее.
• Я не проводил никаких проверок, чтобы проверить его точность или удобство использования в любом другом сценарии.

Вместо этого попробуйте либо одно из следующих действий:

1. Проверить альтернативе сначала проверить, если context.expr() возвращает нуль. Если да, то у вас есть term. Если expr() возвращает ненулевое значение, то вы можете проверить, какой из context.COR() или context.CAND() возвращает не-null, чтобы определить фактический оператор, который использовался.

2. Ярлык ваши внешние альтернативы, как этот

   expr 
       : expr COR term # orExpr 
       | expr CAND term # andExpr 
       | term   # termExpr 
       ; 
   

Answer 2

Я предлагаю вам удалить левую рекурсию на все:

expr 
scope 
{ 
    LogicOperator op; 
} 
     : expr ((COR {expr.op = LogicOperator.Or;} | CAND {expr.op = LogicOperator.And;}) exp)* 
     | term 
     ; 

P.S. my ANTLR3 grammar с логическими операторами и приоритетами