Eclipse Community Forums: TMF (Xtext) » Another problem with left recursion

Help

Home

Home » Modeling » TMF (Xtext) » Another problem with left recursion

Show: Today's Messages :: Show Polls :: Message Navigator

Another problem with left recursion [message #1747132]

Wed, 09 November 2016 21:12

Luiz Paulo Franz

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 153 times)

Report message to a moderator

Re: Another problem with left recursion [message #1747192 is a reply to message #1747132]

Thu, 10 November 2016 15:40

Christian Dietrich

Messages: 14496
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: https://www.itemis.com/en/it-services/methods-and-tools/xtext
Twitter : @chrdietrich
Blog : https://www.dietrich-it.de

Report message to a moderator

Re: Another problem with left recursion [message #1747294 is a reply to message #1747192]

Fri, 11 November 2016 17:50

Luiz Paulo Franz

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

Report message to a moderator

Re: Another problem with left recursion [message #1747298 is a reply to message #1747294]

Fri, 11 November 2016 18:49

Christian Dietrich

Messages: 14496
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: https://www.itemis.com/en/it-services/methods-and-tools/xtext
Twitter : @chrdietrich
Blog : https://www.dietrich-it.de

Report message to a moderator

Re: Another problem with left recursion [message #1747447 is a reply to message #1747298]

Mon, 14 November 2016 20:27

Luiz Paulo Franz

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.

Report message to a moderator

Re: Another problem with left recursion [message #1747454 is a reply to message #1747447]

Tue, 15 November 2016 01:47

Luiz Paulo Franz

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.

Report message to a moderator

Re: Another problem with left recursion [message #1747458 is a reply to message #1747454]

Tue, 15 November 2016 06:07

Christian Dietrich

Messages: 14496
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: https://www.itemis.com/en/it-services/methods-and-tools/xtext
Twitter : @chrdietrich
Blog : https://www.dietrich-it.de

Report message to a moderator

Re: Another problem with left recursion [message #1747483 is a reply to message #1747458]

Tue, 15 November 2016 10:55

Luiz Paulo Franz

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.

Report message to a moderator

Previous Topic:	How to access fields of rules within a grammar
Next Topic:	Folding package/ file

Goto Forum:

-=] Back to Top [=-

[ Syndicate this forum (XML) ] [

]

Current Time: Sat Jun 03 20:32:30 GMT 2023

.:: Contact :: Home ::.

Breadcrumbs

Sign up to our Newsletter