How to enumerate trees from a context-free grammar

While context-free grammars (CFGs) are important in computational linguistics and theoretical computer science, there is no simple, memoryless algorithm for enumerating the trees generated by an arbitrary CFG. One approach is to maintain a priority queue of partially expanded trees according to probability, and expand them through (e.g.) the leftmost unexpanded nonterminal in the tree. This, however, requires storing multiple trees in memory, which can become slow when enumerating many trees. Incremental polynomial time algorithms are also known [1] and related questions have been studied for lexicographic enumeration [2-4]. These algorithms are not particularly well-known, and the tools required to state and analyze them are complex. In contrast, simple techniques exist for enumerating binary trees with a fixed grammar (e.g. S SS | x). A variety of techniques and history is reviewed in Section 7.2.1.6 of [5], including permutation-based methods and gray codes [6-9]. These algorithms, however, do not obviously generalize to arbitrary CFGs. The goal of the present paper is to present an variant of integer-based enumeration schemes that works for arbitrary CFGs.