Use context-free grammars instead of parser combinators and PEG
safinaskar.writeas.com
safinaskar.writeas.com
"I feel that CFGs more naturally represent how we think" but
"All this doesn't apply to situations where you trying to parse some language, whose specification explicitly says that the language is based on PEG formalism"
A terrible context free grammar (with left and right recursion, not a small feat) is presented.
"I blindly converted grammar above to Haskell code"
"I accidentally discovered my grammar was ambiguous!"
"All this gave me psychological trauma (figuratively speaking). I will never use Parsec (and PEG parsers) anymore."
Denial that an ambiguous grammar is a defect, denial that the ambiguity has to be resolved, refusal to use parser combinators to resolve the ambiguity in the correct way.
It's also strange to see someone react to a modest, non-shameful failure (guess what, parsing is difficult is language design is even more difficult) that should be a nice learning opportunity (elegant context free grammars are usually insufficient in practical usage) with anger and radicalization far beyond an acceptable level of blaming the tools.
The other post in the blog, however, follows a similar general pattern: never use a popular technique (de Bruijn indices rather than parser combinators), because they advocate another technique (expressing lambda calculus terms with randomly generated globally unique identifiers for all bound variables rather than pure context free grammars) because that's what they like.
However, I also think that there is a legitimate point here. Which is that parser combinators, even in languages like Haskell, are shockingly tricky to use correctly. In particular, they violate the usual Haskell principle that "if it compiles, then it will probably run correctly". Having written multiple parsers in multiple languages with multiple parsing frameworks (including direct recursive descent), using Parsec in Haskell was the only time I had to write a test suite for the parser specifically. And that's because there were so many footguns that I was repeatedly making mistakes despite the fact that this was a port of a parser I'd already written (and therefore, ought to know backward and forward). (For the record, this was not my first Haskell project either, which is why I was so shocked it went so poorly.)
I'm sure it's possible to make mistakes in CFGs too, but practically speaking I can't remember running into that situation myself. Whereas with Parsec I ran into it repeatedly.
I don't think that's true. The following CFG is unambiguous:
S ::= A S | A
A ::= 'a' | 'a' 'b'
It's a formally very different problem from spontaneously and arbitrarily disambiguating an ambiguous grammar, but in practice it causes the same kind of suffering and it's likely to be a more common issue.
Did you adapt an existing CFG, or another parser combinator implementation, or did you start from scratch? The first case is more treacherous.
Overall, combinators (almost by definition) have the property that you can plug anything into anything else. Haskell encourages a "zero-point" style where you don't even name the parameters (this is sort of the point of parser combinator libraries) and provides a bunch of fancy operators to glue them together in various ways.
I think the mistakes I was making were mainly in just gluing the combinators together in the wrong way. It's not that the grammar was ambiguous, I just messed it up.
You could say some of the same things about CFGs, and I guess that's true at some level. But in my opinion the syntax is more obvious and you don't usually spend time squinting at the syntax to remember how $ works or what order things execute in. And like I said, with parser combinators, there is no feedback (because everything compiles, more or less), so the only way to tell if it's working is to run it, which is a very un-Haskell-like experience.
Ah, an S-expr enjoyer I see
i'm curious if you change your mind once you understand peg's limited backtracking semantics
Author could have replaced the “we” with “I” and made it into a mildly interesting diary entry.
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.
Str = "a" Str "a" / "a"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/.
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' ;)
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.
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.
PEGs can’t do this kind of backtracking, is that the reason?
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
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?
I love PEG parsers though
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!
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.
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.
This is a common problem.
In this case the amount of recursion makes it hard to even guess at what it is trying to express.
If my grammar looked like that, I'd throw it away and start over, because the problem to me appears to be not quite having a clear idea of what the grammar is expressing.
EDIT: Trying to clean up his grammar into something readable
t0 = t1 | a
t1 = t3 ("==>" t1)?
t3 = (id | d)+ c? | b
a = "!!" id c "." t0
b = "%" id c "." t3
c = "::" t0
d = "(" t0 ")"
One thing to note, is that my first instinct when writing parsers is to look for opportunities to factor out rules that start with a terminal, because it's usually a good way of avoiding or reducing the need for lookahead. Hence the extra rules, that to me at least makes it a lot clearer. The part of the grammar to look for places where your formalism causes ambiguities is now much smaller.
This grammar still gives me hives, but without knowing his constraints and intent, it's tricky to see if it can be cleaned up further.
That's fine if you are working in a purely academic domain, or you're just having fun writing something on your free time.
In production settings, you need to keep extending whatever language you have. The alternative is having to start to maintain two separate parsers and a migration tool, and be stuck with that for years.
The point is that being able to throw away code is a luxury that virtually no one is able to afford.
This is not about the language but about his expression of it in this specific instance of the grammar.
As the article makes clear, he didn't understand the language, and my claim is that is to a large extent down to how it is expressed.
Not throwing away this specific grammar instance is something you can't afford.
Then the hard work of leaving behind simplistic, ambiguous, imprecise, inefficient grammar specifications has already been done (mostly) and you are ready to add small new features without serious rewrites.
In a nutshell such a parser is PEG in a sense that the choice is ordered, but with little to no test expressions. In other words, I try to stick to lookahead-1 most of the time. Left recursion quite often could be resolved by lifting the branches to their siblings rather than re-parsing the same things many times using the cache (packrat). In fact both approaches, the packrat and the nodes lifting, are the same in a nutshell, but nodes lifting is usually easier to maintain (again, it all depends).
Writing the parser manually, or in other words a set of relatively simple mutually recursive functions, in my opinion, is not the hardest problem in practical engineering. At least it's not so hard when you have a mental model of the language's syntax upfront.
If the language fits specific class of formal grammars very well, perhaps it would be not so hard to implement it using the parsers generator tool. But it is likely there will be edge cases that are hard to express properly using the formal grammar, and fighting with the tool specifics will waste a lot of your time rather than benefit you.
Working in what languages did you make this observation?
In something like C I would probably agree with you. But in eg Haskell or OCaml, I would probably prefer parser combinators.
I think that packrat parsers are even easier to implement by hand, and even troubleshoot.
It's all procedural code, and you just call the next routine to figure out if you have a token match or not.
More importantly, PEGs promise to be easier to maintain in smaller custom parsers. To support an enum, all you need to do is add a function call, and that's it. One line of code. Can't beat that.
For example I once tried to write a full parser for Lua in LALRPOP and gave up after a week because it was too slow to compile and too hard to avoid conflicts; I ended up writing a recursive descent parser in a single day. I already knew that LALRPOP doesn't resolve shift-reduce conflicts and also how to transform the grammar to avoid them, but that wasn't enough for me.
I think there is a niche for CFG-like formalisms with bounded PEG-like constructs so that it can be quickly adjusted without giving up all the benefits of CFG. I have been already in situations where I really want to have such formalisms for multiple times, including the aforementioned one.
Python switched to PEG in IIRC 3.9, the language standard, parser and the grammer were previously CFG, specifically LL(1).
That switch implies that maybe the author is only correct until your language is widely (if not wildly) successful?
There were some positive side effects to the move and it enabled better exceptions, with more detailed information.
[1] https://podcasts.apple.com/us/podcast/episode-8-the-new-pars...
[2]https://podcasts.apple.com/us/podcast/episode-7-the-old-pars...
You get a LL(1), LR(1), LALR(1), etc. parser and the more of CFG they can parse the more drawbacks there often are.
And making a programming language fit into more limited parsers like LL(1) is a total pain.
So you need something which is more powerful, but still not to complicated to have a fast efficient implementation for python and python tooling.
At which point it can be simpler to just go with PEG especially if you have the amount of people and brain power to make sure you don't slip up with resolving ambiguity in a arbitrary "accidental" way.
I would avoid PEGs they are a huge food gun.
But a lot of things you need to parse are file formats designed to be reasonable straight forward parseable and in many such situations using a parsing combinatorics is all of: the fastest write, the easiest to write, the easiest to debug, the easiest to maintain, the smallest code size (potentially by a lot), the fastest build times and often even the fastest to execute .
So a very clear straightforward win for parsing combinatorics.
Through the moment you parse (programming) languages and similar instead of data formats things often change leading a massive increase of complexity and ways you can subtle get it wrong (e.g. not explicitly handling operator precedence). And here proper grammar parsing frameworks can shine, sometimes.
But even there they don't shine always as they are huge complicates pieces of code which often require running some complicated code gen to have any chance to get acceptable perf/code size which is often hardly debugable in case you might have run into a bug. Furthermore parsing arbitrary CFG is complicated and potentially slow so most frameworks prefer you to use a specific subset like LR(1) grammars. And understanding what exactly that means for your grammar and if that works for you use case is neither obvious nor intuitive and can make you wast a lot of time. Sure you probably should have learned all about it (if you have a CS Bachelor or similar degree) but I mean when was the last time you used that knowledge?
So in the end even for such cases using a PEG or parser generator, while being _very_ _very_ careful about grammar design is sometimes still the better choice (even through it shouldn't, it's a better choice born due to limitations of existing tooling).
As a side note a good hint to weather using a CFG or parser combinator is the better choice is often to ask yourself if a tokenization pass would make parsing much more simple. For thinks where using a CFG is a terrible idea (e.g. parsing msgpack) the answer is often that it doesn't make sense at all. For things where tokenization makes sense, but is literally most of the parsing (e.g. JSON) it's often just easier/better to not use a CFG. But the moment it seems to make a lot of sense (e.g. a programming language) it also tends to be the best choice to use a CFG (or similar) grammar parser.
(1) Retry till the output passes the grammar
(2) Only generate tokens passing the grammar
Assuming (2) actually runs (not guaranteed for all grammars and distributions theoretically, basically never a problem in practice), one of many common failure modes is forcing the generation of grammar-valid tokens after an error has been made.
E.g., one sort of "truncation" error happens when the LLM is producing an object with metadata around a transcription (e.g., an author, timestamp, and blob of text). A common incorrect result looks like
{"author": "John Doe", "timestamp": "20:23:58", "transcript": "My name is John Doe, and ...
Those ellipses weren't just cutting off my description of the invalid data. The model will produce ellipses after the string carries on for too long. If you greedily produce tokens adhering to a grammar, your only options at that point are continuing the string and ending it, and both options are very wrong.
Contrast that with option (1). Empirically, if the model is willing to actually produce those tokens rather than cut off its answer, it's much more likely to be correct (i.e., the presence of that ellipses bug will tend to cut off the entire response, not just truncating the string and still generating a valid object). If you just retry till the model succeeds then you have a substantially higher accuracy in that task.
That particular example may or may not apply to your favorite problem and favorite model, but it highlights the problem that constraining to a grammar forces a large skew in your result distribution. A large part of the power of an LLM is its autoregressiveness, and other sampling algorithms only tend to perform well when there's some outside knowledge relevant to the real-world problem being solved (e.g., if the LLM has >50% accuracy on a task with a small, finite number of outputs, then you might want to drop the temperature to 0 and just sample repeatedly, selecting the most likely option), but messing with the result distribution without a rationale for why you're still likely to get good results is risky.
{"transaction_number": <number>}
For more constrained examples like that, you're probably a lot safer than with completely unconstrained strings.
Even for very simple constraints like that, it's not terribly hard to imagine exactly the same ellipses problem (especially if your chosen JSON grammar isn't very careful with unbounded vs 53-bit integers). You really want a non-negative integer, you're using JSON and don't want to roll your own grammer so you use an off-the-shelf JSON LLM CFG toolkit of some flavor, and you allow _numbers_ in that field. I haven't personally seen ellipses bugs after only a few dozen characters in current-gen LLMs, but to have something concrete talk about let's say your model "tries" to write a transaction_number of 3141592635.... They want to truncate the actual result with an ellipsis. On the first period, the only allowable results include more digits (the grammar prevents the actual ellipsis from happening). You successfully adhere to the grammar and have garbage in that field, where a simple retry loop would have likely completed correctly.
Assuming the grammar actually correctly restricts to just a non-empty contiguous sequence of digits in that spot, that's _harder_ to force a bug into, but it's not impossible. For starters, the whole thing is probabilistic. Suppose the model uses "0" as the first digit. The only remaining valid (integer) JSON is finishing the field. Multiple leading zeros's aren't allowed. If for _any_ reason the model is more likely to produce invalid JSON after incorrectly using a "0" for the first digit, the grammar-constrained implementation will have more errors than a basic retry loop.
You can probably do something clever with changing the sampling temperature based on which part of the grammar you're in to side-step some of those issues. You might also find that for a particular problem my theoretical complaints don't seem to apply in practice. Maybe, for business reasons, past a certain accuracy rate you value being able to write simpler code (i.e., assume valid JSON) even if you dip down from 99% to 98% accuracy on a task. Nothing I've outlined says "don't guide an LLM with grammars." Do be careful with it though and consciously consider the task at hand and your proposed solution. It's not a free lunch.
> I blindly converted grammar above to Haskell code.
> But then I accidentally discovered my grammar was ambiguous!
You wrote an ambiguous CFG, implemented its parser, and then discovered that it was ambiguous.
Would the CFG have become non-ambiguous if you took your advice and avoided parser combinators?
This makes me really want to avoid the CFG step altogether.
You might consider this to be analogous to the difference between static and dynamic typing. A statically typed language will reject an erroneously typed program before attempting to run it, but the dynamically typed language may accept it and attempt to run it, only to fail at runtime if there's a type mismatch.
Parser combinators are more like the dynamic language. You find out at runtime (when parsing), whether the text you have parsed has ambiguities because more than one parse result is returned if that is the case. Normal operation is that the combinator returns a single result, in which case there are no ambiguities in the input, but the parser combinator doesn't provide any guarantees about absence of ambiguity in the language itself - it only proves that there's no ambiguity for the given input. And there's no practical way of testing for all inputs that the defined language is unambiguous, because there are infinite possible inputs.
LL/LR parser generators are like a type system for grammar. They'll take your input grammar, and check that all rules adhere to the constraints of LL/LR, and iff that's the case, then they'll produce a valid parser for a provably unambiguous language.
PEG are also provably unambiguous, but for a given input, the "correct parse" is not necessarily the "desired parse". Essentially, when you're using a PEG, the language is defined by its grammar. When you use an LL/LR parser-generator, you're attempting to use some constraints to formalize a grammar for your language, which you define yourself, and the tool will correct you if you've made a mistake and introduced some ambiguity by accident, whereas a PEG will silently mask that issue by just picking the first option. Rather than prompting you to fix the language to match the intuition you had about its syntax, the "accidental ambiguity" becomes a non-ambiguity and part of the language definition. Also, when extending an existing language with new syntax, PEGs can have unexpected results which may break existing code written in the language, or interpret it differently to what was intended by whoever wrote it.
However, when you're parsing a language that somebody else has already defined, it doesn't really matter which method you use to write the parser, as an incorrect parse is a bug in your code, and not the language itself.
For greenfield languages, I'm largely with the article's author that LL/LR are the correct constructions to use - they assist you in designing a language that is free of ambiguity from the start because incorrect assumptions about your syntax are flagged by the parser-generator. A greenfield language designed with a PEG becomes a language that is defined by the PEG, and any potential mistakes in your intuition become a set-in-stone part of the language.
As for the choice between LL and LR, it's pretty much a non-brainer to use LR (or LALR) to give yourself greater flexibility. LL had their place on resource constrained systems of the past, but on today's systems, LR parsing uses a trivial amount of resources and is only going to be a fraction the compiler or interpreter's memory and CPU time. If you can fit your language into an LL grammar, you certainly should, as it will be blazingly fast to parse, but I don't think you should constrain yourself just because of this.
Recommendation: Use Menhir. It supports writing production rules which are parametrized by other production rules. This can "feel" a bit like parser combinators to write, but it's all ultimately lowered to LR. The parsers it produces are fast, and you can use the tool for incremental parsing.
You're right it's often easy to use them in ways that introduce ambiguity, and some explicitly support ambiguity, though.
PEGs are a better fit for parser combinators because the host language typically has a pattern matching construct which checks patterns from top to bottom, and this matches the semantics of PEGs ordered alternations.
If I write a parser combinator based parser for a grammar that is not ambiguous, I will write it to fail if it comes across an error, just as I would if I were to e.g. hand-write a recursive descent parser. In fact, most of the places where I use parser-combinators, I use them to build parsers structured exactly the way I would structure a recursive descent parser, just with reusable combinators instead of manually written functions, and I will - in the same way as I would wherever possible in a recursive descent parser - aim to bail at the first symbol that causes an error, or optionally jump an error recovery function.
I've never in my life written a parser combinator based parser that required a multi-stage compilation process. Verifying that the parser recognises the language it is meant to, is part of the test suite whichever parsing method you use.
> I suppose alternatively you could verify the parser on application startup and terminate with an error if it's not valid LL/LR.
Why would I run my test-suite on application startup? The grammar is not magically changing between runs.
How do you even know it is not ambiguous to begin with?
I already said it doesn't matter what tool you use to parse a language designed by someone else. The language you design yourself is not automatically free of ambiguity, and intuition only gets you so far. If you stick to only using productions which are valid LL/LR, then why not have that enforced by the tool, so it can warn you when you go astray?
By knowing what makes a grammar ambiguous, and not doing it, and having a test suite that I need anyway.
> If you stick to only using productions which are valid LL/LR, then why not have that enforced by the tool, so it can warn you when you go astray?
A large part of the reason why there are so many parser generators is that we to date do not have a parser generator design that generates parsers that most people like to use for major projects. I've written about 5 generations of parser generators myself over the last 30 years, and I hate every one of them, yet every one was written in response to not finding a parser generator I consider tolerable to work with.
Most of the time it's easier to work with a hand-rolled parser. Parser combinators makes that easier, and more reusable.
Which is also why there is no "just use CFG". CFG is an abstraction from language generation. BNF as a "language" was invented for language generation. It's suitability to parsing was mostly an accident, and we've been dealing with the pragmatic repercussions in the field of parsing ever sense. To make parsing work we have bounded subsets of the abstraction. To make the illusion of the abstraction work we've bent BNF to nearly its breaking point, but the illusion fails as soon as you realize the BNF for LL and LR (and LALR and so on and so forth) is subtly incompatible. There's no universal BNF, there never was, it's a broken illusion.
PEG is just as useful as a bounded subset of the abstraction as LL/LR. The break was PEG decided to stop pretending BNF was a useful lingua franca between these subsets and then parser combinators contributed further to the demise of "universal BNF", which was never universal.
There's also the parser combinator approach of parser-printers ;)
The tendency to assume that your preferences or tastes are globally shared is really puzzling to me. That has never been true and (most likely) never will be true.
OTOH, when comparing LL and LR, we can conclusively say that LR are more expressive than LL because they're a proper superset - any language that can be parsed by an LL(k) grammar can be parsed by an LR(k) grammar (for same k).
This is not known. It is conjectured to be true because if all context-free languages could be parsed with a PEG grammar it would imply you'd have a linear-time boolean matrix multiplication algorithm, but no one has ever constructed a concrete example of a language which is context-free but not parsable with a PEG.