21 ms·

If you think PEG parsers are a good idea and we should use them, comment below which strings this PEG grammar matches: Str = "a" Str "a" / "a" If you get

by orlp 5y ago

If you think PEG parsers are a good idea and we should use them, comment below which strings this PEG grammar matches: Str = "a" Str "a" / "a" If you get it right and you understand the logic, by all means use them. If you get it wrong or can't wrap your head around how it works despite knowing the answer, maybe reconsider. EDIT: since my point was too subtle and I have been misunderstood and downvoted as a result of it, allow me to give a hint. If you believe the above grammar matches aaaaa you fall in the latter category. It does not. Yes, aaa matches, aaaaaaa matches, but aaaaa does not. Yes, this is mind-boggling.

bruce343434 5y ago
Well, it seems simple. But from your tone I'm guessing it's not? a: (a) aaa: (a(a)a) aaaaa: (a(a(a)a)a) etc
- orlp 5y ago
  That is incorrect. Feel free to try it here: https://pegjs.org/online https://pegjs.org/online, you will see that aaaaa is not a match. And no, that is not a bug in pegjs.
  - drothlis 5y ago
    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.
- jules 5y ago
  I think it will parse "a", it will parse "a a a", and "aaa a aaa", and "aaaaaaa a aaaaaaa" and so on, but nothing else.
- edflsafoiewq 5y ago
  The problem for aaaaa is it gets to this parse (a(a(a(a)a) and can't complete the (aXa) parse for the second a, so it backtracks to try the (a) parse (a(a) The issue is since the parse of the third a as (a(a)a) succeeded, it will never try the (a) parse for the third a.
yortus 5y ago
Why not just write it more simply as Str = "a" "aa"* Most languages allow writing tortured and hard to understand logic where simpler alternatives can also be written. I'm not sure why that should make people consider not using them.
- bruce343434 5y ago
  The parse tree from that would be different, though it would match the same strings.
  - orlp 5y ago
    Incorrect, it does not match the same strings.
- orlp 5y ago
  Because that does not recognize the same set of strings. That matches aaaaa, but my example above does not. That is exactly the point I'm trying to make.
  - tonyg 5y ago
    Well, if you wanted all odd-length strings, you'd write what GP wrote. If you wanted whatever it was your grammar accepted, you'd write what you wrote :)
    - orlp 5y ago
      > If you wanted whatever it was your grammar accepted It is one-line, two-rule PEG grammar. What does it accept, and why? If we can't state this with confidence in such a tiny example, what makes us have any confidence in larger, more complex grammars? We should understand our tools. PEG pretends to be simple and understandable, but it's much less so than it might seem on the surface.
      - tonyg 5y ago
        Simple rules can give surprising, complex behaviour. That's a good point. Unfortunately, it's also true not only of PEGs and recursive-descent parsing, but also of essentially every parsing formalism out there. So it doesn't seem to disqualify PEGs in particular. (It's also true of programming languages generally: For which inputs does Collatz halt, and why?)
jules 5y ago
This is a good point in favour of context free grammar based parser generators. I think the trade-off is a bit more subtle though. CFG semantics is nice and declarative when we specify which strings belong to the language, but a parser is a function from strings to parse results, and then the nice semantics stops working due to ambiguities. The PEG semantics on the other hand naturally expresses such a function, and the function you get with PEG semantics is almost always the function you want. When we look at character level grammars, the CFG formalism doesn't work well either. They fundamentally rely on greedy lexical token matching. Extensions such as indentation sensitive parsing and user defined operators quite naturally fit into PEG style semantics, and are more difficult to integrate into CFGs. CFG based parser generators are way more complicated internally than PEG based parser generators, which are extremely simple.
- orlp 5y ago
  > The grammar may not be exactly what you want to illustrate your point (I think you want to swap the two sides of the /) No, I think you might be misunderstanding my point. For example, if you think the grammar I posted matches aaaaa, you'd be wrong.
  - jules 5y ago
    Yes you're right, I had already edited that while you were posting your reply. I thought you wanted to point out the usual simple "a" / "aa" problem.
tonyg 5y ago
This is a good example of a theoretical problem with PEGs. It also applies (of course) to recursive descent parsers. I don't think this problem is a practical issue, though; I can't speak for others, but this kind of problem hasn't come up in practice for me. PEGs do cause other headaches from time to time, but are still head-and-shoulders easier to get right than other styles of working with grammars.
samatman 5y ago
I work with PEGs every working day of my life. When I saw your example, it immediately gave me a chuckle, so thank you for that. Does that mean I'd spot the same gotcha deep in some grammar I was working on? No of course not, that would never happen. It's going to be some other mistake that makes me feel like an idiot after staring at the screen for several hours. Parsers are designed around data, not conundrums. For structured languages, PEGs are a sharp and simple tool for slicing them up. But they're not great at solving the Liar's Paradox.
myrmidon 5y ago
This is a really nice example, but I feel that it comes to an unfair conclusion. I'll concede that this appears counterintuitive, but I feel that cases like this most often just pop up because people have been "overexposed" to EBNF/CFGs before and write PEG grammars with wrong preconceptions (also often ending in "left recursion" confusion, but that at least gives early errors). But I still think that it is much preferable to debug/rewrite a questionable PEG grammar than e.g. a cobbled-together mess of conditionals and regular expressions... But now I'm really interested in what you're advocating for instead? CFG parser frameworks? Or learning how to write the parser by hand? Or learning about PEGs until your example is understood?
- orlp 5y ago
  For general parsing of data I am currently advocating LR(1), and GLR or Earley for those that need ambiguity. The exception to this is programming languages, for which I think the #1 priority is error messages, thus recursive descent is quite logical. If whatever you are parsing is unambiguous isn't strictly LR(1) a small lexer can almost always fix that, but often scannerless works fine. LR(1) gets a bad rap for impossible to understand conflicts while writing a grammar. I strongly believe this is due to most tools advertising LR(1) actually using LALR(1). LALR(1) is deservedly awful, and introduces mysterious conflicts. But modern parser generators can support minimal LR(1), which generates parse tables almost as small (or often exactly ad small) as LALR(1) without the mysterious conflicts. Finally LR(1) gets a bad rap for screaming at you at all during parser writing, but I see this as a feature, like the type checker in a programming language, preventing you from writing ambiguous or expensive to parse constructs.
smartaz42 5y ago
That grammar simply matches 2^(n-1) a's. Not mind-boggling from that point of view

by orlp 5y ago

bruce343434 5y ago

Well, it seems simple. But from your tone I'm guessing it's not? a: (a) aaa: (a(a)a) aaaaa: (a(a(a)a)a) etc

orlp 5y ago
That is incorrect. Feel free to try it here: https://pegjs.org/online https://pegjs.org/online, you will see that aaaaa is not a match. And no, that is not a bug in pegjs.
- drothlis 5y ago
  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.
jules 5y ago
I think it will parse "a", it will parse "a a a", and "aaa a aaa", and "aaaaaaa a aaaaaaa" and so on, but nothing else.
edflsafoiewq 5y ago
The problem for aaaaa is it gets to this parse (a(a(a(a)a) and can't complete the (aXa) parse for the second a, so it backtracks to try the (a) parse (a(a) The issue is since the parse of the third a as (a(a)a) succeeded, it will never try the (a) parse for the third a.

yortus 5y ago

Why not just write it more simply as Str = "a" "aa"* Most languages allow writing tortured and hard to understand logic where simpler alternatives can also be written. I'm not sure why that should make people consider not using them.

bruce343434 5y ago
The parse tree from that would be different, though it would match the same strings.
- orlp 5y ago
  Incorrect, it does not match the same strings.
orlp 5y ago
Because that does not recognize the same set of strings. That matches aaaaa, but my example above does not. That is exactly the point I'm trying to make.
- tonyg 5y ago
  Well, if you wanted all odd-length strings, you'd write what GP wrote. If you wanted whatever it was your grammar accepted, you'd write what you wrote :)
  - orlp 5y ago
    > If you wanted whatever it was your grammar accepted It is one-line, two-rule PEG grammar. What does it accept, and why? If we can't state this with confidence in such a tiny example, what makes us have any confidence in larger, more complex grammars? We should understand our tools. PEG pretends to be simple and understandable, but it's much less so than it might seem on the surface.
    - tonyg 5y ago
      Simple rules can give surprising, complex behaviour. That's a good point. Unfortunately, it's also true not only of PEGs and recursive-descent parsing, but also of essentially every parsing formalism out there. So it doesn't seem to disqualify PEGs in particular. (It's also true of programming languages generally: For which inputs does Collatz halt, and why?)

jules 5y ago

This is a good point in favour of context free grammar based parser generators. I think the trade-off is a bit more subtle though. CFG semantics is nice and declarative when we specify which strings belong to the language, but a parser is a function from strings to parse results, and then the nice semantics stops working due to ambiguities. The PEG semantics on the other hand naturally expresses such a function, and the function you get with PEG semantics is almost always the function you want. When we look at character level grammars, the CFG formalism doesn't work well either. They fundamentally rely on greedy lexical token matching. Extensions such as indentation sensitive parsing and user defined operators quite naturally fit into PEG style semantics, and are more difficult to integrate into CFGs. CFG based parser generators are way more complicated internally than PEG based parser generators, which are extremely simple.

orlp 5y ago
> The grammar may not be exactly what you want to illustrate your point (I think you want to swap the two sides of the /) No, I think you might be misunderstanding my point. For example, if you think the grammar I posted matches aaaaa, you'd be wrong.
- jules 5y ago
  Yes you're right, I had already edited that while you were posting your reply. I thought you wanted to point out the usual simple "a" / "aa" problem.

tonyg 5y ago

This is a good example of a theoretical problem with PEGs. It also applies (of course) to recursive descent parsers. I don't think this problem is a practical issue, though; I can't speak for others, but this kind of problem hasn't come up in practice for me. PEGs do cause other headaches from time to time, but are still head-and-shoulders easier to get right than other styles of working with grammars.

samatman 5y ago

I work with PEGs every working day of my life. When I saw your example, it immediately gave me a chuckle, so thank you for that. Does that mean I'd spot the same gotcha deep in some grammar I was working on? No of course not, that would never happen. It's going to be some other mistake that makes me feel like an idiot after staring at the screen for several hours. Parsers are designed around data, not conundrums. For structured languages, PEGs are a sharp and simple tool for slicing them up. But they're not great at solving the Liar's Paradox.

myrmidon 5y ago

This is a really nice example, but I feel that it comes to an unfair conclusion. I'll concede that this appears counterintuitive, but I feel that cases like this most often just pop up because people have been "overexposed" to EBNF/CFGs before and write PEG grammars with wrong preconceptions (also often ending in "left recursion" confusion, but that at least gives early errors). But I still think that it is much preferable to debug/rewrite a questionable PEG grammar than e.g. a cobbled-together mess of conditionals and regular expressions... But now I'm really interested in what you're advocating for instead? CFG parser frameworks? Or learning how to write the parser by hand? Or learning about PEGs until your example is understood?

orlp 5y ago
For general parsing of data I am currently advocating LR(1), and GLR or Earley for those that need ambiguity. The exception to this is programming languages, for which I think the #1 priority is error messages, thus recursive descent is quite logical. If whatever you are parsing is unambiguous isn't strictly LR(1) a small lexer can almost always fix that, but often scannerless works fine. LR(1) gets a bad rap for impossible to understand conflicts while writing a grammar. I strongly believe this is due to most tools advertising LR(1) actually using LALR(1). LALR(1) is deservedly awful, and introduces mysterious conflicts. But modern parser generators can support minimal LR(1), which generates parse tables almost as small (or often exactly ad small) as LALR(1) without the mysterious conflicts. Finally LR(1) gets a bad rap for screaming at you at all during parser writing, but I see this as a feature, like the type checker in a programming language, preventing you from writing ambiguous or expensive to parse constructs.

smartaz42 5y ago

That grammar simply matches 2^(n-1) a's. Not mind-boggling from that point of view