Lexers

I’ve always been curious why lexer and parser generators are a standard part of the compiler-construction toolkit. Like why do these tasks require metaprogramming, what’s so hard about writing them “normally”.

In particular, parsing is understood to be split into “fancy parser generators” and “ad-hoc handwritten recursive parsers”, but I’m curious what the ad-hoc handwritten lexer looks like. input.split(" ") only gets me so far, and do I really have to bust out the regex engines and code generators just because I want string literals?

So I’ve been trying to explore more points on that spectrum.

Automata

Lexing is an automata problem. The lexer has a state, what the lexer does depends on its current state, and when receiving a character the lexer may or may not consume the character and may or may not change to a different state.

Let’s consider a language with left parenthesis, right parenthesis, and line comments. To lex this language we need two states, since we need to remember whether we’re in a comment or not.

let state = TOP;
for(let c of input) {
    switch(state) {
        case TOP:
            if(whitespace(c)) continue; //skip whitespace
            else if(c == "(") output(LPAREN);
            else if(c == ")") output(RPAREN);
            else if(c == ";") state = COMMENT;
            else throw new Error("Unknown character");
        case COMMENT:
            if(c == "\n") state = TOP;
            else continue; //skip comment
    }
}   

Annoying handwritten lexers

If you use this type of lexer to lex identifiers, things quickly get messy.

• We need to keep track of what time we transitioned into the identifier state, so when we transition out we can substring the identifier from the input. (Great source of off-by-ones.)
• When ending an identifier we need to remember to rewind the clock, because the character which closed the identifier shouldn’t be part of the identifier. Something like (foo)5 should be lexed as LPAREN "foo" RPAREN 5, not LPAREN "foo)" 5.
• EOF can close identifiers.

It just becomes fiddly and unpleasant. I think this is about when people start reaching for lexer generators.

let state = 0;
let start = TOP;
for(let i = 0; i < input.length + 1; i++) { //need the index now?
    let c = i == input.length ? END : input.charAt[i];
    switch(state) {
        case TOP:
            if(c == END) break;
            else if(whitespace(c)) continue;
            else if(c == "(") output(LPAREN);
            else if(c == ")") output(RPAREN);
            else if(c == ";") state = COMMENT;
            else if(/[A-Za-z]/.test(c)) {
                start = i; //i guess?
                state = IDENT;
            }
            else throw new Error("Unknown character");
        case COMMENT:
            if(c == END) break;
            else if(c == "\n") state = TOP;
            else continue;
        case IDENT:
            if(c == END) {
                let id = input.substring(start, i); //is this correct?
                output(IDENT(id));
            }
            else if(/[A-Za-z]/.test(c)) continue; //keep it
            else {
                let id = input.substring(start, i + 1); //is this correct? should it be different?
                output(IDENT(id));
                state = TOP;
                i--; //don't actually consume the closing character?
            }
            continue;
    }
}   

Also .substring/yytext() is not always a convenient way to extract the token. Consider string literals with backslash-escapes; the string you want to tokenize doesn’t appear literally in the source and you need to postprocess it.

Continuation-passing lexing? Explicit-automata lexing?

Okay, this is a type of lexer I’ve played with a few times:

let i = 0;
let pop = () => i < s.length ? s.charAt(i++) : END;
let lexed = [];
let output = x => lexed.push(x);

let top = c => {
    if(c == END)           return undefined;
    if(whitespace(c))      return top;
    if(c == '(')           return output(LPAREN), top;
    if(c == ')')           return output(RPAREN), top;
    if(c == ';')           return comment;
    if(/[A-Za-z]/.test(c)) return id(c);
    else                   throw new Error("unknown character " + c);
};
let comment = c => {
    if(c == END)           return undefined;
    if(c == '\n')          return top;
    else                   return comment;
};
let id = x => c => {
    if(c == END)           return output(makeId(x)), undefined;
    if(/[A-Za-z]/.test(c)) return id(x + c);
    else                   return i--, output(makeId(x)), top;
};

let state = top;
while(state) state = state(pop());

(Sorry for the “comma operator”, it’s to avoid peppering the thing with curly braces. That’s just due to Javascript. Imagine if this was in a language with a decent match/cond expression.)

Ok so the idea is that lexer states are represented by closures. You call the closure with the next character, it does lexing stuff, and returns the next state. The important part is that each state closes over the data it needs (e.g. id is parametrized by the partially-lexed identifier x.) There’s no need to deal with string-indices and substring since the identifier lives right there in the lexer state, ready to use.

How about string literals with character escapes? With CPS it’s quite easy to decode escapes as they’re encountered, no postprocess step needed.

let top = p => {
    //...
    if(p == '"')  return str("");
    //...
};
let str = s => p => {
    if(p == END)  throw new Error("nonterminated string");
    if(p == '"')  return output(makeString(s)), top;
    if(p == '\\') return esc(s);
    else          return str(s + p);
};
let esc = s => p => {
    if(p == END)  throw new Error("nonterminated string");
    if(p == '"')  return str(s + '"');
    if(p == "n")  return str(s + "\n");
    else          throw new Error("unrecognized character escape " + p);
};

Notice how the string is passed back and forth between the s parameters.

I dunno. Well I think it’s cute anyway.

Is this still a finite automata, because str is not just one state but a family of states corresponding to different strings? Hmmmmm

The lexer state mindset

• what happens when I see EOF?
  • Just exit (comment, top)
  • Dump my internal state as a token (identifier, number)
  • Error out because it’s missing a closing delimiter (str)
• do I consume this character or not?
  • Typically yes, unless it’s an “implicit delimiter” like an identifier being closed by a non-identifier character.
• what state to go to next? what should it close over? what type should the closed-over values be?

Also keep in mind that lexer states don’t have a 1:1 relationship with the language’s token types:

• one-character tokens do not need their own state
• all the keyword tokens will be output from the identifier lexer
• sometimes you just need multiple states. like with quoted strings.

alternatives

If you had a language with decent algebraic data types, you could realize the lexer state as one of those:

data LexerState
  = Top
  | Comment
  | Identifier String
  | StringLiteral String
  | StringLiteralEscape String

Lexing is almost a fold over the characters in the string, except the lexer has the option to not consume a character after looking at it (the i-- thing).

There are three things a lexer does after receiving a character:

1. maybe consume a character
2. maybe output a token
3. return the next state

In my js implementation 1) and 2) are done with side effects while 3) is through a return value. It would be possible to push more of this stuff into return values and have a functional lexer.

Can you only do lexing? using more complex code inside each state, could you do some scannerless parsing?

generator functions?

prior art?

Please tell me!

diagnostics?

Dealing with off-by-ones in substring lexers is annoying, but you do get accurate spans…

Isn’t this slow cause it builds up strings character-by-character

who gaf