Parsing Algorithms

I recommend compilers course by Alex Aiken from Stanford open

I really liked the intro. I purchased both the "Building an Interpreter from scratch" and the "Parsing Algorithms" courses from Udemy and went through the first four modules of the former. Very clear presentation!

With your IDE example you need the full parser and type checker to be "tolerant". For recursive-descent parsing, there isn't much to say about theory. You try to pick reliable synchronization points and prevent cascading errors. Here's the classic example:

In a statement-oriented language like C#, synchronizing to the next statement upon finding an error by scanning for a semicolon token is a good place to start. (Statements like 'if' with nested statement blocks as arguments have their own sync logic.) Aside from having reliable sync points, statements (unlike expressions) don't have a type that you need to propagate, so you don't usually have to worry about cascading errors in the type checker from skipping a faulty statement. That said, if you skip a faulty statement that was the sole reference to a local variable, that might get flagged as an 'unreferenced variable' warning. It's often a good idea to disable sensitive warnings (and some errors) for the rest of the function as soon as an error is found.

Probably the most important sync point is at the level of symbol declarations. Even if a function's body is totally botched up, as long as you could successfully resolve the function's signature (name, parameter types and return type) you don't get cascading errors from other functions that reference that function. Resyncing to top-level declarations is so important that if you're designing the syntax it's worth having a dedicated declaration keyword (especially for functions) which is only valid at top level. That way you have a reliable sync point even if everything else is out of wack (unbalanced braces, etc). Something like Go's 'func' keyword is close enough: it can appear in function literals and function types as 'func' followed by '(' but 'func' followed by a name is only valid in top-level declarations.

Fine-grained error recovery for expressions is the biggest problem from both a parsing and type checking perspective. There aren't any reliable expression sync points in a C#-like language and you need to fabricate best-effort types for the faulty expressions (with an 'error' type as a fallback) and make sure that the various operators for combining expressions have heuristics so you don't get spurious cascading errors. It generally involves numerous special cases to good results. If you have a choice in the matter, don't worry about expression error recovery: report the error, sync to the next statement and go for the lower-hanging fruit instead. In my experience it isn't worth it in a statement-oriented language.

If you want to eliminate as many spurious warnings/errors like this as possible during error recovery, you do end up adding many special cases over time. But it's an incremental process and you can get good results immediately with basic recovery techniques.

Various comments:

On the lexer side of things, if you get to design the syntax it helps to avoid multi-line lexemes in the common cases. That's why I cringed a little when I learned that Rust's "..." string literals are multi-line. It's fine to have multi-line lexemes like /* ... */ comments in C and """...""" string literals in Python but make the default choices be single-line lexemes like "..." and // ... so you can sync to the newline.

A benefit of a syntax with indentation-defined block structure is that you don't need to rely on balanced grouping tokens like { ... }, so it's easy and reliable to sync to the outer block levels. (In Python there's a caveat that the lexer suspends indentation tracking when the ([{ nesting level is nonzero, but it's still a robust heuristic even when recovering from an error in a nested state.) In particular, if you require top-level declarations to be at column 0 this avoids the need for dedicated keywords for reliable declaration resync. Then the only thing you have to worry about are unbalanced multi-line lexemes gobbling up chunks of your programs.

While I talked about error recovery, a lot of these syntactic properties help with fast symbol indexing. E.g. it's easy to write a fast symbol indexer when you can just sync to "\n" for top-level declarations and otherwise only need to worry about rare multi-line lexemes. This lets your outer scan loop avoid the byte-at-a-time bottleneck.

One parsing technique that covers a lot of ground for little code is parser combinators[0]. And the more space and time efficient Parsec library[1]. Recursive descent is not difficult to hand-roll but the correspondence between the code and BNF can be more obscured, whereas with parser combinators the correspondence is quite clear.

[0] http://www.cs.nott.ac.uk/~pszgmh/monparsing.pdf

[1] https://dspace.library.uu.nl/bitstream/handle/1874/2535/2001...

Great details, thanks!

> A benefit of a syntax with indentation-defined block structure is that you don't need to rely on balanced grouping tokens like { ... }

In fact from the lexer perspective there is no big difference, the matching indent-dedent is the same token type as would be { and }