解决 xText 中的左递归问题

Question

我目前正致力于在 xText 中创建 DSL，我遇到了一个可能与歧义或左递归问题有关的问题。我不确定这两个问题中的哪一个适用于我的情况（我在网上找到的类似主题也提到这些问题通常看起来相关）但我猜它与左递归有关。

在我的 DSL 代码的第 100 行，我声明了一个名为 Expression 的规则。如您所见，它聚合了多种其他类型（它们再次聚合了多种其他类型，最终也可以聚合称为因子（第 130 行）的类型）。最终，整个 'aggregation tree' 归结为此因子类型的问题。如您所见，该类型可以再次聚合一个 Expression。所以有一个循环；一个 Expression 类型最终可以包含一个 Factor 类型，然后 Factor 类型可以再次包含一个 Expression 类型（之后这个循环理论上可以无限继续；我想这就是问题所在，因为 xText 使用的 ANTLR 解析器不是为此设计的一种递归）。我试图通过在 Expression 类型中使用句法谓词（=> 符号）来解决这个问题（参见

(=> "endSimpleExpression")

但还是不行。我确信它与表达式类型和因子类型之间的关系有关（因为如果我不在因子类型中添加表达式类型，DSL 就可以正常工作）。我假设我没有将句法谓词放在正确的位置。我考虑的另一个解决方案是使用左因子分解，但我不知道如何在这种情况下应用左因子分解。我很好奇你对这个问题的看法。

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='=='
;

Answer 1

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

那么让我们看一下规则FunctionElements:

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

好的，所以 FunctionElements 可以是 IfElseStatement 或 Statement。这听起来很可疑，但确实如此：Statement 可以是 StructuredStatement，而 StructuredStatement 又可以是 IfElseStatement。所以上面是模棱两可的，因为 IfElseStatement 可以通过 FunctionElements -> IfElseStatement 直接派生，也可以通过 FunctionElements -> Statement -> StructuredStatement -> IfElseStatement.

间接派生

所以您应该简单地删除 IfElseStatement 备选方案，因为它是多余的。

解决 xText 中的左递归问题

Solving a left recursion problem in xText

eclipse

xtext

xbase