## 3 Proposed Approach
### Grammar-Mapping of LLM-Generated Code  
In G3P, all programs in the population must adhere to the same grammar rules for genetic operators, such as crossover, mutation, and selection. Hence, without fitting it to the predefined grammar, we cannot seed the LLM-generated code into the G3P system. Initially, we attempted to augment the prompt template with additional grammar information (as shown below), aiming to guide LLMs into generating code that adheres to the same grammar as the randomly generated population. Main task: <Generate a Python function...>  
The function should obey the provided BNF grammar. Task description: {input_task_description}  
Output program format: <Function parameter...>  
Output program grammar: {input_task_BNFgrammar}  
Unfortunately, specifying the grammar in the LLM prompt decreased the success rate of generating correct programs (the LLM tends to generate code that does not address the problem description) and often includes code snippets outside the defined grammar. In response, we developed a grammar-mapping algorithm to transform programs into a format that adheres to a predefined grammar file. In our evolution, we used the automatic grammar file selection approach proposed in the previous work by [PERSON] et al. [28; 54]. In the context of the mapping algorithm, LLMs generated code conflicts with the predefined grammar, primarily in three different aspects. First, certain functions used in the source code lacked support within the BNF grammar, or their function parameters did not align with those specified by the grammar. For example, in most programming languages, functions have multiple optional parameters with default values, while in G3P, the predefined grammar only keeps core parameters (that can be evolved with the genetic algorithm) for certain functions. Second, while the available variable names are fixed in the grammar file, the naming scheme for variables in the source code is more flexible. Third, the structural composition of the source code did not conform to the patterns established by the target grammar. For example, there were often short expressions for certain complex programming structures, while the BNF grammar in G3P does not support these short expressions. The grammar-mapping strategy is described in Algorithm 1. Specifically, we generate an abstract syntax tree (AST) \(T\) of the provided program \(p\). An AST, as described byBaxter [66], is a tree-like data structure to represent the hierarchical structure of a program or code snippet. This representation can reconstruct code functionally equivalent to the original, regardless of the target language. We map the AST \(T\) of our provided program by having its root node \(R\) iterate through its child nodes and constructing the output program \(q\) recursively using _Node_Iterator_. ```
Data: Program \(p\) from arbitrary source, Grammar \(G\) Result: Grammar-mapped program \(q\)  Build Abstract Syntax Tree \(T\) from \(p\); \(R\leftarrow\) Get Root of the \(T\) \(q\leftarrow\) Node_Iterator(\(R\), \(G\)) return\(q\)
```  
**Algorithm 1**Grammar Mapping Algorithm. A general structure of an AST is shown in Figure 2 using an example Python program \"\(a=1\); \(b=a+2\)\". It contains a root node \"_Module_\", indicating the entry of a program, and a series of non-terminal and terminal nodes. For example, the \"_Assign_\" node represents an assign expression in Python with its attributes describing its structure, whereas the \"_Name_\" node represents a variable. Non-terminal nodes (node \"_Assign_\" in the example) also have child nodes, each with a sub-tree representing its sub-elements. Algorithm 2 details the recursion process. We begin by iterating through each child node \(n\) of the given node \(R\). For each child node \(n\), the behaviour changes depending on whether it is a terminal or a non-terminal node. We examine whether the value and parameters conflict with the grammar \(G\) for non-terminal nodes.