Generalized LL (GLL) Parser

Prerequisites
Our grammar
GLL with Separate Stacks
GLL with a Graph Structured Stack (GSS)
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`.

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

class GLLStructuredStack:
    def register_return(self, L, u, j): # create
        v = self.gss.get(L, j) # Let v be the GSS node labeled L^j
        # If there is not an edge from v to u
        if u not in v.children:
            v.children.append(u)
            # paper p183: When a new child node u is added to v,
            # for all (v, k) in P if (Lv, u) notin Uk then
            # (Lv,v,k) is added to R, where Lv is the label of v.
            # **Note:** The above is confusing because according to it, what
            # we should add is (v.L, v, k) while what we are adding below from
            # the same paper, p184 `create(L, u, j)` is `add(v.L, u, j)`
            # but in 183 again, it is said: The function create(L, u, j) creates
            # a GSS node v = Lj with child u if one does not already exist, and
            # then returns v. If (v, k) in P then add(L, u, k) is called.
            for k in self.gss.parsed_indexes(v.label):
                self.add_thread(v.L, u, k) # v.L == L
        return v

def add_thread(self, L, u, j): # add
        if (L, u) not in self.U[j]:
            self.U[j].append((L, u))
            self.threads.append((L, u, j))

def next_thread(self):
        (L, sval, i), *self.threads = self.threads
        return (L, sval, i)

# paper: actions POP(s, i, R) are replaced by actions which add (L, v, i) to
    # R for all children v of node corresponding to the top of s.
    #
    # **Note.** Because this is a GSS, we might already know the children of u
    # which is the node corresponding to top of s. Hence, we can start these
    # threads. However, what if new children are added? This is addressed by
    # maintaining P which maintains (u, k) for which pop has been executed.
    # See register_return
    def fn_return(self, u, j): # pop
        if u != self.u0:
            self.gss.add_parsed_index(u.label, j)
            for v in u.children:
                self.add_thread(u.L, v, j)
        return u

def __init__(self, input_str):
        self.threads = []
        self.gss = GSS()
        self.I = input_str
        self.m = len(self.I) # |I| + 1
        self.u1 = self.gss.get('L0', 0)
        self.u0 = self.gss.get('$', self.m)
        self.u1.children.append(self.u0)

self.U = []
        for j in range(self.m): # 0<=j<=m
            self.U.append([]) # U_j = empty

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

RR_GRAMMAR2 = {
    '<start>': [['<A>']],
    '<A>': [['a','b', '<A>'], []],
}
mystring2 = 'ababababab'
res = compile_grammar(RR_GRAMMAR2, '<start>')
exec(res)
g = GLLStructuredStack(mystring2+'$')
assert parse_string(g) == 'success'

RR_GRAMMAR3 = {
    '<start>': [['c', '<A>']],
    '<A>': [['a', 'b', '<A>'], []],
}
mystring3 = 'cababababab'

res = compile_grammar(RR_GRAMMAR3, '<start>')
exec(res)
g = GLLStructuredStack(mystring3+'$')
assert parse_string(g) == 'success'

RR_GRAMMAR4 = {
    '<start>': [['<A>', 'c']],
    '<A>': [['a', 'b', '<A>'], []],
}
mystring4 = 'ababababc'

res = compile_grammar(RR_GRAMMAR4, '<start>')
exec(res)
g = GLLStructuredStack(mystring4+'$')
assert parse_string(g) == 'success'

RR_GRAMMAR5 = {
'<start>': [['<A>']],
'<A>': [['a', 'b', '<B>'], []],
'<B>': [['<A>']],
}
mystring5 = 'abababab'

res = compile_grammar(RR_GRAMMAR5, '<start>')
exec(res)
g = GLLStructuredStack(mystring5+'$')
assert parse_string(g) == 'success'

RR_GRAMMAR6 = {
'<start>': [['<A>']],
'<A>': [['a', '<B>'], []],
'<B>': [['b', '<A>']],
}
mystring6 = 'abababab'

res = compile_grammar(RR_GRAMMAR6, '<start>')
exec(res)
g = GLLStructuredStack(mystring6+'$')
assert parse_string(g) == 'success'

RR_GRAMMAR7 = {
'<start>': [['<A>']],
'<A>': [['a', '<A>'], ['a']],
}
mystring7 = 'aaaaaaaa'

res = compile_grammar(RR_GRAMMAR7, '<start>')
exec(res)
g = GLLStructuredStack(mystring7+'$')
assert parse_string(g) == 'success'

RR_GRAMMAR8 = {
'<start>': [['<A>']],
'<A>': [['a', '<A>'], ['a']]
}
mystring8 = 'aa'

res = compile_grammar(RR_GRAMMAR8, '<start>')
exec(res)
g = GLLStructuredStack(mystring8+'$')
assert parse_string(g) == 'success'

Artifacts

The runnable Python source for this notebook is available here.

Contents

Prerequisites

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

The GSS container

The GLL GSS

The GSS GLL Compiler

Example

Usage

Artifacts