Как бороться с бесконечной рекурсией

Question

Давайте возьмем следующую грамматику в качестве образца:

Model: 
    m+=Main* 
; 

Main: 
    "bla" r=Rule1 
    | Rule3 
    | Rule2 
; 

    Rule1: 
     i=INT 
     | "key" r=Rule2 
    ; 

    Rule2: 
     "b" r=Rule3 
    ; 

    Rule3: 
     "b" (r=Rule1 | r=Rule2) 
    ; 

Когда я компилирую это я получаю сообщение об ошибке:

error(211): ../org.xtext.example.test/src-gen/org/xtext/example/test/parser/antlr/internal/InternalTest.g:119:1: [fatal] rule ruleMain has non-LL(*) decision due to recursive rule invocations reachable from alts 2,3. Resolve by left-factoring or using syntactic predicates or using backtrack=true option. 

Насколько я понимаю, этот вопрос этих потому что ruleCall для Rule3 может быть бесконечно длинным (так как Rule3 может вызывать Rule2, который затем может снова вызвать Rule3 и т. д.), а также ruleCall для Rule2.
Поэтому анализатор не может создать lookahead для этих бесконечно ruleCalls, а в правиле Main мы требуем, чтобы синтаксический анализатор решал между этими бесконечными альтернативами, но отсутствие этого результата в этом сообщении об ошибке ...
(исправьте меня, если я 'm wrong)

Мой вопрос будет таким, как я могу решить эту проблему?
Должен быть способ реструктурировать эту грамматику, чтобы парсер мог ее обработать.

С наилучшими пожеланиями Raven

Answer 1

Если я смотрю вашу грамматику, я вижу, что у вас есть Правила2 и Правилу3, которые могут быть рефакторинг только в одном правиле. Потому что вы rule2 и 3 начинаете с «b». Так будет, если у вас есть «Правило 2:» b «r = (Правило 1 | Правило2);». По-моему, правило 3 не нужно. Я буду реорганизовать вашу грамматику следующим образом:

Model: 
    m+=Main* 
; 

Main: 
    "bla" r=Rule1 
    | Rule2 
; 

Rule1: 
    i=INT 
    | "key" r=Rule2 
; 

Rule2: 
    "b" r=(Rule1 | Rule2) 
;