Eclipse Community Forums - RDF feed
https://www.eclipse.org/forums/
Eclipse Community Forumsxtext unusably slow for editing and building certain kinds of grammars
https://www.eclipse.org/forums/index.php/mv/msg/492577/1071186/#msg_1071186
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
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.]]>Matthias Meyer2013-07-19T14:11:29-00:00Re: xtext extremely slow for my grammar
https://www.eclipse.org/forums/index.php/mv/msg/492577/1071237/#msg_1071237
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.]]>Ed Willink2013-07-19T16:10:24-00:00Re: xtext extremely slow for my grammar
https://www.eclipse.org/forums/index.php/mv/msg/492577/1071286/#msg_1071286
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.]]>Matthias Meyer2013-07-19T18:54:44-00:00Re: xtext extremely slow for my grammar
https://www.eclipse.org/forums/index.php/mv/msg/492577/1071291/#msg_1071291
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.]]>Ed Willink2013-07-19T19:10:02-00:00Re: xtext extremely slow for my grammar
https://www.eclipse.org/forums/index.php/mv/msg/492577/1071294/#msg_1071294
Matthias Meyer2013-07-19T19:12:58-00:00Anybody?
https://www.eclipse.org/forums/index.php/mv/msg/492577/1073152/#msg_1073152
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.
]]>Matthias Meyer2013-07-24T08:17:26-00:00Re: Anybody?
https://www.eclipse.org/forums/index.php/mv/msg/492577/1073179/#msg_1073179
> 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]]>Sebastian Zarnekow2013-07-24T09:18:07-00:00Re: Anybody?
https://www.eclipse.org/forums/index.php/mv/msg/492577/1073219/#msg_1073219
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.
Matthias]]>Matthias Meyer2013-07-24T10:41:31-00:00Re: Anybody?
https://www.eclipse.org/forums/index.php/mv/msg/492577/1074343/#msg_1074343
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".