A Tree Sampler for Bounded Context-Free Languages
In the following paper, we present a simple method for sampling trees with and without replacement from bounded context-free languages (BCFLs). A BCFL is a context-free language (CFL) corresponding to finite-length strings with holes, which can be completed by valid terminals. We do so by defining a algebraic datatype that compactly represents candidate parse trees for an initial string. Once constructed, sampling trees is a straightforward matter of sampling integers uniformly without a replacement from a finite range.
|A Tree Sampler for Bounded Context-Free Languages (tree-sampler.pdf)