3 ms·

I can't wrap my head around it. Why doesn't it work? It parses this: a a aaa a a But not this: a aaa a

jules 5y ago
The right mental model for PEGs is not whether or not it will parse the entire string. PEGs will attempt to parse some prefix of the string and then stop and leave the cursor there. Here is a list of strings and how far it will parse (hopefully correct): a| a|a aaa| a|aaa aaa|aa aaaaa|a aaaaaaa| a|aaaaaaa aaa|aaaaaa aaaaa|aaaaa aaaaaaa|aaaa aaaaaaaaa|aaa aaaaaaaaaaa|aa aaaaaaaaaaaaa|a aaaaaaaaaaaaaaa| a|aaaaaaaaaaaaaaa aaa|aaaaaaaaaaaaaa aaaaa|aaaaaaaaaaaaa aaaaaaa|aaaaaaaaaaaa aaaaaaaaa|aaaaaaaaaaa Consider your example aaaaa. 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. Therefore the first recursive call will only parse one a, and then return back to the initial call which will parse another a. So the final state is aaa|aa. At a high level, the reason for this behaviour is that PEGs are greedy. The inner recursive calls will always parse as much as they can, without regard for the outer calls that still want to parse more a's.
- drothlis 5y ago
  > 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.
  - jules 5y ago
    Yes I think that's right :) I think I have a way to visualize what's happening more clearly than the | notation I used above. We have grammar: S -> 'a' S 'a' / 'a' I'm going to put (aSa) around parses of the first alternative and <a> for the second alternative. So a successful parse would look like (a(a<a>a)a). Here's what the PEG parser will do for aaaaa. It will first recurse all the way down, trying the first alternative at every point: (a(a(a(a(a ^ The choice indicated by ^ will fail because it is expecting another 'a', so that choice will be backtracked, and it will replace the ( with < at that position: (a(a(a(a<a> ^ Now it will backtrack over that ^ choice and replace the ( with < at that position: (a(a(a<a>a) ^ Now comes the key point: the next thing it backtracks over is the second ( and NOT the third (, because the third ( actually succeeded. So it has skipped over one extra layer. Now it will parse: (a<a>a)aa This one succeeded, and consumed 3 characters. The rest of the input is then still to be parsed by productions further up the stack, but since this S is the main production of the grammar, we declare failure because the whole input was not consumed. In general, after backtracking, a bunch of ('s may initially seem to succeed, and then when it fails it will backtrack over all those, rather than over just one of them. For your larger example: (a(a(a(a(a(a(a ^ (a(a(a(a(a(a<a> ^ (a(a(a(a(a<a>a) ^ (a(a(a<a>a)a)a) So this one does parse the whole input. > Well, now I'm grateful I've never had to implement a parser for anything more complicated than a Lucene-style query syntax. Interestingly, these problems don't seem to come up in practice. But things like this are still a good argument for LR/GLR parsers: LR parsers will report the conflict at grammar compilation time, and GLR parsers will backtrack with all possible choices, so they will parse the way you'd expect. They are certainly the more principled choice. But in practice it may not matter that much in practice because people don't seem to use these kind of grammars, at least not for programming languages.

The right mental model for PEGs is not whether or not it will parse the entire string. PEGs will attempt to parse some prefix of the string and then stop and leave the cursor there. Here is a list of strings and how far it will parse (hopefully correct): a| a|a aaa| a|aaa aaa|aa aaaaa|a aaaaaaa| a|aaaaaaa aaa|aaaaaa aaaaa|aaaaa aaaaaaa|aaaa aaaaaaaaa|aaa aaaaaaaaaaa|aa aaaaaaaaaaaaa|a aaaaaaaaaaaaaaa| a|aaaaaaaaaaaaaaa aaa|aaaaaaaaaaaaaa aaaaa|aaaaaaaaaaaaa aaaaaaa|aaaaaaaaaaaa aaaaaaaaa|aaaaaaaaaaa Consider your example aaaaa. 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. Therefore the first recursive call will only parse one a, and then return back to the initial call which will parse another a. So the final state is aaa|aa. At a high level, the reason for this behaviour is that PEGs are greedy. The inner recursive calls will always parse as much as they can, without regard for the outer calls that still want to parse more a's.

drothlis 5y ago
> 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.
- jules 5y ago
  Yes I think that's right :) I think I have a way to visualize what's happening more clearly than the | notation I used above. We have grammar: S -> 'a' S 'a' / 'a' I'm going to put (aSa) around parses of the first alternative and <a> for the second alternative. So a successful parse would look like (a(a<a>a)a). Here's what the PEG parser will do for aaaaa. It will first recurse all the way down, trying the first alternative at every point: (a(a(a(a(a ^ The choice indicated by ^ will fail because it is expecting another 'a', so that choice will be backtracked, and it will replace the ( with < at that position: (a(a(a(a<a> ^ Now it will backtrack over that ^ choice and replace the ( with < at that position: (a(a(a<a>a) ^ Now comes the key point: the next thing it backtracks over is the second ( and NOT the third (, because the third ( actually succeeded. So it has skipped over one extra layer. Now it will parse: (a<a>a)aa This one succeeded, and consumed 3 characters. The rest of the input is then still to be parsed by productions further up the stack, but since this S is the main production of the grammar, we declare failure because the whole input was not consumed. In general, after backtracking, a bunch of ('s may initially seem to succeed, and then when it fails it will backtrack over all those, rather than over just one of them. For your larger example: (a(a(a(a(a(a(a ^ (a(a(a(a(a(a<a> ^ (a(a(a(a(a<a>a) ^ (a(a(a<a>a)a)a) So this one does parse the whole input. > Well, now I'm grateful I've never had to implement a parser for anything more complicated than a Lucene-style query syntax. Interestingly, these problems don't seem to come up in practice. But things like this are still a good argument for LR/GLR parsers: LR parsers will report the conflict at grammar compilation time, and GLR parsers will backtrack with all possible choices, so they will parse the way you'd expect. They are certainly the more principled choice. But in practice it may not matter that much in practice because people don't seem to use these kind of grammars, at least not for programming languages.