To generate valid test inputs for a system, one needs a specification of its input language—typically a context-free grammar that describes input syntax. But where can one get such a grammar from? In the past years, the field of input grammar mining has emerged, with creative approaches to extract input grammars from inputs, code, or both. But how good are these approaches? In particular; How accurate are the grammars they mine? In this study, we systematically evaluate grammar miners for these questions. Notably, we find that the previous evaluations conducted by the respective authors—producing a set of inputs from a golden grammar and having them checked by the mined grammar, or vice versa—are insufficient, as they have a strong bias towards short, possibly unrealistic inputs. We therefore also measure the diversity of the mined grammars using k-path coverage with varying depths k to find how many combinations of grammar elements are actually represented. Ideally, a mined grammar should have perfect precision and recall regardless of the depth k. However, our results show that for all approaches presented so far, precision and recall can drop significantly compared to reported results when increasing k and thus checking for “deeper” diversity, especially for complex input languages such as Lisp, JSON, or Tiny-C. For instance, the Tiny-C grammar mined by Arvada achieves a precision of 75% when considering k-paths with k = 1 (the originally reported precision was 73%), but this drops to 46% for k = 5. White-box approaches based on program analysis, such as Mimid and Stalagmite, are more stable with varying depth k, but can be challenged by complex parsers such as mjs. Raising the bars for evaluation, our study shows that there is still room for improvement in grammar mining.
International Conference on Software Engineering (ICSE)
2026-04-12
2026-09-24