> The PEG will parse the first a, and then the recursive call will parse from a|aaaa. Now the next recursive call will eventually fail.

Thanks for taking the time & effort to explain! I know you're right because I have reproduced this behaviour in 2 parser generators now (pegjs & grako).

Why does the next recursive call fail? (Don't answer, I think I've worked it out.)

Isn't it supposed to backtrack:

    1. a|a a a a
    2. a a|a a a
    3. a a a a a|  <- "succeeds" but doesn't leave any more input for the outer parses
    3. a a a|a a   <- doesn't it backtrack and try the other choice?
    2. a a a a|a
    1. a a a a a|

I guess it's because the backtracking doesn't happen at recursion level 3 (because it already thinks it succeeded) but at level 2:

    1. a|a a a a
    2. a a|a a a
    3. a a a a a|
    2. a a|a a a   <- tries the other choice
    1. a a a|a a

Let's see if my explanation holds for aaaaaaa:

    1. a|a a a a a a
    2. a a|a a a a a
    3. a a a|a a a a
    4. a a a a|a a a
    5. a a a a a a a|  <- "succeeds" but doesn't leave any more input for the outer parses
    4. a a a a|a a a   <- tries the other choice
    3. a a a a a|a a
    2. a a a a a a|a
    1. a a a a a a a|

Geez.

Well, now I'm grateful I've never had to implement a parser for anything more complicated than a Lucene-style query syntax.