2 ms·
> The advice to "use CFGs" is incomplete. What you really want is to use one of the deterministic subsets of CFGs, like LR(k), and importantly, with a parser-ge
by WorldMaker 2y ago
> The advice to "use CFGs" is incomplete. What you really want is to use one of the deterministic subsets of CFGs, like LR(k), and importantly, with a parser-generator which will reject any non-LR productions in the grammar before even generating the parser.
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.