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.

We’re starting to make some progress on the parser actually producing something that is useful to downstream consumers. It’s not pretty, but this is how the sausage is made. Exciting nonetheless.

Revisiting the scanner

The first thing that needed to be done was to re-visit the scanner and look at the way we were handling some of the numbers. This became even more important as we started parsing durations that exposed this problem. When the number() lexer was designed, I followed the Scheme implementation of real numbers where a number did not need to have another number after the decimal point. This meant that 4. and 4.0 were both converted to LitReal with the same value. When we started looking at durations, this made it hard to break apart the dots from the numbers.

I started digging around the LilyPond parser and I found a couple of clues on how to deal with this. The Flex grammar defines a {STRICTREAL} in addition to accepting “normal” real numbers. The {STRICTREAL} requires a digit after the decimal point, so 4. comes out as 4 plus a separate .. The STRICTREAL appears in music contexts, which is where we are going to spend most of our time (lexer.ll @185, @520)¹. So it makes sense, in order to cut down the reclassifying of tokens, to not stitch these tokens together by default.

The amount of work on the parser to combine these tokens when it thinks it should be a real is less than the parser breaking the number and dot apart when reading a duration. That stitcher does not exist yet. It belongs to the part where values and assignments get parsed (i.e., the place that reals are ACTUALLY used as Scheme values in the backend).

The parser makes music

The Flex lexer looks at idents and calls scan_word() to determine what the ident “means.” If it is a pitch, it returns NOTENAME_PITCH (or TONICNAME_PITCH in chord mode); if not, scan_bare_word lets it fall through to the symbol handling. We are going to do almost the same thing, with a difference in implementation.

LilyPond defines every language’s pitch names in define-note-names.scm¹ as one big association list, language-pitch-names. But that alist is the definition format, not the lookup structure. The lexer flattens the chosen language’s sublist on language switch into a single hash table (lily-lexer.cc @378-387), so per-word lookup is near constant time, never a list walk.

I chose the same shape in the parser, but with a perfect-hash table for every language compiled in at build time. During parsing, the parser just holds a language field pointing at the right table, so pitch names resolve in near constant time without consulting any other language’s data.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

type Note = (PitchName, i8);

static NEDERLANDS: phf::Map<&'static str, Note> = phf_map! {
    "c" => (PitchName::C, 0),
    "cis" => (PitchName::C, 2),
    "ces" => (PitchName::C, -2),
    "bes" => (PitchName::B, -2),
    // ... nine spellings per letter ...
};

static PITCHES: phf::Map<&'static str, &'static phf::Map<&'static str, Note>> =
    phf_map! {
        "nederlands" => &NEDERLANDS,
        "english" => &ENGLISH,
        // ... català, deutsch, español, français, italiano, ...
    };

pub struct Pitch {
    name: PitchName,
    alter: Fraction,
}

impl Pitch {
    fn from_quarters(name: PitchName, quarters: i8) -> Self {
        let magnitude = Fraction::new(quarters.unsigned_abs() as u64, 4u64);
        let alter = if quarters < 0 { -magnitude } else { magnitude };
        Self { name, alter }
    }

    pub fn note_name(language: Language, name: &str) -> Option<Self> {
        let table = PITCHES.get(language.as_str())?;
        table.get(name).map(|&(n, q)| Self::from_quarters(n, q))
    }
}

One design choice that I’m not completely confident with is the way that I decided to encode alterations to the notes (sharp/flat). LilyPond uses a rational number in order to encode this and I have tried to recreate it by using a fraction to represent this. This works in the same way as the Scheme rational as it does not automatically convert this into a float representation in memory. The benefit of this is that we could, in the future or if the composer even wants to, create something like the 1/8 sharp or 5/8 flat note. Looking at the MusicXML accidental-value, it brings up some interesting cases for accidentals beyond the widely used semi and quarter tone alterations. LilyPond does use this rational field in a creative way for these non-Western alterations. The alternative is to use an enum for the alterations. While this is more limiting, it would make the from_quarters encoding unnecessary. Regardless, it works now and we can revisit it later.

And the parser makes silence

In addition to the notes, we also have added the plumbing for the parser to recognize r, R, and s. Even though these are parsed very much in the same way as the notes, they are distinct and need their own categories. We do reuse some of the same code for these elements. Both this set and the notes will parse durations and post-events. Just the “type” is different. Because this is a small set and easily testable, we look for these elements first before trying anything against the pitch table. Eventually, there will be a check for q here as well, but we have not implemented the chord parsing yet, so there is nothing for q to repeat.

The length of the sound

Durations written in LilyPond must have one part and can have two others. The first part that is required is what I call the base duration. This determines if a note is a quarter note, an eighth note, a semibreve, or even a breve. For anything that is longer than a whole note, it is encoded with \breve, \longa, and \maxima (parser.yy @3518-3536)¹. For everything that is a whole note or shorter, the denominator is specified (e.g., a quarter note has a 4, and a sixteenth note has a 16). These numbers will always be a power of two. If the base duration is missing, LilyPond reads the last duration used from an internal state and applies that. We keep this state on the parser and write to it whenever we see a valid duration. This matches the LilyPond implementation.

After this base duration, we can have any number of dots that act in the same way as dots after notes in sheet music. It is also the reason we altered the scanner to produce LitInteger + Period as opposed to a LitReal when there is not another number after the period. These dots are counted and recorded in the duration.

The last part of the duration is the modifier: a chain of *n or *n/m factors (parser.yy @3548-3580)¹. The parser loops over them, parsing each factor’s number before committing, so a * it cannot use will get emitted as an unknown token. The factors multiply into one Fraction, which reduces itself (e.g., *2*1/2 is just 1), and there is no power-of-two restriction on them: c4*3 is legal LilyPond, and so is c4*2*3/4.

What’s next

We’re getting very close to being able to allow the parser to go on its own and parse something. We have many of the pieces and parts that make up the parsing of the music, but we need to deal with the post-events before the parser is in go mode for music parsing. (Well, and symbol resolution, but that’s planned for much later.) Our goal for the next part is to get that post-event parsing scaffolded out and start adding them to music events. These post events include slurs, ties, and other scripts like marcato marks.