1. Prerequisites
  2. Our grammar
  3. GLL with Separate Stacks
    1. The GLL Stack
    2. The Stack GLL Compiler
      1. Compiling a Terminal Symbol
      2. Compiling a Nonterminal Symbol
      3. Compiling a Rule
      4. Compiling a Definition
      5. Compiling a Grammar
      6. Example
    3. Usage
  4. GLL with a Graph Structured Stack (GSS)
    1. The GSS Node
    2. The GSS container
    3. The GLL GSS
    4. The GSS GLL Compiler
      1. Example
    5. Usage
  5. Artifacts

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 Packages These 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`.
  1. simplefuzzer-0.0.1-py2.py3-none-any.whl from "The simplest grammar fuzzer in the world".

Our grammar

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 consumed.

The GSS container


The GSS GLL Compiler

The only difference in the main body when using the GSS is how we check for termination.



Another grammar

Another grammar

Another grammar

Another grammar

Another grammar


The runnable Python source for this notebook is available here.