| Title: | On parsing programming languages with Turing-complete parser |
|---|
| Authors: | ID Slivnik, Boštjan (Author)
ID Mernik, Marjan (Author) |
|---|
| Files: |  Slivnik-2023-On_Parsing_Programming_Languages.pdf (534,88 KB)
MD5: 602B3D7FBE119737EEB9DBB9CF7FC463
 https://doi.org/10.3390/math11071594
|
|---|
| Language: | English |
|---|
| Work type: | Scientific work |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | FERI - Faculty of Electrical Engineering and Computer Science
|
|---|
| 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 |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Submitted for review: | 31.01.2023 |
|---|
| Article acceptance date: | 23.03.2023 |
|---|
| Publication date: | 25.03.2023 |
|---|
| Publisher: | MDPI |
|---|
| Year of publishing: | 2023 |
|---|
| Number of pages: | Str. 1-27 |
|---|
| Numbering: | Letn. 11, Št. 7, št. članka 1594 |
|---|
| PID: | 20.500.12556/DKUM-87060  |
|---|
| UDC: | 004 |
|---|
| ISSN on article: | 2227-7390 |
|---|
| COBISS.SI-ID: | 147237123 |
|---|
| DOI: | 10.3390/math11071594 |
|---|
| Publication date in DKUM: | 14.02.2024 |
|---|
| Views: | 468 |
|---|
| Downloads: | 40 |
|---|
| Metadata: |    |
|---|
| Categories: | Misc.
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
