Tunnel Parsing with counted repetitions

Authors

  • Nikolay Handzhiyski University Of Plovdiv "Paisii Hilendarski", 4000 Plovdiv, Bulgaria ExperaSoft UG (haftungsbeschr√§nkt), Goldasse 10, 77652 Offenburg, Germany https://orcid.org/0000-0003-0681-6871
  • Elena Somova University Of Plovdiv "Paisii Hilendarski", 4000 Plovdiv, Bulgaria https://orcid.org/0000-0003-3393-1058

DOI:

https://doi.org/10.7494/csci.2020.21.4.3753

Abstract

The article describes a new and efficient algorithm for parsing, called Tunnel Parsing, that parses from left to right on the basis of a context-free grammar without left recursion and rules that recognize empty words. The algorithm is applicable mostly for domain-specific languages. In the article, particular attention is paid to the parsing of grammar element repetitions. As a result of the parsing, a statically typed concrete syntax tree is built from top to bottom, that accurately reflects the grammar. The parsing is not done through a recursion, but through an iteration. The Tunnel Parsing algorithm uses the grammars directly without a prior refactoring and is with a linear time complexity for deterministic context-free grammars.

Downloads

Download data is not yet available.

Downloads

Published

2020-11-03

How to Cite

Handzhiyski, N., & Somova, E. (2020). Tunnel Parsing with counted repetitions. Computer Science, 21(4). https://doi.org/10.7494/csci.2020.21.4.3753

Issue

Section

Articles