[antlr-interest] Parser generation takes hours

[Jean-Pierre LAMBERT]

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 rules.

In some way, it is quite normal since LL parsers requires it.


A big thank you for the help. It was greatly appreciated.


JP



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.
>
>
> JP
>
>
>
> 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
>>
>>
>
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address
>
>