Data set preprocessing is a critical step for the successful application of machine learning algorithms in classification tasks. Even though we rely on learning algorithms to pinpoint the optimal decision boundaries in the feature space by properly detecting latent relationships among the input features, their performance is often bounded by the discriminative power of the available features. Therefore, much effort has been devoted to developing preprocessing methods that are capable of transforming the input data with the final goal of aiding the machine learning algorithm in building high-quality classification models. One such a method is feature construction, which is a flexible preprocessing procedure that exploits linear and nonlinear transformations of the original feature space in an attempt to capture useful information that is not explicit in the original data. Since the task of feature construction can be modelled as a heuristic search in the space of novel latent features, this paper investigates an evolutionary approach for performing such a task, namely grammatical evolution (GE). In our proposed approach, GE is employed for building an extra novel feature from the available input data in order to maximize the predictive performance of the learning algorithm in training data. Results show that many interesting implicit relationships are indeed found by the evolutionary approach, improving the performance of two well-known decision-tree induction algorithms.