Implementation of the GLL parsing algorithm [Scott and Johnstone 2010,2013,2016] with the grammar as an explicit parameter.

Function parse receives a Grammar as input together with a list of tokens (the input string).

The type of token is chosen arbitrarily, but the type should be Parseable and Orderable. To be Parseable a type must have two distinct values, eos (end-of-string) and eps (epsilon). The user must ensure that these two values will never occur as part of the input string.

GLL Parsing

Recursive Descent

GLL parsing is a generalisation of recursive descent parsing (RD parsing). A RD parser (RDP), for some grammar G , consists of a set of parse functions f_X, one for every nonterminal X, and a main function which calls f_S, where S is the start symbol. The parse function f_X take an integer l as an argument and produces an integer r, indicating that nonterminal X derives s_l_r, where s_i_j is the substring of the input string s ranging from i to j. We call l and r the right- and left-extent, respectively.

The parse function f_X has a branch for every production X ::= s_1 ... s_k in G, guarded by a look-ahead test, and every branch has k code fragments, one for every symbol s_i, with 1 <= i <= k. A RDP matches grammar positions, represented by slots of the form X ::= a . b, with (input) string positions. The dot in a slot tells us how much of the production's symbols have been matched (the symbols before the dot) and which symbols still need to be matched (the symbols after the dot). The symbol immediately after the dot is the next symbol to be match and is either:

• A terminal token, matched directly with the token at the current string position.
• A nonterminal Y, for which f_Y is called. In the case of LL(1) deterministic parsing, only one (or none) of the productions of Y passes the lookahead-test, say "Y ::= c", and its branch will be executed: the next grammar position is "Y ::= .c".
• No further symbol, represented by "X ::= d." (all symbols have been processed). In this case a return call is made to the caller of f_X (relying on a function call stack).

Handling function/return calls

GLL handles its own function calls and return calls, instead of relying on an underlying mechanism. This form of low-level control allows GLL to avoid much duplicate work, not only for function calls (as in classical memoisation) but also for return calls. The underlying observation is that both return calls and function calls continue matching grammar slots. In non-deterministic RDP, every function call leads to a slot of the form "X ::= . a" being processed, while every return call leads to a slot of the form "X ::= aY.b" being processed, where Y is some nonterminal. GLL uses descriptors, containing a slot of one of these forms, to uniquely identify the computation that processes the slot. The descriptor therefore also needs to contain the initial values of the local variables used in that computation.

A generated GLL parser (Scott and Johnstone 2013) has a code fragment for every nonterminal X (labelled L_X) and slot (labelled "L_{X ::= a.b}"). This Haskell implementation abstracts over the grammar and has a function for executing L_X, for a given X, and a function for executing "L_{X ::= a.b}", for a given "X ::= a.b".

Generalisation

GLL parsing generalises RD parsing by allowing non-determinism: when processing "X ::= a.Yb", all productions of Y, that pass the lookahead test, are considered. A slot is considered, by adding a descriptor for it to the worklist R. Duplicates in the worklist are avoided by maintaining a separate descriptor-set U containing all descriptors added to the worklist before.

The result of a parse function f_X is no longer a single right extent r. Instead, it is a list of right extents rs, indicating that X derives s_l_r for all r in rs and integer input l (left extent). Every discovered right extent is stored in the pop-set P.

When a descriptors for a function call is a duplicate, it is not added to the worklist, but we have to make sure that the corresponding return call is still made. Note that a function call to f_Y, with the same parameters, can be made from multiple right-hand side occurrences of Y. It might be the case that:

• The original descriptors is still being processed. Once finished, a descriptor must be added for all return calls corresponding to function calls that lead to duplicates of this descriptor. GLL uses a Graph-Structured Stack (GSS) to efficiently maintain multiple such continuations.
• The original descriptors has already been processed. In this case, one or more right extents rs are stored in P for the corresponding function call. A descriptor for the return call must be added for all r in rs. The descriptor for the return call must be added to the GSS in this case as well, as other right extents might be found in the future.

Usage

This module provides generalised parsing to other applications that work with BNF grammars.

The user should provide a Grammar and an input string as arguments to top-level functions parse or parseWithOptions.

Example

This example shows simple character level parsing. First we must make Token and instance of Parseable.

instance Parseable Char where
    eos = '$'
    eps = #

This instance mandates that '$' and # are 'reserved tokens' and not part of the input string. This instance is available as an import: GLL.Parseable.Char.

GLL.Parser exports smart constructors for constructing Grammars.

grammar1 = (start "X" , [prod "X" [nterm "A", nterm "A"]
                      , prod "A" [term 'a']
                      , prod "A" [term 'a', term 'a']
                 ] )

fail1       = "a"
success1    = "aa"
success2    = "aaa"
fail2       = "aaaaa"

Note that there are two possible derivations of success2.

The parser can be accessed through parse or parseWithOptions.

run1 = parse grammar1 success1
run2 = parseWithOptions [fullSPPF, strictBinarisation] grammar1 success2

The options fullSPPF, allNodes, packedNodesOnly, decide whether all SPPF nodes and edges are inserted into the resulting value of the SPPF type. Packed nodes are enough to fully represent an SPPF, as the parent and children of a packed node can be computed from the packed nodes' information. For efficiency the SPPF is not strictly binarised by default: a packed node might have a symbol node as a left child. In a strictly binarised SPPF a packed node has an intermediate node as a left child, or no left child at all. To create a strictly binarised SPPF (necessary for GLL.Combinators) the option strictBinarisation is available.

Combinator interface

Module GLL.Combinators.Interface provides a combinator interface to access GLL.Parser. Applicative-like combinators are used to specify a Grammar and call parse. The SPPF is then used to produce semantic results.