Yacc in Python
The classic LALR(1) parser generator tool whose input grammars carry semantic actions.
- File
yacc.py, 327 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/yacc/. The authors are listed in prov/NSTRHE.jsonl.
"""The algorithm of a yacc-style parser generator, and the parser it produces.
Yacc(productions, precedence) builds an LALR(1) table from the LR(0) automaton by
lookahead propagation, resolves its conflicts with operator precedence and the
default rules (shift over reduce, earlier rule over later rule), and keeps a
report of the conflicts that the default rules settled. Yacc.parse runs the
table on a token list, computes semantic values with the actions of the
productions, and recovers from syntax errors with the special token "error".
A production is (lhs, rhs) or (lhs, rhs, action) or (lhs, rhs, action, prec),
where rhs is a tuple of symbols, action maps the list of right-side values to
the value of the left side (default: the first value, or None for an empty
right side), and prec names a terminal whose precedence the rule takes, as
%prec does. The left sides are the nonterminals; every other symbol is a
terminal. The first production's left side is the start symbol.
precedence is a list of (associativity, terminals) from lowest to highest, with
associativity "left", "right" or "nonassoc", like %left, %right and %nonassoc
lines in the order they are written.
"""
from collections.abc import Callable, Sequence
from dataclasses import dataclass, field
from typing import Any
END = "$"
ERROR = "error"
_HASH = object() # the dummy lookahead of the propagation method
@dataclass
class Production:
lhs: str
rhs: tuple[str, ...]
action: Callable[[list[Any]], Any] | None = None
prec: str | None = None
@dataclass
class Conflict:
state: int
token: str
kind: str # "shift/reduce" or "reduce/reduce"
chosen: tuple
discarded: tuple
@dataclass
class ParseResult:
accepted: bool
value: Any = None
errors: list[int] = field(default_factory=list) # token positions of reported errors
class Yacc:
"""An LALR(1) parser built the way yacc builds it."""
def __init__(self, productions: Sequence[tuple], precedence: Sequence[tuple[str, Sequence[str]]] = ()) -> None:
user = [Production(*p) for p in productions]
self.nonterminals: list[str] = []
for p in user:
if p.lhs not in self.nonterminals:
self.nonterminals.append(p.lhs)
self.terminals: list[str] = []
for p in user:
for x in p.rhs:
if x not in self.nonterminals and x not in self.terminals:
self.terminals.append(x)
start = self.nonterminals[0]
aug = start + "'"
while aug in self.nonterminals or aug in self.terminals:
aug += "'"
self.prods = [Production(aug, (start,))] + user
self.nts = set(self.nonterminals) | {aug}
self.level: dict[str, tuple[int, str]] = {}
for i, (assoc, toks) in enumerate(precedence):
for t in toks:
self.level[t] = (i + 1, assoc)
self._first_sets()
self._build()
# ------------------------------------------------------------ grammar analysis
def _first_sets(self) -> None:
self.nullable: set[str] = set()
self.first: dict[str, set[str]] = {a: set() for a in self.nts}
changed = True
while changed:
changed = False
for p in self.prods:
if p.lhs not in self.nullable and all(x in self.nullable for x in p.rhs):
self.nullable.add(p.lhs)
changed = True
for x in p.rhs:
add = self.first[x] if x in self.nts else {x}
if not add <= self.first[p.lhs]:
self.first[p.lhs] |= add
changed = True
if x not in self.nullable:
break
def _first_seq(self, seq: Sequence[str]) -> tuple[set[str], bool]:
out: set[str] = set()
for x in seq:
if x in self.nts:
out |= self.first[x]
if x not in self.nullable:
return out, False
else:
out.add(x)
return out, False
return out, True
def _closure_la(self, kernel: dict[tuple[int, int], set]) -> dict[tuple[int, int], set]:
"""LR(1) closure where each item carries a set of lookaheads."""
items = {it: set(la) for it, la in kernel.items()}
todo = list(items)
while todo:
p, d = todo.pop()
rhs = self.prods[p].rhs
if d >= len(rhs) or rhs[d] not in self.nts:
continue
first, rest_nullable = self._first_seq(rhs[d + 1:])
la = first | items[(p, d)] if rest_nullable else first
for q, prod in enumerate(self.prods):
if prod.lhs == rhs[d]:
cur = items.setdefault((q, 0), set())
if not la <= cur:
cur |= la
todo.append((q, 0))
return items
def _lr0_closure(self, kernel: frozenset) -> list[tuple[int, int]]:
out = set(kernel)
todo = list(kernel)
while todo:
p, d = todo.pop()
rhs = self.prods[p].rhs
if d < len(rhs) and rhs[d] in self.nts:
for q, prod in enumerate(self.prods):
if prod.lhs == rhs[d] and (q, 0) not in out:
out.add((q, 0))
todo.append((q, 0))
return sorted(out)
# ------------------------------------------------------------ table construction
def _build(self) -> None:
order = []
for p in self.prods:
for x in p.rhs:
if x not in order:
order.append(x)
# L1: the LR(0) automaton, states numbered in breadth-first order
self.kernels: list[frozenset] = [frozenset({(0, 0)})] # @line L1
number = {self.kernels[0]: 0}
self.goto: dict[tuple[int, str], int] = {}
q = 0
while q < len(self.kernels):
items = self._lr0_closure(self.kernels[q])
for x in order:
nxt = frozenset((p, d + 1) for p, d in items
if d < len(self.prods[p].rhs) and self.prods[p].rhs[d] == x)
if nxt:
if nxt not in number:
number[nxt] = len(self.kernels)
self.kernels.append(nxt)
self.goto[(q, x)] = number[nxt]
q += 1
# L2: spontaneous lookaheads and propagation links
la: dict[tuple[int, tuple[int, int]], set[str]] = {
(s, it): set() for s, k in enumerate(self.kernels) for it in k}
la[(0, (0, 0))].add(END)
links: dict[tuple[int, tuple[int, int]], list] = {key: [] for key in la}
for s, kernel in enumerate(self.kernels):
for it in kernel:
closed = self._closure_la({it: {_HASH}}) # @line L2
for (p, d), las in closed.items():
rhs = self.prods[p].rhs
if d == len(rhs):
continue
target = (self.goto[(s, rhs[d])], (p, d + 1))
for a in las:
if a is _HASH:
links[(s, it)].append(target)
else:
la[target].add(a)
# L3: propagate until no lookahead set changes
todo = [key for key in la if la[key]]
while todo:
key = todo.pop()
for target in links[key]: # @line L3
if not la[key] <= la[target]:
la[target] |= la[key]
todo.append(target)
self.kernel_lookaheads = la
# L4: fill the cells; accept is kept as a reduction by production 0
cells: dict[tuple[int, str], list] = {}
for (s, x), t in self.goto.items():
if x not in self.nts:
cells.setdefault((s, x), []).append(("shift", t)) # @line L4
for s, kernel in enumerate(self.kernels):
closed = self._closure_la({it: la[(s, it)] for it in kernel})
for (p, d), las in closed.items():
if d == len(self.prods[p].rhs):
for a in las:
cells.setdefault((s, a), []).append(("reduce", p))
self.raw = {k: tuple(sorted(v, key=_order)) for k, v in cells.items()}
self.action: dict[tuple[int, str], tuple] = {}
self.conflicts: list[Conflict] = []
self.resolved_by_precedence = 0
for key in sorted(self.raw, key=lambda k: (k[0], str(k[1]))):
acts = self.raw[key]
chosen = self._resolve(key, acts) if len(acts) > 1 else acts[0]
if chosen is not None:
if chosen == ("reduce", 0):
chosen = ("accept",)
self.action[key] = chosen
# a state whose only action is one reduction reduces without reading the lookahead
rows: dict[int, set] = {}
for (st, _), act in self.action.items():
rows.setdefault(st, set()).add(act)
self.default = {st: next(iter(acts)) for st, acts in rows.items()
if len(acts) == 1 and next(iter(acts))[0] == "reduce"}
def rule_prec(self, p: int) -> tuple[int, str] | None:
"""The precedence of production p: from its %prec token, else from its last terminal."""
prod = self.prods[p]
if prod.prec is not None:
return self.level.get(prod.prec)
for x in reversed(prod.rhs):
if x not in self.nts:
return self.level.get(x)
return None
def _resolve(self, key: tuple[int, str], acts: tuple) -> tuple | None:
state, token = key
shift = next((a for a in acts if a[0] == "shift"), None)
reduces = [a for a in acts if a[0] == "reduce"]
tok = self.level.get(token)
kept = []
for r in reduces: # @line L5
rp = self.rule_prec(r[1])
if shift is None or tok is None or rp is None:
kept.append(r)
elif tok[0] > rp[0]:
pass # the token binds tighter: shift
elif tok[0] < rp[0] or tok[1] == "left":
shift = None
kept.append(r)
elif tok[1] == "right":
pass
else: # nonassoc: neither, the cell becomes an error
shift = None
if len(kept) + (shift is not None) < len(acts):
self.resolved_by_precedence += 1
if shift is not None and kept: # @line L6
self.conflicts.append(Conflict(state, token, "shift/reduce", shift, tuple(kept)))
return shift
if len(kept) > 1: # @line L7
self.conflicts.append(Conflict(state, token, "reduce/reduce", kept[0], tuple(kept[1:])))
return kept[0]
if kept:
return kept[0]
return shift # None when %nonassoc made the cell an error
# ------------------------------------------------------------ the parser
def parse(self, tokens: Sequence[tuple[str, Any] | str], max_steps: int = 1_000_000) -> ParseResult:
"""Run the parser. Tokens are kinds or (kind, value) pairs; END is appended."""
toks = [(t, t) if isinstance(t, str) else (t[0], t[1]) for t in tokens] + [(END, None)]
states = [0]
values: list[Any] = [None]
i = 0
quiet = 0 # tokens still to shift before errors are reported again
result = ParseResult(False)
for _ in range(max_steps):
kind, val = toks[i]
act = self.default.get(states[-1]) or self.action.get((states[-1], kind)) # @line L8
if act is None:
# L12: error recovery with the error token
if quiet == 0:
result.errors.append(i) # @line L12
elif quiet == 3:
if kind == END:
return result
i += 1 # discard the token that could not follow the error token
quiet = 3
while (states[-1], ERROR) not in self.action or self.action[(states[-1], ERROR)][0] != "shift":
if len(states) == 1:
return result
states.pop()
values.pop()
states.append(self.action[(states[-1], ERROR)][1])
values.append(None)
continue
if act[0] == "shift": # @line L9
states.append(act[1])
values.append(val)
i += 1
if quiet:
quiet -= 1
elif act[0] == "reduce": # @line L10
prod = self.prods[act[1]]
k = len(prod.rhs)
args = values[len(values) - k:] if k else []
if k:
del states[-k:]
del values[-k:]
if prod.action is not None:
value = prod.action(args)
else:
value = args[0] if args else None
states.append(self.goto[(states[-1], prod.lhs)])
values.append(value)
else: # @line L11
result.accepted = True
result.value = values[-1]
return result
raise RuntimeError("step limit exceeded")
def _order(a: tuple) -> tuple:
return (0, a[1]) if a[0] == "shift" else (1, a[1])
test_yacc.py 512 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/yacc/. The authors are listed in prov/NSTRHE.jsonl.
import itertools
import random
from yacc import END, ERROR, Yacc
M = 10007
PREC = [("nonassoc", ["<"]), ("left", ["+", "-"]), ("left", ["*"]), ("right", ["^"]), ("right", ["NEG"])]
BINARY = {
"+": lambda a, b: (a + b) % M,
"-": lambda a, b: (a - b) % M,
"*": lambda a, b: (a * b) % M,
"^": lambda a, b: (2 * a + 3 * b) % M, # any operation that is not associative will do
"<": lambda a, b: int(a < b),
}
def expr_productions():
prods = [("E", ("E", op, "E"), (lambda v, f=f: f(v[0], v[2]))) for op, f in BINARY.items()]
prods.append(("E", ("-", "E"), (lambda v: (-v[1]) % M), "NEG"))
prods.append(("E", ("(", "E", ")"), (lambda v: v[1])))
prods.append(("E", ("num",)))
return prods
def stmt_productions():
return [
("L", ("L", "S"), (lambda v: v[0] + [v[1]])),
("L", (), (lambda v: [])),
("S", ("E", ";")),
("S", (ERROR, ";"), (lambda v: "ERR")),
] + expr_productions()
# ---------------------------------------------------------------- oracles
def reduce_grammar(prods):
"""Drop unproductive and unreachable nonterminals; None if the start symbol is unproductive."""
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
start = prods[0][0]
if start not in productive:
return None
prods = [(a, r) for a, r in prods if a in productive and all(x not in nts or x in productive for x in r)]
reach = {start}
changed = True
while changed:
changed = False
for a, rhs in prods:
if a in reach:
for x in rhs:
if x in nts and x not in reach:
reach.add(x)
changed = True
return [(a, r) for a, r in prods if a in reach]
def lalr_by_merging(prods):
"""Reference table: canonical LR(1) states merged by core; cells keyed by (LR(0) kernel, token)."""
s0 = prods[0][0]
pa = [(s0 + "'", (s0,))] + list(prods)
nts = {a for a, _ in pa}
nullable = set()
first = {a: set() for a in nts}
changed = True
while changed:
changed = False
for a, rhs in pa:
if a not in nullable and all(x in nullable for x in rhs):
nullable.add(a)
changed = True
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
def closure(items):
out = set(items)
todo = list(items)
while todo:
p, d, la = todo.pop()
rhs = pa[p][1]
if d < len(rhs) and rhs[d] in nts:
las = set()
for x in rhs[d + 1:]:
las |= first[x] if x in nts else {x}
if x not in nullable:
break
else:
las.add(la)
for j, (b, _) in enumerate(pa):
if b == rhs[d]:
for t in las:
if (j, 0, t) not in out:
out.add((j, 0, t))
todo.append((j, 0, t))
return frozenset(out)
def kernel(state):
return frozenset((p, d) for p, d, _ in state if d > 0 or p == 0)
start = closure({(0, 0, END)})
states = [start]
seen = {start}
cells = {}
q = 0
while q < len(states):
st = states[q]
k = kernel(st)
for p, d, la in st:
rhs = pa[p][1]
if d == len(rhs):
cells.setdefault((k, la), set()).add(("reduce", p))
continue
nxt = closure({(pp, dd + 1, ll) for pp, dd, ll in st
if dd < len(pa[pp][1]) and pa[pp][1][dd] == rhs[d]})
if rhs[d] not in nts:
cells.setdefault((k, rhs[d]), set()).add(("shift", kernel(nxt)))
if nxt not in seen:
seen.add(nxt)
states.append(nxt)
q += 1
return cells
def is_prefix(prods, u):
"""Earley recognition of prefixes: True when u is a prefix of some sentence (reduced grammar)."""
nts = {a for a, _ in prods}
nullable = set()
changed = True
while changed:
changed = False
for a, rhs in prods:
if a not in nullable and all(x in nullable for x in rhs):
nullable.add(a)
changed = True
start = prods[0][0]
sets = [set((p, 0, 0) for p, (a, _) in enumerate(prods) if a == start)]
for j in range(len(u) + 1):
todo = list(sets[j])
while todo:
p, d, i = todo.pop()
rhs = prods[p][1]
new = []
if d < len(rhs) and rhs[d] in nts:
new += [(q, 0, j) for q, (b, _) in enumerate(prods) if b == rhs[d]]
if rhs[d] in nullable:
new.append((p, d + 1, i))
elif d == len(rhs):
a = prods[p][0]
new += [(pp, dd + 1, ii) for pp, dd, ii in list(sets[i])
if dd < len(prods[pp][1]) and prods[pp][1][dd] == a]
for item in new:
if item not in sets[j]:
sets[j].add(item)
todo.append(item)
if j == len(u):
return bool(sets[j])
nxt = set((p, d + 1, i) for p, d, i in sets[j]
if d < len(prods[p][1]) and prods[p][1][d] == u[j])
if not nxt:
return False
sets.append(nxt)
return True
def lang_upto(prods, max_len):
nts = {a for a, _ in prods}
lang = {a: set() for a in nts}
changed = True
while changed:
changed = False
for a, rhs in prods:
cur = {()}
for x in rhs:
src = lang[x] if x in nts else {(x,)}
cur = {u + v for u in cur for v in src if len(u) + len(v) <= max_len}
if not cur <= lang[a]:
lang[a] |= cur
changed = True
return lang
def random_grammar(rng):
names = ["S", "A", "B"][: rng.randint(1, 3)]
prods = []
for a in names:
for _ in range(rng.randint(1, 3)):
rhs = () if rng.random() < 0.2 else 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 tree_yield_ok(tree, prods, w):
"""Check that tree = (p, children) is a derivation tree of w (iteratively)."""
nts = {a for a, _ in prods}
out = []
stack = [(tree, prods[0][0])]
while stack:
node, sym = stack.pop()
if sym not in nts:
if node != sym:
return False
out.append(node)
continue
p, kids = node
if prods[p - 1][0] != sym or len(kids) != len(prods[p - 1][1]):
return False
for kid, s in reversed(list(zip(kids, prods[p - 1][1]))):
stack.append((kid, s))
return tuple(out) == tuple(w)
LEVEL = {"<": (1, "nonassoc"), "+": (2, "left"), "-": (2, "left"), "*": (3, "left"), "^": (4, "right")}
NEG = 5
def all_trees(toks):
"""Every parse tree of toks for the ambiguous expression grammar, bottom-up over intervals."""
n = len(toks)
trees = {}
for length in range(1, n + 1):
for i in range(n - length + 1):
j = i + length
out = []
if length == 1 and toks[i][0] == "num":
out.append(("num", toks[i][1]))
if toks[i][0] == "-" and length >= 2:
out += [("neg", t) for t in trees[(i + 1, j)]]
if toks[i][0] == "(" and toks[j - 1][0] == ")" and length >= 3:
out += [("par", t) for t in trees[(i + 1, j - 1)]]
for k in range(i + 1, j - 1):
if toks[k][0] in BINARY:
for left in trees[(i, k)]:
for right in trees[(k + 1, j)]:
out.append(("bin", toks[k][0], left, right))
trees[(i, j)] = out
return trees.get((0, n), [])
def respects_precedence(tree):
stack = [tree]
while stack:
t = stack.pop()
if t[0] == "num":
continue
if t[0] in ("neg", "par"):
if t[0] == "neg" and t[1][0] == "bin" and LEVEL[t[1][1]][0] <= NEG:
return False
stack.append(t[1])
continue
_, op, left, right = t
lv, assoc = LEVEL[op]
if left[0] == "bin":
l2 = LEVEL[left[1]][0]
if l2 < lv or (l2 == lv and assoc != "left"):
return False
if left[0] == "neg" and NEG < lv:
return False
if right[0] == "bin":
r2 = LEVEL[right[1]][0]
if r2 < lv or (r2 == lv and assoc != "right"):
return False
stack += [left, right]
return True
def evaluate(tree):
"""Value of an expression tree, computed with an explicit stack."""
out = {}
stack = [(tree, False)]
while stack:
t, done = stack.pop()
if t[0] == "num":
out[id(t)] = t[1]
elif not done:
stack.append((t, True))
stack += [(c, False) for c in t[1:] if isinstance(c, tuple)]
elif t[0] == "neg":
out[id(t)] = (-out[id(t[1])]) % M
elif t[0] == "par":
out[id(t)] = out[id(t[1])]
else:
out[id(t)] = BINARY[t[1]](out[id(t[2])], out[id(t[3])])
return out[id(tree)]
def random_expression(rng, depth):
if depth == 0 or rng.random() < 0.3:
return [("num", rng.randrange(10))]
r = rng.random()
if r < 0.15:
return [("-", "-")] + random_expression(rng, depth - 1)
if r < 0.25:
return [("(", "(")] + random_expression(rng, depth - 1) + [(")", ")")]
op = rng.choice(list(BINARY))
return random_expression(rng, depth - 1) + [(op, op)] + random_expression(rng, depth - 1)
# ---------------------------------------------------------------- worked examples
def test_calculator_conflicts_are_settled_by_precedence():
y = Yacc([("E", ("E", "+", "E"), lambda v: v[0] + v[2]),
("E", ("E", "*", "E"), lambda v: v[0] * v[2]),
("E", ("(", "E", ")"), lambda v: v[1]),
("E", ("num",))],
[("left", ["+"]), ("left", ["*"])])
assert len(y.kernels) == 10
raw_conflicts = {k: v for k, v in y.raw.items() if len(v) > 1}
assert len(raw_conflicts) == 4
assert y.resolved_by_precedence == 4 and y.conflicts == []
plus_state = y.goto[(y.goto[(y.goto[(0, "E")], "+")], "E")]
times_state = y.goto[(y.goto[(y.goto[(0, "E")], "*")], "E")]
assert y.action[(plus_state, "+")] == ("reduce", 1)
assert y.action[(plus_state, "*")][0] == "shift"
assert y.action[(times_state, "+")] == ("reduce", 2)
assert y.action[(times_state, "*")] == ("reduce", 2)
r = y.parse([("num", 2), "+", ("num", 3), "*", ("num", 4)])
assert r.accepted and r.value == 14 and r.errors == []
assert y.parse([("num", 2), "*", ("num", 3), "+", ("num", 4)]).value == 10
def test_without_precedence_the_defaults_apply():
y = Yacc([("E", ("E", "+", "E"), lambda v: v[0] + v[2]),
("E", ("E", "*", "E"), lambda v: v[0] * v[2]),
("E", ("num",))])
assert len(y.conflicts) == 4 and all(c.kind == "shift/reduce" for c in y.conflicts)
# shift everywhere makes both operators right-associative with equal precedence
assert y.parse([("num", 2), "*", ("num", 3), "+", ("num", 4)]).value == 14
def test_dangling_else_shifts():
y = Yacc([("S", ("if", "S"), lambda v: ("if", v[1])),
("S", ("if", "S", "else", "S"), lambda v: ("ifelse", v[1], v[3])),
("S", ("a",))])
assert [(c.kind, c.token) for c in y.conflicts] == [("shift/reduce", "else")]
r = y.parse(["if", "if", "a", "else", "a"])
assert r.value == ("if", ("ifelse", "a", "a"))
def test_reduce_reduce_takes_the_earlier_rule():
y = Yacc([("S", ("A",)), ("S", ("B",)), ("A", ("x",), lambda v: "A"), ("B", ("x",), lambda v: "B")])
assert [(c.kind, c.token, c.chosen) for c in y.conflicts] == [("reduce/reduce", END, ("reduce", 3))]
assert y.parse(["x"]).value == "A"
def test_nonassoc_makes_chains_an_error():
y = Yacc(expr_productions(), PREC)
assert y.conflicts == []
ok = y.parse([("num", 1), "<", ("num", 2)])
assert ok.accepted and ok.value == 1
bad = y.parse([("num", 1), "<", ("num", 2), "<", ("num", 3)])
assert not bad.accepted and bad.errors == [3]
def test_error_recovery_trace():
y = Yacc(stmt_productions(), PREC)
assert y.conflicts == []
toks = [("num", 1), "+", ";", ("num", 3), ("num", 4), ";", ("num", 2), ";", ("num", 5), "*", ("num", 6), ";"]
r = y.parse(toks)
assert r.accepted
assert r.value == ["ERR", "ERR", 2, 30]
# the second error comes 2 shifts after the recovery from the first, so it is not reported
assert r.errors == [2]
spaced = toks[:3] + [("num", 7), ";"] + toks[3:]
assert y.parse(spaced).value == ["ERR", 7, "ERR", 2, 30]
assert y.parse(spaced).errors == [2, 6]
assert not y.parse([("num", 1), "+"]).accepted
def test_empty_input_epsilon_and_left_recursion():
y = Yacc([("L", ("L", "x"), lambda v: v[0] + 1), ("L", (), lambda v: 0)])
assert y.conflicts == []
assert y.parse([]).value == 0
assert y.parse(["x"] * 50).value == 50
assert y.parse(["y"]).errors == [0]
r = Yacc([("S", ("a",))]).parse([])
assert not r.accepted and r.errors == [0]
def test_deep_input_has_no_recursion_limit():
y = Yacc([("E", ("(", "E", ")"), lambda v: v[1] + 1), ("E", ("num",), lambda v: 0)])
n = 20000
assert y.parse(["("] * n + [("num", 0)] + [")"] * n).value == n
# ---------------------------------------------------------------- random tests
def test_lalr_table_matches_merged_lr1_on_random_grammars():
rng = random.Random(11)
compared = 0
for _ in range(700):
g = reduce_grammar(random_grammar(rng))
if g is None:
continue
y = Yacc(g)
ref = lalr_by_merging(g)
mine = {}
for (s, t), acts in y.raw.items():
mine[(y.kernels[s], t)] = {(a[0], y.kernels[a[1]]) if a[0] == "shift" else a for a in acts}
assert mine == ref, g
compared += 1
assert compared >= 500
def test_conflict_free_tables_parse_the_language_and_find_errors_early():
rng = random.Random(5)
checked = 0
for _ in range(900):
g = reduce_grammar(random_grammar(rng))
if g is None:
continue
prods = [(a, rhs, (lambda v, p=p: (p, tuple(v)))) for p, (a, rhs) in enumerate(g, start=1)]
y = Yacc(prods)
if y.conflicts:
continue
lang = lang_upto(g, 5)[g[0][0]]
for n in range(6):
for w in itertools.product("ab", repeat=n):
r = y.parse(list(w))
assert r.accepted == (w in lang), (g, w)
if r.accepted:
assert tree_yield_ok(r.value, g, w)
else:
first_bad = next(i for i in range(n + 1) if not is_prefix(g, w[: i + 1]) or i == n)
assert r.errors == [first_bad], (g, w)
checked += 1
assert checked >= 500
def test_precedence_matches_the_unique_disambiguated_tree():
rng = random.Random(9)
y = Yacc(expr_productions(), PREC)
for _ in range(1500):
if rng.random() < 0.7:
toks = random_expression(rng, rng.randint(1, 3))
else:
toks = [rng.choice([("num", 1), ("num", 2), ("+", "+"), ("*", "*"), ("-", "-"), ("<", "<"),
("^", "^"), ("(", "("), (")", ")")]) for _ in range(rng.randint(0, 7))]
if len(toks) > 11:
continue
good = [t for t in all_trees(toks) if respects_precedence(t)]
assert len(good) <= 1, toks
r = y.parse(toks)
assert r.accepted == bool(good), toks
if good:
assert r.value == evaluate(good[0]), toks
def test_error_recovery_matches_statement_by_statement_oracle():
rng = random.Random(13)
y = Yacc(stmt_productions(), PREC)
for _ in range(800):
toks = []
for _ in range(rng.randint(0, 4)):
if rng.random() < 0.6:
seg = random_expression(rng, 2)
else:
seg = [rng.choice([("num", 3), ("+", "+"), ("*", "*"), ("(", "("), (")", ")")])
for _ in range(rng.randint(0, 3))]
toks += seg + [(";", ";")]
if rng.random() < 0.2:
toks += [("num", 1)]
segments = [[]]
for t in toks:
if t[0] == ";":
segments.append([])
else:
segments[-1].append(t)
expect = []
any_bad = False
for seg in segments[:-1]:
good = [t for t in all_trees(seg) if respects_precedence(t)] if len(seg) <= 11 else None
if good is None:
break
if good:
expect.append(evaluate(good[0]))
else:
expect.append("ERR")
any_bad = True
else:
r = y.parse(toks)
if segments[-1]:
assert not r.accepted and r.errors, toks
else:
assert r.accepted and r.value == expect, toks
assert bool(r.errors) == any_bad, toks
def test_unary_minus_needs_prec():
with_prec = Yacc(expr_productions(), PREC)
without = Yacc([p[:3] for p in expr_productions()], PREC)
toks = [("-", "-"), ("num", 2), ("^", "^"), ("num", 3)]
assert with_prec.parse(toks).value == (2 * (M - 2) + 3 * 3) % M # (-2) ^ 3
assert without.parse(toks).value == (-(2 * 2 + 3 * 3)) % M # -(2 ^ 3)
What the next level needs
- the tests did not run in this build