eclipsextextxbase

Solving a left recursion problem in xText

I am currently working on creating a DSL in xText and I am stumbling upon a problem which is probably related to an ambiguity or left recursion problem. I am not sure which of these two problems applies to my case (similar topics I found online also mention that these problems often seem related) but I guess it has to do with left recursion.

On line 100 in my DSL code I declare a rule called Expression. As you can see it aggregates multiple other types (which on their part again aggregate multiple other types and eventually types called Factor (on line 130) can also be aggregated). Eventually this whole 'aggregation tree' boils down to a problem with this Factor type. As you can see, this type can aggregate an Expression again. So there is a loop; an Expression type can eventually contain a Factor type, and the Factor type can then again contain an Expression type (after which this loop can theoretically continue infinitely; I guess that's where the problem is because the ANTLR parser used by xText was not designed for this kind of recursion). I tried to solve this problem by using a syntactic predicate (=> symbol) in the Expression type (see

(=> "endSimpleExpression")

but it's still not working. I know for sure that it has to do with the relationship between the types Expressions and Factor (because if I don't add Expression types in the Factor type, the DSL works just fine). I assume that I am not placing the syntactic predicate on the right place. Another solution that I considered was the use of left Factoring, but I don't know how to apply left factoring in this case. I am curious to your thoughts on this problem.

grammar org.xtext.example.mydsl.FinalDsl with org.eclipse.xtext.common.Terminals

generate finalDsl "http://www.xtext.org/example/mydsl/FinalDsl"


Model:
    'functionName' name = STRING
    functions += FunctionElements*
;

// Function elements of which the model exists. The model can contain
// library functions, for loops, and if/else statements.
  FunctionElements:
    ifElseStatements += IfElseStatements |
    statements += Statement 
; 

// IfElse Statements requiring if statements and optionally followed by
// one else statement.
IfElseStatements: 
    ifStatements += IfStatements
    (elseStatement = ElseStatement)?
;

// If statements requiring conditions and optionally followed by
// library functions or for loops.
IfStatements:
    'if'
    expression = Expression
    (ifFunctions += libraryFunctionsEnum | forLoops += ForLoops)
;

// Else statement requiring one or multiple library functions.
ElseStatement:
    'else' elseFunctions += libraryFunctionsEnum
;

// For loops requiring one condition and followed by zero or more
// library functions
ForLoops:
    'for'
    expressions = Expression
    libraryFunctions += libraryFunctionsEnum*

;


Statement:
    //compoundStatement += CompoundStatement | //left out of Statement because 
    // otherwise a recursive call exists (statement += compoundstatement += statement
    simpleStatement += SimpleStatement |
    structuredStatement += StructuredStatement
;

SimpleStatement:
    classOperationStatement += ClassOperationStatement | 
    libraryInterFaceMethodStatement += LibraryInterFaceMethodStatement | 
    libraryPersistenceMethodStatement += LibraryPersistenceMethodStatement
;

StructuredStatement:
    forLoops += ForLoops | ifElseStatements += IfElseStatements
;



ClassOperationStatement:
    classOperationName += libraryFunctionsEnum
;

LibraryInterFaceMethodStatement:
    interfaceMethods += libraryInterFaceMethodStatementEnum
;


LibraryPersistenceMethodStatement:
    persistenceMethods += libraryPersistenceMethodStatementEnum
;




//*Eventually filled with details from class diagram, but for now we manually fill it for the sake of testing.
enum libraryFunctionsEnum:
    login='login'|
    hasCode= 'encrypt'|
    display='display'
;

enum libraryPersistenceMethodStatementEnum:
    createInstance = "createInstance" |
    log = "log"
;

enum libraryInterFaceMethodStatementEnum:
    mesasge = "message" |
    error = "error"
;

Expression:
simpleExpression = SimpleExpression 
(relationalOperator = RelationalOperator 
additionalSimpleExpression = SimpleExpression)?
(=> "endSimpleExpression")
;


SimpleExpression:

    term = Term
    additionalExpressions += AdditionalExpressions*
;

AdditionalExpressions:
    additionOperator = AdditionOperator
    term = Term
;

Term:
    factorTerm = Factor
    additionalTerm += AdditionalTerm*
;

AdditionalTerm:
    multiplicationOperator = MultiplicationOperator 
    factor = Factor
;

// We can optionally integrate Java types right here (int, boolean, string, etc.)
Factor: {Factor} (
    "("  expression = Expression ")" |
    //'not' factor += Factor |
     operationParameterName = OperationParameterName |
    classAttributeName += ClassAttributeName |
     INT //| STRING //| set = Set 
    )
;

OperationParameterName: // We can use identifiers right here, but for now I put in a string
    'operationParameter' STRING
;

ClassAttributeName: // We can use identifiers right here, but for now I put in a string
    STRING
;

RelationalOperator:
"=" | "<>" | "<" | "<=" | ">" | ">=" | "in"
;

AdditionOperator:
"+" | "-" | "or"
;

MultiplicationOperator:
"*" | "/" | "and"
;

enum logicalOperators:
    greaterThan='>'|
    smallerThan='<'|
    greaterOrEqualThan='=>'|
    smallerOrEqualThan='<='|
    equalTo='=='
;
Solution

  • InternalFinalDsl.g:139:2: [fatal] rule ruleFunctionElements has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2.

    So let's look at the rule FunctionElements:

      FunctionElements:
    ifElseStatements += IfElseStatements |
    statements += Statement 
;

    Okay, so FunctionElements can either be an IfElseStatement or a Statement. That sounds suspicious and sure enough: a Statement can be a StructuredStatement, which can in turn be an IfElseStatement. So the above is ambiguous because an IfElseStatement could either be derived directly via FunctionElements -> IfElseStatement or indirectly via FunctionElements -> Statement -> StructuredStatement -> IfElseStatement.

    So you should simply remove the IfElseStatement alternative because it is redundant.