GHC Parser Principles
ghc.haskell.org
ghc.haskell.org
I didn't work with the parser, mostly the constraint solver in the type checker. Still, I browsed quite a bit of code. It's one of the most pleasant and well documented codebases I've worked in in any language. In particular, the [note] system is an excellent way to embed long form documentation that touches many components without using fancy doc tools: grep suffices.
If you want to see what a large, old, industrial grade Haskell project looks like I think GHC is a good place to look. And if you ever run into trouble with GHC then I encourage you not to be afraid to hack on it. The code won't bite and the maintainers have no shortage of patience for newcomers.
Algebraic Data Types (ADTs) and pattern matching in functional languages
lay a fertile ground to conveniently define and process data types as tree-like
structures. However, in these grounds, trees often cannot grow; once a data type
is defined and compiled, its definition cannot be extended.On one hand, a grammar is an invaluable tool. It helps keep you honest about ambiguities when you start thinking about adding language features. I think languages should always keep some reference grammar up to date.
That said, I don't think it is a good idea for compilers to use parser generators. A hand-written parser can have better error recovery and more helpful error messages. GHC's parser has some pretty bad parse error message.
Some work was merged into Happy a while ago to support better messages (enabling you to see the expected tokens along with the bad token), but using that in GHC itself is blocked by how complex GHC's tokenizer has become.
> A hand-written parser can have better error recovery and more helpful error messages.
A hand-written parser lets you put a breakpoint on the function which handles a given phrase rule, and when the execution stops there, you get a call stack which more or less corresponds to the top-to-bottom derivation, with arguments you can examine at every level.
That depends on what you're comparing to. The Menhir parser generator can generate a file with all possible "error states" in the parser in which you can specify very nice and friendly error messages for each one.
I've posted this before: http://gallium.inria.fr/~fpottier/slides/fpottier-2015-11-ou... (ignore the French title, the rest is in English). The examples for a C grammar in Menhir show much better error messages than the hand-written GCC ones.
My implementation: https://github.com/angel-manuel/schc/blob/c1fa77b332a765b476...
The success sword of GHC is dual edged; it's made Haskell effectively synonymous with "Language accepted by a recent GHC". The upside is an amazing language with great many advanced features. The downside is an enormous language in a monoculture. It's nearly the antithesis of C (small language that grew little and slowly, but for which there are 100s of implementations).
Edit: Spelling.
Does Ruby and MRI have specs detailed enough that you could implement the entired language from just those? Few languages do, but Scheme and Haskell are among them.
Modern GHC Haskell is to Haskell 98 as C++ is to C.
Great UX!
Instead of bailing out at the first error, you parse invalid portions of the input and sync up to the next point where you can recover and keep parsing, annotating the resulting token stream or parse tree with error indicators such as “invalid number literal token” or “missing bracket”.
This lets you report all errors in a source file at once, so they can all be highlighted in an IDE for example, regardless of errors earlier in the file. The more semantic information you have about the correct parts of the program, the better error messages you can produce about the incorrect parts.
You can extend this to all areas of the compilation pipeline—for example, proceeding to resolve names and typecheck the definitions in a program that are syntactically correct, while ignoring the others and leaving them as error markers.
People like saying that, but I've never seen it work well or provide any benefits. Because these tools are necessarily imperfect, you will get false positives, i.e., an earlier error will confuse the system sufficiently to generate later errors that aren't really errors in the program. So you have to fix errors in order anyway. So there is no benefit to producing further messages. You just risk producing several pages of spurious diagnostics for a simple typo.
Of course this is not completely true, but it's true enough. Or if it isn't, I'd like to hear about examples of systems that never produce such false positives, and where for some reason it makes sense (and is actually beneficial) to change something later in the file first.
Until then, just give me the first error. I won't look at the rest anyway, so no need for the compiler to be "clever" about it.
It also really depends on the grammar of the language how well you can do recovery. Ideally a language should be designed from the beginning to support it. Simple example: if a language allows nested function definitions with the same notation as top-level definitions, then you can’t reliably insert a missing closing bracket for a definition, because you can’t assume that the next one is a new top-level; it could be nested. (Although of course you can use heuristics like indentation to get around this.)
Anyway, the point of successful recovery is that the diagnostics later in the file are not spurious. And if the compiler supports recoverable parsing, you can still have a mode where it just bails out after the first error if that’s what you prefer.
True if you only consider superficial syntax things. False in the real world, where compilers also check whether identifiers are declared, and with what type. If you have an error (syntax or semantic) and decide to press on, in general your symbol tables will be in a messed-up state, and you will generate spurious type or "undeclared identifier" errors. Also, in the real world, the compilers I have experience with do not only continue if they can be 100% sure that it makes sense, but they invariably continue further because they try to be "smart".
The IDE point is a semi-valid point since it doesn't scroll to the bottom-most, most useless errors like a terminal does. But I'm still not convinced that it adds value. That it enables situations where it's better to fix the second error before the first.
For example, if a compiler says “Expected semicolon before open bracket”…you should be able to insert a semicolon there! In my experience, that’s what a beginner programmer or someone unfamiliar with the language is going to try. If that’s not possible, the compiler is probably leaking implementation details of the parser, and should say something else. The most important thing is that the source location points to the actual code where something is wrong so the programmer can examine it. The message is secondary—make it actionable if possible, otherwise just avoid making it actively harmful.
But it also really depends on the language how well you can do recovery. Most languages in wide use are not designed to handle this, in both syntax & semantics.
Again, even if you don’t want to go for full error-recovery, it’s still a good thing to support in a compiler pipeline, because it makes it easier to produce good error messages if the compiler accepts a superset of the actual language—recognising common mistakes in order to offer fixes, for example.