- author = "Ning Tao and Anthony Ventresque and Vivek Nallur and Takfarinas Saber",
- title = "Grammar-obeying program synthesis: A novel approach using large language models and many-objective genetic programming",
- journal = "Computer Standards and Interfaces",
- year = "2025",
- volume = "92",
- pages = "103938",
- keywords = "genetic algorithms, genetic programming, G3P, SBMaOG3P, Program synthesis, Grammar, LLMs, Grammar guided GP, Multi-objective",
- ISSN = "0920-5489",
-
URL = "
https://www.human-competitive.org/sites/default/files/saber_text_1.txt",
-
URL = "
https://www.human-competitive.org/sites/default/files/saber_paper_1.pdf",
-
URL = "https://researchrepository.universityofgalway.ie/server/api/core/bitstreams/f296602c-4e0f-4575-9be9-17cc4a7e2212/content",
-
URL = "https://www.sciencedirect.com/science/article/pii/S0920548924001077",
-
DOI = "
10.1016/j.csi.2024.103938",
- size = "10 pages",
- abstract = "Program synthesis is an important challenge that has attracted significant research interest, especially in recent years with advancements in Large Language Models (LLMs). Although LLMs have demonstrated success in program synthesis, there remains a lack of trust in the generated code due to documented risks (e.g., code with known and risky vulnerabilities). Therefore, it is important to restrict the search space and avoid bad programs. In this work, pre-defined restricted Backus-Naur Form (BNF) grammars are used, which are considered safe, and the focus is on identifying the most effective technique for grammar-obeying program synthesis, where the generated code must be correct and conform to the predefined grammar. It is shown that while LLMs perform well in generating correct programs, they often fail to produce code that adheres to the grammar. To address this, a novel Similarity-Based Many-Objective Grammar Guided Genetic Programming (SBMaOG3P) approach is proposed, leveraging the programs generated by LLMs in two ways: (i) as seeds following a grammar mapping process and (ii) as targets for similarity measure objectives. Experiments on a well-known and widely used program synthesis dataset indicate that the proposed approach successfully improves the rate of grammar-obeying program synthesis compared to various LLMs and the state-of-the-art Grammar-Guided Genetic Programming. Additionally, the proposed approach significantly improved the solution in terms of the best fitness value of each run for 21 out of 28 problems compared to G3P.",
-
notes = "Entered 2025 HUMIES cited by
\cite{Pinna:2025:Ital-IA-TW}
Also known as \cite{TAO2025103938}
School of Computer Science, University College Dublin, Dublin, Ireland",
