6 ms·

I found this Rust tutorial[1] on Pratt parsers to be really easy to follow as well. I'm not a Rustacean but I didn't find not knowing Rust to be a barrier. I us

I found this Rust tutorial[1] on Pratt parsers to be really easy to follow as well. I'm not a Rustacean but I didn't find not knowing Rust to be a barrier. I used that as a guide to write the parser for my experimental programming language Fur[2]. However, I'll caution anyone writing their own programming languages to read some wisdom from someone who has written a production-quality programming language[3]. Most programming language developers get bogged down in writing the parser and never even get into solving the real hard problems of language development, which are things like bytecode generation and garbage collection. The fact is, a naive recursive descent parser with some low lookahead number to handle left recursion will be performant and can be written in an afternoon for 99% of parsable languages. I'm not sure what it is about parsers that makes them susceptible to yak shaving, but it seems to be a trap a lot of people fall into (including myself!). [1] https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html https://matklad.github.io/2020/04/13/simple-but-powerful-pra... [2] https://github.com/kerkeslager/fur/blob/main/parser.c https://github.com/kerkeslager/fur/blob/main/parser.c [3] https://craftinginterpreters.com/compiling-expressions.html#design-note https://craftinginterpreters.com/compiling-expressions.html#...

GloomyBoots 3y ago
Maybe in this case it should be spelled yacc shaving.
- kerkeslager 3y ago
  As a pun enthusiast I'd like to express my appreciation for this. :D
norir 3y ago
I don't know. This is becoming conventional wisdom but I think a reverse argument is equally true: aspiring language designers get too bogged down in bytecode generation or gc that they are unable to make a compelling language that adequately differentiates itself from existing languages that already do those things well. Are you actually claiming that handwriting a recursive descent parser for most popular languages can be done in afternoon? Unless the language is a lisp, I find that unlikely in most cases. You can write a parser generator that generates a recursive descent parser. Writing the grammar will almost surely be significantly faster in the parser generator dsl than a handrolled recursive descent parser. To improve your language design skills, you need to design multiple languages. Parser generators will get you a prototype faster and allow you to explore the language design space. You can target a high level language to do the hard parts. Once you are satisfied with a language, then maybe it makes sense to design your own custom bytecode or gc to solve its unique problems. I do agree though that optimizing parsing at an early stage makes no sense and many do get bogged down there.
- kerkeslager 3y ago
  > Are you actually claiming that handwriting a recursive descent parser for most popular languages can be done in afternoon? Unless the language is a lisp, I find that unlikely in most cases. Yes. I've written enough parsers that I can say that with a lot of confidence, and I'm not sure where your doubt is coming from. The parser for Fur was written in about 6 hours and probably 4 hours of that was tracking down pathological semicolon elision edge cases (0/10, would not implement semicolon elision in future languages). I'm sure that Nystrom has written many more parsers than I have. The edge cases might be tricky to iron out for existing, mature languages, but when you're writing your own language I'd shy away from features which require crazy parser shenanigans like JavaScript RegEx literals or C++ templates, at least until you're far along enough to have justification for those kinds of features. This is also the sort of thing that I imagine ChatGPT, even the free version, could do in even less time. There's one caveat here, which is that error reporting is one pretty hard part of parsing. But if you understood that you wouldn't be recommending parser generators; poor error reporting capabilities is exactly why many production-quality languages have hand-rolled their parsers. > Writing the grammar will almost surely be significantly faster in the parser generator dsl than a handrolled recursive descent parser. I'm not interested in hearing speculation on things I've benchmarked. When it comes to performance, benchmark or GTFO. Performance isn't significantly different in most cases, and in pathological worst cases, it's often easily solved by memoizing (i.e. converting the recursive descent parser into a Packrat Parser). You shouldn't even memoize everything in most cases, because a lot of sub-parsers won't trigger backtracking, so there's no need to waste memory on memoization. > To improve your language design skills, you need to design multiple languages. Parser generators will get you a prototype faster and allow you to explore the language design space. To design a language, I don't need to write a parser at all in most cases. I certainly don't need to prototype syntax to design it effectively. Writing programs in your target syntax, even if you can't actually run them, is far more effective. Related to the fact that parsers aren't the hard part, syntax isn't the important part, so if you get bogged down in designing the syntax that's also a lose. I genuinely think most novel syntaxes create more usability/entry barriers for users than the benefits they offer. Go with the syntax of an existing popular language if you at all can--the simpler/more popular, the better. Semantics, idioms, and ecosystem are all much more important in what makes a language useful. > You can target a high level language to do the hard parts. That's exactly why this approach is terrible. The hard parts are the entire point of creating a new language. If the hard parts are all implemented in a different language then people should just use that language instead of yours. > Once you are satisfied with a language, then maybe it makes sense to design your own custom bytecode or gc to solve its unique problems. Still no--I don't think you understood what I meant when I said "the real hard problems of language development, which are things like bytecode generation and garbage collection". If you're targeting an existing VM such as the JVM or CLR you won't need to implement custom bytecode or GC, and even if you decide to implement your own bytecode or GC, you may be able to use an off-the-shelf implementation. You'll note that my post said bytecode generation, which is hard no matter what syntax you're implementing or bytecode you're targeting, because it's translating the semantics of the syntax to semantics that the target architecture can understand. When I said implementing garbage collection was hard, what I meant was not that implementing the algorithms is hard (you can literally plug in an off-the-shelf garbage collector in most cases) but that calling the garbage collection algorithms at the right times is hard.
_a_a_a_ 3y ago
Quoting [3]: "I’m going to make a claim here that will be unpopular with some compiler and language people. It’s OK if you don’t agree. Personally, I learn more from strongly stated opinions that I disagree with than I do from several pages of qualifiers and equivocation. My claim is that parsing doesn’t matter." agreed 100%
- naasking 3y ago
  Parsing matters for tooling, and that's about it. The recent Go retrospective on this goes into this somewhat, but if you have a reusable parser then you or others can easily create linters, formatters, and static analysis tools for your language, which really fleshes out the ecosystem.
  - kerkeslager 3y ago
    I'd say that Nystrom's point in context is more "How you parse doesn't matter." He says, later in that link: "Recursive descent, Pratt parsing, and the popular parser generators like ANTLR or Bison are all fine." Any of these can be reusable parsers that you and/or others can easily use to create tools.

GloomyBoots 3y ago

Maybe in this case it should be spelled yacc shaving.

kerkeslager 3y ago
As a pun enthusiast I'd like to express my appreciation for this. :D

norir 3y ago

I don't know. This is becoming conventional wisdom but I think a reverse argument is equally true: aspiring language designers get too bogged down in bytecode generation or gc that they are unable to make a compelling language that adequately differentiates itself from existing languages that already do those things well. Are you actually claiming that handwriting a recursive descent parser for most popular languages can be done in afternoon? Unless the language is a lisp, I find that unlikely in most cases. You can write a parser generator that generates a recursive descent parser. Writing the grammar will almost surely be significantly faster in the parser generator dsl than a handrolled recursive descent parser. To improve your language design skills, you need to design multiple languages. Parser generators will get you a prototype faster and allow you to explore the language design space. You can target a high level language to do the hard parts. Once you are satisfied with a language, then maybe it makes sense to design your own custom bytecode or gc to solve its unique problems. I do agree though that optimizing parsing at an early stage makes no sense and many do get bogged down there.

kerkeslager 3y ago
> Are you actually claiming that handwriting a recursive descent parser for most popular languages can be done in afternoon? Unless the language is a lisp, I find that unlikely in most cases. Yes. I've written enough parsers that I can say that with a lot of confidence, and I'm not sure where your doubt is coming from. The parser for Fur was written in about 6 hours and probably 4 hours of that was tracking down pathological semicolon elision edge cases (0/10, would not implement semicolon elision in future languages). I'm sure that Nystrom has written many more parsers than I have. The edge cases might be tricky to iron out for existing, mature languages, but when you're writing your own language I'd shy away from features which require crazy parser shenanigans like JavaScript RegEx literals or C++ templates, at least until you're far along enough to have justification for those kinds of features. This is also the sort of thing that I imagine ChatGPT, even the free version, could do in even less time. There's one caveat here, which is that error reporting is one pretty hard part of parsing. But if you understood that you wouldn't be recommending parser generators; poor error reporting capabilities is exactly why many production-quality languages have hand-rolled their parsers. > Writing the grammar will almost surely be significantly faster in the parser generator dsl than a handrolled recursive descent parser. I'm not interested in hearing speculation on things I've benchmarked. When it comes to performance, benchmark or GTFO. Performance isn't significantly different in most cases, and in pathological worst cases, it's often easily solved by memoizing (i.e. converting the recursive descent parser into a Packrat Parser). You shouldn't even memoize everything in most cases, because a lot of sub-parsers won't trigger backtracking, so there's no need to waste memory on memoization. > To improve your language design skills, you need to design multiple languages. Parser generators will get you a prototype faster and allow you to explore the language design space. To design a language, I don't need to write a parser at all in most cases. I certainly don't need to prototype syntax to design it effectively. Writing programs in your target syntax, even if you can't actually run them, is far more effective. Related to the fact that parsers aren't the hard part, syntax isn't the important part, so if you get bogged down in designing the syntax that's also a lose. I genuinely think most novel syntaxes create more usability/entry barriers for users than the benefits they offer. Go with the syntax of an existing popular language if you at all can--the simpler/more popular, the better. Semantics, idioms, and ecosystem are all much more important in what makes a language useful. > You can target a high level language to do the hard parts. That's exactly why this approach is terrible. The hard parts are the entire point of creating a new language. If the hard parts are all implemented in a different language then people should just use that language instead of yours. > Once you are satisfied with a language, then maybe it makes sense to design your own custom bytecode or gc to solve its unique problems. Still no--I don't think you understood what I meant when I said "the real hard problems of language development, which are things like bytecode generation and garbage collection". If you're targeting an existing VM such as the JVM or CLR you won't need to implement custom bytecode or GC, and even if you decide to implement your own bytecode or GC, you may be able to use an off-the-shelf implementation. You'll note that my post said bytecode generation, which is hard no matter what syntax you're implementing or bytecode you're targeting, because it's translating the semantics of the syntax to semantics that the target architecture can understand. When I said implementing garbage collection was hard, what I meant was not that implementing the algorithms is hard (you can literally plug in an off-the-shelf garbage collector in most cases) but that calling the garbage collection algorithms at the right times is hard.

_a_a_a_ 3y ago

Quoting [3]: "I’m going to make a claim here that will be unpopular with some compiler and language people. It’s OK if you don’t agree. Personally, I learn more from strongly stated opinions that I disagree with than I do from several pages of qualifiers and equivocation. My claim is that parsing doesn’t matter." agreed 100%

naasking 3y ago
Parsing matters for tooling, and that's about it. The recent Go retrospective on this goes into this somewhat, but if you have a reusable parser then you or others can easily create linters, formatters, and static analysis tools for your language, which really fleshes out the ecosystem.
- kerkeslager 3y ago
  I'd say that Nystrom's point in context is more "How you parse doesn't matter." He says, later in that link: "Recursive descent, Pratt parsing, and the popular parser generators like ANTLR or Bison are all fine." Any of these can be reusable parsers that you and/or others can easily use to create tools.