One of the worst decisions that I think lex and yacc made was to make the lexer push the parser, rather than the parser pull from the lexer. This means that you can’t have any kind of context-specific parsing, which turns out to be something that’s incredibly valuable for a language (particularly when you want to extend the language later: being able to claim things from the identifier space, but only in a new context, avoids backwards compatibility problems).

In the pull model, the parser says ‘I am in this rule, is the next token one of these?’ and the lexer replies ‘yes, here it is’, or ‘no’. The parser can then be structured to say ‘is the next token this context-dependent keyword?’ and if the lexer says ‘no’, then ask ‘is it an identifier?’. This means that you don’t need to have stupid parser rules that say ‘I accept an identifier or any one of these keywords that happens to look like an identifier’ or move lexing logic into the parser (to say ‘I accept any identifier, but if it isn’t one of the ones that is really a keyword then we’ll abort during parsing’).

If one token class is a subset of another (e.g. a keyword is also a valid identifier) then you can even cache the result of the first call to the lexer so that the second one is fast. I’ve never actually needed to do this because the number of ambiguous rules tends to be fairly small and the cost of re-lexing a few tokens is low.

every shell language I’ve seen

Not Oil’s front end, which parses both OSH/bash and the Oil language!

I agree the the line between the lexer and parser is non-trivial. And if you’re parsing C you can’t avoid “the lexer hack”, which goes by many names.

But I draw a pretty bright line in Oil’s front end – lexing is non-recursive and parsing is recursive – and it has held up for years (which wasn’t obvious at the outset).

https://github.com/oilshell/oil/wiki/Why-Lexing-and-Parsing-Should-Be-Separate

I wrote about the architecture and “lexer modes” technique here:

• How to Parse Shell Like a Programming Language
  • In particular How OSH Uses Lexer Modes

Without lexer modes, it probably would have been impossible to maintain the line. Because shell is composed of mutually recursive sublanguages. (But so is almost every complex language if you look closely enough, e.g. C and C++, and I think Rust)

Rough summary is:

• The parser tells the lexer what mode to lex in. Besides the input lines, that is the ONLY input to the lexer.
• The lexer returns a stream of tokens.
• Sometimes the whole parser must be reinvoked dynamically, but these invocations maintain the same strict separation between lexing and parsing.

Another technique I use which I didn’t write about is what I call “pre-structuring” in the lexer. It might lead to a different solution for the Rust issue described:

This is problematic for nested tuple struct. They need syntax like foo.1.2, but to the lexer this string looks like three tokens: foo, ., 1.2. That is, 1.2 is a floating point number, 6/5. So, historically one had to write this expression as foo.1 .2, with a meaningful whitespace.

Today, this is hacked in the parser, which takes the 1.2 token from the lexer, inspects its text and further breaks it up into 1, . and 2 tokens.

Basically if you have this kind of ambiguity, you create a mode, and design the tokens so it doesn’t prefer either one. (And shell has a lot of this.) You maintain the property that lexing is non-recursive and reads over each input byte once, and then the parser can do more logic with those tokens (which might not be recursive).

It’s a slight difference, but I think one advantage is that it’s easier to maintain location info. I like maintaining a hard correspondence between lexing <-> error locations for error messages. When you start re-lexing and re-parsing tokens then you also have the issue of keeping track of error locations. If you think the tokens are short this may not matter, but in shell it matters in several places.

There are some very specific technical reasons for wanting a clear boundary here:

• lexers are much better amendable to generation from grammar
• lexers are very perf sensitive, as the size of input is larger (every byte, rather than every token)
• lexers are perf sensitive, as they are useful for quick approximate analysis (first phase of syntax highlighting mainly)
• lexers are much easier to make incremental

Would be a massively breaking change. I think rust is committed to not doing those

I’ve definitely always been jealous of Swift’s enum syntax.

As the post explains, Rust pattern is disjoint with expression, so there is nothing shady going on. Some(1 + 2) also does not mean Some(3), it is a syntax error.

You would think so, but no, case is completely nonsyntactic in Rust and you can have lower case constructors and upper case variables. In Rust code, constructors are usually capitalized and variables are not, but that’s just a convention.

Case of the identifier doesn’t affect its syntactic category. You can have const nope: Option<i32> = None and a binding Nope.

LHS of = is a (place) expression, otherwise stuff like foo.bar = baz won’t work.

fn main() {
  let mut x = 1;
  let mut y = 2;
  *if true { &mut x } else { &mut y } = 92;
}

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=a0a0bc560a63c331d74c3eac66fedae0