4 ms·

> 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 un

by 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
  > The ordered choice operator should try all choices, not stop earlier. PEGs made this choice to ensure linear-time parsing. Another example of what I would consider a failure is the PEG grammar: Keyword = "else" / "elseif" This will only match "else", it will never match "elseif" as the ordered choice will refuse to turn the successful match of "else" into a failure to try the "elseif". > So I insist, you are using an incorrect parsing tool. I agree that PEG is an incorrect formalization for parsing, as it has highly unintuitive and surprising behaviors like this one. However, I have to insist that this is part of Parsing Expression Grammars, and not an issue with some particular tool implementing PEGs. It's part of the formalization, and if you wish to avoid this you need a different formalization, like Context-Free Grammars. My personal favorite is LR(1) CFG grammars: you are guaranteed to get unambiguous and linear-time parsing grammars, or else the grammar will fail to compile. What your intuition probably is is that PEGs are Ordered Context-Free Grammars, e.g. such as in https://arxiv.org/pdf/2309.08717 https://arxiv.org/pdf/2309.08717, where first a full ambiguous parse forest is constructed and then using ordered rules a single canonical parse is selected. That is a lot more sensible, but also raises the time complexity of parsing from O(n) to O(n^4) for strings of length n. However, that's not what PEGs are.
  - aidenn0 2y ago
    > Keyword = "else" / "elseif" Are there any languages in which this rule makes sense? I can't imagine wanting to write ifFOOelseifBARelseBAZ And ending your token rules with WS|EOF removes any issues, so if FOO elseif BAR else BAZ works just fine.
  - aidenn0 2y ago
    > My personal favorite is LR(1) CFG grammars: you are guaranteed to get unambiguous and linear-time parsing grammars, or else the grammar will fail to compile. We can both agree that LR(1) is great; it parses a large and useful subset of CFLs; had the minimal LR(1) parser been discovered before YACC was written, I probably would never have moved to PEGs; hopefully we can all agree that LALR parsers are terrible? As a side note, I don't consider LR(1) parsers to be CFGs since they can only parse a subset of CFLs (actually only a subset of DCFLs if I remember my rusty CS correctly). [edit] Also TFA argues for Early parsers, which seems to me to be a poor choice for parsing programming languages.
    - orlp 2y ago
      > Hopefully we can all agree that LALR parsers are terrible? Yes, I think most of the bad reputation LR(1) gets is from stuff that is actually LALR(1) with its nonsense reduce-reduce conflicts. Another great thing is that LR(1) parser generators are being written now that instead of just spitting out a 'oops there was a conflict on these two things in this state', they can actually give you back two conflicting prefixes giving you much more insight in what causes the defect in your grammar and how to fix it.
- thaumasiotes 2y ago
  I worked this out by hand and I'd recommend you do the same. The paper defining the behavior of PEGs is here: https://bford.info/pub/lang/peg.pdf https://bford.info/pub/lang/peg.pdf . Section 3.3 is the relevant one, defining all the parsing rules. As for the simple explanation of what's going wrong: 1. We try to parse `aaaaa` as if it opened with the pattern `a STR a`. [And, with foresight, let's observe that this is true of the way we want the parse to go.] 2. We match the `a` at the beginning of the input and try to parse `aaaa` as if it opened with the pattern `STR a`. 3. This repeats; we make the same guess that we're dealing with a recursive STR, we match an `a`, and then we try to parse `aaa` as if it opened with `STR a`. I didn't mention this before, but the first step of doing this is to match the first element of the concatenation, `STR`, against the input. 4. Here's where things go wrong. We still guess that we're dealing with a recursive STR, because that rule has priority over the terminal rule `STR = a`. With foresight, let's observe that in the parse we want, this guess will fail, because we need the third STR to be a literal `a`. In that world, we'd then match the two following `a`s and our parse would succeed. 5. However, when we try to match our recursive rule `a STR a` against our input `aaa`, this succeeds, because that's a correct match. We have an outer recursive STR and an inner terminal STR, yielding `aaa`. 6. Since our first guess that the suffix `__aaa`` opens with a recursive STR succeeded, we will never experiment with what would happen if it opened with a terminal STR, the way we wish it would. 7. That was our only chance; the whole parse will now fail to match in predictable ways. ----- > The ordered choice operator should try all choices, not stop earlier. You can't defend PEGs by saying you wish they were defined differently. That's not a defense! Look at the paper: > Alternation (case 1): If (e₁, xy) => (n₁, x) then (e₁ / e₂, xy) => (n₁ + 1, x). Alternative e₁ is first tested, and if it succeeds, the expression e₁ / e₂ succeeds without testing e₂. It's hard to be clearer than that.
  - deleted 2y ago
    [deleted]
- kragen 2y ago
  that's not how pegs work, and if you add that kind of unrestricted backtracking to pegs, you get a grammar class that nobody knows how to parse in linear time pegs, by contrast, like ll(1) and lr grammars, have a linear-time parsing algorithm available (though its constant factor is significantly higher). that's one of the reasons people use them you should read an introduction to pegs; you might like them once you get past 'i insist peg parsers are incorrect parsing tools' ;)

by orlp 2y ago

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
> The ordered choice operator should try all choices, not stop earlier. PEGs made this choice to ensure linear-time parsing. Another example of what I would consider a failure is the PEG grammar: Keyword = "else" / "elseif" This will only match "else", it will never match "elseif" as the ordered choice will refuse to turn the successful match of "else" into a failure to try the "elseif". > So I insist, you are using an incorrect parsing tool. I agree that PEG is an incorrect formalization for parsing, as it has highly unintuitive and surprising behaviors like this one. However, I have to insist that this is part of Parsing Expression Grammars, and not an issue with some particular tool implementing PEGs. It's part of the formalization, and if you wish to avoid this you need a different formalization, like Context-Free Grammars. My personal favorite is LR(1) CFG grammars: you are guaranteed to get unambiguous and linear-time parsing grammars, or else the grammar will fail to compile. What your intuition probably is is that PEGs are Ordered Context-Free Grammars, e.g. such as in https://arxiv.org/pdf/2309.08717 https://arxiv.org/pdf/2309.08717, where first a full ambiguous parse forest is constructed and then using ordered rules a single canonical parse is selected. That is a lot more sensible, but also raises the time complexity of parsing from O(n) to O(n^4) for strings of length n. However, that's not what PEGs are.
- aidenn0 2y ago
  > Keyword = "else" / "elseif" Are there any languages in which this rule makes sense? I can't imagine wanting to write ifFOOelseifBARelseBAZ And ending your token rules with WS|EOF removes any issues, so if FOO elseif BAR else BAZ works just fine.
- aidenn0 2y ago
  > My personal favorite is LR(1) CFG grammars: you are guaranteed to get unambiguous and linear-time parsing grammars, or else the grammar will fail to compile. We can both agree that LR(1) is great; it parses a large and useful subset of CFLs; had the minimal LR(1) parser been discovered before YACC was written, I probably would never have moved to PEGs; hopefully we can all agree that LALR parsers are terrible? As a side note, I don't consider LR(1) parsers to be CFGs since they can only parse a subset of CFLs (actually only a subset of DCFLs if I remember my rusty CS correctly). [edit] Also TFA argues for Early parsers, which seems to me to be a poor choice for parsing programming languages.
  - orlp 2y ago
    > Hopefully we can all agree that LALR parsers are terrible? Yes, I think most of the bad reputation LR(1) gets is from stuff that is actually LALR(1) with its nonsense reduce-reduce conflicts. Another great thing is that LR(1) parser generators are being written now that instead of just spitting out a 'oops there was a conflict on these two things in this state', they can actually give you back two conflicting prefixes giving you much more insight in what causes the defect in your grammar and how to fix it.
thaumasiotes 2y ago
I worked this out by hand and I'd recommend you do the same. The paper defining the behavior of PEGs is here: https://bford.info/pub/lang/peg.pdf https://bford.info/pub/lang/peg.pdf . Section 3.3 is the relevant one, defining all the parsing rules. As for the simple explanation of what's going wrong: 1. We try to parse `aaaaa` as if it opened with the pattern `a STR a`. [And, with foresight, let's observe that this is true of the way we want the parse to go.] 2. We match the `a` at the beginning of the input and try to parse `aaaa` as if it opened with the pattern `STR a`. 3. This repeats; we make the same guess that we're dealing with a recursive STR, we match an `a`, and then we try to parse `aaa` as if it opened with `STR a`. I didn't mention this before, but the first step of doing this is to match the first element of the concatenation, `STR`, against the input. 4. Here's where things go wrong. We still guess that we're dealing with a recursive STR, because that rule has priority over the terminal rule `STR = a`. With foresight, let's observe that in the parse we want, this guess will fail, because we need the third STR to be a literal `a`. In that world, we'd then match the two following `a`s and our parse would succeed. 5. However, when we try to match our recursive rule `a STR a` against our input `aaa`, this succeeds, because that's a correct match. We have an outer recursive STR and an inner terminal STR, yielding `aaa`. 6. Since our first guess that the suffix `__aaa`` opens with a recursive STR succeeded, we will never experiment with what would happen if it opened with a terminal STR, the way we wish it would. 7. That was our only chance; the whole parse will now fail to match in predictable ways. ----- > The ordered choice operator should try all choices, not stop earlier. You can't defend PEGs by saying you wish they were defined differently. That's not a defense! Look at the paper: > Alternation (case 1): If (e₁, xy) => (n₁, x) then (e₁ / e₂, xy) => (n₁ + 1, x). Alternative e₁ is first tested, and if it succeeds, the expression e₁ / e₂ succeeds without testing e₂. It's hard to be clearer than that.
- deleted 2y ago
  [deleted]
kragen 2y ago
that's not how pegs work, and if you add that kind of unrestricted backtracking to pegs, you get a grammar class that nobody knows how to parse in linear time pegs, by contrast, like ll(1) and lr grammars, have a linear-time parsing algorithm available (though its constant factor is significantly higher). that's one of the reasons people use them you should read an introduction to pegs; you might like them once you get past 'i insist peg parsers are incorrect parsing tools' ;)