Eclipse Community Forums
Forum Search:

Search      Help    Register    Login    Home
Home » Modeling » TMF (Xtext) » xtext unusably slow for editing and building certain kinds of grammars(a small grammer (< 100 productions) with two similar production trees requires more than 30 minutes to build, xtext (editing the xtext file) frequently hangs for more than 30 minutes. Generated par)
xtext unusably slow for editing and building certain kinds of grammars [message #1071186] Fri, 19 July 2013 14:11 Go to next message
Matthias Meyer is currently offline Matthias MeyerFriend
Messages: 6
Registered: July 2013
Junior Member
Hello forum,

I am implementing a subset of the "go" programming language for an experimental computer system. In a first step, I just want to describe the grammar to have syntax checking and syntax highlighting in Eclipse.

Unfortunately, I encountered a serious problem:

The syntax specification for "go" requires that composite literals "T{...}" must appear within parentheses "(T{...})" in some contexts to resolve a parsing ambiguity between the keywords "if", "for", "switch" and the corresponding "{".

To describe a corresponding grammar in xtext, I duplicated the production tree for expressions. Production "Expression" is used whenever composite literals may appear without parantheses, while production "R_Expression" is used in the context described above. The only difference between the two production trees is that "Expression" allows composite literals as primary prefixes, while "R_Expression" does not.

For this grammar, building xtext artifacts is EXTREMELY slow (takes more than 30 minutes). In addition to that, editing the xtext file in Eclipse becomes more than unresponsive, the GUI frequently freezes for more than 30 minutes, and starting Eclipse with my xtext workspace takes 30 minutes as well.

I managed to isolate the source of the problem. Xtext seems to have problems with "self similar" grammars, i.e. grammars that contain similar production trees.

I append my grammar to this post, the problem is easy to reproduce, you just need one single file. It contains 18 terminal definitions and less than 90 productions.

As soon as you remove the comment from line 145 and add it to line 145

Expression:
CondAndExpr ('||' CondAndExpr)*
// R_CondAndExpr ('||' R_CondAndExpr)*
;

===>

Expression:
// CondAndExpr ('||' CondAndExpr)*
R_CondAndExpr ('||' R_CondAndExpr)*
;

there is effectively only one production tree left for expressions, and the problem does not exist anymore, i.e. the editor becomes fairly responsive and building xtext artifacts completes in less than a minute. But of course, the grammar does not describe the required syntax anymore.

I reproduced the problem with various versions of Eclipse (3 & 4), xtext (2.2, 2.4) and different platforms (Linux, MacOS).

Is this a known problem? Is something wrong with my grammar? Is there a better way to solve my problem? Or is there a workaround to avoid this problem?

I am grateful for any kind of help.

Matthias.
  • Attachment: Gosub.xtext
    (Size: 5.88KB, Downloaded 32 times)

[Updated on: Tue, 23 July 2013 13:04]

Report message to a moderator

Re: xtext extremely slow for my grammar [message #1071237 is a reply to message #1071186] Fri, 19 July 2013 16:10 Go to previous messageGo to next message
Ed Willink is currently offline Ed WillinkFriend
Messages: 4154
Registered: July 2009
Senior Member
Hi

Under the hoods Xtext is LL and so isn't very smart Pervesely the EBNF
capabilities give you left recuersion after all. LL pursues a simple
left parse approach and backs up if its wrong and resolves ambiguioties
accidentally by choosing the first . (An LALR grammar detects the
ambiguities and compile time and produces an optimized parsing state
machine.) To use Xtext effectively you need to work with it's
limitations. You may find implementing the grammar first with an LAKLR
toolenables you to understand it better.

To make the grammar fast in Xtext you MUST factor out common terms so
that Xtext never needs to retry.

I had a similar problem with the OCL grammar. When I instrumented an
inner parsing routine it was being called exponentially: more than a
million times for a simple repetious example. When I refactored the
common prefixes the exponential cost vanished and the inner routine was
executed barely a hundred times.

Regards

Ed Willink




On 19/07/2013 15:49, Matthias Meyer wrote:
> Hello forum,
>
> I am implementing a subset of the "go" programming language for an experimental computer system. In a first step, I just want to describe the grammar to have syntax checking and syntax highlighting in Eclipse.
>
> Unfortunately, I encountered a serious problem:
>
> The syntax specification for "go" requires that composite literals "T{...}" must appear within parentheses "(T{...})" in some contexts to resolve a parsing ambiguity between the keywords "if", "for", "switch" and the corresponding "{".
>
> To describe a corresponding grammar in xtext, I duplicated the production tree for expressions. Production "Expression" is used whenever composite literals may appear without parantheses, while production "R_Expression" is used in the context described above. The only difference between the two production trees is that "Expression" allows composite literals as primary prefixes, while "R_Expression" does not.
>
> For this grammar, building xtext artifacts is EXTREMELY slow (takes more than 30 minutes). In addition to that, editing the xtext file in Eclipse becomes more than unresponsive, the GUI frequently freezes for more than 30 minutes, and starting Eclipse with my xtext workspace takes 30 minutes as well.
>
> I managed to isolate the source of the problem. Xtext seems to have problems with "self similar" grammars, i.e. grammars that contain similar production trees.
>
> I append my grammar to this post, the problem is easy to reproduce, you just need one single file. It contains 18 terminal definitions and less than 90 productions.
>
> As soon as you remove the comment from line 145 and add it to line 145
>
> Expression:
> CondAndExpr ('||' CondAndExpr)*
> // R_CondAndExpr ('||' R_CondAndExpr)*
> ;
>
> ===>
>
> Expression:
> // CondAndExpr ('||' CondAndExpr)*
> R_CondAndExpr ('||' R_CondAndExpr)*
> ;
>
> there is effectively only one production tree left for expressions, and the problem does not exist anymore, i.e. the editor becomes fairly responsive and building xtext artifacts completes in less than a minute. But of course, the grammar does not describe the required syntax anymore.
>
> I reproduced the problem with various versions of Eclipse (3 & 4), xtext (2.2, 2.4) and different platforms (Linux, MacOS).
>
> Is this a known problem? Is something wrong with my grammar? Is there a better way to solve my problem? Or is there a workaround to avoid this problem?
>
> I am grateful for any kind of help.
>
> Matthias.
Re: xtext extremely slow for my grammar [message #1071286 is a reply to message #1071237] Fri, 19 July 2013 18:54 Go to previous messageGo to next message
Matthias Meyer is currently offline Matthias MeyerFriend
Messages: 6
Registered: July 2013
Junior Member
Hi Ed,

thank you for the suggestions.

Are you talking about the performance of generating the parser (building xtext artefacts, editing the xtext file in eclipse) or the performance of the generated parser?

In my case, the generated parser (i.e. Eclipse plugin) is fine, the problems I described occur while I work with the xtext file, i.e. while xtext parses my grammar, while xtext generates the plugin etc., NOT while the plugin parses my language.

Matthias.
Re: xtext extremely slow for my grammar [message #1071291 is a reply to message #1071286] Fri, 19 July 2013 19:10 Go to previous messageGo to next message
Ed Willink is currently offline Ed WillinkFriend
Messages: 4154
Registered: July 2009
Senior Member
Hi

Different issue. I'm talking about the speed of parsing your language.
Not Xtext parsing your grammar.

Xtext building is not spectacularly fast, but I don't find the 20
seconds that some of many editors take nearly enough of a problem to
demand faster speed.

Regards

Ed Willink


On 19/07/2013 19:54, Matthias Meyer wrote:
> Hi Ed,
>
> thank you for the suggestions.
>
> Are you talking about the performance of generating the parser
> (building xtext artefacts, editing the xtext file in eclipse) or the
> performance of the generated parser?
>
> In my case, the generated parser (i.e. Eclipse plugin) is fine, the
> problems I described occur while I work with the xtext file, i.e.
> while xtext parses my grammar, while xtext generates the plugin etc.,
> NOT while the plugin parses my language.
>
> Matthias.
Re: xtext extremely slow for my grammar [message #1071294 is a reply to message #1071291] Fri, 19 July 2013 19:12 Go to previous messageGo to next message
Matthias Meyer is currently offline Matthias MeyerFriend
Messages: 6
Registered: July 2013
Junior Member
Of course, but in my case it takes 30 minutes, and the editor frequently hangs for 30 minutes as well. This is a blocker, not only an annoyance.
Anybody? [message #1073152 is a reply to message #1071291] Wed, 24 July 2013 08:17 Go to previous messageGo to next message
Matthias Meyer is currently offline Matthias MeyerFriend
Messages: 6
Registered: July 2013
Junior Member
Any ideas?

It's hard for me to believe that nobody encountered this problem before. Xtext would be great for my application, a simple syntax highlighting plugin works already, but any simple change of my .xtext file requires hours (literally!) because of xtext editor hangs and extremely long build times.

Re: Anybody? [message #1073179 is a reply to message #1073152] Wed, 24 July 2013 09:18 Go to previous messageGo to next message
Sebastian Zarnekow is currently offline Sebastian ZarnekowFriend
Messages: 2940
Registered: July 2009
Senior Member
Am 24.07.13 10:17, schrieb Matthias Meyer:
> Any ideas?
>
> It's hard for me to believe that nobody encountered this problem before.
> Xtext would be great for my application, a simple syntax highlighting
> plugin works already, but any simple change of my .xtext file requires
> hours (literally!) because of xtext editor hangs and extremely long
> build times.
>
>

Hi Matthias,

sorry for the delayed response.

The grammar that you appended is unfortunately completely bogus and does
contain almost no assignments, e.g. it will not produce a meaningful
AST. I can imagine that the problem vanishes if you fix the grammar and
enable the parallel hierachy afterwards. If that's not an option, I'd
comment all rules besides the one that you start working on and enable
them step by step. Since the problem seems to be related to coloring,
opening the grammar with a plain text editor may help, too.

But the problem is indeed reproducable, could you please file a bugzilla?

Regards,
Sebastian
--
Looking for professional support for Xtext, Xtend or Eclipse Modeling?
Go visit: http://xtext.itemis.com
Re: Anybody? [message #1073219 is a reply to message #1073179] Wed, 24 July 2013 10:41 Go to previous messageGo to next message
Matthias Meyer is currently offline Matthias MeyerFriend
Messages: 6
Registered: July 2013
Junior Member
Hi Sebastian,

thank you for your response, and thanks for taking the time to reproduce the problem.

Regarding the "bogus" grammar: I wanted to start with a pure grammar first to get a simple editor with syntax highlighting and syntax checking. Next step will be generating the AST to enable more features. Because of the reported problem, however, I started to doubt whether I should continue using xtext for my project.

I filed a bug one week ago:
https://bugs.eclipse.org/bugs/show_bug.cgi?id=413171

Thanks again,

Matthias
Re: Anybody? [message #1074343 is a reply to message #1073219] Fri, 26 July 2013 14:45 Go to previous message
Matthias Meyer is currently offline Matthias MeyerFriend
Messages: 6
Registered: July 2013
Junior Member
Hi Sebastian,

someone responded to my bug report, acknowledging what you already suspected:

"You face an algorithmic performance problem which bites you, because you don't use any assignments".

Thanks again for your help.

Matthias.
Previous Topic:[XBase] Extending XBase to support different call ids
Next Topic:Auto edit strategy with ID's
Goto Forum:
  


Current Time: Wed Nov 26 14:15:34 GMT 2014

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

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