Context-sensitive parsing for programming languages

Slivnik, Boštjan (author)

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.

• Language: English
• 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
• Year: 2022
• Number of pages: 16 str.
• Numbering: Vol. 73, art. 101172
• PID: 20.500.12556/RUL-143395
• UDC: 004.43
• ISSN on article: 2590-1184
• DOI: 10.1016/j.cola.2022.101172
• COBISS.SI-ID: 127800323
• Publication date in RUL: 19.12.2022

Record is a part of a journal

• Title: Journal of computer languages
• Publisher: Elsevier
• ISSN: 2590-1184
• COBISS.SI-ID: 22167062

Licences

• License: CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
• Link: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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

• Language: Slovenian
• Keywords: sintaksna analiza, kontekstnoodvisne gramatike, programski jeziki