LR(0) parsing in Python
Shift-reduce parser whose states come from LR(0) items without lookahead.
- File
lr0_parsing.py, 160 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/lr0-parsing/. The authors are listed in prov/37Z7NT.jsonl.
"""LR(0) parsing, with the end marker shifted like a token.
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 parse tree is
a pair (A, children) for a nonterminal node, and a plain string for a token leaf.
The grammar is augmented with the production S' -> S $, and the parser accepts
after it has shifted $.
"""
END = "$"
AUG = ("S'",) # the new start symbol; a tuple, so it cannot clash with a name
SHIFT = "shift"
ACCEPT = "accept"
Production = tuple[str, tuple[str, ...]]
Tree = tuple[str, list] | str
class ParseError(Exception):
"""The input is not in the language; position is the index of the bad token."""
def __init__(self, position: int, message: str) -> None:
super().__init__(f"at token {position}: {message}")
self.position = position
class LR0Table:
"""The LR(0) automaton of the augmented grammar and its actions.
prods[0] is S' -> S $. states[q] is the set of items (p, dot) of state q,
goto[(q, X)] the successor state, and action[q] is SHIFT, ACCEPT, the index
of the production to reduce, or None for a state without items to act on.
"""
def __init__(self, prods, nts, states, goto, action):
self.prods = prods
self.nts = nts
self.states = states
self.goto = goto
self.action = action
def _productive(productions: list[Production]) -> list[Production]:
"""Drop the productions that use a nonterminal deriving no terminal string."""
nts = {a for a, _ in productions}
good: set[str] = set()
changed = True
while changed:
changed = False
for a, rhs in productions:
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 productions
if a in good and all(x in good or x not in nts for x in r)]
def build_lr0(productions: list[Production], start: str) -> LR0Table:
"""Build the LR(0) automaton and its action table. Raises ValueError on a conflict.
Productions that use a nonterminal deriving no terminal string are removed
first; they take part in no derivation of a sentence. Cost: O(N |G|^2) time
for N states.
"""
nts = {a for a, _ in productions} | {start}
prods = [(AUG, (start, END))] + _productive(productions)
nts.add(AUG)
by_lhs: dict = {}
for p, (a, _) in enumerate(prods):
by_lhs.setdefault(a, []).append(p)
def closure(kernel):
items = set(kernel)
todo = list(kernel)
seen: set = set()
while todo:
p, d = todo.pop()
rhs = prods[p][1]
if d < len(rhs) and rhs[d] in nts and rhs[d] not in seen:
seen.add(rhs[d])
for q in by_lhs.get(rhs[d], ()):
if (q, 0) not in items:
items.add((q, 0))
todo.append((q, 0))
return frozenset(items)
states = [closure([(0, 0)])]
index = {states[0]: 0}
goto: dict = {}
q = 0
while q < len(states):
moves: dict = {}
for p, d in states[q]:
rhs = prods[p][1]
if d < len(rhs):
moves.setdefault(rhs[d], []).append((p, d + 1))
for x, kernel in moves.items():
j = closure(kernel)
if j not in index:
index[j] = len(states)
states.append(j)
goto[q, x] = index[j]
q += 1
action: list = []
for q, items in enumerate(states):
complete = [p for p, d in items if d == len(prods[p][1])]
shifts = [p for p, d in items if d < len(prods[p][1]) and prods[p][1][d] not in nts]
if len(complete) > 1 or (complete and shifts):
raise ValueError(f"not LR(0): conflict in state {q}")
if complete:
action.append(ACCEPT if complete[0] == 0 else complete[0])
else:
action.append(SHIFT if shifts else None)
return LR0Table(prods, nts, states, goto, action)
def lr0_parse(productions: list[Production], start: str, tokens: list[str],
table: LR0Table | None = None) -> Tree:
"""Parse tokens with an LR(0) grammar and return the parse tree.
Precondition: the grammar with S' -> S $ is LR(0) (build_lr0 raises ValueError
otherwise). Raises ParseError at the first token that cannot continue a sentence.
Cost: O(n) time and space after the table is built.
"""
if table is None:
table = build_lr0(productions, start)
prods, goto, action = table.prods, table.goto, table.action
w = list(tokens) + [END]
states = [0] # @line L1
trees: list = []
i = 0
while True: # @line L2
q = states[-1]
act = action[q] # @line L3
if act == SHIFT: # @line L4
nxt = goto.get((q, w[i]))
if nxt is None: # @line L5
raise ParseError(i, f"unexpected {w[i]!r}")
states.append(nxt) # @line L6
trees.append(w[i])
i += 1
elif act == ACCEPT: # @line L7
if i != len(w):
raise ParseError(i - 1, "unexpected end marker inside the input")
return trees[0]
elif act is None:
raise ParseError(i, "the language is empty")
else: # @line L8
a, rhs = prods[act]
k = len(rhs)
node = (a, trees[len(trees) - k:]) # @line L9
del trees[len(trees) - k:]
del states[len(states) - k:]
states.append(goto[states[-1], a]) # @line L10
trees.append(node)
test_lr0_parsing.py 183 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/lr0-parsing/. The authors are listed in prov/37Z7NT.jsonl.
import itertools
import random
import pytest
from lr0_parsing import END, ParseError, build_lr0, lr0_parse
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 test_list_example():
# L -> L , x | x is LR(0) once S' -> L $ is used
g = [("L", ("L", ",", "x")), ("L", ("x",))]
t = build_lr0(g, "L")
assert len(t.states) == 6
toks = ["x", ",", "x", ",", "x"]
tree = lr0_parse(g, "L", toks, t)
check_tree(g, "L", tree, toks)
assert tree == ("L", [("L", [("L", ["x"]), ",", "x"]), ",", "x"])
for bad, pos in ((["x", "x"], 1), ([",", "x"], 0), (["x", ","], 2), ([], 0),
(["x", "$", "x"], 1)):
with pytest.raises(ParseError) as e:
lr0_parse(g, "L", bad, t)
assert e.value.position == pos
def test_conflicts_are_refused():
expr = [("E", ("E", "+", "T")), ("E", ("T",)), ("T", ("T", "*", "F")), ("T", ("F",)),
("F", ("(", "E", ")")), ("F", ("id",))]
with pytest.raises(ValueError):
build_lr0(expr, "E")
with pytest.raises(ValueError): # right recursion needs lookahead
build_lr0([("L", ("x", ",", "L")), ("L", ("x",))], "L")
with pytest.raises(ValueError): # ambiguous
build_lr0([("E", ("E", "+", "E")), ("E", ("a",))], "E")
with pytest.raises(ValueError): # a cycle of unit productions
build_lr0([("S", ("A",)), ("A", ("S",)), ("A", ("a",))], "S")
def test_empty_productions_and_empty_input():
g = [("S", ("A", "a")), ("A", ())]
tree = lr0_parse(g, "S", ["a"])
assert tree == ("S", [("A", []), "a"])
g2 = [("S", ("S", "a")), ("S", ())]
assert lr0_parse(g2, "S", []) == ("S", [])
assert lr0_parse(g2, "S", ["a", "a"]) == ("S", [("S", [("S", []), "a"]), "a"])
with pytest.raises(ValueError): # reduce S -> ε or shift a: needs lookahead
build_lr0([("S", ("a", "S", "b")), ("S", ())], "S")
def test_deep_input_has_no_recursion_limit():
g = [("S", ("(", "S", ")")), ("S", ("x",))]
n = 200000
toks = ["("] * n + ["x"] + [")"] * n
tree = lr0_parse(g, "S", toks)
check_tree(g, "S", tree, toks)
def test_random_against_brute_force():
rng = random.Random(4127)
terms = ["a", "b"]
tested = 0
for _ in range(6000):
prods = productive_only(random_grammar(rng, rng.randint(1, 4), terms))
if not any(a == "S" for a, _ in prods):
continue
try:
table = build_lr0(prods, "S")
except ValueError:
continue
tested += 1
bound = 6
lang = lang_upto(prods, bound)
prefixes = prefix_lang(prods, bound + 1)["S"]
for m in range(bound + 1):
for w in itertools.product(terms, repeat=m):
if w in lang["S"]:
check_tree(prods, "S", lr0_parse(prods, "S", list(w), table), w)
else:
with pytest.raises(ParseError) as e:
lr0_parse(prods, "S", list(w), table)
i = e.value.position
# valid prefix property: the tokens before the error start a sentence
assert w[:i] in prefixes, (prods, w, i)
assert w[:i + 1] not in prefixes or i == len(w), (prods, w, i)
assert tested >= 500
What the next level needs
- the tests did not run in this build