GLL parsing in Python
Generalized top-down parsing with descriptors and a graph-structured stack that handles all context-free grammars, due to Scott and Johnstone.
- File
gll_parsing.py, 104 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/gll-parsing/. The authors are listed in prov/0BHT8C.jsonl.
"""A GLL recognizer: generalized top-down parsing with descriptors and a graph-structured stack.
gll(productions, tokens) decides whether the token sequence belongs to the
language of the grammar, for any context-free grammar, including left-recursive,
ambiguous and cyclic ones and grammars with epsilon-productions.
A production is (lhs, rhs) with rhs a tuple of symbols. The left sides are the
nonterminals; every other symbol is a terminal. The first production's left
side is the start symbol.
A grammar slot is (p, d): production p with the dot before rhs[d]. A GSS node is
(p, d, i): the return slot (p, d), right after a nonterminal, and the input
position i at which that nonterminal was called. The root node is ROOT. A
descriptor (p, d, u, i) says: continue at slot (p, d) with stack top u at input
position i.
"""
from collections.abc import Sequence
from dataclasses import dataclass, field
ROOT = ("$root",)
@dataclass
class GLLResult:
accepted: bool
ends: set[int] = field(default_factory=set) # positions i such that S derives tokens[:i]
spans: set[tuple[str, int, int]] = field(default_factory=set) # (A, i, j): A called at i derives tokens[i:j]
descriptors: int = 0 # the number of distinct descriptors processed
gss_nodes: int = 0
gss_edges: int = 0
def gll(productions: Sequence[tuple[str, Sequence[str]]], tokens: Sequence[str]) -> GLLResult:
"""Recognize tokens with the grammar; also report the derived spans that the search found."""
prods = [(a, tuple(rhs)) for a, rhs in productions]
nts = {a for a, _ in prods}
by_lhs: dict[str, list[int]] = {}
for p, (a, _) in enumerate(prods):
by_lhs.setdefault(a, []).append(p)
start = prods[0][0]
n = len(tokens)
seen: set[tuple] = set() # U: every descriptor ever added
todo: list[tuple] = [] # R: descriptors still to process
edges: dict[tuple, set[tuple]] = {} # GSS node -> the nodes below it
popped: dict[tuple, set[int]] = {} # P: GSS node -> positions at which it was popped
result = GLLResult(False)
def add(p: int, d: int, u: tuple, i: int) -> None:
if (p, d, u, i) not in seen: # @line L12
seen.add((p, d, u, i))
todo.append((p, d, u, i))
def create(p: int, d: int, u: tuple, i: int) -> tuple:
v = (p, d, i) # @line L7
below = edges.setdefault(v, set())
if u not in below: # @line L8
below.add(u)
for k in list(popped.get(v, ())):
add(p, d, u, k)
return v # @line L9
def pop(u: tuple, i: int) -> None:
if u == ROOT: # @line L10
result.ends.add(i)
return
ks = popped.setdefault(u, set())
if i not in ks: # @line L11
ks.add(i)
p, d, _ = u
for v in list(edges[u]):
add(p, d, v, i)
for p in by_lhs[start]:
add(p, 0, ROOT, 0) # @line L1
while todo:
p, d, u, i = todo.pop() # @line L2
rhs = prods[p][1]
while d < len(rhs) and rhs[d] not in nts: # @line L3
if i < n and tokens[i] == rhs[d]:
d += 1
i += 1
else:
break
else:
if d < len(rhs):
v = create(p, d + 1, u, i) # @line L4
for q in by_lhs[rhs[d]]:
add(q, 0, v, i)
else:
pop(u, i) # @line L5
result.accepted = n in result.ends # @line L6
for (p, d, i), ks in popped.items():
a = prods[p][1][d - 1]
for j in ks:
result.spans.add((a, i, j))
result.descriptors = len(seen)
result.gss_nodes = len(edges)
result.gss_edges = sum(len(s) for s in edges.values())
return result
test_gll_parsing.py 192 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/gll-parsing/. The authors are listed in prov/0BHT8C.jsonl.
import itertools
import random
from gll_parsing import gll
# ---------------------------------------------------------------- oracles
def derived_spans(prods, w):
"""D[A] = the set of (i, j) with A =>* w[i:j], by a fixed point over all substrings."""
nts = {a for a, _ in prods}
n = len(w)
d = {a: set() for a in nts}
def seq_spans(rhs, i):
"""The ends j such that rhs =>* w[i:j], with the current D."""
cur = {i}
for x in rhs:
nxt = set()
for k in cur:
if x in nts:
nxt |= {j for (s, j) in d[x] if s == k}
elif k < n and w[k] == x:
nxt.add(k + 1)
cur = nxt
if not cur:
break
return cur
changed = True
while changed:
changed = False
for a, rhs in prods:
for i in range(n + 1):
for j in seq_spans(rhs, i):
if (i, j) not in d[a]:
d[a].add((i, j))
changed = True
return d, seq_spans
def called_pairs(prods, w):
"""The pairs (A, i) such that a top-down parser reaches a call of A at position i."""
nts = {a for a, _ in prods}
d, seq_spans = derived_spans(prods, w)
called = {(prods[0][0], 0)}
changed = True
while changed:
changed = False
for (b, k) in list(called):
for a, rhs in prods:
if a != b:
continue
for m, x in enumerate(rhs):
if x in nts:
for i in seq_spans(rhs[:m], k):
if (x, i) not in called:
called.add((x, i))
changed = True
return called, d, seq_spans
def random_grammar(rng):
names = ["S", "A", "B"][: rng.randint(1, 3)]
prods = []
for a in names:
for _ in range(rng.randint(1, 3)):
if rng.random() < 0.25:
rhs = ()
else:
rhs = tuple(rng.choice(names + ["a", "b"]) for _ in range(rng.randint(1, 3)))
if (a, rhs) not in prods:
prods.append((a, rhs))
return prods
def oracle_gss_nodes(g, w):
"""The GSS nodes (p, m + 1, i) a correct GLL run must create: production p of a called
nonterminal B at k, rhs[m] a nonterminal, and rhs[:m] deriving w[k:i]."""
nts = {a for a, _ in g}
called, d, seq_spans = called_pairs(g, w)
out = set()
for (b, k) in called:
for p, (a, rhs) in enumerate(g):
if a != b:
continue
for m, x in enumerate(rhs):
if x in nts:
for i in seq_spans(rhs[:m], k):
out.add((p, m + 1, i))
return out, d
def check_against_oracle(g, w):
res = gll(g, w)
nodes, d = oracle_gss_nodes(g, w)
start = g[0][0]
assert res.ends == {j for (i, j) in d[start] if i == 0}
assert res.accepted == ((0, len(w)) in d[start])
assert res.gss_nodes == len(nodes)
for (a, i, j) in res.spans: # sound
assert (i, j) in d[a]
for (p, m, i) in nodes: # complete for every call the search made
a = g[p][1][m - 1]
assert {(a, i, j) for (s, j) in d[a] if s == i} <= res.spans
return res
# ---------------------------------------------------------------- tests
EXPR = [("E", ("E", "+", "E")), ("E", ("n",))]
def test_worked_example_ambiguous_left_recursive():
w = ["n", "+", "n", "+", "n"]
res = gll(EXPR, w)
assert res.accepted
assert res.ends == {1, 3, 5}
assert res.gss_nodes == 5
assert {(a, i, j) for (a, i, j) in res.spans} == {
("E", 0, 1), ("E", 0, 3), ("E", 0, 5), ("E", 2, 3), ("E", 2, 5), ("E", 4, 5)}
assert not gll(EXPR, ["n", "+"]).accepted
assert not gll(EXPR, ["+", "n"]).accepted
def test_empty_input_and_epsilon():
assert gll([("S", ())], []).accepted
assert not gll([("S", ("a",))], []).accepted
assert gll([("S", ("A", "A", "a")), ("A", ()), ("A", ("a",))], ["a"]).accepted
assert not gll([("S", ("a",))], ["a", "a"]).accepted
def test_cyclic_and_hidden_left_recursion_terminate():
g = [("S", ("S",)), ("S", ("S", "S")), ("S", ("a",)), ("S", ())]
for m in range(6):
assert gll(g, ["a"] * m).accepted
assert not gll(g, ["b"]).accepted
g = [("S", ("A", "S", "b")), ("S", ("a",)), ("A", ())]
assert gll(g, ["a", "b", "b"]).accepted
assert not gll(g, ["b"]).accepted
def test_long_inputs_have_no_recursion_limit():
n = 20000
w = ["n"] + ["+", "n"] * (n // 2)
left = [("E", ("E", "+", "n")), ("E", ("n",))]
res = gll(left, w)
assert res.accepted and res.descriptors <= 2 * len(w)
right = [("S", ("a", "S")), ("S", ("b",))]
res = gll(right, ["a"] * n + ["b"])
assert res.accepted and res.descriptors <= 4 * (n + 1)
assert not gll(right, ["a"] * n).accepted
def test_matches_language_on_random_grammars_and_inputs():
rng = random.Random(23)
grammars = 0
flags = {"eps": 0, "left": 0}
for _ in range(600):
g = random_grammar(rng)
for m in range(0, 7):
for w in itertools.product("ab", repeat=m):
check_against_oracle(g, list(w))
grammars += 1
flags["eps"] += any(not r for _, r in g)
flags["left"] += any(r and r[0] == a for a, r in g)
assert grammars >= 500 and flags["eps"] >= 100 and flags["left"] >= 100
def test_random_longer_inputs():
rng = random.Random(41)
for _ in range(300):
g = random_grammar(rng)
w = [rng.choice("ab") for _ in range(rng.randint(5, 8))]
check_against_oracle(g, w)
def test_size_bounds():
"""Descriptors are at most s^2 (n+1)^2 and GSS nodes at most s (n+1), s the number of slots."""
rng = random.Random(5)
for _ in range(300):
g = random_grammar(rng)
s = sum(len(r) + 1 for _, r in g)
w = [rng.choice("ab") for _ in range(rng.randint(0, 8))]
res = gll(g, w)
n = len(w)
assert res.gss_nodes <= s * (n + 1)
assert res.descriptors <= s * (s * (n + 1) + 1) * (n + 1)
assert res.gss_edges <= res.gss_nodes * (s * (n + 1) + 1)
What the next level needs
- the tests did not run in this build