How to enumerate trees from a context-free grammar

by luu • 2 years ago

53 9 2 years ago

I prefer to enumerate via a shortlex variant, primary key being number of leaves and secondary being the index of the particular expansion.

CoastalCoder• 2 years ago

Why the preference?

(For context, I'm completely new to this topic.)

0823498723498723• 2 years ago

Because I use them for testing, so I generally want to uniformly generate samples within a particular size of tree.

(generating random trees the naive way tends to produce the occasional huge tree amidst huge numbers of tiny trees)

morgante• 2 years ago

Do you have an example of doing this?

bmc7505• 2 years ago

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]:

[1] https://github.com/breandan/galoisenne/blob/master/latex/laf...

rictic• 2 years ago

Related work: Functional Enumeration of Algebraic Data Types - https://mengwangoxf.github.io/Papers/Haskell12.pdf

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.

How to enumerate trees from a context-free grammar

Related Stories