License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.SLATE.2022.16
URN: urn:nbn:de:0030-drops-167620
Go to the corresponding OASIcs Volume Portal

Pinto, Gonçalo Rodrigues ; Henriques, Pedro Rangel ; da Cruz, Daniela ; Cruz, João

Determining Programming Languages Complexity and Its Impact on Processing

OASIcs-SLATE-2022-16.pdf (0.8 MB)


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.

BibTeX - Entry

  author =	{Pinto, Gon\c{c}alo Rodrigues and Henriques, Pedro Rangel and da Cruz, Daniela and Cruz, Jo\~{a}o},
  title =	{{Determining Programming Languages Complexity and Its Impact on Processing}},
  booktitle =	{11th Symposium on Languages, Applications and Technologies (SLATE 2022)},
  pages =	{16:1--16:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-245-7},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{104},
  editor =	{Cordeiro, Jo\~{a}o and Pereira, Maria Jo\~{a}o and Rodrigues, Nuno F. and Pais, Sebasti\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-167620},
  doi =		{10.4230/OASIcs.SLATE.2022.16},
  annote =	{Keywords: Complexity, Grammar, Language-based-Tool, Programming Language, Static code analysis}

Keywords: Complexity, Grammar, Language-based-Tool, Programming Language, Static code analysis
Collection: 11th Symposium on Languages, Applications and Technologies (SLATE 2022)
Issue Date: 2022
Date of publication: 27.07.2022
Supplementary Material: Software (Web Application): archived at:

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI