28. Writing a scanner

Eighty lines

The last chapter described tokens. Now for the program that makes them. In the companion code it is a single function, scan, in companion/ts/src/scanner.ts: about eighty lines that take a string and return an array of tokens.

function scan(
  source: string,
  reporter: Reporter,
): Token[]

The reporter is where it sends error messages. Everything else happens inside. You met a small version of this loop in chapter 10. This is the real thing.

The state and the helpers

The two fingers are two numbers. There is also a line counter, for the source location:

let start = 0;   // where this token began
let current = 0; // the next char to read
let line = 1;

Around them sit a few tiny helper functions. They are closures, from chapter 6: arrow functions declared inside scan, so they can all see source, start and current. Here are the first three:

const atEnd = () =>
  current >= source.length;
const advance = () => source[current++];
const peek = () =>
  atEnd() ? '\0' : source[current];

advance reads a character and moves current past it. peek only looks. At the end of the source it returns '\0', a stand-in character that none of the scanner’s checks will match, so callers never have to deal with undefined. When a token is complete, add cuts its lexeme out of the source with slice, from start up to (not including) current:

const add = (type, literal = null) => {
  tokens.push({
    type,
    lexeme: source.slice(start, current),
    literal,
    line,
  });
};

(The real add also has type annotations. Here and below, the code is simplified from scanner.ts to fit your screen.)

The loop

Every round of the loop makes at most one token. It moves start up to current, reads one character, and lets a switch decide what that character begins. Step through it on a short line:

while (!atEnd()) {
  start = current;
  const c = advance();
  switch (c) {
    case ';': add(';'); break;
    case '<':
      add(match('=') ? '<=' : '<');
      break;
    case ' ': break;
    default:
      if (isDigit(c)) {
        while (isDigit(peek())) advance();
        add('number');
      } else if (isAlpha(c)) {
        while (isAlnum(peek())) advance();
        add('identifier');
      }
  }
}
// then: push the eof token

The real loop has the same shape, with a case for every kind of character:

while (!atEnd()) {
  start = current;
  const c = advance();
  switch (c) {
    case '(': case ')': case '{':
    // … the other one-character tokens
      add(c);
      break;
    case ' ': case '\r': case '\t':
      break;
    case '\n':
      line++;
      break;
    // … more cases
  }
}
tokens.push({ type: 'eof', lexeme: '',
  literal: null, line });

Notice add(c). Because a punctuation token’s type is its own spelling (chapter 27), the character c is the type. Whitespace cases do nothing, and a newline only bumps line. Neither makes a token.

Lookahead

Some characters can’t be decided alone. A < might be the whole token, or the first half of <=. The scanner has to glance at the next character before it commits.

peek is one way to glance. The other is match, which glances and then consumes the character, but only if it is the one expected:

const match = (expected) => {
  if (atEnd()) return false;
  if (source[current] !== expected) {
    return false;
  }
  current++;
  return true;
};

With it, each of !, =, < and > takes one line of the switch:

case '<':
  add(match('=') ? '<=' : '<');
  break;

Comments use the same trick. A / followed by another / starts a comment, which runs to the end of the line:

case '/':
  if (match('/')) {
    while (peek() !== '\n' && !atEnd()) {
      advance();
    }
  } else {
    add('/');
  }
  break;

The comment loop uses peek, not advance, to test for '\n'. That leaves the newline unread, so the next round of the main loop handles it in the '\n' case and line stays correct.

Always the biggest bite

When the scanner sees <=, it could make two tokens, < and =. It doesn’t: match grabs the = whenever it can. The same rule runs all through the scanner. A run of digits is one number, not several. And orchid is one identifier, not the keyword or followed by chid.

One of the Lox tests feeds the scanner !===. Taking the longest token each time gives != and then ==, never ! followed by === or anything else. Try it below. This is a pocket-sized scanner written just for this page, with the same habits:

function scan(src) {
  const out = [];
  let start = 0;
  let cur = 0;
  const peek = () => src[cur] ?? '\0';
  const match = (c) => {
    if (peek() !== c) return false;
    cur++;
    return true;
  };
  const isD = c => c >= '0' && c <= '9';
  while (cur < src.length) {
    start = cur;
    const c = src[cur++];
    if (c === ' ') continue;
    if ('<>=!'.includes(c)) match('=');
    else if (isD(c)) {
      while (isD(peek())) cur++;
    }
    out.push(src.slice(start, cur));
  }
  return out;
}

console.log(scan('!==='));
console.log(scan('n <= 12'));
console.log(scan('3 >= 30 != 4'));

JavaScript’s spec states the same rule in its own words: source text is scanned left to right, “repeatedly taking the longest possible sequence of code points as the next input element”^[2]. That is why a+++b in JavaScript means a++ + b.

When the switch finds nothing that fits, the default case reports “Unexpected character.” through the reporter, with the current line, and carries on. One run can report every bad character, instead of stopping at the first.

Your turn

The core exercise is a complete little scanner for arithmetic. The extra one is all about lookahead and maximal munch.

function isDigit(c) {
  // your code here
}

function scan(src) {
  const out = [];
  // your code here
  return out;
}

console.log(scan('1+23*4'));

function scanOps(src) {
  const out = [];
  // your code here
  return out;
}

console.log(scanOps('!==='));

What you learned

• A scanner turns characters into tokens. Drip’s keeps two pointers: start, where the token began, and current, the next character to read. Each token’s lexeme is source.slice(start, current).
• The main loop reads one character, and a switch decides what it begins. Whitespace and comments make no tokens, and '\n' bumps the line count.
• Lookahead: peek looks without consuming, and match consumes only when the next character is the expected one.
• Maximal munch: always take the longest token that fits, so <= is one token and orchid is one identifier.

Next: the tokens with the most going on inside them: numbers, strings, names and keywords.