Eclipse Community Forums: TMF (Xtext) » Compiling a larger grammar takes forever

Home » Modeling » TMF (Xtext) » Compiling a larger grammar takes forever(I'm trying to compile a large grammar in xText. It takes forever and does not generate useful error messages.)

Compiling a larger grammar takes forever [message #756639]

Mon, 14 November 2011 09:49

Eclipse User

Hello Guys!

I've converted a large grammar for the Arden Syntax from a SableCC-compatible form to xText. I mainly changed the grammar syntax and solved left-recursion to accomplish this. Also I added names to a couple of rule calls because in several rules, I got the warning "An unassigned rule call is not allowed when the 'current' is already created." .

The code basically is a valid LL(1)-grammar though it seems it is not a valid xCode grammar because of the problem presented below.

Aside from some warnings of the kind "The rule ... may be consumed without object instantiation...", the code validates fine.
But my problem is, when I try to generate the xText Artifacts, the compiler takes a really long time and does not finish. Once it ran for 6 hours, but it did not complete, so I canceled it.

Because the grammar is really big, I attached the project as a .zip file instead of copying it into this post.

Do you have any ideas how I can get the grammar compiled?
Maybe adding further names to rule calls or anything else?

Edit: I know that there are several Java Errors but I think they should be gone after code generation completes.

Attachment: arden.xtext.zip
(Size: 652.29KB, Downloaded 256 times)

[Updated on: Mon, 14 November 2011 09:54] by Moderator

Re: Compiling a larger grammar takes forever [message #756729 is a reply to message #756639]

Mon, 14 November 2011 15:37

Eclipse User

The ANTLR generation phase when generating the content assist parser exhibits continuous time outs. Along with all the other ANTLR errors which are given for the regular, full-blown parser this indicates that the generated ANTLR grammar is actually broken. This is not really surprising as the Xtext grammar itself is extremely "non-Xtext-y": Xtext is an abstraction over ANTLR (and LL(*), in general) but that also means that you have to take of proper feature assignment for Xtext to be able to do proper generation to an ANTLR grammar, which you are doing almost nowhere - it'd also take care of the "The rule ... may be consumed without object instantiation..." warnings and "An unassigned rule call is not allowed when the 'current' is already created." errors. Also, the layering into 2 grammars which only have terminal definitions is understandable in the light of other parser techniques but unpractical in the Xtext 'verse.

I think you should step back a bit and do a very small DSL from scratch in Xtext or study a few basic examples, in order to gain some more understanding of Xtext. From what I can see, the grammar's not that huge and should be processed within a minute or so on a decent machine. And I think by "adding further names to rule calls" you actually mean feature assignment - in which case, the answer is "yes, that would definitely help".

Re: Compiling a larger grammar takes forever [message #756846 is a reply to message #756729]

Tue, 15 November 2011 05:41

Eclipse User

On 11/14/2011 09:37 PM, Meinte Boersma wrote:
> The ANTLR generation phase when generating the content assist parser
> exhibits continuous time outs. Along with all the other ANTLR errors

by timeout do you mean messages like this?

error(10): internal error:
org.antlr.tool.Grammar.createLookaheadDFA(Grammar.java:1279): could not
even do k=1 for decision 81; reason: timed out (>1000ms)

I've just experienced it today by running the mwe2 file on the
domainmodel example of the tutorial "Five simple steps to your JVM
language"...

can this be avoided somehow?

cheers
Lorenzo

--
Lorenzo Bettini, PhD in Computer Science, DI, Univ. Torino
ICQ# lbetto, 16080134 (GNU/Linux User # 158233)
HOME: http://www.lorenzobettini.it MUSIC: http://www.purplesucker.com
http://www.myspace.com/supertrouperabba
BLOGS: http://tronprog.blogspot.com http://longlivemusic.blogspot.com
http://www.gnu.org/software/src-highlite
http://www.gnu.org/software/gengetopt
http://www.gnu.org/software/gengen http://doublecpp.sourceforge.net

Re: Compiling a larger grammar takes forever [message #756860 is a reply to message #756846]

Tue, 15 November 2011 06:24

Eclipse User

This might help: http://20000frames.blogspot.com/2010/09/dealing-with-could-not-even-do-k1-for.html
but probably only for cases where you see this once every often, instead of numerous times per run as is the case for Hannes.

Re: Compiling a larger grammar takes forever [message #756869 is a reply to message #756846]

Tue, 15 November 2011 06:53

Eclipse User

I was plagued by problems like this when using Xtext 1.x - needed *lots*
of memory due to excessive backtracking and inefficient handling in
Xtext of a particular case. This was later greatly improved in Xtext 2.x.

In my case, the root cause for the inefficiency was a large number of
small (one character) terminals in combination with lots of
backtracking. Since then, my grammar is rewritten (using an external lexer).

I still need to use more memory, and longer timeout than the default,
but now it never fails.

Regards
- henrik

On 11/15/11 11:41 AM, Lorenzo Bettini wrote:
> On 11/14/2011 09:37 PM, Meinte Boersma wrote:
>> The ANTLR generation phase when generating the content assist parser
>> exhibits continuous time outs. Along with all the other ANTLR errors
>
> by timeout do you mean messages like this?
>
> error(10): internal error:
> org.antlr.tool.Grammar.createLookaheadDFA(Grammar.java:1279): could not
> even do k=1 for decision 81; reason: timed out (>1000ms)
>
> I've just experienced it today by running the mwe2 file on the
> domainmodel example of the tutorial "Five simple steps to your JVM
> language"...
>
> can this be avoided somehow?
>
> cheers
> Lorenzo
>

Re: Compiling a larger grammar takes forever [message #756899 is a reply to message #756869]

Tue, 15 November 2011 08:22

Eclipse User

I'm pretty sure the generated lexer can still have severe performance problems (both runtime and while generating) with "small" terminals or large sets of terminals which have common prefixes, since the lexer effectively tries all of the terminals in sequence and doesn't employ, e.g., an efficient trie structure. One case where this applies is parsing XML/SGML - this and the fact that tag keywords occurring in PCDATA and entity references are lexed as keywords and not as texts, made me write a generic SGML lexer: see https://github.com/dslmeinte/Xtext2-DSLs - I'll write a blog about it one day as well.

Especially since Xtext2.x has some support for syntactic predicates, I don't see much reason why a well-behaved (and properly lexed) grammar would need the ANTLR backtracking switched on.

[Updated on: Tue, 15 November 2011 08:24] by Moderator

Re: Compiling a larger grammar takes forever [message #757437 is a reply to message #756899]

Fri, 18 November 2011 08:02

Eclipse User

Thanks for your help, guys. I added feature assignments in all important places and got beyond that endless loop. Yet there are still errors and warnings but I think I can fix them.

Regards
Hannes

Re: Compiling a larger grammar takes forever [message #757453 is a reply to message #757437]

Fri, 18 November 2011 08:40

Eclipse User

Be sure to check out http://www.antlr.org/works/index.html, as it could help quite a bit with getting rid of the errors and warnings. And you might be needing the syntactic predicate construct ('=>') seeing that the grammar's quite GPL-y.

Previous Topic:	Create new file wizard in context project menu -> new
Next Topic:	Invalidating the builder state

Goto Forum:

-=] Back to Top [=-

Current Time: Thu Jul 03 14:27:50 EDT 2025

.:: Contact :: Home ::.

Breadcrumbs

Sign up to our Newsletter