[antlr-interest] Parser generation takes hours

Jean-Pierre LAMBERT jp.raven at worldonline.fr
Wed Jan 6 06:17:38 PST 2010

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.
>> Thanks,
>> Gokul.
>> 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
>>      grammar.
>>      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.
>>      JP
>>      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 mailing list