Note: This post is part of a multipart series on building a LilyPond lexer/parser. The code, as it is being built throughout the series, can be found at https://github.com/gpit2286/broucku.

In the last part, I looked at why the Flex lexer and Bison parser are difficult to reuse outside of LilyPond itself. The largest problem was the shared state between Flex and Bison. So how do we remove the hidden state if it is at the center of this process? The goal I outlined was to make lexing a pure function of the input. The parser would solely own the context later.

The first question is to deduce what the parser actually needs to do its job. Only then can I decide which tokens to produce. The tokens we are looking for are not going to be a direct equivalent of what Flex and Bison produce. Some rules in Flex collapse into a single token kind. Some tokens that used to be one token split apart so the parser can make sense of them later.

The scanner with no memory

To make lexing a pure function, the scanner itself only needs to be a tiny machine. It is an Iterator over tokens and two pointers. One tells us where the current token starts and the other the current length. The overall design and many of the helper methods were highly inspired by the rustc lexer.

1
2
3
4
5
6
7
8

pub struct Scanner<'src> {
    /// An iterator of the chars in the given source code
    chars: Chars<'src>,
    /// The start byte of current token
    start: usize,
    /// The current length of current token
    current: usize,
}

The hidden power in the lexer is in the lex_range method. Because there is no state, I can point the scanner at any slice of the source and get the same tokens I would have gotten from the whole file. This is the rescanning I anticipated in part one that would make later re-parsing of sections possible.

This call is meant to be used without direct user input, though. Any caller that re-lexes has to ensure it is asking for a sane slice, so lex_range panics on a half-codepoint byte boundary, an out-of-range end, or a backwards range. It fails on purpose. If it fails, it was either a previous logical error of the lexer giving out an incorrect range or the caller calculating the range incorrectly.

What is a command?

This question is where the new scanner and the Flex lexer notably part ways. In the Flex lexer and Bison parser, exactly one character starts LilyPond commands: the backslash. And nearly every backslash expression ends up in the same place: lookup_identifier_symbol().¹ In other words, a command in LilyPond is not really a lexical category. It is a symbol lookup.

1

    Command { name: Span, quoted: bool, terminated: bool },

That is the data that is captured at lex time. You may notice the absence of any kind of typing, again by design. Three pieces of information are captured:

• The span of the name (symbol/identifier), whatever shape the name happened to take.
• Whether the name was spelled with quotes around it.
• Whether the quoted command was terminated. This follows the design pattern of the string literal.

What the name means, what it takes, and whether it even exists is the parser’s problem. I am not entirely sure how much weight the parser will put on quoted in the end. LilyPond treats "var" and var as the same symbol, and when used as an expression, \var and \"var" are resolved to the same place in the symbol table. But quoted is cheap to include, and the day you need to tell \var from \"var" apart is the day you would hate to have thrown it away. It is the same reasoning that we keep whitespace in the token stream. One day, at one time, someone downstream, maybe formatting, maybe an LSP, is going to want it. Even though the quoted field adds data usage to all TokenKind variants, this is negligible. The additional bool will live in padding that would exist regardless.²

The many shapes after a backslash

The backslash has more to say for itself than any other character in the language. There are four commands and one error, decided entirely by what the backslash was allowed to see first:

• \command: A backslash, then the longest symbol we can eat. The whole thing becomes one Command token whose name is exactly the span between the backslash and the end. \varA and \relative and \version all are scanned this way.

• \"command": The quoted spelling. On the Flex side, {SYMBOL} simply cannot carry a digit. The character class is letters and byte values 128 through 255, nothing else.³ So how do you write a command name that is not a symbol? The answer LilyPond settled on was to allow the quoted spelling. \violin1 and \"violin1" would be treated the same. They live in the same symbol table, they can reference the same data, and they can appear in the same places. The only difference is that \"violin1" (with quotes) is valid and the other is not.

• \1: string numbers like \1, \2, \5. What is interesting is that on the Flex side, this one does not go through lookup_identifier_symbol at all. Flex passes this to a {E_UNSIGNED} token, and the parser turns it straight into a StringNumberEvent.

• (.|\\.): Flex’s {SHORTHAND} rule is a single character or backslash plus any character. I understand why a regex lexer needs something like this. The items this catches include \( and \) for phrasing slurs and \< and \> for hairpins. But the rule reads a backslash and then (metaphorically) literally anything. LilyPond would likely benefit from restricting this to a set of symbols as opposed to the . regex… but that’s above my knowledge and pay grade.

• \: the error case. If there is nothing after the backslash at all, there is no grammar in either LilyPond or Scheme that wants a stray single backslash. So we produce the one error token the scanner knows how to make: IncompleteCommand.

What we lose without state

Because we are lexing all of these as just “commands,” we start losing some of the benefits the Flex and Bison combination are able to leverage. In Flex, each of these rules could resolve to a token in the middle of scanning, because the lexer could ask the parser-ish machinery what the name meant. Here they all agree on a Command with a name span, and the parser becomes the mythical sorting hat in the next phase.

Statelessness has a flip side, and it shows up in the lone marks too. Bare spellings like ~, (, [, ], and | all go through Flex’s {SHORTHAND} rule into a cascading set of lookups. This can assign a symbol like [ to the beginning of a beaming group or the start of a figured bass group.

Shorthands in the new scanner, because there is no backslash involved, come through as their own structural tokens: Tilde, ParenOpen, BracketOpen, BracketClose, Pipe. The same character is always the same token. This is then passed to the parser that acts as the judge, jury, and executioner of the provided tokens.

But again, the advantage of the new scanner is that it is deterministic regardless of how you got to it. Re-lexing a section to see what a user definition changed costs nothing⁴, because there is no state to warm up. No initialization files to re-scan.

Where we are going next

To sum it all up, commands were the most complicated part of the lexing, and rightfully so. In the Flex lexer nearly every backslash path ended up in lookup_identifier_symbol and here they all end up in the same Command arm.

The rest of the scanner is the supporting cast. There is some routine number/literal value lexing and a lot of Rust pattern matching. In the next part, I will start parsing these tokens together and building the context state machine.