5 ms·

> And if you agree with me that grammar above in intuitive sense is ambiguous, i. e. if you agree that A :: B ==> C allows two parse trees, then your brain thin

> And if you agree with me that grammar above in intuitive sense is ambiguous, i. e. if you agree that A :: B ==> C allows two parse trees, then your brain thinks in terms of CFG, too! CFGs are simply more natural. Count me as my brain being on team PEG then, so also a data point against CFGs being more natural. In fact, I think this example proves that author of TFA does not think in CFG, otherwise they wouldn't have accidentally written an ambiguous grammar! In my experience, it's an extraordinarily tiny fraction of people who actually want parse forests instead of parse trees in the languages they are constructing (TFA specifically excludes pre-existing languages). A PEG will be unambiguous. People want unambiguous. There's a chance it disambiguates against the intent of the author, but a CFG won't disambiguate at all, which will nearly always be against the intent of the author.

orlp 2y ago
Great! Someone who's brain is on team PEG. You are just the person I need. Can you explain in plain English what strings match the following PEG grammar? Str = "a" Str "a" / "a"
- HelloNurse 2y ago
  Any odd number 2n+1 of "a" repetitions, longest match. The inflating first rule is preferred about 2n times until it fails at input end, then the parser backtracks until the middle "a" is matched by the second rule and the others by n expansions of the first rule.
  - orlp 2y ago
    I'm sorry that is not correct at all. It does not match the string "aaaaa" for example.
    - HelloNurse 2y ago
      Why not? Preferring the first rule, after seeing a you expect Str a; after seeing another a you expect Str a a; after seeing the third a you expect Str a a a (and you can already realize it cannot match) so after some backtracking you match the third a with the second rule instead, expecting a a, which are the fourth and fifth a in the input. Do you have a different parsing algorithm in mind?
      - orlp 2y ago
        > Do you have a different parsing algorithm in mind? Yes, since I specified a PEG grammar I assumed a PEG parsing algorithm. You can try the grammar yourself in a PEG parser, e.g. https://shamansir.github.io/pegjs-fn/ https://shamansir.github.io/pegjs-fn/.
        HelloNurse 2y ago
        This tool seems to dislike recursion, it manages to parse aaaaa with Str = "a" Str2 "a" /"a" Str2 = "a" Str3 "a" /"a" Str3 = "a" or also Str = "a" Str2 "a" Str2 = "a" Str3 "a" Str3 = "a" I'd call it a bug. Note that Str = "aa"*"a" parses any odd number of "a" repetitions correctly.
        orlp 2y ago
        > I'd call it a bug. It's not a bug in the tool, it's inherent to PEG. All PEG parsers will behave the same on this grammar. My point is that PEG is highly unintuitive in how it works to most human brains, which is why I specifically asked for a plain explanation why this happens to someone who claims their brains align with how PEG works.
        HelloNurse 2y ago
        The ordered choice operator should try all choices, not stop earlier. There's probably some cache confusing, for instance, not matching the first Str rule at the third a with not matching a Str at all (neither rule) at the third a. The original example (here with parentheses, just in case) Str= ("a" Str "a") / "a" matches strings of 2N-1 "a" repetitions if N is a power of 2 (i.e. length 1,3,7,15,31,63...) which is an obvious symptom of improperly constraining rule expansion. So I insist, you are using an incorrect parsing tool. Interestingly, Str= ("a" Str "a") / "b" matches strings of N "a", one "b" in the middle and N "a" for any N, without degenerate behaviour.
        orlp 2y ago
    - redman25 2y ago
      Wow, this is surprising to me. Why doesn’t this work?
      - adwn 2y ago
        (I'll use position 1...5 to refer to the characters in "aaaaa", and first, second, third level to refer to the initial and then the recursive calls to the Str rule) 1. When the PEG parser enters the third level of Str, its first choice will successfully match on positions 3...5, and return to the second level of Str. 2. The first choice on the second level will fail, however, because it expects an "a" at position 6, which doesn't exist. Therefore, the first choice is discarded. 3. The second choice on the second level will succeed by matching "a" on position 2, successfully returning to the first level. 4. The first level finishes matching the first choice by consuming the "a" on position 3, successfully returning the parse tree Str = ("a" ("a") "a") 5. The remaining "aa" on positions 4...5 weren't consumed.
      - HelloNurse 2y ago
        See the nearby comment by adwn: aggressive "packrat" caching fixates on long matches starting at intermediate positions, without considering any shortest matches at the same position. Correct parsing would require discarding these long matches because they cause higher level rule expansions to fail, but smarter algorithms with an increase of runtime due to complete backtracking and/or an increase of memory usage to distinguish and remember different matches for the same rule at the same location would be required. EDIT: two nearby comments by adwn.
        kragen 2y ago
        this is not specific to the packrat parsing algorithm; any algorithm for parsing pegs has the same behavior as packrat. your understanding of peg semantics is incorrect
    - OskarS 2y ago
      I’ve never touched a PEG parser in my life and parsing isn’t super my thing in general, but: a recursive descent parser could parse this just fine (not left recursive), correct? But it would have to backtrack after trying rule 1 five times, and switch to rule 2 when it backtracks to the third layer of recursion? PEGs can’t do this kind of backtracking, is that the reason?
      - kragen 2y ago
        yes, exactly correct it's common to write recursive-descent parsers without this kind of backtracking support, though, because expressing that kind of backtracking in a natural way requires coroutines
- dxdm 2y ago
  Interesting. I've last had to deal with formal grammars in the previous century, and your post had me go scratch the surface of what PEGs are. If I understand correctly, your example is not a well-formed grammar, because of the left recursion. So what you're saying is that PEGs align badly with our expectations, tempting us to create non-well-formed grammars, and making it hard to recognize them as such, because our brains want to parse them differently. Right?
  - orlp 2y ago
    My grammar has no left recursion, there is a terminal string before the recursive nonterminal.
  - kragen 2y ago
    it doesn't have left recursion, but grammars in general can have left recursion; it doesn't make them ill-formed. warth even hacked in left recursion as an extension to pegs
- deleted 2y ago
  [deleted]
- nhatcher 2y ago
  Beautiful example! `2^n -1` times a? I love PEG parsers though
  - orlp 2y ago
    Yes, that is the correct answer, although you're missing the 'explanation' part for why this happens :)
thequux 2y ago
The question here is whether it is better to silently guess at the author's intent or to loudly say "your intent isn't clear; try again". I strongly believe that the second is the better approach for nearly all use cases. When I'm writing a grammar, I'm focused on the happy case and not on how the rules interact with each other. My intent was to write a grammar with only a single result, indeed, but if that's not what I've done, I'd want to know!
- nbadg 2y ago
  I disagree on both counts. I think the fundamental question here is "how easily can you construct (write or generate) a parser that matches your intent?". And to answer that question, I think you have to look at the entire process. What good does it do you to hear "your intent isn't clear; try again" if you don't understand where the ambiguity is? Presumably, if you knew where the ambiguity was, you wouldn't have written it -- since you know it can't create a grammar. So really what that message is telling you is, "you don't understand your own grammar" or "you don't understand how to write rules for your PG". And in my experience with several different PGs, the failure messages returned in those cases are... less than helpful. So you end up spending hours banging your head against your desk trying to figure out where the ambiguity is, even with a grammar you know back-to-front. Furthermore, even if you use a CFG, you still haven't gathered evidence that the resulting parse matches your intent. For that you need test cases. And as soon as you write a test case, you get immediate feedback that your intent isn't clear, regardless of PEG, CFG, or anything else: you see that your resulting parse doesn't match with the expected one. Given both of those things, it seems to me that issue at hand really does boil down to "which feels more natural, PEG, CFG, etc", which is always going to be a personal preference.
  - IshKebab 2y ago
    > Presumably, if you knew where the ambiguity was, you wouldn't have written it Well, no because people make mistakes. > And in my experience with several different PGs, the failure messages returned in those cases are... less than helpful. So you end up spending hours banging your head against your desk trying to figure out where the ambiguity is, even with a grammar you know back-to-front. Yeah that's my experience too but is "something is wrong" better than nothing? Maybe. I really like Nom & Chumksy though and haven't accidentally made ambiguous grammars (as far as I know) so it feels like a small risk to base your entire parser decision on.

orlp 2y ago

Great! Someone who's brain is on team PEG. You are just the person I need. Can you explain in plain English what strings match the following PEG grammar? Str = "a" Str "a" / "a"

HelloNurse 2y ago
Any odd number 2n+1 of "a" repetitions, longest match. The inflating first rule is preferred about 2n times until it fails at input end, then the parser backtracks until the middle "a" is matched by the second rule and the others by n expansions of the first rule.
- orlp 2y ago
  I'm sorry that is not correct at all. It does not match the string "aaaaa" for example.
  - HelloNurse 2y ago
    Why not? Preferring the first rule, after seeing a you expect Str a; after seeing another a you expect Str a a; after seeing the third a you expect Str a a a (and you can already realize it cannot match) so after some backtracking you match the third a with the second rule instead, expecting a a, which are the fourth and fifth a in the input. Do you have a different parsing algorithm in mind?
    - orlp 2y ago
      > Do you have a different parsing algorithm in mind? Yes, since I specified a PEG grammar I assumed a PEG parsing algorithm. You can try the grammar yourself in a PEG parser, e.g. https://shamansir.github.io/pegjs-fn/ https://shamansir.github.io/pegjs-fn/.
      - HelloNurse 2y ago
        This tool seems to dislike recursion, it manages to parse aaaaa with Str = "a" Str2 "a" /"a" Str2 = "a" Str3 "a" /"a" Str3 = "a" or also Str = "a" Str2 "a" Str2 = "a" Str3 "a" Str3 = "a" I'd call it a bug. Note that Str = "aa"*"a" parses any odd number of "a" repetitions correctly.
        orlp 2y ago
        > I'd call it a bug. It's not a bug in the tool, it's inherent to PEG. All PEG parsers will behave the same on this grammar. My point is that PEG is highly unintuitive in how it works to most human brains, which is why I specifically asked for a plain explanation why this happens to someone who claims their brains align with how PEG works.
        HelloNurse 2y ago
        The ordered choice operator should try all choices, not stop earlier. There's probably some cache confusing, for instance, not matching the first Str rule at the third a with not matching a Str at all (neither rule) at the third a. The original example (here with parentheses, just in case) Str= ("a" Str "a") / "a" matches strings of 2N-1 "a" repetitions if N is a power of 2 (i.e. length 1,3,7,15,31,63...) which is an obvious symptom of improperly constraining rule expansion. So I insist, you are using an incorrect parsing tool. Interestingly, Str= ("a" Str "a") / "b" matches strings of N "a", one "b" in the middle and N "a" for any N, without degenerate behaviour.
        orlp 2y ago
  - redman25 2y ago
    Wow, this is surprising to me. Why doesn’t this work?
    - adwn 2y ago
      (I'll use position 1...5 to refer to the characters in "aaaaa", and first, second, third level to refer to the initial and then the recursive calls to the Str rule) 1. When the PEG parser enters the third level of Str, its first choice will successfully match on positions 3...5, and return to the second level of Str. 2. The first choice on the second level will fail, however, because it expects an "a" at position 6, which doesn't exist. Therefore, the first choice is discarded. 3. The second choice on the second level will succeed by matching "a" on position 2, successfully returning to the first level. 4. The first level finishes matching the first choice by consuming the "a" on position 3, successfully returning the parse tree Str = ("a" ("a") "a") 5. The remaining "aa" on positions 4...5 weren't consumed.
    - HelloNurse 2y ago
      See the nearby comment by adwn: aggressive "packrat" caching fixates on long matches starting at intermediate positions, without considering any shortest matches at the same position. Correct parsing would require discarding these long matches because they cause higher level rule expansions to fail, but smarter algorithms with an increase of runtime due to complete backtracking and/or an increase of memory usage to distinguish and remember different matches for the same rule at the same location would be required. EDIT: two nearby comments by adwn.
      - kragen 2y ago
        this is not specific to the packrat parsing algorithm; any algorithm for parsing pegs has the same behavior as packrat. your understanding of peg semantics is incorrect
  - OskarS 2y ago
    I’ve never touched a PEG parser in my life and parsing isn’t super my thing in general, but: a recursive descent parser could parse this just fine (not left recursive), correct? But it would have to backtrack after trying rule 1 five times, and switch to rule 2 when it backtracks to the third layer of recursion? PEGs can’t do this kind of backtracking, is that the reason?
    - kragen 2y ago
      yes, exactly correct it's common to write recursive-descent parsers without this kind of backtracking support, though, because expressing that kind of backtracking in a natural way requires coroutines
dxdm 2y ago
Interesting. I've last had to deal with formal grammars in the previous century, and your post had me go scratch the surface of what PEGs are. If I understand correctly, your example is not a well-formed grammar, because of the left recursion. So what you're saying is that PEGs align badly with our expectations, tempting us to create non-well-formed grammars, and making it hard to recognize them as such, because our brains want to parse them differently. Right?
- orlp 2y ago
  My grammar has no left recursion, there is a terminal string before the recursive nonterminal.
- kragen 2y ago
  it doesn't have left recursion, but grammars in general can have left recursion; it doesn't make them ill-formed. warth even hacked in left recursion as an extension to pegs
deleted 2y ago
[deleted]
nhatcher 2y ago
Beautiful example! `2^n -1` times a? I love PEG parsers though
- orlp 2y ago
  Yes, that is the correct answer, although you're missing the 'explanation' part for why this happens :)

thequux 2y ago

The question here is whether it is better to silently guess at the author's intent or to loudly say "your intent isn't clear; try again". I strongly believe that the second is the better approach for nearly all use cases. When I'm writing a grammar, I'm focused on the happy case and not on how the rules interact with each other. My intent was to write a grammar with only a single result, indeed, but if that's not what I've done, I'd want to know!

nbadg 2y ago
I disagree on both counts. I think the fundamental question here is "how easily can you construct (write or generate) a parser that matches your intent?". And to answer that question, I think you have to look at the entire process. What good does it do you to hear "your intent isn't clear; try again" if you don't understand where the ambiguity is? Presumably, if you knew where the ambiguity was, you wouldn't have written it -- since you know it can't create a grammar. So really what that message is telling you is, "you don't understand your own grammar" or "you don't understand how to write rules for your PG". And in my experience with several different PGs, the failure messages returned in those cases are... less than helpful. So you end up spending hours banging your head against your desk trying to figure out where the ambiguity is, even with a grammar you know back-to-front. Furthermore, even if you use a CFG, you still haven't gathered evidence that the resulting parse matches your intent. For that you need test cases. And as soon as you write a test case, you get immediate feedback that your intent isn't clear, regardless of PEG, CFG, or anything else: you see that your resulting parse doesn't match with the expected one. Given both of those things, it seems to me that issue at hand really does boil down to "which feels more natural, PEG, CFG, etc", which is always going to be a personal preference.
- IshKebab 2y ago
  > Presumably, if you knew where the ambiguity was, you wouldn't have written it Well, no because people make mistakes. > And in my experience with several different PGs, the failure messages returned in those cases are... less than helpful. So you end up spending hours banging your head against your desk trying to figure out where the ambiguity is, even with a grammar you know back-to-front. Yeah that's my experience too but is "something is wrong" better than nothing? Maybe. I really like Nom & Chumksy though and haven't accidentally made ambiguous grammars (as far as I know) so it feels like a small risk to base your entire parser decision on.