Modelling equivalence classes of feature models with concept lattices to assist their extraction from product descriptions

Abstract Software product line engineering gathers a set of methods to help create, manage and maintain a collection of similar software systems. Variability modelling is a focal point of this paradigm, where feature models (FMs) are the prevalent notation. Migration from single system development to software product lines is a spreading topic in software engineering. To ease the migration, research has been done to automatically extract FMs from software descriptions, but most of these approaches are defined in a functional manner based on an ad-hoc variability analysis. In this paper, we propose a theoretical view on FM extraction from software descriptions based on Formal Concept Analysis (FCA). It is a structural framework for variability representation which allows to lay down theoretical foundation to variability extraction. We propose an original mapping between relationships expressed in FMs and the ones emphasised in FCA conceptual structures. We show that conceptual structures represent equivalence classes of FMs that steer the user choices during their synthesis, and propose a reverse engineering method based on them. We discuss its applicability and show that the combinatorial explosion of concept lattices can be avoided by the use of two sub-orders embodying the necessary information concerning variability.