Context-sensitive parsing for programming languages

Slivnik, Boštjan (avtor)

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.

• Jezik: Angleški jezik
• Ključne besede: parsing, context-sensitive grammars, programming languages
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2022
• Št. strani: 16 str.
• Številčenje: Vol. 73, art. 101172
• PID: 20.500.12556/RUL-143395
• UDK: 004.43
• ISSN pri članku: 2590-1184
• DOI: 10.1016/j.cola.2022.101172
• COBISS.SI-ID: 127800323
• Datum objave v RUL: 19.12.2022

Gradivo je del revije

• Naslov: Journal of computer languages
• Založnik: Elsevier
• ISSN: 2590-1184
• COBISS.SI-ID: 22167062

Licence

• Licenca: CC BY-NC-ND 4.0, Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by-nc-nd/4.0/deed.sl
• Opis: Najbolj omejujoča licenca Creative Commons. Uporabniki lahko prenesejo in delijo delo v nekomercialne namene in ga ne smejo uporabiti za nobene druge namene.

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: sintaksna analiza, kontekstnoodvisne gramatike, programski jeziki