3 ms·

> 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

by 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
      > 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.
- adwn 2y ago
  No, orlp is right, as far as I understand. It's not a bug in the tool, but inherent to PEGs in general. Wikipedia has a section on this problem: https://en.wikipedia.org/wiki/Parsing_expression_grammar#The_midpoint_problem https://en.wikipedia.org/wiki/Parsing_expression_grammar#The...

by orlp 2y ago

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
    > 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.
adwn 2y ago
No, orlp is right, as far as I understand. It's not a bug in the tool, but inherent to PEGs in general. Wikipedia has a section on this problem: https://en.wikipedia.org/wiki/Parsing_expression_grammar#The_midpoint_problem https://en.wikipedia.org/wiki/Parsing_expression_grammar#The...