ACL Findings2025
HyGenar: An LLM-Driven Hybrid Genetic Algorithm for Few-Shot Grammar Generation
Weizhi Tang, Yixuan Li, Chris Sypherd, Elizabeth Polgreen, Vaishak Belle
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 LLMdriven 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 1 . John W Backus. 1959. The syntax and the semantics of the proposed international algebraic language of the zurich acm-gamm conference. In ICIP Proceedings, pages 125-132.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on2
- Reflexion: language agents with verbal reinforcement learningNoah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan et al.NeurIPS 2023 · 5,828 citations
- Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical ReasoningLiangming Pan, Alon Albalak, Xinyi Wang, William Yang WangEMNLP Findings 2023 · 145 citations
Related papers
- Grammar Prompting for Domain-Specific Language Generation with Large Language ModelsBailin Wang, Zi Wang, Xuezhi Wang, Yuan Cao et al.NeurIPS 2023 · 138 citations
- Self-Correction Makes LLMs Better ParsersZiyan Zhang, Yang Hou, Chen Gong, Zhenghua LiEMNLP Findings 2025 · 5 citations
- GRAMMAR-LLM: Grammar-Constrained Natural Language GenerationGabriele Tuccio, Luana Bulla, Maria Madonia, Aldo Gangemi et al.ACL Findings 2025 · 5 citations
- Grammar-Based Code Representation: Is It a Worthy Pursuit for LLMs?Qingyuan Liang, Zhao Zhang, Zeyu Sun, Zheng Lin et al.ACL Findings 2025 · 5 citations
- NL Schedule: Evaluate Multitask Scheduling Capability of Large Language ModelsWenrui Liao, Weihong Du, Yi Li, Hongru Liang et al.ACL 2026
