- Our grammar
- GLL with Separate Stacks
- GLL with a Graph Structured Stack (GSS)
Important: Pyodide takes time to initialize. Initialization completion is indicated by a red border around Run all button.
We previously discussed the implementation of an Earley parser with Joop Leo’s optimizations. Earley parser is one of the general context-free parsing algorithms available. Another popular general context-free parsing algorightm is Generalized LL parsing, which was invented by Elizabeth Scott and Adrian Johnstone. In this post, I provide a complete implementation and a tutorial on how to implement a GLL parser in Python.
Note: This post is not complete. Given the interest in GLL parsers, I am simply providing the source until I have more bandwidth to complete the tutorial.
As before, we start with the prerequisite imports.
Available PackagesThese are packages that refer either to my previous posts or to pure python packages that I have compiled, and is available in the below locations. As before, install them if you need to run the program directly on the machine. To install, simply download the wheel file (`pkg.whl`) and install using `pip install pkg.whl`.
GLL with Separate Stacks
The GLL Stack
The Stack GLL Compiler
Compiling a Terminal Symbol
Compiling a Nonterminal Symbol
Compiling a Rule
Compiling a Definition
Compiling a Grammar
GLL with a Graph Structured Stack (GSS)
The GSS Node
Each GSS Node is of the form $L_i^j$ where
j is the index of the character
The GSS container
The GLL GSS
The GSS GLL Compiler
The only difference in the main body when using the GSS is how we check for termination.
The runnable Python source for this notebook is available here.