Post #2479123

@olynch@mathstodon.xyz I'm not sure recursive descent parsers are the best example, for a few reasons: - People often tacitly assume a correspondence between finite lookahead RD and LL(k) parsing, but RD is actually more expressive. For example, no LL(k) grammar can resolve a "dangling else" conflict (https://dl.acm.org/doi/10.1145/322344.322350), but people frequently use handwritten RD parsers to parse C and other languages that have "dangling else" conflicts. Even in its pure form without backtracking, RD has ordered choice, as opposed to the declarative/nondeterministic generative semantics of context-free grammars. - In basically every instance I am aware of where people produced a handwritten RD parser with a particular grammar in mind but did not do grammar-based testing along the way, the parser turns out to be parsing a different language than the one generated by the intended grammar. I would posit a few more reasons for the gap between parsing theory and practice: - Most parsing theory uses BNF, but most people find EBNF to be more natural for describing programming languages. - EBNF integrates naturally into LL(k) parsers, somewhat cleanly within Earley parsing, but is fairly miserable for LR(k)-based methods, which are usually presented as the "sweet spot" for usage. Also, none of this is really covered by any of the standard textbooks on the subject. - Generating type-correct code for LR(1) parsers is difficult (impossible?) without dependent types. You get the closest with recursive-ascent parsing (also usually not covered in textbooks), but still run into problems when you have multiple reduction items in an LR state with different RHS lengths. - There are a few standard tricks for handling operator precedence in the middle of other parsers. RD parsers generally use the "local left-corner transform" approach, often called "precedence climbing" or the like. LR parsing tools generally use a hack of arbitrarily resolving shift/reduce conflicts based on user annotations, which is actually incorrect in some cases. Correctly implementing precedence for LR parsers is a huge step-up in complexity (and made even worse by several papers on the topic containing mistakes). (continued)