H y G enar: An LLM -Driven Hybrid Genetic Algorithm for Few-Shot Grammar Generation (2025)

Abstract: Grammar plays a critical role in natural language processing and text/code generation by enabling the definition of syntax, the creation of parsers, and guiding structured outputs. Although large language models (LLMs) demonstrate impressive capabilities across domains, their ability to infer and generate grammars has not yet been thoroughly explored. In this paper, we aim to study and improve the ability of LLMs for few-shot grammar generation, where grammars are inferred from sets of a small number of positive and negative examples and generated in Backus-Naur Form. To explore this, we introduced a novel dataset comprising 540 structured grammar generation challenges, devised 6 metrics, and evaluated 8 various LLMs against it. Our findings reveal that existing LLMs perform sub-optimally in grammar generation. To address this, we propose an LLM-driven hybrid genetic algorithm, namely HyGenar, to optimize grammar generation. HyGenar achieves substantial improvements in both the syntactic and semantic correctness of generated grammars across LLMs.

## introduction grammar inference, also known as grammar induction, consists of inferring a grammar from a set of examples @xcite @xcite . it has been studied and used in various fields, such as natural language processing, where it can reduce the effort required to generate syntactic or semantic models automatically @xcite , and software engineering, where inferred grammars can guide reverse engineering and automated parser generation @xcite . by relying on characteristic examples (de la higuera, 2010), grammar infer1 the code is open-source and available at https:// github.com/rutatang/hygenar . ence enables automated discovery of underlying syntactic or structural patterns. backus-naur form (bnf) is used to define the grammar of formal languages @xcite @xcite , typically context-free grammars (cgfs) @xcite . it has also been used in various ways such as in parser generators like antlr4 @xcite and @xcite or in constraining output structure of large language models (llms) @xcite . although llms have exhibited remarkable capabilities across diverse domains @xcite @xcite @xcite , their capacity for grammar inference, and partic-ularly for generating grammars in bnf, has not yet been well explored. this paper focuses on investigating and improving the ability of llms to infer a cfg and generate it in bnf from a given set of positive and negative examples. a correctly generated grammar should accept all positives and reject all negatives. typically, grammar inference requires a large set of characteristic examples that can uniquely identify a cfg (de la higuera, 2010). however, we instead explore whether llms can infer a cfg from fewer examples without imposing any constraints on the examples, based on their experience and knowledge acquired through training on large-scale corpora. we refer to this process as "few-shot grammar generation", emphasizing both the grammar inference of cfgs with fewer examples and their generation in bnf, and we use "grammar" to denote a cfg represented in bnf. an example is shown in figure 1 . to explore the capacity of llms for few-shot grammar generation, we first construct a dedicated dataset of 540 challenges, each with only 3 positive and 3 negative examples, and use it to evaluate the performance of 8 llms, encompassing both open-and closed-source models of varying parameter sizes, including those specialized for code generation. we then propose an llm-driven hybrid genetic algorithm, namely hygenar, which adapts the principles of genetic algorithms with the integration of llm-driven population initialization and mutation. we devised and adopted 6 metrics to comprehensively evaluate and analyze their performance from the perspectives of syntax and semantic correctness, over-fitting, overgeneralization, and utility. the results show that, while most llms demonstrate unsatisfactory performance, our proposed algorithm significantly enhances the grammar generation ability across most of the evaluated llms. we summarize the main contributions of this paper as follows: ## grammar generation ability of llms in this section, we describe the dedicated dataset constructed to evaluate the ability of llms in grammar generation, introduce 6 metrics we use in evaluation, explain experiments, and analyze results in detail. we detail each in the following subsections. ## conclusion to explore the few-shot grammar generation ability of llms, we constructed a dedicated dataset consisting of 540 challenges, devised and adopted 6 metrics, and evaluated 8 various llms. due to their unsatisfactory performance, we introduced hygenar, an llm-driven hybrid genetic algorithm for grammar generation. our results indicate that hygenar significantly enhances both syntax and semantic correctness compared to the two baselines. we believe this work provides valuable insights into llm-based grammar generation and highlights the potential of llm-driven hybrid genetic algorithms in this domain.