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.
Abstract (translated)
语法在自然语言处理和文本/代码生成中扮演着关键角色，它能够定义句法、创建解析器，并指导结构化输出。尽管大型语言模型（LLMs）在其广泛的应用领域表现出令人印象深刻的能力，但它们推断和生成语法规则的能力尚未得到充分探索。在这篇论文中，我们旨在研究并改进LLM在小样本语法生成中的能力，在这种情况下，从一组少量的正例和反例中推导出语法，并将其以Backus-Naur形式（BNF）生成出来。为了探究这一点，我们引入了一个包含540个结构化语法生成挑战的新数据集，设计了6种评估指标，并对8种不同的LLM进行了评测。我们的研究发现表明，现有的LLM在语法生成方面表现不佳。为了解决这个问题，我们提出了一种新的方法——HyGenar，这是一种由LLM驱动的混合遗传算法，旨在优化语法规则的生成过程。HyGenar显著提高了不同LLM在语法生成中的句法和语义正确性。
URL
https://arxiv.org/abs/2505.16978
