#!/usr/bin/env python3 """kite_de_exact_parse.py -- the exact parser of the shipped kite-family connection (no sympy). The connection file of this directory (lbl3se-kite-de.json in files/lbl3se, its byte-copy lbl3kp-kite-de.json in files/lbl3kp) holds each entry A_ij(w, d) of the 9x9 connection d/dw J = A(w, d) J as a string in this grammar, and nothing else: integer literals, the names w and d, the operators + - * / **, parentheses (every one of the 81 entries tokenises in these classes -- the census is in the bundle's CHANGES.md; 24 entries are nonzero; a token outside them is refused by name with its position). Precedence and associativity are Python's (the strings are Python expressions): ** binds tighter than unary minus, * and / left to right, + and - left to right; ** takes a non-negative integer exponent. What the module gives the scripts that read the connection (lbl3se-evaluate.py, lbl3kp-evaluate.py, lbl3se-w5-seed.py -- the lbl3kp-w5-seed.py shim runs the latter): parse_entry(text) -> (P, Q): the entry as the exact bivariate rational function P(d,w)/Q(d,w), the polynomials as dicts {(deg_d, deg_w): Fraction} (fractions.Fraction throughout); eps_grade(P, Q, neps) -> {k: (N_k, D_k)}: the eps-Taylor coefficients of the entry at d = 4 - 2*eps for k = 0..neps as univariate rational functions of w (ascending Fraction lists), by the closed forms c0 = P0/Q0, c1 = (P1 Q0 - P0 Q1)/Q0^2, ... (exact; uncancelled); cancel(num, den) -> the same rational function in lowest terms with INTEGER coefficient lists, the joint content of numerator and denominator 1 and the denominator's leading coefficient positive (a constant denominator under a non-constant numerator is divided into the numerator, over 1; a constant over a constant stays p/q) -- the normalisation sympy's cancel() gives these entries (checked offline, entry by entry, against the lists the earlier sympy pipeline of these scripts produced; the numerics therefore consume the same integers as before); graded_lists(A, rows, neps) -> {(i, j, k): (num, den)} over the nonzero entries A[i][j] with i, j in rows, k = 0..neps with a nonzero coefficient: cancel(eps_grade(...)) as ascending Fraction lists (integer-valued), each asserted equal to its uncancelled form as a rational function (num * D_k == den * N_k exactly) before it is returned; singular_certificate(lists) -> the set of the roots met, after asserting that every denominator's roots lie in {0, 1, 9} EXACTLY: each denominator is divided by w, w - 1 and w - 9 as often as they divide it and the residual must be a constant (a non-constant residual has a root outside the set and is refused by name with its coefficients). The scripts convert each integer coefficient c to mpf as mp.mpf(c.numerator) / mp.mpf(c.denominator), the operation the earlier sympy pipeline performed on the same integers, so every mpf list is the same binary number as before. Lineage: the tokenizer, parser and eps-grading are those of files/kite/kite_exact_parse.py (the row-14 parser, 2026-09-05) with the names (d, s) -> (d, w); the cancel() normalisation and the singular-point certificate are this module's. Refusals raise ParseError (a ValueError) with the entry, the position and the token named; the consuming scripts turn that into their exit code 3 (integrity) before any value is printed. """ import math import re from fractions import Fraction __all__ = ["ParseError", "tokenize", "parse_entry", "eps_grade", "cancel", "graded_lists", "singular_certificate", "NAMES", "SING"] NAMES = ("d", "w") # the two indeterminates of the grammar, in the exponent order of the dict keys D_SUBST = (Fraction(4), Fraction(-2)) # d = 4 - 2*eps: (constant, eps coefficient) SING = (0, 1, 9) # the singular points of the connection in w (the certificate's set) class ParseError(ValueError): """A string outside the shipped grammar, a failed internal identity, or a denominator root outside SING.""" # --------------------------------------------------------------------------- # 1. Tokens and the recursive-descent parser (values are exact rational functions) # --------------------------------------------------------------------------- _TOKEN = re.compile(r"\s*(?:(\d+)|([A-Za-z_][A-Za-z_0-9]*)|(\*\*)|([-+*/()]))") def tokenize(text): """The token list of one entry: ('INT', int) | ('NAME', 'd'|'w') | ('OP', '+' '-' '*' '/' '**' '(' ')'). Anything else is refused by name with its 0-based position.""" toks, pos, n = [], 0, len(text) while pos < n: if text[pos:].strip() == "": break m = _TOKEN.match(text, pos) if not m: raise ParseError(f"entry {text!r}: character {text[pos]!r} at position {pos} is outside the grammar " f"(integers, the names d and w, + - * / **, parentheses)") if m.group(1) is not None: toks.append(("INT", int(m.group(1)))) elif m.group(2) is not None: if m.group(2) not in NAMES: raise ParseError(f"entry {text!r}: name {m.group(2)!r} at position {m.start(2)} is outside the " f"grammar (the names are d and w)") toks.append(("NAME", m.group(2))) elif m.group(3) is not None: toks.append(("OP", "**")) else: toks.append(("OP", m.group(4))) pos = m.end() return toks # bivariate polynomials: {(a, b): Fraction} = sum c * d^a * w^b (zero polynomial = {}) def _padd(p, q): r = dict(p) for k, v in q.items(): x = r.get(k, 0) + v if x: r[k] = x elif k in r: del r[k] return r def _pneg(p): return {k: -v for k, v in p.items()} def _pmul(p, q): r = {} for (a1, b1), v1 in p.items(): for (a2, b2), v2 in q.items(): k = (a1 + a2, b1 + b2) x = r.get(k, 0) + v1 * v2 if x: r[k] = x elif k in r: del r[k] return r def _ppow(p, n): r = {(0, 0): Fraction(1)} for _ in range(n): r = _pmul(r, p) return r _ONE = {(0, 0): Fraction(1)} class _Parser: def __init__(self, text): self.text = text self.toks = tokenize(text) self.i = 0 def peek(self): return self.toks[self.i] if self.i < len(self.toks) else (None, None) def take(self): t = self.peek() self.i += 1 return t def fail(self, what): raise ParseError(f"entry {self.text!r}: {what} at token {self.i} of {len(self.toks)}") def parse(self): if not self.toks: self.fail("empty entry") v = self.expr() if self.i != len(self.toks): self.fail(f"unexpected token {self.peek()!r}") return v def expr(self): # term (('+'|'-') term)* p, q = self.term() while self.peek() == ("OP", "+") or self.peek() == ("OP", "-"): op = self.take()[1] p2, q2 = self.term() num = _padd(_pmul(p, q2), _pmul(p2, q)) if op == "+" else _padd(_pmul(p, q2), _pneg(_pmul(p2, q))) p, q = num, _pmul(q, q2) return p, q def term(self): # factor (('*'|'/') factor)* p, q = self.factor() while self.peek() == ("OP", "*") or self.peek() == ("OP", "/"): op = self.take()[1] p2, q2 = self.factor() if op == "*": p, q = _pmul(p, p2), _pmul(q, q2) else: if not p2: self.fail("division by the zero polynomial") p, q = _pmul(p, q2), _pmul(q, p2) return p, q def factor(self): # ('+'|'-') factor | power if self.peek() == ("OP", "-"): self.take() p, q = self.factor() return _pneg(p), q if self.peek() == ("OP", "+"): self.take() return self.factor() return self.power() def power(self): # atom ('**' INT)? p, q = self.atom() if self.peek() == ("OP", "**"): self.take() kind, val = self.take() if kind != "INT": self.fail(f"** needs a non-negative integer exponent, got {(kind, val)!r}") p, q = _ppow(p, val), _ppow(q, val) return p, q def atom(self): # INT | NAME | '(' expr ')' kind, val = self.take() if kind == "INT": return ({(0, 0): Fraction(val)} if val else {}), dict(_ONE) if kind == "NAME": return {((1, 0) if val == "d" else (0, 1)): Fraction(1)}, dict(_ONE) if (kind, val) == ("OP", "("): v = self.expr() if self.take() != ("OP", ")"): self.fail("missing ')'") return v self.fail(f"unexpected token {(kind, val)!r}") def parse_entry(text): """(P, Q): the entry string as the exact rational function P(d, w) / Q(d, w) (bivariate dict polynomials over Fraction; Q is the product of the denominators met, never cancelled against P).""" return _Parser(text).parse() # --------------------------------------------------------------------------- # 2. Univariate helpers (ascending Fraction lists; [] is the zero polynomial) # --------------------------------------------------------------------------- def _utrim(p): while p and p[-1] == 0: p.pop() return p def _uadd(p, q): n = max(len(p), len(q)) return _utrim([(p[i] if i < len(p) else 0) + (q[i] if i < len(q) else 0) for i in range(n)]) def _uscale(p, c): return _utrim([c * v for v in p]) if c else [] def _umul(p, q): if not p or not q: return [] r = [Fraction(0)] * (len(p) + len(q) - 1) for i, a in enumerate(p): if a: for j, b in enumerate(q): r[i + j] += a * b return _utrim(r) def _upow(p, n): r = [Fraction(1)] for _ in range(n): r = _umul(r, p) return r def _udivmod(p, q): """Exact polynomial division with remainder over Q.""" p = list(p) if not q: raise ZeroDivisionError("polynomial division by zero") dq, lq = len(q) - 1, q[-1] out = [Fraction(0)] * max(0, len(p) - dq) while len(p) - 1 >= dq and p: c = p[-1] / lq k = len(p) - 1 - dq out[k] = c for i, b in enumerate(q): p[k + i] -= c * b _utrim(p) if not p: break return _utrim(out), p def _ugcd(p, q): """Monic gcd over Q (Euclid); gcd(0, 0) = [].""" p, q = _utrim(list(p)), _utrim(list(q)) while q: _, r = _udivmod(p, q) p, q = q, r if not p: return [] lc = p[-1] return [v / lc for v in p] def _by_power_of_d(P): """P(d, w) as {exponent of d: univariate poly in w}.""" out = {} for (a, b), v in P.items(): lst = out.setdefault(a, []) if len(lst) <= b: lst.extend([Fraction(0)] * (b + 1 - len(lst))) lst[b] += v return {e: _utrim(l) for e, l in out.items() if _utrim(list(l))} def _binom(n, k): r = 1 for i in range(k): r = r * (n - i) // (i + 1) return r def _subst_d(P): """P(4 - 2*eps, w) as {k: P_k(w)} (univariate Fraction lists in w), exact.""" c0, c1 = D_SUBST out = {} for a, ps in _by_power_of_d(P).items(): for k in range(a + 1): coef = Fraction(_binom(a, k)) * c0 ** (a - k) * c1 ** k out[k] = _uadd(out.get(k, []), _uscale(ps, coef)) return {k: v for k, v in out.items() if v} def eps_grade(P, Q, neps): """{k: (N_k, D_k)} for k = 0..neps: the eps^k coefficient of P/Q at d = 4 - 2*eps as the univariate rational function N_k(w) / D_k(w), D_k = Q_0^(k+1), by the recursion N_k = P_k Q_0^k - sum_{m=1..k} Q_m N_{k-m} Q_0^(m-1); exact, uncancelled. Absent k means the coefficient is identically zero.""" Pk, Qk = _subst_d(P), _subst_d(Q) Q0 = Qk.get(0, []) if not Q0: raise ParseError("the denominator vanishes identically at d = 4 (a pole in eps): outside the grading") N = {} out = {} for k in range(neps + 1): nk = _umul(Pk.get(k, []), _upow(Q0, k)) for m in range(1, k + 1): nk = _uadd(nk, _uscale(_umul(_umul(Qk.get(m, []), N[k - m]), _upow(Q0, m - 1)), Fraction(-1))) N[k] = nk if nk: out[k] = (nk, _upow(Q0, k + 1)) return out def cancel(num, den): """num/den in lowest terms as integer coefficient lists (ascending Fractions with denominator 1): the common factor over Q divided out, both lists scaled to integers, the joint content (the gcd of every coefficient of both) divided out, the denominator's leading coefficient made positive -- the form sympy's cancel() gives.""" num, den = _utrim(list(num)), _utrim(list(den)) if not den: raise ZeroDivisionError("cancel: zero denominator") if not num: return [], [Fraction(1)] g = _ugcd(num, den) if len(g) > 1: num, r1 = _udivmod(num, g) den, r2 = _udivmod(den, g) if r1 or r2: raise ParseError("internal: the gcd does not divide both polynomials") L = 1 for v in num + den: L = L * v.denominator // math.gcd(L, v.denominator) ni = [v * L for v in num] di = [v * L for v in den] G = 0 for v in ni + di: G = math.gcd(G, int(v)) if G > 1: ni = [v / G for v in ni] di = [v / G for v in di] if di[-1] < 0: ni = [-v for v in ni] di = [-v for v in di] if len(di) == 1 and len(ni) > 1: # a constant denominator under a non-constant numerator is divided into the numerator, as sympy's # expression-level cancel() does (rational numerator coefficients over 1; a constant over a constant stays # the integer pair p/q); none of the shipped entries has a constant denominator return [Fraction(v) / di[0] for v in ni], [Fraction(1)] return [Fraction(v) for v in ni], [Fraction(v) for v in di] def graded_lists(A, rows, neps): """{(i, j, k): (num, den)} over the nonzero entries A[i][j] (i, j in rows; the connection's row-major string matrix) and k = 0..neps with a nonzero eps^k coefficient: cancel(eps_grade(...)) as ascending integer-valued Fraction lists. Every list is asserted equal to its uncancelled form as a rational function (num * D_k == den * N_k exactly) before it is returned -- a failed identity is refused by name.""" out = {} for i in rows: for j in rows: P, Q = parse_entry(A[i][j]) if not P: continue for k, (nk, dk) in eps_grade(P, Q, neps).items(): num, den = cancel(nk, dk) if _umul(num, dk) != _umul(den, nk): raise ParseError(f"internal: entry ({i}, {j}) eps^{k}: the cancelled form is not the graded " f"rational function (num*D_k != den*N_k)") out[(i, j, k)] = (num, den) return out def _poly_str(p): terms = [] for e in range(len(p) - 1, -1, -1): v = p[e] if v: mon = "w" if e == 1 else (f"w**{e}" if e > 1 else "") c = str(v.numerator) if v.denominator == 1 else f"{v.numerator}/{v.denominator}" terms.append((c + "*" + mon) if (mon and c not in ("1", "-1")) else ((("-" if c == "-1" else "") + mon) if mon else c)) return " + ".join(terms).replace("+ -", "- ") if terms else "0" def singular_certificate(lists): """Assert that every denominator in `lists` ({key: (num, den)}) has all its roots in SING = {0, 1, 9}: each denominator is divided by w, (w - 1) and (w - 9) as often as they divide it; the residual must be a constant. Returns the set of the roots met (a subset of SING). A non-constant residual is refused by name with the entry key and the residual's coefficients (it has a root outside SING).""" met = set() letters = [(r, [Fraction(-r), Fraction(1)]) for r in SING] for key, (_num, den) in lists.items(): p = _utrim(list(den)) if not p: raise ParseError(f"entry {key}: zero denominator") for r, lin in letters: while len(p) > 1: q, rem = _udivmod(p, lin) if rem: break p = q met.add(r) if len(p) != 1: raise ParseError(f"entry {key}: the denominator has a root outside {set(SING)}: after dividing out w, w - 1 " f"and w - 9 the residual {_poly_str(p)} is not a constant") return met