Test tree structure rather than arithmetic answers
This experiment constructs a parser, not a calculator. For 1 + 2 * 3 the root must be addition; for (1 + 2) * 3 it must be multiplication. Both inputs contain three integers and the same operator spellings, yet their parent-child relationships differ. Tests compare complete nested tuples because a numeric answer can accidentally conceal a wrong grouping. Each node follows one representation rule: a number has a num tag and value, a name has a name tag and spelling, and a binary operation has an operator tag and two children. Parentheses influence the construction but do not remain as independent nodes. Draw both trees before executing the implementation and explain why the root changes.
Map grammar levels to functions
Implement three grammar levels. An expression combines terms with addition or subtraction; a term combines atoms with multiplication or division; an atom is a number, name or parenthesized expression. The term function finishes its inner multiplication work before returning to the expression function. When atom sees an opening parenthesis, it calls expr and then requires a closing parenthesis after that call returns. The same expression rules therefore work inside nested parentheses. We avoid directly left-recursive calls that could recur without consuming input. Unary minus, exponentiation and function calls are outside this grammar, even if similar-looking Python expressions support them. Follow exactly how far each function advances through the token list instead of importing assumptions from the implementation language.
Construct left associativity explicitly
Start the input 8 - 3 - 1 with the tree for 8 in left. Reading the next subtraction replaces left with a node containing 8 and 3. Reading the following subtraction wraps that whole tree as the left child of another node, with 1 on the right. Earlier structure is preserved as part of a larger tree rather than discarded. An evaluator can subsequently follow the tree without implementing another associativity rule. Replacing the right operand parser with a recursive call to an entire expression can instead create a right-associated tree. Choose subtraction as a diagnostic input because its result exposes this difference. Small integer additions can produce identical answers under different groupings and therefore provide a weaker test of the parser’s intended structure.
Run the complete standalone file
Save all of the code as parser.py and execute it using Python 3.12 or a compatible later version. It includes the scanner, so it does not depend on modifying the file from the previous experiment. Token kinds and positions retain the same contract. The printed tree has + at the root, * as its right child and - inside that multiplication. There is no parenthesis node. The program checks two expected valid trees and three deliberately invalid inputs, exiting successfully only after those assertions complete. This is evidence for the stated short examples, not a guarantee about arbitrarily deep or large input. Recursive call depth and token storage remain resource limits that an externally exposed parsing service would need to address separately.
import re
def scan(source):
tokens = []
i = 0
while i < len(source):
if source[i].isspace():
i += 1
continue
match = re.match(r'[0-9]+|[A-Za-z_][A-Za-z_0-9]*|[()+*\-/]', source[i:])
if not match:
raise SyntaxError(f'character at {i}')
word = match.group()
kind = 'NUM' if word.isdecimal() else 'NAME' if word[0].isalpha() or word[0] == '_' else word
tokens.append((kind, word, i))
i += len(word)
tokens.append(('EOF', '', i))
return tokens
class Parser:
def __init__(self, source):
self.tokens = scan(source)
self.i = 0
def take(self, kind):
token = self.tokens[self.i]
if token[0] != kind:
raise SyntaxError(f'expected {kind} at {token[2]}')
self.i += 1
return token
def atom(self):
kind, word, pos = self.tokens[self.i]
if kind == 'NUM':
self.take('NUM')
return ('num', int(word))
if kind == 'NAME':
self.take('NAME')
return ('name', word)
if kind == '(':
self.take('(')
node = self.expr()
self.take(')')
return node
raise SyntaxError(f'atom at {pos}')
def term(self):
left = self.atom()
while self.tokens[self.i][0] in ('*', '/'):
op = self.take(self.tokens[self.i][0])[0]
left = (op, left, self.atom())
return left
def expr(self):
left = self.term()
while self.tokens[self.i][0] in ('+', '-'):
op = self.take(self.tokens[self.i][0])[0]
left = (op, left, self.term())
return left
def parse(self):
tree = self.expr()
self.take('EOF')
return tree
assert Parser("1 + 2 * 3").parse() == ('+', ('num',1), ('*',('num',2),('num',3)))
assert Parser("8 - 3 - 1").parse() == ('-', ('-',('num',8),('num',3)), ('num',1))
for source, expected in [("1 2", 'expected EOF at 2'), ("(1+2", 'expected ) at 4'), ("", 'atom at 0')]:
try:
Parser(source).parse()
except SyntaxError as error:
assert str(error) == expected
else:
raise AssertionError(source)
print(Parser("12 + 3 * (4 - 1)").parse())Require the entire input to be consumed
After expr returns a tree, parse requires EOF. This rejects 1 2 instead of pretending that the source contained only the first valid expression. The diagnostic reports an expected EOF at position two. For (1+2, the internal expression can be constructed, but a closing parenthesis is missing at position four. Empty input fails at position zero because there is no atom. These are different incomplete states, not one error repaired by blindly appending a character. Checking expected failures prevents a change that merely makes ordinary examples work while disabling rejection. Inspect what was expected and where the input was examined. Line numbers and source excerpts can improve a real diagnostic, but they depend on the underlying offset being correct first.
Extend a specification before extending code
A new operator weaker than addition could be handled by another grammar level outside expr. A right-associative operator may require a different construction from the loop that repeatedly updates left. Specify the expected tree first, then write rules that construct it, and only then modify the implementation. Parentheses provide another useful distinction: equal counts of opening and closing characters do not establish a grammatical nesting. The input )( has equal counts but does not satisfy the atom rule. Keep previous acceptance and rejection tests when extending the language so that an unrelated behavior does not change unnoticed. This exercise is about coordinating specification, tree representation, tests and implementation, rather than presenting an untested completed implementation of every proposed operator.
Exercise: distinguish two similar trees
Draw trees for 9 - (4 - 1) and 9 - 4 - 1. In the first, the root subtraction has another subtraction on its right. In the second, the root subtraction has the earlier subtraction on its left. Their later evaluated results are six and four, so parentheses are not decorative. Next predict the diagnostic for 1 + ): an atom is expected at position four. If the observed position differs, inspect scanner offsets before investigating when take advances the parser. A correct tree for valid input does not excuse an incorrect diagnostic contract for invalid input. When you can explain both the tree distinction and the rejection position, continue to evaluation with an explicit variable environment. The experiment creates no server or external state requiring cleanup.