Shift-reduce parsing in Python
Bottom-up parsing using a stack, shifting input and reducing handles to nonterminals.
- File
shift_reduce_parsing.py, 200 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/shift-reduce-parsing/. The authors are listed in prov/PZXCZZ.jsonl.
"""Shift-reduce parsing: a generic driver and an exact decision procedure.
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. A tree is
(A, children) where each child is a tree or a terminal.
`shift_reduce(tokens, decide)` is the driver of the page. It knows nothing
about how to choose a move: `decide(symbols, pos)` returns ("shift",),
("reduce", k) for production k, ("accept",) or ("error",).
`ExactDecider` is a decision procedure that works for every context-free
grammar, including ambiguous ones, epsilon-productions and cycles. It sees the
whole input. It calls a configuration good if some sequence of moves from it
ends in accept, and it tests this with the item chains of the stack:
the stack X1...Xm is good at position pos iff it is beta_1 ... beta_m for a
chain of items [S' -> beta_1 . A_2 delta_1], [A_2 -> beta_2 . A_3 delta_2], ...,
[A_m -> beta_m . delta_m] with delta_m delta_(m-1) ... delta_1 =>* w[pos:].
It shifts when shifting keeps the configuration good, and otherwise takes the
first move of a shortest sequence of good reductions after which a shift (or
accept) is good. Deterministic methods such as LR(1) replace it with a table.
"""
from collections import deque
from typing import Callable, Sequence
Production = tuple[str, tuple[str, ...]]
AUG = -1 # the augmented production S' -> S
class ParseError(ValueError):
"""The input is not in the language of the grammar."""
def shift_reduce(
tokens: Sequence[str],
prods: Sequence[Production],
decide: Callable[[list[str], int], tuple],
trace: list | None = None,
):
"""Run the shift-reduce driver. Returns (tree, reductions), where
reductions is the list of production indices in the order they were used."""
stack: list = [] # @line L1: stack of (symbol, tree) pairs; pos = 0
pos = 0
reductions: list[int] = []
while True: # @line L2
symbols = [s for s, _ in stack]
act = decide(symbols, pos) # @line L3
if trace is not None:
trace.append((" ".join(symbols), " ".join(tokens[pos:]), act))
if act[0] == "shift": # @line L4
stack.append((tokens[pos], tokens[pos])) # @line L5
pos += 1
elif act[0] == "reduce": # @line L6
a, rhs = prods[act[1]]
k = len(rhs)
popped = stack[len(stack) - k:] if k else [] # @line L7
assert [s for s, _ in popped] == list(rhs), "decide chose a reduction that is not on top"
del stack[len(stack) - k:]
stack.append((a, (a, tuple(t for _, t in popped)))) # @line L8
reductions.append(act[1])
elif act[0] == "accept": # @line L9
return stack[0][1], reductions
else: # @line L10
raise ParseError(f"no move at token {pos}")
def _spans(prods: Sequence[Production], w: Sequence[str]) -> set:
"""The set of (A, i, j) with A =>* w[i:j], by a least fixpoint."""
nts = {a for a, _ in prods}
n = len(w)
known: set = set()
changed = True
while changed:
changed = False
for a, rhs in prods:
for i in range(n + 1):
ends = {i}
for x in rhs:
nxt = set()
for p in ends:
if x in nts:
nxt.update(q for q in range(p, n + 1) if (x, p, q) in known)
elif p < n and w[p] == x:
nxt.add(p + 1)
ends = nxt
for j in ends:
if (a, i, j) not in known:
known.add((a, i, j))
changed = True
return known
class ExactDecider:
"""The exact decision procedure for one input w (see the module docstring)."""
def __init__(self, prods: Sequence[Production], start: str, tokens: Sequence[str]) -> None:
self.prods = [(a, tuple(r)) for a, r in prods]
self.start = start
self.nts = {a for a, _ in self.prods}
self.w = list(tokens)
self.n = len(self.w)
self.known = _spans(self.prods, self.w)
self.by_lhs: dict[str, list[int]] = {a: [] for a in self.nts}
for k, (a, _) in enumerate(self.prods):
self.by_lhs[a].append(k)
self._ends: dict = {}
self._sets: dict = {(): self._closure({(AUG, 0, self.n)})}
def rhs(self, k: int) -> tuple[str, ...]:
return (self.start,) if k == AUG else self.prods[k][1]
def ends(self, k: int, d: int, i: int) -> frozenset:
"""All j with rhs(k)[d:] =>* w[i:j]."""
key = (k, d, i)
if key not in self._ends:
cur = {i}
for x in self.rhs(k)[d:]:
nxt = set()
for p in cur:
if x in self.nts:
nxt.update(q for q in range(p, self.n + 1) if (x, p, q) in self.known)
elif p < self.n and self.w[p] == x:
nxt.add(p + 1)
cur = nxt
self._ends[key] = frozenset(cur)
return self._ends[key]
def _closure(self, items: set) -> frozenset:
todo = list(items)
out = set(items)
while todo:
k, d, e = todo.pop()
r = self.rhs(k)
if d < len(r) and r[d] in self.nts:
for e2 in range(e + 1):
if e in self.ends(k, d + 1, e2):
for kb in self.by_lhs[r[d]]:
it = (kb, 0, e2)
if it not in out:
out.add(it)
todo.append(it)
return frozenset(out)
def items(self, symbols: tuple) -> frozenset:
"""The (item, end) pairs of all item chains that spell the stack.
Built from the longest cached prefix, one symbol at a time."""
m = len(symbols)
while symbols[:m] not in self._sets:
m -= 1
for j in range(m + 1, len(symbols) + 1):
x = symbols[j - 1]
below = self._sets[symbols[: j - 1]]
moved = {(k, d + 1, e) for k, d, e in below if d < len(self.rhs(k)) and self.rhs(k)[d] == x}
self._sets[symbols[:j]] = self._closure(moved)
return self._sets[symbols]
def good(self, symbols: tuple, pos: int) -> bool:
return any(e in self.ends(k, d, pos) for k, d, e in self.items(symbols))
def _target(self, symbols: tuple, pos: int) -> bool:
if pos == self.n:
return symbols == (self.start,)
return self.good(symbols + (self.w[pos],), pos + 1)
def _reductions(self, symbols: tuple):
for k, (a, r) in enumerate(self.prods):
if len(r) <= len(symbols) and symbols[len(symbols) - len(r):] == r:
yield k, symbols[: len(symbols) - len(r)] + (a,)
def __call__(self, stack_symbols: list[str], pos: int) -> tuple:
cur = tuple(stack_symbols)
if not self.good(cur, pos):
return ("error",)
if pos == self.n and cur == (self.start,):
return ("accept",)
if pos < self.n and self._target(cur, pos):
return ("shift",)
# Breadth-first search over good reductions for the nearest target.
first: dict = {cur: None}
queue = deque([cur])
while queue:
s = queue.popleft()
for k, t in self._reductions(s):
if t in first or not self.good(t, pos):
continue
first[t] = k if first[s] is None else first[s]
if self._target(t, pos):
return ("reduce", first[t])
queue.append(t)
return ("error",) # unreachable when the configuration is good
def parse(prods: Sequence[Production], start: str, tokens: Sequence[str], trace: list | None = None):
"""Parse tokens with the exact decider; returns (tree, reductions)."""
if start not in {a for a, _ in prods}:
raise ValueError("the start symbol has no production")
return shift_reduce(list(tokens), prods, ExactDecider(prods, start, tokens), trace)
test_shift_reduce_parsing.py 165 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/shift-reduce-parsing/. The authors are listed in prov/PZXCZZ.jsonl.
import itertools
import random
import pytest
from shift_reduce_parsing import ParseError, parse, shift_reduce
EXPR = [
("E", ("E", "+", "T")), ("E", ("T",)), ("T", ("T", "*", "F")), ("T", ("F",)),
("F", ("(", "E", ")")), ("F", ("id",)),
]
def derives(prods, start, w):
"""Independent oracle: does start =>* w? Least fixpoint over spans."""
nts = {a for a, _ in prods}
n = len(w)
known = set()
def ok(rhs, i, j):
ends = {i}
for x in rhs:
nxt = set()
for p in ends:
if x in nts:
nxt |= {q for q in range(p, j + 1) if (x, p, q) in known}
elif p < j and w[p] == x:
nxt.add(p + 1)
ends = nxt
return j in ends
changed = True
while changed:
changed = False
for a, rhs in prods:
for i in range(n + 1):
for j in range(i, n + 1):
if (a, i, j) not in known and ok(rhs, i, j):
known.add((a, i, j))
changed = True
return (start, 0, n) in known
def tree_ok(tree, prods, w):
pset = {(a, tuple(r)) for a, r in prods}
leaves, stack = [], [tree]
while stack:
t = stack.pop()
if isinstance(t, str):
leaves.append(t)
continue
a, kids = t
if (a, tuple(k if isinstance(k, str) else k[0] for k in kids)) not in pset:
return False
stack.extend(reversed(kids))
return leaves == list(w)
def is_reverse_rightmost(prods, start, reductions, w):
"""The reductions, read backwards, must be the steps of a rightmost derivation of w."""
nts = {a for a, _ in prods}
form = [start]
for k in reversed(reductions):
a, rhs = prods[k]
idx = [i for i, x in enumerate(form) if x in nts]
if not idx or form[idx[-1]] != a:
return False
i = idx[-1]
form[i:i + 1] = list(rhs)
return form == list(w)
def random_grammar(rng):
names = ["S", "A", "B"][: rng.randint(1, 3)]
terms = ["a", "b"]
prods = []
for a in names:
for _ in range(rng.randint(1, 3)):
k = rng.choice([0, 1, 1, 2, 2, 3])
prods.append((a, tuple(rng.choice(names + terms + terms) for _ in range(k))))
out = []
for p in prods:
if p not in out:
out.append(p)
return out
def test_example_trace() -> None:
trace = []
toks = "id + id * id".split()
tree, red = parse(EXPR, "E", toks, trace)
moves = [a[0] if a[0] != "reduce" else EXPR[a[1]] for _, _, a in trace]
assert moves == [
"shift", ("F", ("id",)), ("T", ("F",)), ("E", ("T",)), "shift", "shift",
("F", ("id",)), ("T", ("F",)), "shift", "shift", ("F", ("id",)),
("T", ("T", "*", "F")), ("E", ("E", "+", "T")), "accept",
]
assert len(red) == 8 and is_reverse_rightmost(EXPR, "E", red, toks)
assert tree_ok(tree, EXPR, toks)
with pytest.raises(ParseError):
parse(EXPR, "E", "id + * id".split())
with pytest.raises(ParseError):
parse(EXPR, "E", [])
def test_greedy_decider_can_fail() -> None:
"""The driver is only as good as its decisions: reducing whenever a right
side is on top fails on id + id * id, which is in the language."""
def greedy(symbols, pos):
for k, (a, r) in enumerate(EXPR):
if r and tuple(symbols[len(symbols) - len(r):]) == r:
return ("reduce", k)
if symbols == ["E"] and pos == 5:
return ("accept",)
return ("shift",) if pos < 5 else ("error",)
with pytest.raises(ParseError):
shift_reduce("id + id * id".split(), EXPR, greedy)
def test_ambiguous_epsilon_and_cycles() -> None:
g = [("S", ("S", "S")), ("S", ("a",)), ("S", ())] # ambiguous, epsilon, left recursive
for n in range(5):
w = ["a"] * n
tree, red = parse(g, "S", w)
assert tree_ok(tree, g, w) and is_reverse_rightmost(g, "S", red, w)
cyc = [("S", ("A",)), ("A", ("S",)), ("A", ("b",)), ("S", ("S", "a"))] # unit cycle S => A => S
tree, red = parse(cyc, "S", ["b", "a", "a"])
assert tree_ok(tree, cyc, ["b", "a", "a"])
with pytest.raises(ParseError):
parse(cyc, "S", ["a"])
eps = [("S", ())]
assert parse(eps, "S", [])[0] == ("S", ())
def test_random_grammars_against_oracle() -> None:
rng = random.Random(1965)
checked = accepted = 0
kinds = {"eps": 0, "unit": 0, "left": 0}
for _ in range(400):
g = random_grammar(rng)
start = g[0][0]
kinds["eps"] += any(not r for _, r in g)
kinds["unit"] += any(len(r) == 1 and r[0] in {a for a, _ in g} for _, r in g)
kinds["left"] += any(r and r[0] == a for a, r in g)
for n in range(0, 5):
for w in itertools.product("ab", repeat=n):
w = list(w)
want = derives(g, start, w)
try:
tree, red = parse(g, start, w)
except ParseError:
assert not want, (g, w)
else:
assert want, (g, w)
assert tree_ok(tree, g, w), (g, w)
assert is_reverse_rightmost(g, start, red, w), (g, w)
accepted += 1
checked += 1
assert checked >= 500 and accepted >= 1000
assert min(kinds.values()) >= 50, kinds
What the next level needs
- the tests did not run in this build