Browsing by Subject "concrete syntax tree"

Now showing 1 - 1 of 1

Access status: Open Access ,
Tunnel parsing with counted repetitions
(Wydawnictwa AGH, 2020) Handzhiyski, Nikolay; Somova, Elena
This article describes a new and efficient algorithm for parsing (called tunnel parsing) that parses from left to right on the basis of context-free grammar without left recursion nor rules that recognize empty words. The algorithm is mostly applicable 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.