this post was submitted on 25 Dec 2022
1 points (100.0% liked)

Software Engineering Research

54 readers
0 users here now

Software Engineering Research related posts only

founded 2 years ago
MODERATORS
 

Generalized LL parsing is a relatively new technique for parsing arbitrary context-free grammars while achieving a cubic bound on the running time. By overcoming the limitations of traditional LL recursive descent parsers, GLL parsers are capable to support a larger class of grammars using the same reasoning as in LL parsing. In contrast to alternative parsing algorithms, GLL parsers are known for their straightforward implementation and efficiency. Since this type of parsing is still in its infancy, there are still many existing techniques such as error recovery that have to be developed. The design of these techniques however often requires a detailed understanding of how the underlying parser deals with phenomena such as non-determinism and left recursion. Since the GLL algorithm consider multiple stacks in parallel, the actual control flow of the algorithm can become rather complex, thereby making it more difficult for engineers to enhance the algorithm with new extensions. In this project, we will try to overcome this issue by explaining how a GLL parser actually works using visualization techniques. By making the relationships between GLL parsing, LL parsing, and input data explicit, the learning curve of the algorithm can significantly be reduced, thereby making it easier to develop new extensions for GLL parsing. Furthermore, the step-by-step visualization of the algorithm can be used as a debug application to test the behaviour of grammars at early stages of language development.

no comments (yet)
sorted by: hot top controversial new old
there doesn't seem to be anything here