3 ms·

> It’s possible to write the lexer and parser entirely by hand I write mine all by hand. It's the easiest part of a compiler to write, by far. It's also the le

> It’s possible to write the lexer and parser entirely by hand I write mine all by hand. It's the easiest part of a compiler to write, by far. It's also the least troublesome. One advantage of doing them by hand is better, more targeted error messages are easier to fold in.

fredrikholm 1y ago
I suspect that this is the more common opinion, especially when the desired outcome is real world use. Recursive descent is surprisingly ergonomic and clean if one gets the heuristics right. Personally I find it way easier than writing BNF and its derivatives as you quickly get into tricky edge cases, slow performance and opaque errors.
- hombre_fatal 1y ago
  Yeah, grammars seem easy at first, but they're full of arcane knowledge like writing your tokens with the right affinity and greediness, ensuring back tracking is performant, and that you'll get good error messages. Same with parser combinators. Not until a bunch of trial and error do you build up the intuitions you need to use them in production, I think. Despite two decades of using those, I've found it much simpler to write my own scanning or RD parser.
- WalterBright 1y ago
  D was originally designed to require only one token lookahead, but it turns out to get the aesthetic I wanted, that arbitrary lookup was needed. That turned out to be very handy when adapting it to compile C code. Much of the parser code, if you compare the code with the BNF grammar, is a 1:1 correspondence. Super easy to do.
sph 1y ago
> I write mine all by hand. It's the easiest part of a compiler to write, by far. It's also the least troublesome. It's also the most annoying if you're writing a new language. You want to iterate on its ideas, but can't do so until you have a parser done. I've been designing a few language concepts over the past year, and it feels 80% of this time has been writing and debugging parsers; by the time I get to the meat of language design - the shape of its AST, the semantics of it - any small syntactic change means going back to update the lexer and parser stage. Doesn't help that I can't settle on a syntax. BTW I first started with PEG, which are nice in theory, but I feel the separation of lexing and parsing stage to very helpful to reduce boilerplate (handling whitespace in PEG is obnoxious). Later, I hand-wrote my parsers (in C), but it's gotten so repetitive I've dedicated a weekend to just learning lex/yacc (actually flex/bison). Even if parsers are easy to write, it's good to have higher level tools to reduce the tedium of it.
- fjfaase 1y ago
  There are other tools for prototyping the grammar for a new language. There are several online tools that can interactively parse input based on a given grammar. The one I developed is: https://fransfaase.github.io/MCH2022ParserWorkshop/IParseStudio.html https://fransfaase.github.io/MCH2022ParserWorkshop/IParseStu... The page does contain a sample grammar and sample input. For the grammar for the grammar see: https://fransfaase.github.io/MCH2022ParserWorkshop/index.html https://fransfaase.github.io/MCH2022ParserWorkshop/index.htm...
- thesz 1y ago
  > You want to iterate on its ideas, but can't do so until you have a parser done. Embed your language into host language. It is simple to do even in C++. Iterate on ideas till your heart content, then add syntax.
  - gpderetta 1y ago
    Alternatively (or concurrently) use s-expressions and add syntactic sugar later.
- WalterBright 1y ago
  Anecdotally, lex and yacc gets your prototype up and running quickly, but the ongoing adjustments needed winds up with it behind. The time lost comes from: 1. having to learn lex and yacc 2. running into limitations with lex and yacc 3. having a foreign program (i.e. lex and yacc) integrated into your build process 4. requiring a particular version of lex and yacc that may be awkward on multiple platforms 5. optimizing the code. (Once you start doing that, you cannot use lex/yacc to generate a new version.) And so on. At one point, we decided to write a D program that built the D compiler, instead of using make. Well, that turned out to be a greater time sink than just using make.
dboreham 1y ago
In my lifetime parsers have gone from: written by hand with great effort, to: use a parser generator to be sure the grammar is correct and save effort, to: just write by hand because it's not that hard and error reporting, to: just use AI.
- daeken 1y ago
  Out of curiosity, have you had luck using LLMs for parser generation? I should really try it out with my parser combinator library; would be cool to be able to throw in sample code and some basic instructions and get a usable parser out for prototyping. Think I might try that next time I build a new language, just for fun.
- WalterBright 1y ago
  > just use AI I suspect you might spend more time trying to specify what you want to the AI than just writing it.
ModernMech 1y ago
I don't think I know any lang devs who don't write their own parser. Beyond just being the easiest part it's also the most fun, and it's the thing that gets you sucked in the first place. If you're using a generator you're missing out.
WalterBright 1y ago
Another advantage is error recovery code can be made much better. Yacc and lex don't know what common errors are, but you as the language designer knows what the most likely intention of the user was. Yacc/lex tend to produce generic error messages and do very poorly with error recovery.
ivanjermakov 1y ago
Can't pass by without mentioning this amazing post about parsing with error recovery: https://matklad.github.io/2023/05/21/resilient-ll-parsing-tutorial.html https://matklad.github.io/2023/05/21/resilient-ll-parsing-tu...

fredrikholm 1y ago

I suspect that this is the more common opinion, especially when the desired outcome is real world use. Recursive descent is surprisingly ergonomic and clean if one gets the heuristics right. Personally I find it way easier than writing BNF and its derivatives as you quickly get into tricky edge cases, slow performance and opaque errors.

hombre_fatal 1y ago
Yeah, grammars seem easy at first, but they're full of arcane knowledge like writing your tokens with the right affinity and greediness, ensuring back tracking is performant, and that you'll get good error messages. Same with parser combinators. Not until a bunch of trial and error do you build up the intuitions you need to use them in production, I think. Despite two decades of using those, I've found it much simpler to write my own scanning or RD parser.
WalterBright 1y ago
D was originally designed to require only one token lookahead, but it turns out to get the aesthetic I wanted, that arbitrary lookup was needed. That turned out to be very handy when adapting it to compile C code. Much of the parser code, if you compare the code with the BNF grammar, is a 1:1 correspondence. Super easy to do.

sph 1y ago

> I write mine all by hand. It's the easiest part of a compiler to write, by far. It's also the least troublesome. It's also the most annoying if you're writing a new language. You want to iterate on its ideas, but can't do so until you have a parser done. I've been designing a few language concepts over the past year, and it feels 80% of this time has been writing and debugging parsers; by the time I get to the meat of language design - the shape of its AST, the semantics of it - any small syntactic change means going back to update the lexer and parser stage. Doesn't help that I can't settle on a syntax. BTW I first started with PEG, which are nice in theory, but I feel the separation of lexing and parsing stage to very helpful to reduce boilerplate (handling whitespace in PEG is obnoxious). Later, I hand-wrote my parsers (in C), but it's gotten so repetitive I've dedicated a weekend to just learning lex/yacc (actually flex/bison). Even if parsers are easy to write, it's good to have higher level tools to reduce the tedium of it.

fjfaase 1y ago
There are other tools for prototyping the grammar for a new language. There are several online tools that can interactively parse input based on a given grammar. The one I developed is: https://fransfaase.github.io/MCH2022ParserWorkshop/IParseStudio.html https://fransfaase.github.io/MCH2022ParserWorkshop/IParseStu... The page does contain a sample grammar and sample input. For the grammar for the grammar see: https://fransfaase.github.io/MCH2022ParserWorkshop/index.html https://fransfaase.github.io/MCH2022ParserWorkshop/index.htm...
thesz 1y ago
> You want to iterate on its ideas, but can't do so until you have a parser done. Embed your language into host language. It is simple to do even in C++. Iterate on ideas till your heart content, then add syntax.
- gpderetta 1y ago
  Alternatively (or concurrently) use s-expressions and add syntactic sugar later.
WalterBright 1y ago
Anecdotally, lex and yacc gets your prototype up and running quickly, but the ongoing adjustments needed winds up with it behind. The time lost comes from: 1. having to learn lex and yacc 2. running into limitations with lex and yacc 3. having a foreign program (i.e. lex and yacc) integrated into your build process 4. requiring a particular version of lex and yacc that may be awkward on multiple platforms 5. optimizing the code. (Once you start doing that, you cannot use lex/yacc to generate a new version.) And so on. At one point, we decided to write a D program that built the D compiler, instead of using make. Well, that turned out to be a greater time sink than just using make.

dboreham 1y ago

In my lifetime parsers have gone from: written by hand with great effort, to: use a parser generator to be sure the grammar is correct and save effort, to: just write by hand because it's not that hard and error reporting, to: just use AI.

daeken 1y ago
Out of curiosity, have you had luck using LLMs for parser generation? I should really try it out with my parser combinator library; would be cool to be able to throw in sample code and some basic instructions and get a usable parser out for prototyping. Think I might try that next time I build a new language, just for fun.
WalterBright 1y ago
> just use AI I suspect you might spend more time trying to specify what you want to the AI than just writing it.

ModernMech 1y ago

I don't think I know any lang devs who don't write their own parser. Beyond just being the easiest part it's also the most fun, and it's the thing that gets you sucked in the first place. If you're using a generator you're missing out.

WalterBright 1y ago

Another advantage is error recovery code can be made much better. Yacc and lex don't know what common errors are, but you as the language designer knows what the most likely intention of the user was. Yacc/lex tend to produce generic error messages and do very poorly with error recovery.

ivanjermakov 1y ago

Can't pass by without mentioning this amazing post about parsing with error recovery: https://matklad.github.io/2023/05/21/resilient-ll-parsing-tutorial.html https://matklad.github.io/2023/05/21/resilient-ll-parsing-tu...