Context-Free Grammar Inference for Complex Programming Languages in Black Box Settings DOI: 10.1145/3744916.3773147 Conference: 48th IEEE/ACM International Conference on Software Engineering; April 12-18 2026; Rio de Janeiro, Brazil ISBN: 978-1-4503-XXXX-X/18/06 CCS: Do Not Use This Code Generate th
Feifei Li 1,6 , Xiao Chen 2 , Xiaoyu Sun 3 , Xi Xiao 1,6* , Shaohua Wang 4 , Yong Ding 5* , Sheng Wen 5 , Qing Li 6 · 2026
Read Context-Free Grammar Inference for Complex Programming Languages in Black Box Settings DOI: 10.1145/3744916.3773147 Conference: 48th IEEE/ACM International Conference on Software Engineering; April 12-18 2026; Rio de Janeiro, Brazil ISBN: 978-1-4503-XXXX-X/18/06 CCS: Do Not Use This Code Generate th by Feifei Li 1,6 , Xiao Chen 2 , Xiaoyu Sun 3 , Xi Xiao 1,6* , Shaohua Wang 4 , Yong Ding 5* , Sheng Wen 5 , Qing Li 6 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-12385.txt.
Introduction
Feifei Li and seven co authors study how to learn the grammar of a programming language from the outside. In a black box setup, one can run code and watch what works, but the rules stay hidden. Past ways to infer those rules fail to scale. They take too long on the large, real world languages that coders use each day.
Grammar inference matters because a clear grammar is the base for many code tools. Tests, parsers, and safety checks all lean on it. The team takes up the scale problem for complex languages head on. Their work asks how far inference can go when time is tight and the language is large. The paper was set for a major software engineering venue in 2026.
Catalog record
| CREATOR | Feifei Li 1,6 , Xiao Chen 2 , Xiaoyu Sun 3 , Xi Xiao 1,6* , Shaohua Wang 4 , Yong Ding 5* , Sheng Wen 5 , Qing Li 6 |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-12385
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Context-Free Grammar Inference for Complex Programming Languages in Black Box Settings DOI: 10.1145/3744916.3773147 Conference: 48th IEEE/ACM International Conference on Software Engineering; April 12-18 2026; Rio de Janeiro, Brazil ISBN: 978-1-4503-XXXX-X/18/06 CCS: Do Not Use This Code Generate the Correct Terms for Your Paper CCS: Do Not Use This Code Generate the Correct Terms for Your Paper CCS: Do Not Use This Code Generate the Correct Terms for Your Paper CCS: Do Not Use This Code Generate the Correct Terms for Your Paper Feifei Li 1,6 , Xiao Chen 2 , Xiaoyu Sun 3 , Xi Xiao 1,6* , Shaohua Wang 4 , Yong Ding 5* , Sheng Wen 5 , Qing Li 6 Abstract . † † *Corresponding authors: Xi Xiao and Yong Ding. Emails: Feifei Li ([email protected]), Xiao Chen ([email protected]), Xiaoyu Sun ([email protected]), Xi Xiao ([email protected]), Shaohua Wang ([email protected]), Yong Ding ([email protected]), Sheng Wen ([email protected]), Qing Li ([email protected]). Grammar inference for complex programming languages remains a significant challenge, as existing approaches fail to scale to real-world datasets within practical time constraints. In our experiments, none of the state-of-the-art tools, including Arvada , Treevada and Kedavra were able to infer grammars for complex languages such as C, C++, and Java within 48 hours. Arvada and Treevada perform grammar inference directly on full-length input examples, which proves inefficient for large files commonly found in such languages. While Kedavra introduces data decomposition to create shorter examples for grammar inference, its lexical analysis still relies on the original inputs. Additionally, its strict no-overgeneralization constraint limits the construction of complex grammars. To overcome these limitations, we propose Crucio , which builds a decomposition forest to extract short examples for lexical and grammar inference via a distributional matrix. Experimental results show that Crucio is the only method capable of successfully inferring grammars for complex programming languages (where the number of nonterminals is up to 23 × \times greater than in prior benchmarks) within reasonable time limits. On the prior simple benchmark, Crucio achieves an average recall improvement of 1.37 × \times and 1.19 × \times over Treevada and Kedavra , respectively, and improves F1 scores by 1.21 × \times and 1.13 × \times . 1. Introduction Inferring context-free grammars (CFGs) ( 13 ) from example strings has a wide range of applications in software engineering, including code understanding ( 28 ) , reverse engineering ( 25 ) , protocol specification recovery ( 11 ; 26 ) , and input generation for fuzz testing ( 15 ; 6 ; 2 ; 14 ; 27 ; 31 ; 32 ) . Most existing grammar inference techniques operate in grey-box or white-box settings, where the internal structure or source code of the parser is accessible ( 10 ; 23 ; 18 ) . In contrast, black-box grammar inference aims to recover the underlying grammar of a parser with no access to its internal implementation, relying solely on input samples and binary feedback (accept or reject) from the parser. The objective is to construct a grammar that approximates the oracle’s behavior, accurately predicting acceptance for arbitrary inputs. Recent work in black-box grammar inference includes methods such as Arvada ( 21 ) , Treevada ( 5 ) , and Kedavra ( 22 ) . While these approaches show promise on small, synthetic grammars, they struggle with real-world programming languages. The datasets on which Arvada , Treevada , and Kedavra were evaluated typically correspond to parser grammars with fewer than 20 nonterminals. To evaluate scalability, we introduce challenging benchmarks derived from C, C++, Java, Lua, and Rust, including grammars with 20–200 nonterminals and input samples averaging over 2,000 characters. Existing tools fail to produce valid grammars on these datasets. Inferring grammars for realistic programming languages presents a number of challenges. First, the large size of input programs — often containing thousands of tokens — makes direct grammar inference computationally expensive. Arvada and Treevada both generalize grammar rules by selecting bubbles to merge based on contextual similarity on original input programs, resulting in grammars that are overly complex, and inefficient to infer. Although Kedavra introduces data decomposition to improve scalability, its lexical inference still operates on the original, undecomposed samples, resulting in a significant performance bottleneck. Furthermore, its decomposition strategy does not guarantee that the decomposed fragments preserve the grammar coverage of the original inputs, leading to potential generalization loss. Kedavra also enforces strict constraints to prevent overgeneralization, but its reliance on sampling-based validation means that errors can go undetected. These undetected errors accumulate over time and can render future grammar generalization steps ineffective or unstable. To address these limitations, we propose Crucio , a novel black-box grammar inference framework designed to scale to complex programming languages while maintaining precision and interpretability. Crucio introduces several key innovations. First, it introduces the concept of the decomposition forest , which systematically explores structured decompositions of input samples. This enables the discovery of short, generalizable samples while preserving grammar coverage — overcoming the generalization loss observed in Kedavra . Second, Crucio improves lexical inference by operating on shorter decomposed samples. It uses decision trees to classify tokens and applies the L* algorithm ( 4 ) to generalize token-level lexical rules efficiently and robustly. Third, for grammar inference, Crucio constructs a distributional matrix and applies grammar generalization over parse trees while enforcing first-order swap correctness . This ensures bounded correctness guarantees without requiring additional oracle queries beyond the initial stage. To the best of our knowledge, Crucio is the first approach capable of inferring usable grammars for complex programming languages such as C, C++, and Java in black-box settings within a practical timeframe. This paper makes the following contributions: • We present Crucio , a novel grammar inference framework that improves the generalization capability and scalability of black-box grammar inference. The tool is open-sourced and available at https://github.com/Sinpersrect/crucio . • Crucio is the first tool capable of inferring accurate grammars for real-world programming languages within a practical time limit. On the complex benchmarks (including C, C++, Java, etc.), it is the only method that produces results within the timeout threshold. On the simple benchmarks (used in evaluating state-of-the-art (SOTA) tools and involving languages such as Lisp, JSON, Turtle etc.), Crucio achieves performance comparable to that of the state-of-the-art grammar inference tools. • We propose Swap Precision , a new grammar evaluation metric that addresses key limitations of sample-based precision. Swap Precision avoids biases in sample-based precision that favor invalid grammars focusing on few samples and grammars generating short samples, enabling more reliable evaluation. 2. Background and Related Works Context-Free Grammar (CFG) ( 13 ) is a well-established mathematical formalism used to define the syntactic structure of formal languages, particularly in the specification of programming language syntax. Formally, a CFG is defined as a quadruple G=(V,\Sigma,R,S) , where V denotes a finite set of nonterminal symbols, \Sigma denotes the set of terminal symbols (disjoint from V ), R is a finite set of production rules of the form A\rightarrow\alpha with A\in V and \alpha\in(V\cup\Sigma)^{*} , and S\in V is the designated start symbol. CFGs allow the recursive definition of potentially infinite languages through a finite set of rules. For example, consider the grammar with V=\{S\},\quad\Sigma=\{a,b\},\quad\text{and production rules}\quad S\rightarrow aSb\mid ab. This grammar generates the language \{a^{n}b^{n}\mid n\geq