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  |
 Matthias Meyer
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 123 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  |
Ed Willink
Messages: 7655
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 #1071291 is a reply to message #1071286] |
Fri, 19 July 2013 19:10 |
Ed Willink
Messages: 7655
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: Anybody? [message #1073179 is a reply to message #1073152] |
Wed, 24 July 2013 09:18 |
Sebastian Zarnekow
Messages: 3118
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
|
|
| | |
Goto Forum:
Current Time: Wed Apr 24 15:32:01 GMT 2024
Powered by FUDForum. Page generated in 0.03953 seconds |
] 
Search
Help
Register
Login
Home
