That wiki page is a great summary.

My main intuition is: lexing can be done in a fixed amount of memory with a finite-state machine (or equivalent regular language); parsing requires an arbitrary amount of memory (i.e. it needs the stack) to recognize recursive/nested structures.

Also, most syntax highlighters are based on lexing. So you’ll want a distinct lexing grammar, anyways.

Though if your parser isn’t at least in the ballpark of O(n), you have way bigger problems than the size of the constant.

The only real reason to split it into two phases is because it performs better that way. Parsing is slow, lexing is fast. Do as much work in your lexer and only involve the parser when you need it.

The only reason to separate lexing and parsing into two distinct phases, it because it’s easier to write. Otherwise, doing the lexing “on-demand” is always better

Wait a minute, the two aren’t mutually exclusive. Especially if what matters to you is the ease of writing: typically lexer.next_token() would be defined separately from your parser. Heck, it’s this very separation that allows your parser from switching lexers without causing your source code to be a complete mess: one file per lexer, another file for the parser, all neatly separated.

It’s not a runtime separation of phases (lexing and parsing would actually be interleaved), but that hardly hurts source code clarity.

Yes, I get tripped up on PEGs for the same reason: what are distinct phases in my mind get complected together, and I have to remember that. It is really handy to have all the parsing rules in one place, but it more complicated. Really depends on the task at hand.

I think the traditional way to handle what you’re talking about is to settle on a convention of consuming excess whitespace either immediately before or after reading in a lexical entity.

PEG libraries that I’ve used have an explicit token wrapper that means ‘match this with no whitepace’ and then they permit whitepace (or white space and things that match the comment rule, if you’re discarding comments) in any other matches. Does lpeg not have some equivalent?

Unfortunately the lexing grammar is non-regular; the lexer behaves differently depending on whether you are inside a module, or inside a block comment section, or whatever.

You need several lexers, one per context. Those will be regular. Then your parser can just call the relevant lexer for their terminal symbols, depending on what you are parsing. Hopefully your parsing tool can do that. Otherwise, hand written recursive descent will be able to.

Note that you cannot just lex a whole stream of tokens, and then parse them. You need to lex on demand, with something like a next_token() function. And you need your lexers to play nice with each other (when one reads a token the other must know where to resume exactly, which might be a problem depending how you buffer data).

While the other replies cover the standard approach (treating it as whitespace), that’s not always what you want, especially if you’re building a “blessed” parser for a language since a lot of use cases want to understand your comments (for example formatters which need to preserve comments and LSPs which might use documentation comments).

You can check what rust-analyzer and black do for references.

In my parser, every lexeme stores its position in the input text. (This can be done as a separate array.) Then a comment can just be a single COMMENT token; to get the content of the comment (if you need it for some reason, like doc generation), just grab the position and look up the original text.

(Though most parse rules treat it as equivalent to whitespace, and ignore it.)

Recognize them as a kind of whitespace, and let them get handled by the rule (which might be explicit or implicit) that ignores whitespace between significant tokens.

You treat it as whitespace; for example given functions like this:

static void eatspaces() { // consume whitespace and comments from input stream
    for (;; nextchr()) {
        int c = peekchr();
        if (c == '#') { // comment
            while ((c = peekchr()) != '\n' && c != EOF) nextchr() ;
            continue;
        } // you could match multiline comments, even nested ones, too
        if (!aisspace(peekchr())) {
            break;
        }
   }
}

static bool match_nospc(int c) {
    eatspaces();
    return match(c);
}

static void expect_nospc(int c) {
    eatspaces();
    expect(c);
}

and the parser:

static Expr primary() {
    eatspaces(cm);
    int c = nextchr();
    if (aisdigit(c)) { // number literal
        ...
    } else if (c == '(')) { // '(' EXPR ')'
        Expr ex = expression();
        expect_nospc(')');
        return ex;
    } else ...
}

static Expr unary() {
    if (match_nospc('-')) { // '-' UNARY
        return makeunaryexpr('-', unary());
    } else if ... {
        ...
    } else {
        return primary();
    }
}

I wouldn’t recommend doing things this way (unified lexer and parser), it can get pretty messy.

It doesn’t have to slow it down, but it can slow it down. Each transformation from one IR to the next causes overhead. But that new IR may make the analysis/transformation you want to do on it easier or more efficient. It’s a tradeoff. Some compiler tools, such as nanopass, encourage you to do lots of IR transformations, but I haven’t used them in practice.