Parse chart in Python
Table indexed by input span that stores recognized partial parses in chart parsers.
- File
parse_chart.py, 137 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/parse-chart/. The authors are listed in prov/37Y8RW.jsonl.
"""A parse chart of dotted edges, and a general chart parser that uses it.
A grammar is a list of productions (A, rhs) with rhs a tuple of symbols. The
nonterminals are the left sides; every other symbol is a terminal. An edge
(i, j, (p, d)) says that the first d symbols of production p derive
tokens[i:j]. Any context-free grammar is allowed, with empty productions,
unit cycles, left recursion and ambiguity.
"""
Production = tuple[str, tuple[str, ...]]
Tree = tuple[str, list] | str
Edge = tuple[int, int, tuple[int, int]]
class ParseError(Exception):
"""The input is not a sentence; position is len(tokens) or the first unusable token."""
def __init__(self, position: int, message: str) -> None:
super().__init__(f"{message} at token {position}")
self.position = position
class Chart:
"""Edges indexed by span, with the two indexes that the fundamental rule needs."""
def __init__(self, prods: list[Production], n: int) -> None:
self.prods = prods
self.n = n
self.back: dict[Edge, tuple | None] = {} # edge -> how it was first built
self.active = [dict() for _ in range(n + 1)] # j -> X -> [(i, item)] waiting for X at j
self.passive = [dict() for _ in range(n + 1)] # i -> A -> [(j, item)] complete A from i
def add(self, i: int, j: int, item: tuple[int, int], back) -> bool:
"""Insert an edge; return False if it was already there."""
key = (i, j, item)
if key in self.back: # @line L1
return False
self.back[key] = back # @line L2
p, d = item
lhs, rhs = self.prods[p]
if d < len(rhs):
self.active[j].setdefault(rhs[d], []).append((i, item)) # @line L3
else:
self.passive[i].setdefault(lhs, []).append((j, item)) # @line L4
return True
def __contains__(self, edge: Edge) -> bool:
return edge in self.back
def waiting(self, j: int, x: str) -> list:
"""The active edges (i, item) that end at j and need x next."""
return self.active[j].get(x, [])
def complete(self, i: int, a: str) -> list:
"""The complete edges (j, item) for the nonterminal a that start at i."""
return self.passive[i].get(a, [])
def __len__(self) -> int:
return len(self.back)
def fill_chart(productions: list[Production], start: str, tokens: list[str]) -> Chart:
"""Run the chart parser; return the chart."""
nts = {a for a, _ in productions}
by_lhs: dict[str, list[int]] = {}
for p, (a, _) in enumerate(productions):
by_lhs.setdefault(a, []).append(p)
n = len(tokens)
chart = Chart(productions, n)
agenda: list[Edge] = []
def push(i, j, item, back):
if chart.add(i, j, item, back):
agenda.append((i, j, item))
for p in by_lhs.get(start, []): # @line L5
push(0, 0, (p, 0), None)
while agenda: # @line L6
i, j, item = agenda.pop()
p, d = item
lhs, rhs = productions[p]
if d < len(rhs):
x = rhs[d]
if x in nts:
for q in by_lhs[x]: # @line L7
push(j, j, (q, 0), None)
for k, it in list(chart.complete(j, x)): # @line L8
push(i, k, (p, d + 1), ((i, j, item), (j, k, it)))
elif j < n and tokens[j] == x: # @line L9
push(i, j + 1, (p, d + 1), ((i, j, item), x))
else:
for h, it in list(chart.waiting(i, lhs)): # @line L10
push(h, j, (it[0], it[1] + 1), ((h, i, it), (i, j, item)))
return chart
def _children(chart: Chart, edge: Edge) -> list:
kids = []
back = chart.back[edge]
while back is not None:
prev, child = back
kids.append(child)
back = chart.back[prev]
kids.reverse()
return kids
def chart_tree(chart: Chart, edge: Edge) -> Tree:
"""Read one parse tree off the backpointers of a complete edge, without recursion."""
built: dict[Edge, Tree] = {}
todo = [(edge, False)]
while todo:
e, ready = todo.pop()
if e in built:
continue
kids = _children(chart, e)
if ready:
lhs = chart.prods[e[2][0]][0]
built[e] = (lhs, [k if isinstance(k, str) else built[k] for k in kids])
continue
todo.append((e, True))
todo.extend((k, False) for k in kids if not isinstance(k, str) and k not in built)
return built[edge]
def chart_parse(productions: list[Production], start: str, tokens: list[str]) -> Tree:
"""Return a parse tree of tokens, or raise ParseError."""
chart = fill_chart(productions, start, tokens)
n = len(tokens)
for j, item in chart.complete(0, start): # @line L11
if j == n:
return chart_tree(chart, (0, n, item)) # @line L12
last = max((j for (_, j, _) in chart.back), default=0)
raise ParseError(min(last, n), "no parse")
test_parse_chart.py 189 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/parse-chart/. The authors are listed in prov/37Y8RW.jsonl.
import itertools
import random
import pytest
from parse_chart import ParseError, chart_parse, fill_chart
EXPR = [
("E", ("E", "+", "T")),
("E", ("T",)),
("T", ("T", "*", "F")),
("T", ("F",)),
("F", ("(", "E", ")")),
("F", ("id",)),
]
def lang_upto(prods, max_len):
"""Oracle: for each nonterminal, the strings of length <= max_len that it derives."""
nts = {a for a, _ in prods}
lang = {a: set() for a in nts}
def of(x):
return lang[x] if x in nts else {(x,)}
changed = True
while changed:
changed = False
for a, rhs in prods:
cur = {()}
for x in rhs:
cur = {u + v for u in cur for v in of(x) if len(u) + len(v) <= max_len}
if not cur:
break
if not cur <= lang[a]:
lang[a] |= cur
changed = True
return lang
def prefix_lang(prods, max_len):
"""Oracle: for each nonterminal, the prefixes of length <= max_len of the strings it derives.
Every nonterminal must be productive, so that each symbol after a prefix can be completed.
"""
nts = {a for a, _ in prods}
full = lang_upto(prods, max_len)
pre = {a: set() for a in nts}
def full_of(x):
return full[x] if x in nts else {(x,)}
def pre_of(x):
return pre[x] if x in nts else {(), (x,)}
changed = True
while changed:
changed = False
for a, rhs in prods:
new = {()}
cur = {()}
for x in rhs:
new |= {u + v for u in cur for v in pre_of(x) if len(u) + len(v) <= max_len}
cur = {u + v for u in cur for v in full_of(x) if len(u) + len(v) <= max_len}
if not new <= pre[a]:
pre[a] |= new
changed = True
return pre
def productive_only(prods):
"""Remove the productions that use a nonterminal deriving no terminal string."""
nts = {a for a, _ in prods}
good = set()
changed = True
while changed:
changed = False
for a, rhs in prods:
if a not in good and all(x in good or x not in nts for x in rhs):
good.add(a)
changed = True
return [(a, r) for a, r in prods if a in good and all(x in good or x not in nts for x in r)]
def check_tree(prods, start, tree, tokens):
"""Iteratively check that tree is a parse tree of tokens with root start."""
nts = {a for a, _ in prods}
rules = set(prods)
assert isinstance(tree, tuple) and tree[0] == start
leaves = []
todo = [tree]
while todo:
t = todo.pop()
if isinstance(t, str):
assert t not in nts
leaves.append(t)
continue
a, kids = t
labels = tuple(k if isinstance(k, str) else k[0] for k in kids)
assert (a, labels) in rules
todo.extend(reversed(kids))
assert leaves == list(tokens)
def random_grammar(rng, n_nt, terms, eps_prob=0.2):
names = ["S", "A", "B", "C"][:n_nt]
prods = []
for a in names:
for _ in range(rng.randint(1, 3)):
k = 0 if rng.random() < eps_prob else rng.randint(1, 3)
prods.append((a, tuple(rng.choice(names + terms) for _ in range(k))))
return prods
def derives(lang, nts, symbols, max_len):
"""The strings of length <= max_len derived by a string of symbols."""
cur = {()}
for x in symbols:
opts = lang[x] if x in nts else {(x,)}
cur = {u + v for u in cur for v in opts if len(u) + len(v) <= max_len}
return cur
def test_expression_chart():
w = "id + id * id".split()
chart = fill_chart(EXPR, "E", w)
tree = chart_parse(EXPR, "E", w)
check_tree(EXPR, "E", tree, w)
assert [j for j, _ in chart.complete(0, "E")] == [1, 3, 5] or sorted(j for j, _ in chart.complete(0, "E")) == [1, 3, 5]
assert sorted(j for j, _ in chart.complete(2, "T")) == [3, 5]
with pytest.raises(ParseError) as e:
chart_parse(EXPR, "E", ["id", "+", ")", "id"])
assert e.value.position == 2
with pytest.raises(ParseError) as e:
chart_parse(EXPR, "E", [])
assert e.value.position == 0
def test_empty_cycles_and_ambiguity():
g = [("S", ("A", "S", "b")), ("S", ()), ("A", ("a",)), ("A", ())]
for w in [[], ["b"], ["a", "b", "b"], ["a", "a", "b", "b"]]:
check_tree(g, "S", chart_parse(g, "S", w), w)
cyc = [("S", ("S",)), ("S", ("S", "S")), ("S", ()), ("S", ("a",))]
for m in range(6):
w = ["a"] * m
check_tree(cyc, "S", chart_parse(cyc, "S", w), w)
def test_long_input():
g = [("L", ("L", ",", "x")), ("L", ("x",))]
m = 20000
w = ["x"] + [",", "x"] * m
tree = chart_parse(g, "L", w)
check_tree(g, "L", tree, w)
assert len(fill_chart(g, "L", w)) < 10 * len(w)
right = [("R", ("x", ",", "R")), ("R", ("x",))]
w = ["x"] + [",", "x"] * 500 # right recursion fills a quadratic chart
check_tree(right, "R", chart_parse(right, "R", w), w)
def test_random_against_brute_force():
rng = random.Random(20261106)
checked = 0
for _ in range(1500):
terms = ["a", "b"][: rng.randint(1, 2)]
prods = productive_only(random_grammar(rng, rng.randint(1, 3), terms))
nts = {a for a, _ in prods}
if "S" not in nts:
continue
lang = lang_upto(prods, 5)
pre = prefix_lang(prods, 6)["S"]
for m in range(6):
for w in itertools.product(terms, repeat=m):
checked += 1
chart = fill_chart(prods, "S", list(w))
for (i, j, (p, d)) in chart.back:
assert w[i:j] in derives(lang, nts, prods[p][1][:d], 5)
try:
tree = chart_parse(prods, "S", list(w))
except ParseError as e:
assert w not in lang["S"]
i = e.position
assert w[:i] in pre and (i == len(w) or w[: i + 1] not in pre)
continue
assert w in lang["S"]
check_tree(prods, "S", tree, w)
assert checked >= 20000
What the next level needs
- the tests did not run in this build