114. A small Python front-end

Where does the loop end?

Here is a Python function:

def step(ps):
    for p in ps:
        p.x += p.vx
    return ps
print(1)

In JavaScript, a { opens the loop body and a } closes it. Here nothing closes anything. The body of for is everything indented further than the for, and it ends at return, because return moves back to the left. The spaces at the start of a line are syntax.

That sounds like a problem for a parser. The parsers you wrote in Part III ignore whitespace. Python’s own answer is neat: let the tokenizer measure the spaces, and turn each change into a token. The parser never sees a space.

A stack of widths

Step through the tokenizer on that function:

def step(ps):
    for p in ps:
        p.x += p.vx
    return ps
print(1)

This is the core of frontend-python/src/tokens.ts, simplified (the real one also expands tabs to the next multiple of 8 and skips blank and comment-only lines):

const indents = [0];
// at the start of every logical line:
let col = 0;
while (src[i] === ' ') { col++; i++; }
let top = indents[indents.length - 1];
if (col > top) {
  indents.push(col);
  toks.push({ type: 'indent' });
} else {
  while (col < top) {
    indents.pop();
    toks.push({ type: 'dedent' });
    top = indents[indents.length - 1];
  }
  if (col !== top) {
    err('inconsistent indentation');
  }
}

At the end of the file, one dedent is pushed for every width still on the stack above 0, so every block that was opened gets closed.

Here is the same algorithm in JavaScript, working on a list of lines. Change the indentation and watch the tokens:

function indents(lines) {
  const stack = [0];
  const out = [];
  for (const line of lines) {
    let col = 0;
    while (line[col] === ' ') col++;
    if (col === line.length) continue;
    let top = stack[stack.length - 1];
    if (col > top) {
      stack.push(col);
      out.push('INDENT');
    } else {
      while (col < top) {
        stack.pop();
        out.push('DEDENT');
        top = stack[stack.length - 1];
      }
      if (col !== top) {
        throw new Error('inconsistent');
      }
    }
    out.push(line.trim());
  }
  while (stack.length > 1) {
    stack.pop();
    out.push('DEDENT');
  }
  return out;
}

const src = [
  'for p in ps:',
  '    p.x += 1',
  '    if p.x > 9:',
  '        p.x = 0',
  'print(ps)',
];
console.log(indents(src).join('\n'));

Brackets switch it off

Python lets a long expression run over several lines if it is inside brackets:

ps.append(P(float(i),
            1.0))

The second line’s indentation means nothing, and there is no NEWLINE between the two lines: they are one logical line. The tokenizer keeps a depth counter: (, [ and { add one, the closing brackets subtract one, and while depth > 0 a line end produces no NEWLINE and the next line’s width is not measured.

The part of Python it accepts

Viscosity doesn’t need all of Python. It needs the part that numeric, data-heavy code uses, and it needs to know exactly where that part ends. The parser accepts:

• def functions, return, pass, break, continue, global
• @dataclass classes with annotated fields
• if / elif / else, while, for x in ...
• assignment, += and friends, x: float = ...
• arithmetic, comparisons, and / or / not, calls with keyword arguments, lists like [] and [a, b], import and from ... import

Everything else is refused with a clear message. These are real ones:

list comprehensions: not supported by
Viscosity's Python subset at line 1
near 'for'
dict and set literals: not supported …
slices: not supported …
default parameter values: not …
chained comparisons: not supported …
'try': not supported …

When the parser refuses, the plugin catches the error, returns an empty module, and emit returns the file exactly as it was. Nothing is half-transformed. The cost is that the reason stays inside the plugin: viscosity explain only says “No arrays of objects found.”

Why refuse chained comparisons, which look harmless? Because they mean something else in JavaScript. Python reads 1 < 3 < 2 as 1 < 3 and 3 < 2, so it is False^[3]. JavaScript reads (1 < 3) < 2, which is true < 2, which is true. A parser that treated it as an ordinary binary operator would build the wrong tree.

Blocks and binding powers

With INDENT and DEDENT in the stream, Python’s block rule is short. This is block() from parser.ts:

function block() {
  op(':');
  if (peek().type !== 'newline') {
    return simpleLine(); // if x: y = 1
  }
  p++;                   // NEWLINE
  if (peek().type !== 'indent') {
    fail('expected an indented block');
  }
  p++;                   // INDENT
  const body = [];
  while (peek().type !== 'dedent' &&
         peek().type !== 'eof') {
    body.push(...statement());
  }
  p++;                   // DEDENT
  return body;
}

It is the same recursive descent as Part III, with INDENT for { and DEDENT for }. Statements start with a keyword (def, for, …) and are parsed by one function each. Expressions use binding powers, as in chapter 33, from one table:

const BIN = {
  or: 1, and: 2,
  '<': 4, '==': 4, in: 4, 'not in': 4,
  is: 4, 'is not': 4,
  '|': 5, '^': 6, '&': 7, '<<': 8,
  '+': 9, '-': 9,
  '*': 10, '/': 10, '//': 10, '%': 10,
};

(Trimmed.) Two operators are two words, not in and is not, so the parser looks one token ahead to spot them. And elif is handled with a small trick: the parser rewrites the elif token to if and parses the rest as a nested if statement in the else branch.

Your turn

function nest(toks) {
  return toks;
}

function logicalLines(src) {
  return src.split('\n');
}

What you learned

• Indentation tokens turn significant whitespace into INDENT and DEDENT, using a stack of open-block widths that starts at 0.
• Inside brackets, line ends and indentation don’t count: one logical line can span several physical lines.
• The Python subset covers functions, dataclasses, lists, loops, if, assignment, arithmetic and calls. Anything else is refused, and the file is left exactly as it was.
• After tokenizing, Python parses with the same recursive descent and binding powers as any other language.