“How to Enumerate Trees from a Context-Free Grammar”, Steven T. Piantadosi2023-04-30 (compression)⁠:

I present a simple algorithm for enumerating the trees generated by a Context Free Grammar (CFG).

The algorithm uses a pairing function to form a bijection between CFG derivations and natural numbers, so that trees can be uniquely decoded from counting. This provides a general way to number expressions in natural logical languages, and potentially can be extended to other combinatorial problems.

I also show how this algorithm may be generalized to more general forms of derivation, including analogs of Lempel-Ziv coding on trees.