Precedence is call depth: one line through my C lexer and parser

Line 6 of Sprout's f-string test is when f"{name}-{x + y}" == "Sam-15":, and the parser never sees an f-string in it.

My lexer turns those 35 characters into 22 tokens, rewriting the f-string into a chain of + on the way, and the parser folds the tokens into one comparison. I wrote both in plain C for Sprout, with no parser generator, and the test around that line touches indentation, f-strings and precedence at once.

Five lines from fstrings.sprout

The program is lines 2 to 7 of src/tests/fstrings.sprout. The file goes on with an otherwise: branch, which I’ve left off.

make name = "Sam"
make x = 5
make y = 10

when f"{name}-{x + y}" == "Sam-15":
    show "ok: fstring with expression"

It has a blank line that must not count, an indented block, an f-string with an expression inside, and + and == fighting over the same operands. If any stage gets its part wrong, the test fails.

Characters to tokens: a stack of indent widths

The parser never measures a space. The lexer emits NEWLINE, INDENT and DEDENT instead, so a block is an ordinary grammar rule, block = ":" NEWLINE INDENT { statement } DEDENT, and the logic fits in one 37-line tokenize function:

static void tokenize(const char *src, int len) {
  int indents[256]; int top = 0; indents[0] = 0;
  ...
    while (i < len && (src[i] == ' ' || src[i] == '\t')) { spaces++; i++; }
    /* blank line or comment-only line: skip without affecting indentation */
    if (i >= len || src[i] == '\n' || src[i] == '\r' || src[i] == '~') {
      ...
      continue;
    }
    /* indentation changes — but NOT while inside ( ) [ ] { }, where leading space is just padding */
    if (g_bracket_depth == 0) {
      if (spaces > indents[top]) { if (top >= 254) fail(line, "this is nested too deeply (too many indentation levels)."); indents[++top] = spaces; push_tok(T_INDENT, NULL, 0, line); }
      while (spaces < indents[top]) { top--; push_tok(T_DEDENT, NULL, 0, line); }
      if (spaces != indents[top]) fail(line, "the indentation doesn't line up with the block.");
    }
    ...
    if (g_bracket_depth == 0) push_tok(T_NEWLINE, NULL, 0, line);
    ...
  while (top > 0) { top--; push_tok(T_DEDENT, NULL, 0, line); }
  push_tok(T_EOF, NULL, 0, line);
}

The stack starts as [0]. A deeper line pushes its width and emits one INDENT. A shallower line pops in a while, because one line can close several blocks, and landing between two open levels stops with “the indentation doesn’t line up with the block.” There’s no fixed unit, and a tab counts as one column, since spaces++ runs for both characters.

Sprout has no flag that prints tokens, so I traced everything below by hand from the C source, then checked it with a small harness that includes sprout.c and prints its real token array and tree. They match token for token. As a file of its own, our program comes out of that function like this.

MAKE IDENT(name) EQ STR("Sam") NEWLINE
MAKE IDENT(x) EQ NUM(5) NEWLINE
MAKE IDENT(y) EQ NUM(10) NEWLINE
WHEN LPAREN STR("") PLUS LPAREN IDENT(name) RPAREN PLUS STR("-")
     PLUS LPAREN IDENT(x) PLUS IDENT(y) RPAREN PLUS STR("") RPAREN
     EQEQ STR("Sam-15") COLON NEWLINE
INDENT SHOW STR("ok: fstring with expression") NEWLINE
DEDENT EOF

Blank line 5 left no trace: blank and comment-only lines are skipped before measuring, or an empty line would measure 0 and close every open block. Line 7 is four spaces deep, so the stack becomes [0, 4] and one INDENT goes out. At end of file the drain loop pops back to [0] and emits the DEDENT that closes the when.

Brackets switch indentation off

A long list shouldn’t need a backslash per line, so Sprout ignores newlines and indentation inside ( ), [ ] and { }. One global counter does it, updated by scan_token.

    case '[': push_tok(T_LBRACK, NULL, 0, line); g_bracket_depth++; i++; break;
    case ']': push_tok(T_RBRACK, NULL, 0, line); if (g_bracket_depth > 0) g_bracket_depth--; i++; break;

tokenize reads it at the start of a line, to decide whether leading spaces are indentation or padding, and at the end, to decide whether to emit NEWLINE. So make nums = [ ends at depth 1 and gets no NEWLINE, and the closing ] line ends at depth 0 and finishes the statement. Without the > 0 clamp, a stray ) would push the counter to -1, and the lexer would drop every NEWLINE and stop checking indentation until a later bracket brought it back to 0.

The f-string becomes a plus chain in the lexer

To desugar syntax is to rewrite it into syntax you already support. Sprout does it to f-strings in the lexer, so the AST (abstract syntax tree, the parser’s output) has no f-string node. When scan_token sees f", it hands off to scan_fstring, whose header comment is the design.

/* f"Hello, {name}!" desugars to  ( "Hello, " + (name) + "!" )  so it needs no new AST/eval. */
static void scan_fstring(const char *src, int *ip, int len, int line) {
  ...
  push_tok(T_LPAREN, NULL, 0, line);
  ...
      push_tok(T_PLUS, NULL, 0, line); push_tok(T_LPAREN, NULL, 0, line);
      ...
        scan_token(src, &i, len, line);

That’s where line 6’s 22 tokens come from. f"{name}-{x + y}" became ( "" + ( name ) + "-" + ( x + y ) + "" ). Three things about that rewrite matter:

• A string token always comes first, even an empty one. Sprout’s + concatenates when either side is text, so the leading "" makes the whole chain text.
• Every {...} gets its own parentheses. Without them our line would be "" + name + "-" + x + y + "", which glues 5 and then 10 onto the text and gives Sam-510. With them, x + y is added first.
• The inside goes through the normal scan_token, so the same file can check that f"len={length(items)}, first={items[0]}" is "len=3, first=1".

Ten functions, one per precedence level

Sprout’s parser is recursive descent, one C function per grammar rule. Each precedence level is its own rule, and each gets its operands from the next tighter one:

The when statement calls expression for its condition, and our tokens walk the ladder like this.

expression -> and_expr -> compare -> pipe_expr -> range_expr -> term
term    -> factor -> unary -> postfix -> primary: '(' so expression() again
  term    folds "" + (name) + "-" + (x + y) + "" left to right
  term    stops at ')', primary consumes it
term    sees '==', not one of its operators: returns
compare sees '==', asks pipe_expr for the right side: "Sam-15"
compare sees ':', no second comparison: returns

Nothing compares precedence numbers. term takes every +, the == waits for compare, and each ( ... ) from the f-string sends primary back to the top, so x + y is finished before the outer + sees it.

Three levels (and_expr, term, factor) run the same loop with different operators. Sprout writes that loop once.

static Expr *binary_level(Expr *(*next)(void), const TokType *ops, int nops, int logical) {
  Expr *left = next();
  for (;;) {
    int found = 0; TokType op = T_EOF;
    for (int k = 0; k < nops; k++) if (check(ops[k])) { op = ops[k]; found = 1; break; }
    if (!found) break;
    int line = peek().line; advance();
    Expr *right = next();
    Expr *e = new_expr(logical ? E_LOGICAL : E_BINARY, line);
    e->op = op; e->left = left; e->right = right; left = e;
  }
  return left;
}

left = e folds each operator onto the tree so far, and that one assignment is left-associativity. The tree it leaves for line 6 is below. Each (op left right) is one node.

(when (== (+ (+ (+ (+ "" name) "-") (+ x y)) "")
          "Sam-15")
  (show "ok: fstring with expression"))

Where precedence climbing would differ

Sprout doesn’t use precedence climbing, the standard alternative, where every operator gets a number and one loop decides how far to recurse. After an operator with precedence p, it parses the right side with a minimum of p + 1 if the operator is left-associative, or p if it’s right-associative. Operators at or above that minimum are swallowed into the right side, and looser ones return to the outer loop.

Sprout’s odd levels could live in that loop too: compare failing on a second operator is one check after right, and the pipe’s rewrite of x |> f(a) into f(x, a) goes where the node is built. The ladder gives each special rule, like compare’s ban on chaining, its own function, but costs one call per level per operand, so a lone 5 passes through all ten functions. The loop is shorter and turns the rules into if (op == ...) cases.

Tabs: one column to the lexer, four to the formatter

That spaces++ for tabs is the case I haven’t settled. sprout format counts a tab as four columns and the lexer counts one. Put four spaces on one line of a block and a tab on the next, and the formatter sees one level while the lexer pops back to [0], finds 1 doesn’t match 0, and stops with “the indentation doesn’t line up with the block.” I ran exactly that file: the lexer stops on the tab line, and sprout format happily prints both lines at four spaces.