Optimizing SGLR Parser Performance

Bachelor thesis (2021)

Authors

J. de Ruiter Electrical Engineering, Mathematics and Computer Science

Contributors

Eelco Visser Programming Languages - EEMCS (mentor)
J. Denkers Programming Languages - EEMCS (mentor)
D.A.A. Pelsmaeker Programming Languages - EEMCS (mentor)
Ranga Rao Venkatesha Prasad Embedded Systems - EEMCS (graduation committee member)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright: © 2021 Justin de Ruiter
More Info
expand_more

Published Date

02-07-2021

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

The Scannerless Generalized-LR (SGLR) parsing algorithm allows parsing of declarative and modular syntax definitions. However, SGLR is notorious for having low performance, negatively impacting its adoption in practice. This paper presents several performance optimizations for JSGLR2, which is an implementation of SGLR. All optimizations are implemented and evaluated in parallel, which is possible due to JSGLR2's modular architecture. The evaluation is performed using existing sources from three different languages. A combined speed-up of 9% up to 44% is achieved, improving the practicality of JSGLR2.