> 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/.
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/.
Str = "a" Str2 "a" /"a"
Str2 = "a" Str3 "a" /"a"
Str3 = "a"
Str = "a" Str2 "a"
Str2 = "a" Str3 "a"
Str3 = "a"
Note that
Str = "aa"*"a"
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.
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"
Interestingly,
Str= ("a" Str "a") / "b"
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"
> 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, 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.
Are there any languages in which this rule makes sense? I can't imagine wanting to write
ifFOOelseifBARelseBAZ
if FOO elseif BAR else BAZ
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.
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.
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.
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' ;)