On Parsing Programming Languages with Turing-Complete Parser

Boštjan Slivnik and Marjan Mernik ()
Additional contact information
Boštjan Slivnik: Faculty of Computer and Information Science, University of Ljubljana, Večna Pot 113, 1000 Ljubljana, Slovenia
Marjan Mernik: Faculty of Electrical Engineering and Computer Science, University of Maribor, Koroška Cesta 46, 2000 Maribor, Slovenia

Mathematics, 2023, vol. 11, issue 7, 1-27

Abstract: A new parsing method based on the semi-Thue system is described. Similar to, but with more efficient implementation than Markov normal algorithms, it can be used for parsing any recursively enumerable language. Despite its computational power, it is meant to be used primarily for parsing programming and domain-specific languages. It enables a straightforward simulation of a number of existing parsing algorithms based on context-free grammars. The list includes both top-down shift-produce methods (such as SLL and LL) and bottom-up shift-reduce methods (such as LALR and LR), as well as mixed top-down-and-bottom-up methods such as LLLR. To justify the use of the new parsing method, the paper provides numerous examples of how a parser can actually be made in practice. It is advised that the main part of the parser is based on some simple well-established approach, e.g., SLL(1), while syntactically more complicated phrases can be parsed by exploiting the full power of the new parser. These phrases may either be extensions to the original language or some embedded domain-specific language. In all such and similar cases, no part of the language is restricted to be context-free. In fact, context-sensitive languages can be handled quite efficiently.

Keywords: turing-complete parsing; context-sensitive; error recovery (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/7/1594/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/7/1594/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:7:p:1594-:d:1107110

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().