A Tree Sampler for Bounded Context-Free Languages
summary
Claims a practical method to enumerate and sample distinct parse trees from bounded context-free languages by building an algebraic tree datatype that compactly represents all candidate parses for a template with holes. It replaces an earlier boolean-sat blocking approach with a compact forest representation, sorts productions by heuristics, counts structures and maps them via an integer bijection sampling to get sampling without replacement. Implementation powers a real-time syntax-repair tool, scales with more cores and yields efficient parallel enumeration.
AI-written summary · about