Skip to main content


Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Modeling » TMF (Xtext) » Left Recursion Problem in xText
Left Recursion Problem in xText [message #1806473] Thu, 09 May 2019 14:01 Go to next message
J Bouwhuis is currently offline J BouwhuisFriend
Messages: 16
Registered: April 2019
Junior Member
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='=='
;

[Updated on: Thu, 09 May 2019 14:07]

Report message to a moderator

Re: Left Recursion Problem in xText [message #1806513 is a reply to message #1806473] Fri, 10 May 2019 05:24 Go to previous messageGo to next message
Christian Dietrich is currently offline Christian DietrichFriend
Messages: 13067
Registered: July 2009
Senior Member
this is a cross post from
https://stackoverflow.com/questions/56062149/solving-a-left-recursion-problem-in-xtext/56068261#56068261


Need professional support for Xtext, Xpand, EMF?
Go to: https://www.itemis.com/en/xtext/
Twitter : @chrdietrich
Blog : https://www.dietrich-it.de
Re: Left Recursion Problem in xText [message #1806534 is a reply to message #1806513] Fri, 10 May 2019 08:58 Go to previous message
J Bouwhuis is currently offline J BouwhuisFriend
Messages: 16
Registered: April 2019
Junior Member
Thanks for your reaction. Yes I also posted this on StackOverflow and the problem has already been solved over there. I was just about to comment on that in this topic; so the answer can be found in the StackOverflow topic. If this is against the policies (of the xText community), please let me know then I will stick to one forum from now on. I was thinking that by cross posting it on different forums I could reach more people providing feedback, but I see that most of the people replying on xText topics are active on most major forums anyway (so that would just make my topics redundant instead of them reaching more people).
Previous Topic:Test with a cross-reference model
Next Topic:How scoping works on Ecore Editor ?
Goto Forum:
  


Current Time: Wed Aug 21 06:02:28 GMT 2019

Powered by FUDForum. Page generated in 0.01704 seconds
.:: Contact :: Home ::.

Powered by: FUDforum 3.0.2.
Copyright ©2001-2010 FUDforum Bulletin Board Software

Back to the top