Post #2334008

2026-05-09 05:57 UTC

I think one reason why a lot of the academic literature on parsing and grammars is so disconnected from what language implementations use in practice is that what matters is not having a declarative spec for what an instance of the grammar is, what matters is following an algorithm whose failure conditions are understandable. When you implement recursive descent, at the point of a failure you know more or less what is going on. A full declarative specification of what the parser should do in these error cases is not that much shorter than just writing the darn recursive descent algorithm out. I feel like this is a general phenomenon, there are wide classes of programs where the spec is essentially the algorithm, and thus verification is kind of meaningless, it&#39;s more of a question of &quot;does the algorithm do a reasonable and mostly predictable thing in practice&quot;? And this is why I like category theory for computer science, it works at so much higher of a level that it&#39;s orthogonal to a lot of practical questions. If category theory were lower level, I&#39;d rather just scrap it and write code. But precisely because it forgets so much, it actually makes it easier to think about some questions. The &quot;awkward middle&quot; between math and programming where a lot of CS sits is often neither practically relevant nor conceptually simplifying.

Replies (3)

@takeoutweight@mastodon.social 2026-05-09 06:30

@olynch@mathstodon.xyz It it's easy for me to give up on the declarative graph DSLs for similar reasons. I have these subtle ways I want to align and group and space to express relationships and it quickly becomes easier just to place them on the page myself

Open ##2479112
@MartinEscardo@mathstodon.xyz 2026-05-09 06:46

@olynch@mathstodon.xyz What if you had *two* parsers? * One damn fast, prone to formal verification, following known theory, that is bad at error recovery. * The other ad hoc and slower that is better at error recovery and giving useful information about errors, triggered when the first one reports a failure. In a large codebase, the first one would be used most of the time. The second one would be applicable only at the file you are currently developing or modifying.

Open ##2479114
@zwarich@hachyderm.io 2026-05-09 15:08

@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)

Open ##2479123