Contents

  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.

Prerequisites

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



Example



Usage



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 GLL GSS



The GSS GLL Compiler

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



Example



Usage



Another grammar



Another grammar



Another grammar



Another grammar



Another grammar



Artifacts

The runnable Python source for this notebook is available here.