Skip to main content


Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Modeling » TMF (Xtext) » Left recursive type declarations in Xtext(Working around left-recursive languages)
icon5.gif  Left recursive type declarations in Xtext [message #1698334] Sun, 14 June 2015 10:19 Go to next message
Alex Blewitt is currently offline Alex BlewittFriend
Messages: 12
Registered: July 2009
Junior Member
I'm experimenting with Xtext as a means to generate a Swift IDE at https://github.com/alblue/swiftclipse. I've run into a problem that is a property of the language (rather than the grammar) which is left-recursive; so it's not a case of simply modifying the grammar to resolve.

I've put an example at https://github.com/alblue/swiftclipse/blob/experiments/xtext-recursive/xtext.Recursive/src/xtext/Recursive.xtext (in the experiments/xtext-recursive branch) that exhibits the problem:

grammar xtend.Recursive with org.eclipse.xtext.common.Terminals

generate myDsl "http://www.eclipse.org/xtext/Recursive"

Program:
	statements+=Statement+;

Statement:
	'var' ID ':' Type ';';

Type:
	'Int' |
//	Type '?' | // uncomment this to see the problem
	'Bool';


This admits simple variable type declarations as:

var foo:Int;
var bar:Int;


What it needs to be able to support is statements like:

var foo:Int?;
var bar:Int??;


(In other words, it's not sufficient to define something like "OptionalType:Type '?'?" and then hoist everything; a type is also an array-of-type as well.)

Can this be implemented in Xtext somehow?
Re: Left recursive type declarations in Xtext [message #1698339 is a reply to message #1698334] Sun, 14 June 2015 13:56 Go to previous messageGo to next message
Christian Dietrich is currently offline Christian DietrichFriend
Messages: 14661
Registered: July 2009
Senior Member
Program:
	statements+=Statement+;

Statement:
	'var' ID ':' type=Type ';';

Type:
	SimpleType ("?" {OptinalType.type=current})*
;

SimpleType returns Type:
	({IntType}"Int" | {BoolType}"Bool");
	
	


Twitter : @chrdietrich
Blog : https://www.dietrich-it.de
Re: Left recursive type declarations in Xtext [message #1698340 is a reply to message #1698339] Sun, 14 June 2015 14:11 Go to previous messageGo to next message
Alex Blewitt is currently offline Alex BlewittFriend
Messages: 12
Registered: July 2009
Junior Member
So it's not just as simple as sticking a * on the end. There are other intersecting rules as well. The extended pattern needs to admit other suffixes as well:

Type: 
  ArrayType | DictionaryType | OptionalType | ImplicitlyUnwrappedType | SimpleType;

ArrayType returns Type:
    '[' Type ']';

DictionaryType:
    '[' key=Type ':' value=Type ']';

OptionalType returns Type:
    Type '?';

ImplicitlyUnwrappedOptionalType returns Type:
    Type '!';


In other words, we need to be able to parse things like:

[Int!]?!


It's not just 'how many optionals are there on the end' -- not only that, but
Int??
is a shorthand for
Optional<Optional<Int>>
. So it's semantically important to know how many optionals there are.
Re: Left recursive type declarations in Xtext [message #1698345 is a reply to message #1698340] Sun, 14 June 2015 16:17 Go to previous messageGo to next message
Ed Willink is currently offline Ed WillinkFriend
Messages: 7655
Registered: July 2009
Senior Member
HI

If you want to count ?'s accumulate them in a collection

qMarks+='?'

Regards

Ed Willink


On 14/06/2015 15:11, Alex Blewitt wrote:
> So it's not just as simple as sticking a * on the end. There are other
> intersecting rules as well. The extended pattern needs to admit other
> suffixes as well:
>
>
> Type: ArrayType | DictionaryType | OptionalType |
> ImplicitlyUnwrappedType | SimpleType;
>
> ArrayType returns Type:
> '[' Type ']';
>
> DictionaryType:
> '[' key=Type ':' value=Type ']';
>
> OptionalType returns Type:
> Type '?';
>
> ImplicitlyUnwrappedOptionalType returns Type:
> Type '!';
>
>
> In other words, we need to be able to parse things like:
>
>
> [Int!]?!
>
>
> It's not just 'how many optionals are there on the end' -- not only
> that, but Int?? is a shorthand for Optional<Optional<Int>>. So it's
> semantically important to know how many optionals there are.
Re: Left recursive type declarations in Xtext [message #1698346 is a reply to message #1698340] Sun, 14 June 2015 16:20 Go to previous messageGo to next message
Sven Efftinge is currently offline Sven EfftingeFriend
Messages: 1823
Registered: July 2009
Senior Member
Would this work for your case?

The entry-rule would be TypeReference.

TypeReference returns Type:
    Type ({UnwrappedOrOptionalType.type=current} operators+=('!'|'?')+)?;

Type: 
  ArrayType | DictionaryType | SimpleType;

ArrayType returns Type:
    '[' component=Type ']';

DictionaryType:
    =>('[' key=Type ':') value=Type ']';

SimpleType:
	name=ID
;

[Updated on: Sun, 14 June 2015 16:20]

Report message to a moderator

Re: Left recursive type declarations in Xtext [message #1698347 is a reply to message #1698340] Sun, 14 June 2015 16:22 Go to previous message
Christian Dietrich is currently offline Christian DietrichFriend
Messages: 14661
Registered: July 2009
Senior Member
Hi,

nobody says left factoring is easy. it is acutally pita
this semantic is kept by the star. through the tree rewrite you actually dont get a list, but a tree.
the same way the unrapping could happen

Statement:
	'var' ID ':' type=Type ';';

Type:
	(
	( "[" Type ((":" {MapType.keyType=current} valueType=Type)|{ArrayType.type=current})  "]")
	
	|SimpleType
	)(("?" {OptinalType.type=current}) | ("!"{UnwrappedOptional.type=current}))*
;


Twitter : @chrdietrich
Blog : https://www.dietrich-it.de
Previous Topic:Dependencies between myDsl - Files
Next Topic:Content assist in embedded editor
Goto Forum:
  


Current Time: Tue Mar 19 09:09:33 GMT 2024

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

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

Back to the top