- author = "Ning Tao",
- title = "Multi-Objective Grammar-Guided Genetic Programming for Grammar-Obeying Program Synthesis",
- school = "School of Computer Science, University College Dublin",
- year = "2025",
- address = "Ireland",
- month = mar,
- keywords = "genetic algorithms, genetic programming, G3P, MOG3P, Large language models, LLM, ANN, IO, Natural language task, NLP, AI generated programs, Grammar compliance, BNF, Computer programming",
-
URL = "
http://hdl.handle.net/10197/28256",
-
URL = "https://researchrepository.ucd.ie/entities/publication/b11d1a67-05ba-46eb-bf61-7f9b42245ea6",
- size = "163 pages",
-
abstract = "Grammar-obeying program synthesis is a subfield of
program synthesis (i.e., the task of automatically
discovering an executable piece of code) that requires
generated code to follow a Backus-Naur Form (BNF)
grammar. Having code that obeys a grammar limits the
structure of the code and the set of callable
functions/methods/libraries, thus having an impact on
(i) security: e.g., using malicious functionalities,
blacklisted libraries, and questionable constructs,
(ii) the computing environment: e.g., if the hardware
is not able to run some functions or if some functions
are too costly in terms of memory or energy, and (iii)
code quality: improving code style and readability,
reducing code smells, and enhancing
consistency.
Grammar-Guided Genetic Programming (G3P) is recognised as one of the most successful approaches for grammar-obeying program synthesis that evolves programs in arbitrary languages to solve program synthesis problems based on a set of input-output examples and predefined BNF grammars. Despite its success, the restriction on the evolutionary system to only leverage input-output error rate during its assessment of the programs it derives limits its scalability to larger and more complex program synthesis problems. Alternatively, while large language models (LLMs) are showing increasing success in program synthesis from a task description, they often struggle to generate accurate code due to ambiguity in task specifications, complex programming syntax, and lack of reliability in the generated code. Furthermore, their generative nature limits their ability to fix erroneous code with iterative LLM prompting.
In this thesis, I focus on enhancing the performance of G3P for grammar-obeying program synthesis tasks. I begin by evaluating the state-of-the-art systems, including G3P and LLMs, in grammar-obeying program synthesis. Next, I explore how to map LLM-generated code into grammar-obeying forms, followed by seeding the grammar-mapped LLM-generated code into G3P initial population to improve the evolutionary process. Building on these foundations, I investigate the potential of using code similarity measures to guide the evolution of programs, leading to the development of Bi-Objective Grammar-Guided Genetic Programming (BOG3P) and Multi-Objective Grammar-Guided Genetic Programming (MOG3P), which combine input-output error rate with multiple similarity measures as objective functions. Finally, I integrate LLM generated code into the MOG3P framework in two ways: (i) using LLM-generated code as a seed for the evolutionary process through a grammar-mapping phase, and (ii) leveraging multiple similarity measures towards LLM-generated code to guide the search process throughout the evolution. Additionally, I further extend the MOG3P framework by incorporating code from multiple LLMs to enhance the diversity and effectiveness of the search process.",
-
notes = "Student ID: 15205926
Supervisors: Takfarinas Saber, Anthony Ventresque, Vivek Nallur",
