Geometry, sweep, simulation, and parsing · HTML
At position i, choose a rule by character class; the rule consumes one nonempty maximal prefix and returns (type,value,next_i).
Recognition signals
- Input is a character stream rather than tokens
- Whitespace, numbers, names, and symbols follow different rules
- Longest match affects boundaries
- Later grammar depends on token type
- Invalid-character positions should be reported
False friends
| Signal | Why it is different |
|---|
| Splitting on individual characters | Multi-digit numbers, escapes, and unary symbols are cut incorrectly. |
| Expecting tokenization to solve nesting | Lexing recognizes words; precedence and parentheses still need a parser or stack. |
Core invariant
Before each loop, s[:i] has been completely and non-overlappingly tokenized; the next rule consumes at least one character or reports an error.
State, transition, and processing order
| Item | Definition |
|---|
| State | Pointer i, output tokens, current character class, and optional quote/escape mode. |
| Transition | Skip whitespace; maximally extend digits or names; emit known symbols; reject unknown characters. |
| Frontier / order | i is the sole boundary between parsed prefix and unknown suffix, and every successful branch advances it. |
Python skeleton
def tokenize(s):
tokens, i = [], 0
while i < len(s):
ch = s[i]
if ch.isspace():
i += 1
elif ch.isdigit():
j = i + 1
while j < len(s) and s[j].isdigit(): j += 1
tokens.append(('INT', int(s[i:j])))
i = j
elif ch.isalpha() or ch == '_':
j = i + 1
while j < len(s) and (s[j].isalnum() or s[j] == '_'): j += 1
tokens.append(('NAME', s[i:j]))
i = j
elif ch in '+-*/()':
tokens.append((ch, ch)); i += 1
else:
raise ValueError(f'unexpected character at {i}: {ch!r}')
return tokens
Correctness sketch
- Every rule starts at current i, so emitted tokens do not overlap.
- Digit and name loops consume the longest contiguous prefix in their class.
- Every branch advances i or throws, ensuring termination without silent skips.
- Induction shows the returned tokens reconstruct the non-whitespace input.
Complexity
| Time | Space | Parameters |
|---|
| O(n) | O(k) output | n characters and k emitted tokens |
Edge cases
- Empty input returns no tokens
- A multi-character token may end at EOF
- Unary minus is usually parser context
- Decide which Unicode letters are legal
- Quotes and escapes need extra modes
Error patterns
| Pattern | Why it fails / fix |
|---|
| A branch does not advance i | The scanner loops forever. |
| Always attaching minus to numbers | Subtraction and unary negation require grammar context. |
| Silently ignoring unknown characters | This shifts error location and fabricates valid-looking output. |
Selection and exclusion rules
- Separate lexical boundaries before nested grammar.
- Every rule must consume a nonempty prefix.
- Define precedence among competing longest matches.
- Carry source positions into errors and, when useful, tokens.
Original micro-example
| Part | Detail |
|---|
| Result | Tokens are NAME, +, INT, *, (, NAME, -, INT, ). |
| Scenario | Input sum_2 + 17*(x-3). |
| Walkthrough | Names and integers use maximal runs; symbols consume one character and whitespace is explicitly skipped. |
Recall prompts
My notes