SLR(1) parsing in Python
LR(0) automaton with reductions limited to FOLLOW-set lookaheads.
- File
slr_parsing.py, 207 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/slr-parsing/. The authors are listed in prov/7X628Y.jsonl.
"""SLR(1) parsing: the LR(0) automaton with reductions limited to FOLLOW sets.
A grammar is a list of productions (A, rhs), where rhs is a tuple of symbols.
A symbol is a nonterminal if it is the left side of some production, and a
terminal otherwise. Production k of the user's grammar is reported as k.
"""
END = "$"
START = "S'"
class GrammarConflict(Exception):
"""The grammar is not SLR(1); .conflicts lists (state, token, actions)."""
def __init__(self, conflicts):
super().__init__(f"{len(conflicts)} SLR(1) conflicts")
self.conflicts = conflicts
class ParseError(Exception):
"""The input is not a sentence; .position is the index of the bad token
(len(tokens) for the end of the input)."""
def __init__(self, position):
super().__init__(f"syntax error at token {position}")
self.position = position
def useful_productions(prods, start):
"""Indices of the productions in which every symbol derives a terminal
string and whose left side is reachable from start through such rules."""
nts = {a for a, _ in prods}
productive = set()
changed = True
while changed:
changed = False
for a, rhs in prods:
if a not in productive and all(x not in nts or x in productive for x in rhs):
productive.add(a)
changed = True
ok = [k for k, (a, rhs) in enumerate(prods)
if a in productive and all(x not in nts or x in productive for x in rhs)]
reach, todo = {start}, [start]
while todo:
b = todo.pop()
for k in ok:
if prods[k][0] == b:
for x in prods[k][1]:
if x in nts and x not in reach:
reach.add(x)
todo.append(x)
return [k for k in ok if prods[k][0] in reach]
def follow_sets(P, nts):
"""Nullable set and FOLLOW sets of the augmented grammar P, by fixpoints."""
nullable, first = set(), {a: set() for a in nts}
changed = True
while changed:
changed = False
for a, rhs in P:
for x in rhs:
add = first[x] if x in nts else {x}
if not add <= first[a]:
first[a] |= add
changed = True
if x not in nullable:
break
else:
if a not in nullable:
nullable.add(a)
changed = True
follow = {a: set() for a in nts}
follow[START].add(END)
changed = True
while changed:
changed = False
for a, rhs in P:
trailer = set(follow[a])
for x in reversed(rhs):
if x in nts:
if not trailer <= follow[x]:
follow[x] |= trailer
changed = True
trailer = trailer | first[x] if x in nullable else set(first[x])
else:
trailer = {x}
return nullable, follow
class SLRTable:
"""The LR(0) automaton of a grammar and its SLR(1) ACTION and GOTO tables.
action[(state, terminal)] is a list of actions: ("shift", j),
("reduce", k) with k the index of the user's production, or ("accept",).
"""
def __init__(self, prods, start):
self.prods = [(a, tuple(r)) for a, r in prods]
keep = useful_productions(self.prods, start)
# P[0] is S' -> start; P[i] for i >= 1 is the user's production orig[i].
P = [(START, (start,))] + [self.prods[k] for k in keep]
orig = [None] + keep
nts = {START} | {a for a, _ in self.prods}
by_lhs = {}
for i, (a, _) in enumerate(P):
by_lhs.setdefault(a, []).append(i)
self.nullable, self.follow = follow_sets(P, nts)
def closure(kernel):
items, todo = set(kernel), list(kernel)
while todo:
i, d = todo.pop()
rhs = P[i][1]
if d < len(rhs):
for j in by_lhs.get(rhs[d], ()):
if (j, 0) not in items:
items.add((j, 0))
todo.append((j, 0))
return frozenset(items)
states = [closure({(0, 0)})]
index = {states[0]: 0}
trans = {}
q = 0
while q < len(states):
succ = {}
for i, d in sorted(states[q]):
rhs = P[i][1]
if d < len(rhs):
succ.setdefault(rhs[d], set()).add((i, d + 1))
for x, kernel in succ.items():
target = closure(kernel)
if target not in index:
index[target] = len(states)
states.append(target)
trans[q, x] = index[target]
q += 1
action = {}
for q, items in enumerate(states):
for i, d in sorted(items):
a, rhs = P[i]
if d < len(rhs) and rhs[d] not in nts:
act = ("shift", trans[q, rhs[d]])
keyed = action.setdefault((q, rhs[d]), [])
if act not in keyed:
keyed.append(act)
elif d == len(rhs) and i == 0:
action.setdefault((q, END), []).append(("accept",))
elif d == len(rhs):
for t in sorted(self.follow[a]):
action.setdefault((q, t), []).append(("reduce", orig[i]))
self.P, self.states, self.nts = P, states, nts
self.action = action
self.goto = {(q, x): j for (q, x), j in trans.items() if x in nts}
self.conflicts = sorted((q, t, acts) for (q, t), acts in action.items() if len(acts) > 1)
def slr_table(prods, start):
"""The SLR(1) table, or GrammarConflict if the grammar is not SLR(1)."""
table = SLRTable(prods, start)
if table.conflicts:
raise GrammarConflict(table.conflicts)
return table
def parse(table, tokens, choose=None, trace=None, limit=None):
"""Parse tokens with the table. Returns (tree, reductions): a tree is a
token or (A, children), and reductions lists the user's production
indices in the order the parser used them. choose(acts) picks an action
when an entry has several (only needed for tables with conflicts).
If trace is a list, (states, symbols, remaining input, action) is appended
for every step. limit bounds the number of moves (a RuntimeError is
raised beyond it); a table without conflicts never needs it."""
w = list(tokens) + [END]
states, trees, reductions = [0], [], [] # @line L1
i = moves = 0
while True: # @line L2
moves += 1
if limit is not None and moves > limit:
raise RuntimeError("move limit exceeded")
q, a = states[-1], w[i] # @line L3
acts = table.action.get((q, a))
if not acts: # @line L4
raise ParseError(i)
act = acts[0] if len(acts) == 1 else choose(acts)
if trace is not None:
symbols = [t if isinstance(t, str) else t[0] for t in trees]
trace.append((list(states), symbols, w[i:], act))
if act[0] == "shift": # @line L5
states.append(act[1]) # @line L6
trees.append(a)
i += 1
elif act[0] == "reduce": # @line L7
lhs, rhs = table.prods[act[1]]
k = len(rhs)
kids = tuple(trees[len(trees) - k:]) # @line L8
del states[len(states) - k:]
del trees[len(trees) - k:]
states.append(table.goto[states[-1], lhs]) # @line L9
trees.append((lhs, kids))
reductions.append(act[1])
else:
return trees[0], reductions # @line L10
test_slr_parsing.py 239 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/slr-parsing/. The authors are listed in prov/7X628Y.jsonl.
import itertools
import random
import pytest
from slr_parsing import GrammarConflict, ParseError, SLRTable, parse, slr_table
EXPR = [
("E", ("E", "+", "T")), ("E", ("T",)), ("T", ("T", "*", "F")), ("T", ("F",)),
("F", ("(", "E", ")")), ("F", ("id",)),
]
def grammar(text):
prods = []
for rule in text.split(";"):
a, rhs = rule.split("->")
for alt in rhs.split("|"):
prods.append((a.strip(), tuple(x for x in alt.split() if x != "eps")))
return prods
def spans(prods, w):
"""Independent oracle: the set of (X, i, j) with X =>* w[i:j], by a least fixpoint."""
nts = {a for a, _ in prods}
n, known = len(w), set()
def ends(rhs, i, j):
cur = {i}
for x in rhs:
nxt = set()
for p in cur:
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)
cur = nxt
return cur
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 j in ends(rhs, i, j):
known.add((a, i, j))
changed = True
return known
def is_prefix(prods, start, x):
"""Independent oracle: is x a prefix of some sentence of the grammar?
pre[(X, p)] means that X derives a string that starts with x[p:]."""
nts = {a for a, _ in prods}
n = len(x)
known = spans(prods, x)
# productive nonterminals: derive some terminal string (fixpoint)
productive = set()
changed = True
while changed:
changed = False
for a, rhs in prods:
if a not in productive and all(s not in nts or s in productive for s in rhs):
productive.add(a)
changed = True
pre = set()
def pre_sym(s, p):
if s in nts:
return (s, p) in pre
return p == n or (p == n - 1 and x[p] == s)
changed = True
while changed:
changed = False
for a, rhs in prods:
if not all(s not in nts or s in productive for s in rhs):
continue
for p in range(n + 1):
if (a, p) in pre:
continue
cur, ok = {p}, False
for s in rhs:
if any(pre_sym(s, q) for q in cur):
ok = True
break
nxt = set()
for q in cur:
if s in nts:
nxt |= {r for r in range(q, n + 1) if (s, q, r) in known}
elif q < n and x[q] == s:
nxt.add(q + 1)
cur = nxt
if ok or n in cur:
pre.add((a, p))
changed = True
return (start, 0) in pre
def tree_ok(tree, prods, w):
pset = set(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):
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
form[idx[-1]:idx[-1] + 1] = list(rhs)
return form == list(w)
def random_grammar(rng):
names = ["S", "A", "B", "C"][: rng.randint(1, 4)]
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 + ["a", "b", "a", "b"]) for _ in range(k))))
return list(dict.fromkeys(prods))
def test_expression_table_and_trace() -> None:
t = slr_table(EXPR, "E")
assert len(t.states) == 12
assert t.follow["E"] == {"+", ")", "$"} and t.follow["T"] == t.follow["F"] == {"+", "*", ")", "$"}
trace = []
tree, red = parse(t, "id * id + id".split(), trace=trace)
assert [s for s, _, _, _ in trace][:7] == [[0], [0, 5], [0, 3], [0, 2], [0, 2, 7], [0, 2, 7, 5], [0, 2, 7, 10]]
assert [a[0] for _, _, _, a in trace] == ["shift", "reduce", "reduce", "shift", "shift", "reduce", "reduce",
"reduce", "shift", "shift", "reduce", "reduce", "reduce", "accept"]
assert red == [5, 3, 5, 2, 1, 5, 3, 0]
assert tree_ok(tree, EXPR, "id * id + id".split())
for bad, pos in [("id + * id", 2), ("( id", 2), ("id id", 1), ("", 0), (")", 0)]:
with pytest.raises(ParseError) as e:
parse(t, bad.split())
assert e.value.position == pos
def test_classification_of_page_examples() -> None:
ok = ["S -> a S b | eps", "S -> S a | eps", "S -> A a | B b ; A -> c ; B -> c", "S -> x S | x"]
for g in ok:
assert SLRTable(grammar(g), "S").conflicts == [], g
lr = SLRTable(grammar("S -> L = R | R ; L -> * R | id ; R -> L"), "S")
assert [(t, sorted(a[0] for a in acts)) for _, t, acts in lr.conflicts] == [("=", ["reduce", "shift"])]
eps = SLRTable(grammar("S -> A a A b | B b B a ; A -> eps ; B -> eps"), "S")
assert [(q, t) for q, t, _ in eps.conflicts] == [(0, "a"), (0, "b")]
rr = SLRTable(grammar("S -> A a | B b | d A b | e B a ; A -> c ; B -> c"), "S")
assert sorted(t for _, t, _ in rr.conflicts) == ["a", "b"]
assert all(all(a[0] == "reduce" for a in acts) for _, _, acts in rr.conflicts)
dangling = SLRTable(grammar("S -> i E t S | i E t S e S | a ; E -> b"), "S")
assert [t for _, t, _ in dangling.conflicts] == ["e"] and len(dangling.states) == 10
with pytest.raises(GrammarConflict):
slr_table(grammar("E -> E + E | id"), "E")
# empty language: S derives no terminal string, every input is rejected at once
t = slr_table(grammar("S -> a S"), "S")
for w in ([], ["a"], ["a", "a"]):
with pytest.raises(ParseError) as e:
parse(t, w)
assert e.value.position == 0
def test_random_grammars_against_oracles() -> None:
rng = random.Random(1971)
checked = accepted = rejected = grammars = conflicted = 0
kinds = {"eps": 0, "unit": 0, "left": 0}
for _ in range(700):
g = random_grammar(rng)
start = g[0][0]
table = SLRTable(g, start)
nts = {a for a, _ in g}
if table.conflicts:
conflicted += 1
# with conflicts the table may fail, but an accepted tree is still right
for n in range(4):
for w in itertools.product("ab", repeat=n):
try:
tree, red = parse(table, w, choose=lambda acts: acts[-1], limit=200)
except (ParseError, RuntimeError):
continue
assert tree_ok(tree, g, w) and is_reverse_rightmost(g, start, red, w)
continue
grammars += 1
kinds["eps"] += any(not r for _, r in g)
kinds["unit"] += any(len(r) == 1 and r[0] in nts for _, r in g)
kinds["left"] += any(r and r[0] == a for a, r in g)
for n in range(6):
for w in itertools.product("ab", repeat=n):
w = list(w)
want = (start, 0, n) in spans(g, w)
trace = []
try:
tree, red = parse(table, w, trace=trace)
except ParseError as e:
assert not want, (g, w)
# the error is at the first token that no sentence allows there
first_bad = next((i for i in range(n) if not is_prefix(g, start, w[:i + 1])), n)
assert e.position == first_bad, (g, w)
rejected += 1
else:
assert want, (g, w)
assert tree_ok(tree, g, w) and is_reverse_rightmost(g, start, red, w), (g, w)
accepted += 1
assert len(trace) <= 40 * (n + 1), (g, w)
checked += 1
assert grammars >= 200 and conflicted >= 100
assert checked >= 10000 and accepted >= 800 and rejected >= 10000
assert min(kinds.values()) >= 30, kinds
def test_long_inputs_do_not_recurse() -> None:
right = slr_table(grammar("S -> x S | x"), "S")
tree, red = parse(right, ["x"] * 100000)
assert len(red) == 100000
left = slr_table(EXPR, "E")
w = ["id"] + ["+", "id"] * 50000
tree, red = parse(left, w)
assert tree_ok(tree, EXPR, w)
nested = ["("] * 20000 + ["id"] + [")"] * 20000
tree, red = parse(left, nested)
assert tree_ok(tree, EXPR, nested)
What the next level needs
- the tests did not run in this build