News for hackers. Stuff that matters.
Re:A meta approach to implementing programming languages (2018) by WalterBright on Sunday February 24, 2019 @04:40PM (#19240783)
Lexing and parsing are the easiest (by far) parts of writing a compiler. Writing them by hand is very easy, and the code often looks like the grammar. They also tend to be the least buggy parts, I would handwave that maybe 1 in a thousand bugs were in the lexer/parser.

Lexer/parser generators are simply not needed and not particularly helpful. Two areas where they are particularly inferior:

1. Error messages. Since the generator doesn't know what you're doing, error messages tend to be generic and very unhelpful to the user. With a hand-built one, context can be supplied to the user in the language of the language(!). Suggestions for corrections for the most common mistakes can be given.

2. Error recovery. Doing this well relies on guessing at what the most likely AST was intended by the user. But a generator can't know that.

By the time you've expended effort trying to overcome (1) and (2), you'd have been better off just writing a custom one.

Here are D's lexer and parser:

https://github.com/dlang/dmd/blob/master/src/dmd/lexer.d

https://github.com/dlang/dmd/blob/master/src/dmd/parse.d

For a complex language like D, they are pretty simple. (The lexer even comes with some builtin unittests!)

Probably the most complex part is the arbitrary lookahead scheme. Of course, this wouldn't be necessary if the grammar didn't need lookahead.

P.S. The initial versions of these were written 20 years ago in C, so the coding style is a bit archaic and could use improvement.

Re:A meta approach to implementing programming languages (2018) by WalterBright on Sunday February 24, 2019 @05:13PM (#19240962)
For comparison, here's the C++ lexer for Digital Mars C++:

https://github.com/DigitalMars/Compiler/blob/master/dm/src/d...

The parser isn't in its own file, it's intermingled with the semantic processing, a mistake I didn't want to repeat with D :-)

Re:A meta approach to implementing programming languages (2018) by targon on Sunday February 24, 2019 @06:04PM (#19241228)
> They also tend to be the least buggy parts, I would handwave that maybe 1 in a thousand bugs were in the lexer/parser.

Ehh, I don't know... https://johanengelen.github.io/ldc/2018/01/14/Fuzzing-with-L...

From the article:

> My expectation was that there would be a bug deep down with some rare cornercase of a cornercase, and that the fuzzer would have to run for hours and hours covering more and more of the lexer to, perhaps, finally find a bug. So I was preparing for a long fuzzing session, wanted to go to bed and kick this one off but… The fuzzer found a first failure within a second.

> Running the fuzzer several times, sometimes it still hadn’t found a bug after 15 seconds, but usually it found the bug within a second; the process is (semi-)random so that’s expected.

Re:A meta approach to implementing programming languages (2018) by WalterBright on Sunday February 24, 2019 @06:23PM (#19241323)
It found a bug in the lexer, which is good, because then it was fixed. I never said that handbuilding a lexer would mean it doesn't have any bugs.
Re:A meta approach to implementing programming languages (2018) by mruts on Friday March 01, 2019 @04:29PM (#19285438)
The advantage of parser combinators is that you can use them with a lot of different things. Parsing some UDP protocol, no problem, 20 lines of codes. Parsing some bespoke binary format, no problem. I agree that maybe if your problem space is just compilers that maybe you should consider something else, but most parsing is not about code and more about data. In these cases, parser combinators are a no-brainer.