# Grammars for Free: Toward Grammar Inference for Ad Hoc Parsers

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Feb 2022.

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

- [HyGenar: An LLM-Driven Hybrid Genetic Algorithm for Few-Shot Grammar Generation](https://mlsanity.com/paper/2505.16978/) (2025)
- [Example-Free Learning of Regular Languages with Prefix Queries](https://mlsanity.com/paper/2504.02170/) (2025)

## Abstract (arXiv)

Ad hoc parsers are everywhere: they appear any time a string is split, looped over, interpreted, transformed, or otherwise processed. Every ad hoc parser gives rise to a language: the possibly infinite set of input strings that the program accepts without going wrong. Any language can be described by a formal grammar: a finite set of rules that can generate all strings of that language. But programmers do not write grammars for ad hoc parsers -- even though they would be eminently useful. Grammars can serve as documentation, aid program comprehension, generate test inputs, and allow reasoning about language-theoretic security. We propose an automatic grammar inference system for ad hoc parsers that would enable all of these use cases, in addition to opening up new possibilities in mining software repositories and bi-directional parser synthesis.