Should we restrict somehow the nesting?

[pablogsal]

When investigating what is the current maximum nesting with the current grammar, I found this:

where test_case is this function:

def test_case(n):
    parser.parse_string("("*n + "1+1" + ")"*n)

This means that the parser will appear to hang if the nesting is >>25 as the timings grow exponentially.

What do you think we should do about this?

[pablogsal]

Hummm, this seems that does not happen if we turn on memoization again

[pablogsal]

This is what I get before we-like-parsers/pegen_experiments@54d84ad.

This means that we need to activate memoization for some rules, likely.

[pablogsal]

Found it! Seems that there is a high recursion with target and memorizing both fixes this problem

Seems that I need to memoize target and star_atom.

Can any of you reproduce these results?

[gvanrossum]

Cool discovery and great swift action!

How do we know there aren't other rules that could exhibit the same problem?

[lysnikolaou]

How do we know there aren't other rules that could exhibit the same problem?

Since this was happening due to recursion and there are no other rules that use recursion, but do not get memoized, I think we should be fine.

The three rules that were changed here are special, in that they are "indirectly left-recursive" and thus the generator does not automatically memoize them.

[gvanrossum]

The three rules that were changed here are special, in that they are "indirectly left-recursive" and thus the generator does not automatically memoize them.

Hm, they don't look (indirectly or directly) *left-*recursive to me. (They are plain recursive but that's not a problem since it consumes at least one token before recursing.)

However, t_primary is left-recursive, and the three affected rules all have alternatives starting with t_primary. So maybe something's up with that?

[lysnikolaou]

Hm, they don't look (indirectly or directly) *left-*recursive to me. (They are plain recursive but that's not a problem since it consumes at least one token before recursing.)

However, t_primary is left-recursive, and the three affected rules all have alternatives starting with t_primary. So maybe something's up with that?

Yeah, left-recursive is wrong. What I actually meant is that all three affected rules call their own atom counterparts (star_atom, t_atom, etc.) and these then call the top-level *targets rules back again. So I was thinking this might have been the reason.

[gvanrossum]

Hm, it would be good to trace through the motions of the parser in detail (maybe using the visualizer I wrote for the blog last year). There's probably a ton of backtracking going on -- it must double the amount of backtracking for each level of parentheses to become exponential. I guess it consumes one '(', then goes

inside_paren_ann_assign_target -> ann_assign_subscript_attribute_target -> t_primary -> atom

and then parses everything as atom, but then finds there's no t_lookahead, backs out of everything until it's at inside_paren_ann_assign_target again, and tries the 3rd alternative there, which consumes one '(' and then starts the same thing all over.

Though I've run out of time proving this theory. :-(

[lysnikolaou]

So, I ran a small experiment and the parser indeed hangs in a loop between star_targets and star_atom.

Your chain of rule calls (inside_paren_ann_assign_target -> ann_assign_subscript_attribute_target -> t_primary -> atom) is indeed correct. That completes without a problem, even with a nesting of 25. Maybe that's because parsing a parenthesis in atom ultimately leads to a call to expression, which is memoized. (would that make sense?)

But then we get back to assignment, there's no : there and the second alternative fails. The third one is subsequently expanded, which leads to the parser getting hung at the loop I mentioned before.

[pablogsal]

So, I ran a small experiment and the parser indeed hangs in a loop between star_targets and star_atom.

This is before of after #39? What string did you use to test?

Even if we have a way to "recognize patterns" in the parser motions the challenging part is making the parser receive a string that exercises the backtracing enough. For instance, for the nested parenthesis, the pathological behaviour is lost among the "noise" until you reach ~20 levels.

[lysnikolaou]

This is before of after #39? What string did you use to test?

That's before #39 and I used "(" * 30 + "1+1" + ")" * 30 as the test string.

[lysnikolaou]

Can we close this?