Determining Programming Languages Complexity and Its Impact on Processing

Abstract

Tools for Programming Languages processing, like Static Analysers (for instance, a Static Application Security Testing (SAST) tool), must be adapted to cope with a different input when the source programming language changes. Complexity of the programming language is one of the key factors that deeply impact the time of giving support to it.
This paper aims at proposing an approach for assessing language complexity, measuring, at a first stage, the complexity of its underlying context-free grammar (CFG). From the analysis of concrete case studies, factors have been identified that make the support process more time-consuming, in particular in the stages of language recognition and in the transformation to an abstract syntax tree (AST). In this sense, at a second stage, a set of language characteristics is analysed in order to take into account the referred factors that also impact on the language processing.
The principal goal of the project here reported is to help development teams to improve the estimation of time and effort needed to cope with a new programming language. In the paper a tool is proposed, and its prototype is presented, that allows the evaluation of the complexity of a language based on a set of metrics to classify the complexity of its grammar, along with a set of properties. The tool compares the new language complexity so far determined with previously supported languages, to predict the effort to process the new language.