Lexie meets a small Lisp

A Lisp arrives with a bag of parentheses. It insists they are all necessary.

Before we can discuss that, somebody has to read them.

Lexie 1.0.0 generates Pooka lexers from TOML. Give it the spellings a language permits and it writes token classes, a scanner, and location helpers. It can generate a syntax highlighter too.

Let us give it a small Lisp-shaped language. We will read symbols, numbers, strings, parentheses, and quotes. Evaluation can wait outside with its coat on.

Make a place for it

Start a project and add the tools:

pooka new little_lisp
cd little_lisp
pooka add lexie --dev
pooka add poke --dev
pooka run -m lexie init

Lexie is available on Hex. It is a development dependency; the generated lexer needs only the standard library.

init creates .lexie/lexie.toml and adds .lexie/ to Git’s ignore rules. The specification stays in the local workshop. The generated source is what we commit.

Teach it the alphabet

Replace .lexie/lexie.toml with:

location-info = true

[output]
dir = "src"

[module]
name = "lisp"

[identifier]
start = ["a-z", "A-Z", "_+-*/=<>!?"]
continue = ["a-z", "A-Z", "0-9", "_+-*/=<>!?"]
token = "Symbol"

[punctuation]
items = ["(", ")", "'"]

[comments.line]
start = ";"
emit = false

[strings.double]
quote = "\""
escapes = true

The identifier rules allow names such as set-car! and nil?. A digit may continue a symbol, but cannot start one. Numbers have their own rules.

Parentheses and the single quote are punctuation. A semicolon starts a line comment, which the scanner consumes without emitting a token. Double-quoted strings allow escapes.

We have deliberately left define out of a keyword list. This little Lisp reads it as a symbol, just like pair. Its meaning is a question for a later stage.

Generate the modules:

pooka run -m lexie

They appear under src/lisp/: token.pooka, location.pooka, and lexer.pooka. output.dir chooses the source root; module.name chooses the module path beneath it.

Read a sentence

Replace src/main.pooka with:

module main

import lisp/lexer
import pooka/list

main() {
  let source = "; squares\n(set-car! pair 'nil?)"
  let tokens = lexer.lex(source)
    |> list.map(fn(lexeme) { lexeme.token })
  echo tokens
}

Run it with pooka run. Below the usual build and echo location information, the value is:

[LeftParen(), Symbol("set-car!"), Symbol("pair"), Quote(), Symbol("nil?"), RightParen(), End()]

The comment has gone. The punctuation has names. set-car! remains one symbol, despite looking mildly alarming to a lexer accustomed to a different language.

End() makes the end of the input explicit. A parser can ask for another token without inventing a separate convention for an empty list.

Keep the address

With location-info = true, lexer.lex returns lexemes: each carries a token and its span. Mapping to .token above deliberately discarded those addresses for a shorter display.

The addresses are worth keeping when something goes wrong. Add this to test/lisp.spec.pooka:

module lisp_test

import lisp/lexer
import lisp/token
import poke/should
import pooka/list

test "symbols keep their punctuation" {
  let tokens = lexer.lex("; squares\n(set-car! pair 'nil?)")
    |> list.map(fn(lexeme) { lexeme.token })
  should.equal(tokens, [
    token.LeftParen(),
    token.Symbol("set-car!"),
    token.Symbol("pair"),
    token.Quote(),
    token.Symbol("nil?"),
    token.RightParen(),
    token.End()
  ])
}

test "the symbol keeps its source address" {
  let symbol = lexer.lex("; squares\n(set-car! pair 'nil?)")
    |> list.at(1)
    |> should.be_some()
  should.equal(symbol.span.start.line, 2)
  should.equal(symbol.span.start.column, 2)
  should.equal(symbol.span.start.byte_offset, 11)
  should.equal(symbol.span.end.column, 10)
}

Run pooka test. The second test checks that set-car! begins just after the opening parenthesis on line two. Line and column numbers start at one. Byte offsets start at zero. The end position is just after the symbol, so the span can be used directly to slice its original text.

Columns count characters; offsets count UTF-8 bytes. Those are different measurements once a visitor brings a name outside ASCII.

If you only want token values, set location-info = false and regenerate. lexer.lex then returns tokens directly. The explicit lexer.lex_with_locations entry point still provides spans when a tool needs them.

What remains on the desk

This is a lexer, so an unmatched parenthesis is still a perfectly recognisable token. Deciding whether parentheses balance belongs to a parser. Deciding what a balanced expression means belongs further along.

That division is useful. We can test the spelling rules before we have a parser, and test the parser before we have anything worth evaluating.

Lexie’s guide covers the other configuration sections, including number formats and highlighting. There is also a smaller cookbook example with a binding and its source positions.

The Lisp still has its bag of parentheses. At least we now know where it put them.

— Peregrine Finch

· pooka, lexie, compilers, lisp