# Learning Highly Recursive Input Grammars

arXiv: https://arxiv.org/abs/2108.13340 · HTML: https://mlsanity.com/paper/2108.13340/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Aug 2021.

## Built on by (most cited first, 4 of 4)

- [Learning Program Behavioral Models from Synthesized Input-Output Pairs](https://mlsanity.com/paper/2407.08597/) (2024)
- [Example-Free Learning of Regular Languages with Prefix Queries](https://mlsanity.com/paper/2504.02170/) (2025)
- [Decode-Time Grammars: Constrained LLM Generation over a Refinement Order of Grammar Fragments](https://mlsanity.com/paper/2607.18357/) (2026)
- [Learning Context-Free Grammars for Grammar-Constrained Decoding via Declarative Agentic Programming with Guarantees](https://mlsanity.com/paper/2608.05493/) (2026)

## Abstract (arXiv)

This paper presents Arvada, an algorithm for learning context-free grammars from a set of positive examples and a Boolean-valued oracle. Arvada learns a context-free grammar by building parse trees from the positive examples. Starting from initially flat trees, Arvada builds structure to these trees with a key operation: it bubbles sequences of sibling nodes in the trees into a new node, adding a layer of indirection to the tree. Bubbling operations enable recursive generalization in the learned grammar. We evaluate Arvada against GLADE and find it achieves on average increases of 4.98x in recall and 3.13x in F1 score, while incurring only a 1.27x slowdown and requiring only 0.87x as many calls to the oracle. Arvada has a particularly marked improvement over GLADE on grammars with highly recursive structure, like those of programming languages.