On Parsing Programming Languages with Turing-Complete Parser
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-03-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/11/7/1594 |
| _version_ | 1827746781900832768 |
|---|---|
| author | Boštjan Slivnik Marjan Mernik |
| author_facet | Boštjan Slivnik Marjan Mernik |
| author_sort | Boštjan Slivnik |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-11T05:31:12Z |
| format | Article |
| id | doaj.art-d7f0d675a76e4a9d982878a4b51921e4 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-11T05:31:12Z |
| publishDate | 2023-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-d7f0d675a76e4a9d982878a4b51921e42023-11-17T17:07:50ZengMDPI AGMathematics2227-73902023-03-01117159410.3390/math11071594On Parsing Programming Languages with Turing-Complete ParserBoštjan Slivnik0Marjan Mernik1Faculty of Computer and Information Science, University of Ljubljana, Večna Pot 113, 1000 Ljubljana, SloveniaFaculty of Electrical Engineering and Computer Science, University of Maribor, Koroška Cesta 46, 2000 Maribor, SloveniaA 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.https://www.mdpi.com/2227-7390/11/7/1594turing-complete parsingcontext-sensitiveerror recovery |
| spellingShingle | Boštjan Slivnik Marjan Mernik On Parsing Programming Languages with Turing-Complete Parser Mathematics turing-complete parsing context-sensitive error recovery |
| title | On Parsing Programming Languages with Turing-Complete Parser |
| title_full | On Parsing Programming Languages with Turing-Complete Parser |
| title_fullStr | On Parsing Programming Languages with Turing-Complete Parser |
| title_full_unstemmed | On Parsing Programming Languages with Turing-Complete Parser |
| title_short | On Parsing Programming Languages with Turing-Complete Parser |
| title_sort | on parsing programming languages with turing complete parser |
| topic | turing-complete parsing context-sensitive error recovery |
| url | https://www.mdpi.com/2227-7390/11/7/1594 |
| work_keys_str_mv | AT bostjanslivnik onparsingprogramminglanguageswithturingcompleteparser AT marjanmernik onparsingprogramminglanguageswithturingcompleteparser |