Post #2479125

2026-05-10 14:48 UTC

@zwarich@hachyderm.io This thing about grammar based testing is very interesting. I think it's probably a good idea to write down a grammar and then try to do property-based testing on the handwritten parser by seeing if it can parse an arbitrary string sampled randomly from the grammar, and it gives back the same tree that the grammar gave; this seems related to what @MartinEscardo@mathstodon.xyz was suggesting but in a bit of a different direction. One of my colleagues recently wrote a property based tester for fnotation, but it was manually written; it would be much better to generate this automatically from a declarative spec. Though... there still is a tricky thing here which is that if you want to test your precedence parsing, you have to generate strings that have some, but not all parentheses, so you have to express precedences numerically in the grammar still.

Replies (2)

@olynch@mathstodon.xyz 2026-05-10 14:50

@zwarich@hachyderm.io @MartinEscardo@mathstodon.xyz And I will admit that I probably ignorantly used LL(1) incorrectly; I really just meant "no backtracking, always commit to a decision on what to do by looking only at the next token."

Open ##2479126
@zwarich@hachyderm.io 2026-05-10 14:52

@olynch@mathstodon.xyz @MartinEscardo@mathstodon.xyz Another solution is to write the ambiguous grammar but disambiguate by intersecting with regular tree languages. This is a folklore idea from the formal languages world, but it thankfully got published separately at a workshop: https://michaeldadams.org/papers/disambiguating-grammars/ Most (all?) interesting grammar classes are closed under intersection with regular string and tree languages, so it shouldn't affect the rest of your generator.

Open ##2479127