After diving into compiler and parser creation with Crafting Interpreters, I wanted to apply it to something that would be helpful to me. As I do a lot of working with musical scores in LilyPond, I thought how great it would be to have an LSP (Language Server Protocol) server to help detect errors before I hit “compile.”

The state is the problem

Looking at the built-in lexer and parser, there are some significant challenges. The first one, and the largest one I anticipate dealing with, is that the Flex lexer and Bison parser are constantly communicating with each other about the state of the lexing. The lexer defines thirteen definitive states, however some of them are not interacting with the lexical states and rather just telling the overall system information.¹ The lexical states we are concerned with are:

• notes: Where we can actually enter music
• chords: Used for entering music in chord mode
• figures: Used for entering figured bass
• lyrics: You guessed it, used for entering lyrics
• markup: The markup system is used for entering text and symbols that are not in any other context. Primarily though, this is used for generating text such as instrumentation notes or music direction

For example, if we lexed a symbol/identifier c:

• In a notes context, it would be treated as the pitch of a note
• In a chords context, it would be treated as a C major chord
• In a lyrics context, it would be treated as the word “c”
• In a markup context, it would also be treated as the word “c”

And the deep state

But the lexical states are only half of the problem. Part of the reason the lexer needs to talk to the parser so often is because the user, through the Scheme (Guile) backend, can change the environment and/or overwrite anything except for the built-in lexical keywords.

Let’s go back to the example of a single letter symbol. This time let’s look at the letter b. You would expect that in a notes context, it would simply be the pitch “B.” Most of the time it is, but if the user switched the music language to German, it is now B-flat. h would be B natural. This can also happen in the drum mode where the user can switch the drums style. This not only changes the symbols that are accepted but all of a sudden the bass drum note can be below the staff and not on the bottom space.

Expressions such as \command present an even larger problem. Many commands are coded into the “startup” files for LilyPond and are read before the parsing of a user file begins. These commands are also not typed in any way. \command could create or modify markup, it could be a musical expression, it could be a string or another scalar value. And to build on this, within the user files, the user can overwrite any of these values (by design). This means that trying to check function arguments can’t only rely on built in command signatures. They need to be read from the LilyPond initialization files and then superseded by user definitions.

So how do we remove the state if it is the backbone of so many different pipelines within the lexer and parser? It truly can’t be zero state as described above. But rather, maybe thinking about it as “no hidden state.” Instead of the lexer carrying modes and pitch tables around internally, I want to make lexing a pure function² of the input.

Removing some of the state?

The question then becomes, “who is responsible for what?” In my design, I hope to accomplish:

• A lexer that produces output that does not change. Tokens are the same regardless of context. Not only does this have all of the benefits above, but it also allows the lexer to look at smaller chunks of code and produce the same output for that section.
• A parser that keeps track of its own context and builds the AST from that knowledge. Even though the tokens were lexed differently with Flex and Bison, our goal is to produce an AST that is very similar (if Flex/Bison let us inspect their AST). The parser then would also take the ownership of storing commands and their signatures by using a progressive scanning method that would have placeholders for yet-to-be discovered grammars. Because of the stateless lexer, rescanning partial parts of the code is trivial.
• Downstream consumers that drive the parser. The parser should be used for one thing: generating the AST. It would be downstream consumers, like an LSP server, that would follow included files, load initialization files, and delegate other work to the parser and generate the “whole picture.”

This overall design will, hopefully, fix some of the problems that plague the current lexer as well. One example is the trailing-context rules that exist only to avoid backup states. Rests (r, R), skips, and chord repetitions (q) are music events that can take post-events like -.. Because of this, the lexer needs special /[-\_] patterns to tell the event apart from what follows. It isn’t a bug. This is rather a shortcoming of trying to lex the syntax with regular expressions.

382/* Flex picks the longest matching pattern including trailing
383 * contexts.  Without the backup pattern, r-. does not trigger the
384 * {RESTNAME} rule but rather the {SYMBOL}/[-_] rule coming later,
385 * needed for avoiding backup states.
386*/

Some rules are extremely long and complex that don’t need to be.

601[^|*.=$#{}\"\\ \t\n\r\f0-9][^$#{}\"\\ \t\n\r\f0-9]* {
602    /* ugr. This sux. */
603	string s (YYText_utf8 ());
604    yylval = SCM_UNSPECIFIED;
605	if (s == "__")
606		return EXTENDER;
607	if (s == "--")
608		return HYPHEN;
609	s = lyric_fudge (s);
610	yylval = to_scm (s);
611
612	return SYMBOL;
613}

Other functions in lexer.ll seem out of place as well. YYText_utf8() is a function in the lexer that is called many times and analyzes every byte to make sure that the utf-8 is valid. lyric_fudge() exists only to replace _ with spaces in a loop as opposed to using a find and replace method. Overall, the goal is a system that doesn’t need comments like “Shut up lexer warnings.”³

The Scheme question

The part that is the largest unknown for me, and one that I have not quite figured out yet, is what place does the Scheme interpreter play in the lexer and parser and when does it need to be introduced. At a minimum, it needs to be parsed. But since this is a library that is planned to be used for static analysis, I don’t know if it ever needs to be evaluated. To keep the design outlined above, nothing beyond parsing should happen in the lexer. LilyPond code can also appear in Scheme code which turns this whole implementation into a turducken at best.

Where we’re going first

To sum it all up, the Flex lexer is managing many different states. There are the lexical modes (notes, chords, figures, lyrics, markup) and there’s the environment (the pitch tables and user definitions that decide what a token even is, etc.). Neither can be deleted. The goal is a scanner with no hidden state: the parser owns the modes and the environment, and lexing becomes a pure function of the input plus the context handed to it. Downstream consumers, like our eventual LSP, drive the parser, load what needs loading, and feed it all back in. In the next part, I’ll start designing the scanner itself. It’s going to be a lot of Rust pattern matching.