Gold Open-Access
Refine
Year of publication
- 2022 (679) (remove)
Document Type
- Article (596)
- Monograph/Edited Volume (18)
- Review (12)
- Master's Thesis (10)
- Doctoral Thesis (8)
- Conference Proceeding (7)
- Other (7)
- Part of Periodical (6)
- Bachelor Thesis (5)
- Part of a Book (5)
Language
- English (544)
- German (128)
- Spanish (5)
- French (1)
- Multiple languages (1)
Keywords
- Tolkien (7)
- climate change (7)
- machine learning (7)
- Germany (6)
- exercise (6)
- COVID-19 (5)
- diabetes (5)
- permafrost (5)
- Lateinunterricht (4)
- muscle strength (4)
Institute
- Extern (122)
- Institut für Biochemie und Biologie (111)
- Institut für Geowissenschaften (67)
- Institut für Physik und Astronomie (66)
- Institut für Umweltwissenschaften und Geographie (45)
- Historisches Institut (41)
- Department Sport- und Gesundheitswissenschaften (36)
- Strukturbereich Kognitionswissenschaften (35)
- Institut für Ernährungswissenschaft (28)
- Hasso-Plattner-Institut für Digital Engineering GmbH (24)
Language developers who design domain-specific languages or new language features need a way to make fast changes to language definitions. Those fast changes require immediate feedback. Also, it should be possible to parse the developed languages quickly to handle extensive sets of code.
Parsing expression grammars provides an easy to understand method for language definitions. Packrat parsing is a method to parse grammars of this kind, but this method is unable to handle left-recursion properly. Existing solutions either partially rewrite left-recursive rules and partly forbid them, or use complex extensions to packrat parsing that are hard to understand and cost-intensive. We investigated methods to make parsing as fast as possible, using easy to follow algorithms while not losing the ability to make fast changes to grammars.
We focused our efforts on two approaches.
One is to start from an existing technique for limited left-recursion rewriting and enhance it to work for general left-recursive grammars. The second approach is to design a grammar compilation process to find left-recursion before parsing, and in this way, reduce computational costs wherever possible and generate ready to use parser classes.
Rewriting parsing expression grammars is a task that, if done in a general way, unveils a large number of cases such that any rewriting algorithm surpasses the complexity of other left-recursive parsing algorithms. Lookahead operators introduce this complexity. However, most languages have only little portions that are left-recursive and in virtually all cases, have no indirect or hidden left-recursion. This means that the distinction of left-recursive parts of grammars from components that are non-left-recursive holds great improvement potential for existing parsers.
In this report, we list all the required steps for grammar rewriting to handle left-recursion, including grammar analysis, grammar rewriting itself, and syntax tree restructuring. Also, we describe the implementation of a parsing expression grammar framework in Squeak/Smalltalk and the possible interactions with the already existing parser Ohm/S. We quantitatively benchmarked this framework directing our focus on parsing time and the ability to use it in a live programming context. Compared with Ohm, we achieved massive parsing time improvements while preserving the ability to use our parser it as a live programming tool.
The work is essential because, for one, we outlined the difficulties and complexity that come with grammar rewriting. Also, we removed the existing limitations that came with left-recursion by eliminating them before parsing.
Vom Bolschoi nach Sanssouci
(2022)