Search code examples
grammarxtextleft-recursion

Left recursive call error and translation of grammars


I'm having problems with a slightly different grammar, it's a grammar with a single rule (a giant one), and with several calls to itself. I do not know how to represent this grammar using Xtext, it is an academic work, a language to specify requirements. The originating grammar, obtained from the article is:

and my frustrated attempt is shown below:

Relax:
root+=General+;

//nao tinha o tipo boleano  
terminal BOOLEAN returns ecore::EBoolean: 
    'true'|'false'
;

General:
    root+=BOOLEAN|STRING|ShallOperator|MayOperator|EventuallyOperator|UntilOperator|BeforeOperator|AfterOperator|InOperator;


ShallOperator:
    'shall' elements=General;


MayOperator:
    "may" action1=General 'or' action2=General;

EventuallyOperator:
    'eventually' element=General;

UntilOperator:
//  {General.left=current}'&' right=General;
//  ({General.left=current}) 'until' element2=General;
left=General 'until' right=General;

The error "this rule call is part of a recursive call graph" occurs in the last line.

Besides this error, even the "correct" parts of the grammar do not produce the right results.

I searched for the error, but I was not able to understand the problem, I'm still a beginner, so I have 2 questions:

Is it correct how I translate grammar?

How to resolve this left recursive error?

Bonus question: Materials for study (I am already reading the official documentation).

Any help is welcome.

Thank you all.


Solution

  • the "default" xtext way of left factoring should help

    Relax:
    root+=General+;
    
    terminal BOOLEAN returns ecore::EBoolean:
    'true'|'false'
    ;
    
    General:
    
    root=Rest =>({UntilOperator.left=current}'until' right=General)*;
    
    Rest:
    Primitive|ShallOperator|MayOperator|EventuallyOperator
    ;
    
    Primitive:
    BooleanValue | StringValue
    ;
    
    BooleanValue:
    value=BOOLEAN
    ;
    
    StringValue:
    value=STRING
    ;
    
    
    ShallOperator:
    'shall' elements=General;
    
    MayOperator:
    "may" action1=General 'or' action2=General;
    
    EventuallyOperator:
    'eventually' element=General;