Context-sensitive parsing for programming languages
ID Slivnik, Boštjan (Author)

.pdfPDF - Presentation file, Download (905,18 KB)
MD5: D4A355A24B726A7539DEAAD13E4F41D5
URLURL - Source URL, Visit https://www.sciencedirect.com/science/article/pii/S2590118422000697 This link opens in a new window

Parsing programming languages using context-sensitive rather than context-free grammars is being considered here because a stronger formalism might be beneficial for dealing with increasingly complex programming languages and their syntax, or is more appropriate in some applications. A new deterministic non-backtracking algorithm for parsing deterministic context-sensitive languages is described. It is a significant improvement of the algorithm built into WEAVE and CWEAVE tools for literate programming and requires that the language is described by a context-sensitive reduction system, namely a deterministic formalism similar to a context-sensitive grammar but with strict rules about how reductions are to be applied. The new algorithm uses a reduction automaton for finding the position of the next reduction at each step during parsing rather than a hardcoded trie that is build into the original algorithm of WEAVE and CWEAVE. The new algorithm performs at least twice as few operations per input symbol as the original one. Furthermore, it is shown that parsing a language described by a context-sensitive reduction system need not be limited to typesetting purposes as in literate programming but can be used as a general parsing approach.

Keywords:parsing, context-sensitive grammars, programming languages
Work type:Article
Typology:1.01 - Original Scientific Article
Organization:FRI - Faculty of Computer and Information Science
Publication status:Published
Publication version:Version of Record
Number of pages:16 str.
Numbering:Vol. 73, art. 101172
PID:20.500.12556/RUL-143395 This link opens in a new window
ISSN on article:2590-1184
DOI:10.1016/j.cola.2022.101172 This link opens in a new window
COBISS.SI-ID:127800323 This link opens in a new window
Publication date in RUL:19.12.2022
Copy citation
Share:Bookmark and Share

Record is a part of a journal

Title:Journal of computer languages
COBISS.SI-ID:22167062 This link opens in a new window


License:CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
Description:The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.

Secondary language

Keywords:sintaksna analiza, kontekstnoodvisne gramatike, programski jeziki

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections: