[antlr-interest] Parser generation takes hours
jp.raven at worldonline.fr
Wed Jan 6 13:31:39 PST 2010
Looks like I finally hit the nail on the head!
After doing some crucial left-factorizations, I can put all four sets of
mutually left-recursive productions all together, and the parser
generation takes only a couple of minutes. It seems even faster than
with only three sets without left-factorization.
It definitely looks like ANTLR is *very* sensible to left-factorization
In some way, it is quite normal since LL parsers requires it.
A big thank you for the help. It was greatly appreciated.
Le 06/01/2010 15:17, Jean-Pierre LAMBERT a écrit :
> After investigating the problem further, it looks like I have rounded up
> the faulty rules.
> In my grammar I have four sets of productions who are mutually
> (indirectly) left-recursive. After removing left-recursion, I have the
> "3 hours parser generation" problem.
> If I remove from the grammar any one of these four sets, after removing
> left-recursion the parser generation takes less than 5 minutes, which is
> the expected behavior.
> I will try tackling the other problems of the grammar (namely left
> factorisation for start) and I will see later if that changes anything
> when I include back all the four sets of mutually left-recursive rules.
> Thanks everybody.
> Le 06/01/2010 12:52, Jean-Pierre LAMBERT a écrit :
>> I have already started to remove parts of the grammar and the problem is
>> still there.
>> Le 06/01/2010 07:42, Gokulakannan Somasundaram a écrit :
>>> Hi Jean,
>>> I faced up with a similar issue, when i tried the migration
>>> of a LR parser. But it's definitely because of recursion stuffs. The
>>> way i removed is sort of layman stuff, but thought of just informing you.
>>> Try to split the grammar into multiple sections(group of
>>> rules) and try to add them one-by-one. You don't need to wait till the
>>> errors are emitted. As soon as the parser generation takes more than 3-4
>>> mins, just stop the generation. The last section, which resulted in the
>>> increase most probably contains the problematic code. Bear with me, if
>>> this approach looks very awkward.
>>> On Tue, Jan 5, 2010 at 8:22 PM, Jean-Pierre LAMBERT
>>> <jp.raven at worldonline.fr<mailto:jp.raven at worldonline.fr>> wrote:
>>> Hello everybody,
>>> I'm currently rewriting a LR parser to be used for ANTLR. As a result,
>>> ANTLR works literaly for hours before it outputs errors about my
>>> My work is not finished; I have removed all left-recursions but I still
>>> have to do left-factorisations. The problem being that since ANTLR works
>>> for hours before I get the errors, it isn't very practical for me to fix
>>> the grammar.
>>> Do you have any suggestions in this case? What could be done so that
>>> ANTLR would take only dozen of minutes? Is there something capital that
>>> I missed about ANTLR and LL grammars? How should be written ANTLR rules
>>> to avoid such a problem?
>>> Thanks in advance, any adice will be welcome.
>>> List: http://www.antlr.org/mailman/listinfo/antlr-interest
>> List: http://www.antlr.org/mailman/listinfo/antlr-interest
>> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address
More information about the antlr-interest