This is a very nice approach. Unfortunately, Piantadosi's pairing function does not work for acyclic grammars (i.e., finite CFLs). We found a variant that handles enumerating all trees of a certain width from an arbitrary CFG, i.e., L(G) ∩ Σ^n, or whose language is finite [1]:<p>[1]: <a href="https://github.com/breandan/galoisenne/blob/master/latex/lafi2024/acmart.pdf">https://github.com/breandan/galoisenne/blob/master/latex/laf...</a>
Related work: Functional Enumeration of Algebraic Data Types - <a href="https://mengwangoxf.github.io/Papers/Haskell12.pdf" rel="nofollow">https://mengwangoxf.github.io/Papers/Haskell12.pdf</a><p>It's quite efficient, able to generate the 10^100th element in ~a second on 2013 hardware. It also groups the generated values by size, so you can e.g. randomly sample among ASTs with N nodes.