Left Recursive Grammar Stalls with Standard Configuration

[GoogleCodeExporter]

Left Recursive Grammar Stalls with Standard Configuration

[GoogleCodeExporter]

s/Lookup/Lookahead/

Original comment by [email protected] on 15 Mar 2009 at 5:50

[GoogleCodeExporter]

Hmmm.  The above stalls because Lookahead() doesn't consume anything.  Whether 
or not
that is considered a bug or not, it's not the error I am seeing in my code.

Original comment by [email protected] on 15 Mar 2009 at 6:49

[GoogleCodeExporter]

    def test_problem_from_regexp(self):

        item     = Delayed()
        item    += item[:] 
        expr     = item & Drop(Eos())

        parser = expr.string_parser()
        parser('abc')

This is what I am hitting in the regexp code.

Original comment by [email protected] on 15 Mar 2009 at 6:58

[GoogleCodeExporter]

Ah, OK, now it is clearer.  The second case is similar to the first, in that 
there is
a repeated match that can be empty.  This is not a left-recursion issue, it's 
just an
error (although one we can perhaps try to detect somehow?).

What was confusing me was that I thought the LMemo (left recursion memoizer) 
would
deal with this issue (even if it is not exactly what it is intended for).  But 
what
happens is that after the left recursion "maxes out" an empty match is 
returned.  In
a normal left-recursion case the stack can then unwind and do some matching.  
But in
this case no matching is done on the rewind, so the matcher ends up "where it
started" with an empty match.  And then it repeats.

Note that the "stack" does not expand.  When left recursion "explodes" (without 
the
LMemo guard) memory is consumed in pending matchers (I hesitate to say that 
stack is
consumed because it's not the program stack, its just the stored state 
necessary for
the trampoline).

So this is a won't-fix for now.

Original comment by [email protected] on 15 Mar 2009 at 8:45

[GoogleCodeExporter]

If it makes things any clearer, this does get caught by LMemo:

        item     = Delayed()
        item    += item[1:] 
        expr     = item & Drop(Eos())

Original comment by [email protected] on 15 Mar 2009 at 8:46

[GoogleCodeExporter]

Original comment by [email protected] on 15 Mar 2009 at 8:49

• Changed state: WontFix

[GoogleCodeExporter]

I'm going back through old comments and noticed this one was starred, which 
worried
me, so I thought I would add some clarification:

In general, if LEPL "freezes up" (uses lots of CPU time but doesn't do 
anything) then
it is either a bug in my code (LEPL) or a bug in your code (the grammar)

In this case, I thought it was a bug in LEPL.  It turned out to be a bug in the
grammar.  If a grammar has an unlimited repeat of something that doesn't 
consume any
data from the input then it will continue to repeat that matcher "for ever".  
In that
case LEPL is doing exactly what it was asked to do - repeat "nothing" for as 
many
times as possible.

So if LEPL freezes, check that the grammar doesn't do that (checking can be 
quite
difficult, as even quite simple looking grammars can be doing something complex
"under the hood").

Having said all that, if you still have a problem, please consider raising a bug
report or just posting a question on the mailing list.  LEPL is growing rapidly 
and
most certainly contains many bugs.  So you may well have found a completely 
different
problem.

Also, I will consider whether making LMemo the default would "fix" this issue.  
If
so, I may do that so that "out of the box" LEPL doesn't fail on what could be a 
quite
common mistake.

Original comment by [email protected] on 24 Apr 2009 at 1:28

[GoogleCodeExporter]

Oh!  *I* starred it.  Duh.

Original comment by [email protected] on 24 Apr 2009 at 1:31