Tunnel Parsing with counted repetitions

Nikolay Handzhiyski, Elena Somova

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.

Full Text:

PDF


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

Refbacks

  • There are currently no refbacks.