This repository contains the following runtime1 parser-generator implementations:
| Name | Parser Algorithm | Language | Notes |
|---|---|---|---|
| pygll | GLL-CRF-BSR2 | Python (>= 3.7) | 100% complete but with minimal tests |
| hsgll | GLL-CRF-BSR | Haskell | Approx. 40% complete |
The parser implementations are contained in subfolders with their respective names.
Footnotes
-
As opposed to the more commonly seen compile-time parser generators (which typically consume a grammar input file and generate grammar-specific parser code as output), runtime parser generators consume a grammar data structure at runtime and generate a parser object. ↩
-
While this parsing algorithm is called clustered nonterminal parsing (CNP) by its creators, I find the name GLL-CRF-BSR (i.e., a generalized, left-to-right, leftmost derivation (GLL) parser which stores its intermediate state in a call return forest (CRF) and emits a binary subtree representation (BSR) encoding of its parse forest) as opposed to plain ol' GLL (i.e., GLL-GSS-SPPF, a GLL parser which stores its intermediate state in a graph-structured stack (GSS) and emits a shared packed parse forest (SPPF) encoding of its parse forest) provides a better intuition about what the algorithm does. For more details, see their paper: Elizabeth Scott, Adrian Johnstone, L. Thomas van Binsbergen: Derivation representation using binary subtree sets. Sci. Comput. Program. 175: 63-84 (2019). ↩