Experiments and implementations · Intermediate

Build a scanner for a small expression language

Implement a position-aware scanner and test complete numbers, identifier boundaries, whitespace, end of input and unknown characters.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Specify the scanner contract
  2. Prepare a reproducible run
  3. Advance at the current position
  4. Compare complete token sequences
  5. Treat deliberate rejection as a passing test
  6. Explore boundaries one change at a time
  7. Exercise and worked answer
  8. Ask Logeia about this articleCheck your understanding

Specify the scanner contract

Start with the source 12 + price_2 and predict four output tokens: a number, an addition operator, a name and an end marker. Represent each token as a triple of kind, original spelling and starting position. Keep the number spelling as text for now; converting it to a numeric value is a separate operation. Retaining that spelling also leaves room for later rules about leading zeros. Positions in this experiment are Python string indices, not offsets into UTF-8 encoded bytes. Write the expected starts beside the source before executing anything: zero, three and five. That independent expected sequence is the test oracle. Do not redefine the correct answer simply to match whatever the implementation prints.

Prepare a reproducible run

Use the complete code below with Python 3.12 or a compatible later version; no third-party package is required. Save it as scanner.py and run python scanner.py. Integer spellings use ASCII digits. Names start with an ASCII letter or underscore and may subsequently contain digits. Operators and parentheses are single-character tokens. The whitespace predicate is intentionally separate from the number and identifier rules. A non-ASCII name or digit-like character is therefore outside this teaching language, even if Python itself accepts it in some context. This is not an implementation of a production language’s Unicode identifier policy. The program reads only short literals embedded in the test and creates no database or persistent test data. Record the interpreter version alongside any changes to these recognition rules.

Advance at the current position

The variable i denotes the next unread character. Whitespace advances it by one; otherwise a regular expression must match at exactly that position. Using search instead of match would allow the scanner to jump over an invalid character and find a convenient later token. A digit sequence is consumed as a whole, so 12 remains one literal rather than becoming separate 1 and 2 tokens. Every successful iteration advances by a positive spelling length. An alternative that matches an empty string would break that progress argument and could create an infinite loop. Once the source is consumed, append one EOF token with an empty spelling and the end position. Even an empty source has this token, giving the parser one consistent way to recognize termination.

Compare complete token sequences

The final line prints the triples for 12, +, price_2 and EOF in that order. Assertions compare spelling and position, so recognizing the right numeric value with a wrong source offset still fails. For a source containing two spaces, only the EOF at position two remains. Omitting whitespace tokens does not mean forgetting to advance the source position. The 12a test intentionally produces two tokens. This scanner does not decide whether two expressions require an operator between them; the parser later rejects the leftover name. Preserve that separation instead of adding unrelated grammar decisions to the scanner. Inspect the printed tuples against the original indexed string, and explain which input characters each token consumed before moving to the parsing experiment.

python
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


source = "12 + price_2"
assert scan(source) == [('NUM','12',0), ('+','+',3), ('NAME','price_2',5), ('EOF','',12)]
assert scan("  ") == [('EOF','',2)]
assert scan("12a")[:2] == [('NUM','12',0), ('NAME','a',2)]
try:
    scan("1 + @")
except SyntaxError as error:
    assert str(error) == 'character at 4'
else:
    raise AssertionError('invalid character accepted')
print(scan(source))

Treat deliberate rejection as a passing test

For 1 + @, the expected outcome is a SyntaxError naming position four. The program catches that exception and checks its message, so the overall test exits successfully when rejection works as intended. A passing test here does not mean that the invalid source was accepted. Replace @ with whitespace and scanning succeeds, but the remaining 1 + still cannot be parsed as a complete expression. This counterexample separates scanner success from program validity. If the original rejection test stops failing, inspect whether the pattern became broader or recognition started searching beyond the current position. Compare the exception message and source offset rather than terminal colors or a complete formatted traceback, which can vary across environments without changing the underlying diagnostic contract.

Explore boundaries one change at a time

Rename the variable to _price2 and predict one NAME token. Rename it to price-2 and expect a name, a subtraction token and a number. Allowing hyphens inside identifiers would change that decision and must be coordinated with the grammar. A proposed <= operator raises another choice: should a two-character rule run before one-character alternatives, and how is the longest valid spelling selected? Neither comparison operator exists in the published teaching implementation. Do not infer a feature merely because a regular expression could be extended to recognize it. Vary whitespace, identifier length and the location of an invalid character separately. Small controlled inputs expose the recognition contract more clearly than a large speed benchmark that changes several conditions at once.

Exercise and worked answer

Write the complete output for a12 + 003 before running the scanner. The answer is NAME a12 at position zero, + at position four, NUM 003 at position six, and EOF at position nine. Notice that the scanner has not converted 003 to the numeric value three. If the language later rejects leading zeros, retaining the original spelling makes that validation possible. For a second exercise, prepend two spaces to 1 + @. The invalid character moves to position six even though the sequence of preceding token kinds is unchanged. A test comparing kinds alone would miss that diagnostic error. Once you can explain both cases, continue with recursive descent to build trees from the token sequence. Keep the saved file as a baseline; no server or external connection remains to shut down.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 20

Choose a learning path