5 ms·
> 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 co
by 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.