Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Modeling » TMF (Xtext) » Another problem with left recursion
Another problem with left recursion [message #1747132] Wed, 09 November 2016 21:12 Go to next message
Luiz Paulo Franz is currently offline Luiz Paulo FranzFriend
Messages: 19
Registered: November 2016
Junior Member
Hello guys,

I have a problem with the left recursion, I need to represent a grammar, but it's a bit strange grammar for those accustomed to formal languages.

The grammar makes references to itself several times, and it is all represented in a single rule (a giant one). It is an academic work, and I am not able to transcribe the grammar of the paper for Xtext grammar language, I will attach an image , Which contains the proposed grammar, my results so far are these:


Relax:
	root+=General+;

terminal BOOLEAN returns ecore::EBoolean: 
    'true'|'false'
;

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


ShallOperator:
	'shall' elements=General;

MayOperator:
	"may" action1=General 'or' action2=General;
	
EventuallyOperator:
	'eventually' element=General;

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



The error displayed is: "this rule call is part of a recursive call graph" on the line
Left = General 'until' right = General;

I already researched this, but I could not apply a solution in my situation, as you can see in the commented lines.

I'm new to Xtext, I need help with this, and I take this opportunity to ask if I'm representing the grammar correctly in Xtext (see attached original grammar).

Any help is welcome.

Thank you.
  • Attachment: relax.png
    (Size: 68.35KB, Downloaded 50 times)
Re: Another problem with left recursion [message #1747192 is a reply to message #1747132] Thu, 10 November 2016 15:40 Go to previous messageGo to next message
Christian Dietrich is currently online Christian DietrichFriend
Messages: 10799
Registered: July 2009
Senior Member
can you try something like the traditional xtext left factoring approach

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;



Need professional support for Xtext, Xpand, EMF?
Go to: http://xtext.itemis.com
Twitter : @chrdietrich
Blog : christiandietrich.wordpress.com
Re: Another problem with left recursion [message #1747294 is a reply to message #1747192] Fri, 11 November 2016 17:50 Go to previous messageGo to next message
Luiz Paulo Franz is currently offline Luiz Paulo FranzFriend
Messages: 19
Registered: November 2016
Junior Member
Hi, thanks for the reply.

Can you please explain the code to me? Especially the part of the "until" operator, or indicate materials to study this on their own?

I put your grammar here, syntax errors (in grammar) do not exist, but it does not allow the formulation of valid sentences, for example, this would be a valid sentence:

the ventilation shall work until the environment is cool.


However, the natural language strings contained in "STRING" are apparently not allowed. Any idea?

I have studied formal languages on graduation, but I never before developed one.

Again sorry, I do not have much knowledge about compilers, or DSLs, any help is welcome.

Thank you very much
Re: Another problem with left recursion [message #1747298 is a reply to message #1747294] Fri, 11 November 2016 18:49 Go to previous messageGo to next message
Christian Dietrich is currently online Christian DietrichFriend
Messages: 10799
Registered: July 2009
Senior Member
have a look at assigned actions in the doc and https://typefox.io/parsing-expressions-with-xtext

your problem that "this" is a string, an this is not

thus

Primitive:
BooleanValue | StringValue | IdValue
;

IdValue:
value=ID
;


Need professional support for Xtext, Xpand, EMF?
Go to: http://xtext.itemis.com
Twitter : @chrdietrich
Blog : christiandietrich.wordpress.com
Re: Another problem with left recursion [message #1747447 is a reply to message #1747298] Mon, 14 November 2016 20:27 Go to previous messageGo to next message
Luiz Paulo Franz is currently offline Luiz Paulo FranzFriend
Messages: 19
Registered: November 2016
Junior Member
Hi, thanks for your response, it really helped me.
But now another problem. If I assume, as you suggested:

IdValue:
value=ID
;


For the following statement (a correct one):

"Ventilation shall operate until the environment is cool."

The parser processes the words separately, creating nodes for the words "the", "ventilation" in the parser tree. I need this to be processed as a single input, such as "the ventilation"

I'm trying to do it, but to no avail.

My results so far:

terminal ST: ('a'..'z'|'A'..'Z'|'_'|'0'..'9'|' ')*  ;


With this, the parser considers the space " ", but the problem is that other operators, like ShallOperator, are now considered as part of this rule. Any ideas?

Bellow I present the grammar:

Relax:
root+=General+;

terminal BOOLEAN returns ecore::EBoolean:
	'true'|'false'
;

terminal ST: ('a'..'z'|'A'..'Z'|'_'|'0'..'9'|' ')* ;

General:
	root=Rest =>({UntilOperator.left=current}'until' right=General)*;

Rest:
	Primitive|ShallOperator|MayOperator|EventuallyOperator
;

Primitive:
BooleanValue | StringValue
;

BooleanValue:
value=BOOLEAN
;

StringValue:
value=ST
;

ShallOperator:
'shall' elements=General;



Thank you very much.
Re: Another problem with left recursion [message #1747454 is a reply to message #1747447] Tue, 15 November 2016 01:47 Go to previous messageGo to next message
Luiz Paulo Franz is currently offline Luiz Paulo FranzFriend
Messages: 19
Registered: November 2016
Junior Member
Hello, I think I was able to solve this problem as follows:

terminal FREESTRING:  ('a'..'z'|'A'..'Z'|'_'|'0'..'9')*  ;

//Natural Language, trechos que serao em LN
NL hidden(WS): FREESTRING ( FREESTRING)*;


So I can have values with spaces and even with line breaks, which is perfect. But now I am facing another problem, when I test the following entry in the grammar:

"The synchronization process shall be initiated as early as possible after Alice enters the room and as close as possible to 30 min intervals thereafter"

The Xtext displays the following error:

"no viable alternative at input 'eof' '"

Also, I need to define that the ";" Is the delimiter of a block, that after this, a new block is started, how to do that? And how can I do to scape the ";" inside a block?

The grammar follows:

//a primeira regra deve ser uma regra da gramatica
Relax:
root+=General+;
//declaramos tipos ainda nao existentes
terminal BOOLEAN returns ecore::EBoolean:'true'|'false';
terminal FREESTRING:  ('a'..'z'|'A'..'Z'|'_'|'0'..'9')*  ;

//Natural Language, trechos que serao em LN
NL hidden(WS): FREESTRING ( FREESTRING)*;

//Essa eh a regra mae da gramatica, ja tratando a recursividade a esquerda 
General:
	root=Rest =>({UntilOperator.left=current}'until' right=General)*;

//aqui se encontram as demais regras da gramatica
Rest:
	Primitive|ShallOperator|MayOperator|EventuallyOperator|BeforeOperator|AfterOperator|InOperator|AsCloseOperator|AsOperator|';'
;
// tipos primitivos, como boleanos (previstos na gramatica original) e os trechos em LN
Primitive:
	BooleanValue | StringValue
;
//novamente os operadores primitivos
BooleanValue:value=BOOLEAN;
StringValue:value=NL;

//aqui sao tratados todos os operandos (exceto o UNTIL) 
ShallOperator:
'shall' elements=General;

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

EventuallyOperator:
'eventually' element=General;

BeforeOperator:
	'before' event=NL other=General
;

AfterOperator:
	'after' event=NL other=General
;

InOperator:
	'in' t=NL other=General
;
//Frquencia ou Quantidade f or q
AsCloseOperator:
	'as' 'close' 'as' 'possible' 'to' ForQ=NL other=General  
;

AsOperator:
	'as' ('early'|'late'|'many'|'few') 'as' 'possible' value=General
;


The doubts are:

How to resolve the error: "no viable alternative at input ' eof ' "?
How do I set multiple blocks in a same file using the ";" delimiter?
How to escape ";" Inside a block?

Again, thanks for the help.
Re: Another problem with left recursion [message #1747458 is a reply to message #1747454] Tue, 15 November 2016 06:07 Go to previous messageGo to next message
Christian Dietrich is currently online Christian DietrichFriend
Messages: 10799
Registered: July 2009
Senior Member
well if you want a semikolon you need to introduce it as keyword.
if you want to escape it you need to introduce a escape symbol (have a look at escaping inside STRING rule from terminals)

AsCloseOperator:
'as' 'close' 'as' 'possible' 'to' ForQ=NL other=General
;

=> if all gets eaten up by NL what does into general ?!?


Need professional support for Xtext, Xpand, EMF?
Go to: http://xtext.itemis.com
Twitter : @chrdietrich
Blog : christiandietrich.wordpress.com
Re: Another problem with left recursion [message #1747483 is a reply to message #1747458] Tue, 15 November 2016 10:55 Go to previous message
Luiz Paulo Franz is currently offline Luiz Paulo FranzFriend
Messages: 19
Registered: November 2016
Junior Member
I made this rule this way because I'm trying to translate the grammar, and in the original grammar this is something like this:

G = simple and general grammar rule with a lot of recursive calls.

AS CLOSE AS POSSIBLE TO f G

In the original grammar, this rule (G) has several recursive calls, I do not know if I'm doing the right thing in Xtext, but there, I have no rule for "f", I just know it's some input, however it should be possible to continue writing the phrases.

Thanks for your help.
Previous Topic:Hide technical UID in XText editor
Next Topic:How to override and extend the JvmModelGenerator to generate complex enumerations
Goto Forum:
  


Current Time: Wed Jun 28 19:32:57 GMT 2017

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

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