"""A tokenizer, a recursive-descent parser and a tree-walk evaluator, in which associativity is a *parameter* instead of a property of the code. There is only ONE parser here. `Parser` reads a table of precedence levels and, for each level, a fold direction. The tokenizer, the node types and the evaluator are shared, so when two runs disagree, the disagreement can only have come from the fold. THE LINE -------- Inside `binary`, immediately after an operator is consumed: rhs = self.tighter(level) # left: take ONE operand, let the loop fold rhs = self.binary(level) # right: swallow the whole REST of the chain That is the entire difference between `2-3-4 == -5` and `2-3-4 == 3`. It is not a typo-shaped bug. `rhs = self.binary(level)` is exactly how a real parser implements a right-associative operator, which is why the `^` level in the table below asks for it on purpose: the same edit is a bug for `-` and the fix for `^`. EXACT ARITHMETIC ---------------- Every number is a `fractions.Fraction`, so "the two parsers agree" is exact equality and never a rounding artifact -- which matters, because in floating point even `+` is not associative and the comparison would be measuring IEEE 754 instead of the parser. No clock, no randomness, no floats: a result here is a function of (source, assoc) alone. """ from fractions import Fraction # --- Tokenizer: characters -> a flat list of (kind, value) pairs SYMBOLS = "+-*/^()" def tokenize(source): """`2-3-4` -> [('num', 2), ('-', '-'), ('num', 3), ('-', '-'), ('num', 4), ('eof', None)] Symbols carry themselves as their kind, so the parser can test a token directly against an entry in `LEVELS` without a second lookup table. The trailing `eof` makes `peek` total: no bounds check anywhere in the parser. """ tokens, i = [], 0 while i < len(source): char = source[i] if char.isspace(): i += 1 elif char.isdigit(): start = i while i < len(source) and source[i].isdigit(): i += 1 tokens.append(("num", int(source[start:i]))) elif char in SYMBOLS: tokens.append((char, char)) i += 1 else: raise SyntaxError(f"stray {char!r} at offset {i}") tokens.append(("eof", None)) return tokens # --- The tree: three node kinds, and that is the whole language class Num: """A literal. Holds a Fraction so the evaluator never has to convert.""" __slots__ = ("value",) def __init__(self, value): self.value = Fraction(value) def __repr__(self): return str(self.value) class Neg: """Prefix minus. A separate node kind, not a `Bin` with a zero on the left, because it is parsed at a different level and the demo needs to be able to say that unary minus is *not* where the associativity bug lives. """ __slots__ = ("operand",) def __init__(self, operand): self.operand = operand def __repr__(self): return f"(-{self.operand!r})" class Bin: """An infix application. `repr` is fully parenthesized on purpose: the shape of this string IS the result the demo is measuring. """ __slots__ = ("op", "left", "right") def __init__(self, op, left, right): self.op, self.left, self.right = op, left, right def __repr__(self): return f"({self.left!r} {self.op} {self.right!r})" # --- Parser: one table of levels, one fold direction per level # Loosest first. Index in this tuple IS the precedence: `binary(0)` is the # whole expression, `binary(len(LEVELS) - 1)` is the tightest infix level. LEVELS = (("+", "-"), ("*", "/"), ("^",)) CORRECT = ("left", "left", "right") # what every real language does FLIPPED = ("right", "right", "right") # the bug, in both arithmetic levels ADD_FLIPPED = ("right", "left", "right") # the bug in `expr()` only class Parser: """Recursive descent, with the recursion driven by `LEVELS` rather than by one hand-written function per level. The two shapes are behaviourally identical (the commentary checks 11,232 cases); the table is used here so that `assoc` can be a parameter instead of an edit. """ def __init__(self, tokens, assoc=CORRECT): if len(assoc) != len(LEVELS): raise ValueError("need one fold direction per precedence level") self.tokens, self.pos, self.assoc = tokens, 0, assoc def peek(self): return self.tokens[self.pos][0] def take(self): token = self.tokens[self.pos] self.pos += 1 return token def parse(self): node = self.binary(0) if self.peek() != "eof": raise SyntaxError(f"trailing {self.peek()!r}") return node def tighter(self, level): """Whatever binds one notch tighter than `level`. Below the last infix level there is no next table row, so control drops out to prefixes. """ if level + 1 < len(LEVELS): return self.binary(level + 1) return self.unary() def binary(self, level): node = self.tighter(level) while self.peek() in LEVELS[level]: op = self.take()[0] if self.assoc[level] == "right": # Re-enter the SAME level: this call consumes the entire rest # of the chain, so the `while` never gets a second turn and # the tree leans right. rhs = self.binary(level) else: # One operand only. The loop does the folding, and each turn # buries the tree built so far one node deeper on the left. rhs = self.tighter(level) node = Bin(op, node, rhs) return node def unary(self): if self.peek() == "-": self.take() # Not `self.unary()`: prefix minus binds LOOSER than `^`, so # `-2^2` is -(2^2) = -4, matching Python's `-2**2`. return Neg(self.binary(len(LEVELS) - 1)) return self.atom() def atom(self): kind, value = self.take() if kind == "num": return Num(value) if kind == "(": node = self.binary(0) if self.take()[0] != ")": raise SyntaxError("unclosed '('") return node raise SyntaxError(f"expected a number or '(', got {kind!r}") # --- Evaluator: walk the tree, post-order def evaluate(node): """Post-order walk. Note what is NOT here: no precedence, no associativity, no operator table. By the time a tree exists, every grouping question has already been answered by the parser -- which is why a one-line parser change can move an answer without the evaluator changing at all. """ if isinstance(node, Num): return node.value if isinstance(node, Neg): return -evaluate(node.operand) left, right = evaluate(node.left), evaluate(node.right) if node.op == "+": return left + right if node.op == "-": return left - right if node.op == "*": return left * right if node.op == "/": if right == 0: raise ZeroDivisionError("division by zero") return left / right if node.op == "^": if right.denominator != 1: raise ValueError("fractional exponent would leave the rationals") return left ** right raise ValueError(f"unknown operator {node.op!r}") def parse(source, assoc=CORRECT): return Parser(tokenize(source), assoc).parse() def run(source, assoc=CORRECT): return evaluate(parse(source, assoc))