[antlr-interest] Parser generation takes hours

[Gokulakannan Somasundaram]

Hi JP,
        One of most tough problem in the migration for me was to resolve the
left factoring. I couldn't find any easy way of doing it. If your project is
a big one, then definitely the solution for left factoring discussed in the
antlr website may not work for you.
        If your parser is not performance critical, then you can use
syntactic predicates heavily and solve the issue. But then the
compilation(atleast if you keep a higher value for k) and runtime will be
more for that.

My approach was approximately like this.

if there are a set of rules like
a: b|c;
b : d f | X;
c : d e | Y;

I rewrote the rules like this
a: d ( b_minus_d | c_minus_d ) | b_without_d | c_without_d;

b: d f | X;
b_minus_d : f;
b_without_d : X;

c : d e | Y;
c_minus_d : e;
c_without_d : Y;

This helped me to  keep the relevant rules together and with minimal code
repetition in the actions.

If you find out any other elegant way to resolve left factoring(without
using syntactic predicates), please do let me know.

Thanks,
Gokul.

On Wed, Jan 6, 2010 at 7:47 PM, Jean-Pierre LAMBERT <jp.raven at worldonline.fr
> wrote:

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