| Title |
Parsing with Scannerless Earley Virtual Machines / |
| Authors |
Šaikūnas, Audrius |
| DOI |
10.22364/bjmc.2019.7.2.01 |
| Full Text |
|
| Is Part of |
Baltic journal of modern computing.. Riga : Latvijas Universitāte. 2019, vol. 7, no. 2, p. 171-189.. ISSN 2255-8942. eISSN 2255-8950 |
| Keywords [eng] |
Implementation ; scannerless parsing ; virtual machine |
| Abstract [eng] |
Earley parser is a well-known parsing method used to analyse context-free grammars. While being less efficient in practical contexts than other generalized context-free parsing algo- rithms, such as GLR, it is also more general. As such it can be used as a foundation to build more complex parsing algorithms. We present a new, virtual machine based approach to parsing, heavily based on the original Earley parser. We show how to translate grammars into virtual machine instruction sequences that are then used by the parsing algorithm. Additionally, we introduce an optimization that merges shared rule prefixes to increase parsing performance. Finally, we present and evaluate an implementation of Scannerless Earley Virtual Machine called north. |
| Published |
Riga : Latvijas Universitāte |
| Type |
Journal article |
| Language |
English |
| Publication date |
2019 |
