3 ms·

I am most excited about the parser change, previously discussed here: https://news.ycombinator.com/item?id=36310130 https://news.ycombinator.com/item?id=363101

I am most excited about the parser change, previously discussed here: https://news.ycombinator.com/item?id=36310130 https://news.ycombinator.com/item?id=36310130 - Rewriting the Ruby parser (2023-06-13, 176 comments) I remember being taught to use yacc in our compiler course because "writing it by hand is too hard". But looks like Ruby joins the growing list of languages that have hand-written parsers, apparently working with generated parsers turned out to be even harder in the long run. That said, replacing a ~16k line parse.y[1] with a 22k line prism.c[2] is a pretty bold move. [1] https://github.com/ruby/ruby/blob/master/parse.y https://github.com/ruby/ruby/blob/master/parse.y [2] https://github.com/ruby/prism/blob/main/src/prism.c https://github.com/ruby/prism/blob/main/src/prism.c

PittleyDunkin 2y ago
I'm pretty sure the only reason people ever used parser generators is that it allows a language that vaguely resembles the formal description of the target language. I always found them very confusing to write, confusing to debug, and much less efficient than writing your own. It's actually pretty straightforward once you get the tokenization and lookahead working.
- pests 2y ago
  Agreed. Parser generators are a magic black box. Parsing is not too difficult, there is some actual computer science in some spots, but I think parsing should be a core complacency of a programming language to unlock full potential.
  - capitol_ 2y ago
    A very very long list of CVEs disagrees with that parsers are "not too difficult".
    - supriyo-biswas 2y ago
      Binary format parsing != Programming language parsing.
    - Blackthorn 2y ago
      Binary formats are rarely context free.
    - PittleyDunkin 2y ago
      Agreed, but there are different things being prioritized with each approach.
  - debo_ 2y ago
    "core complacency" was an excellent typo in the context of this conversation.
    - emptiestplace 2y ago
      It's rather compelling even without the context. :(
- cleanerbob 2y ago
  [dead]
psychoslave 2y ago
Number of line is as any metrics, it gives you a quick idea of some amount, and that's it. To start having a sense of what it means, you need to be more acquainted with the topic at end. It's not that uncommon to have an implementation with code that is lengthier but with an obvious pattern, while the smarter compressed implementation whose understanding is not necessary trivial to grab even for people seasoned to metaprogramming, reflexivity and so on. Not to say that is what happen here, the point here was to recall that number of lines is not an absolute linear metrics.
IshKebab 2y ago
It's not a "growing list" - the vast majority of languages use hand-written parsers.
viraptor 2y ago
It seems like you're ignoring the context/environment. Ruby has enough advanced developers, large enough test suite and enough people who care about performance, that it can tackle the parser as a longer project regardless of its complexity. The same thing will apply to other popular languages. But it won't apply to smaller projects with very localised parser use. In those cases writing anything custom would be a waste of time (and potential introduce bugs solved years ago in generators).
- lolinder 2y ago
  Having tried both on solo projects, I disagree: like other commenters here, I've found parser generators to be a big waste of time. Writing a parser by hand requires understanding the theory of parsing and understanding your implementation language. Writing a parser with a parser generator requires understanding the theory of parsing, your implementation language, and a gigantic black box that tries unsuccessfully to abstract away the theory of parsing. The time spent learning and troubleshooting the black box is almost always better spent putting together your own simple set of helper methods for writing a parser and then using them to write your own. The final result ends up being far easier to maintain than the version where you pull in a generator as a dependency.
  - plranw 2y ago
    The big plus of parser generators is that they report ambiguities. Handling conflicts is a pain but explicit. Do people who write predictive recursive descent parsers (LL(k)) really calculate first/follow sets by hand? What if the grammar requires backtracking?
    - lolinder 2y ago
      There's nothing to stop you from writing out a grammar in some form that is intelligible to a verification tool and then implementing the grammar by hand. I almost always write out the grammar anyway because that's the design—without it I'm flying blind. The cost of the generator isn't writing out the grammar, it's in using the runtime code it generates, which is optional even if you want to use it for verification.
badsectoracula 2y ago
> I remember being taught to use yacc in our compiler course because "writing it by hand is too hard". But looks like Ruby joins the growing list of languages that have hand-written parsers, apparently working with generated parsers turned out to be even harder in the long run. I've been writing parsers for simple (and sometimes not so simple) languages ever since i was in middle school and learned about recursive descent parsing from a book (i didn't knew it was called like that back then, the book had a section on writing an expression parser and i just kept adding stuff) - that was in the 90s. I wonder why yacc, etc were made in the first place since to me they always felt more complicated and awkward to work with than writing a simple recursive descent parser that works with the parsed text or builds whatever structure you want. Was it resource constraints that by the 90s didn't really exist anymore but their need in previous decades ended up shaping how parsers were meant to be written?
- junek 2y ago
  My hot take is that the allure of parser-generators is mostly academic. If you're designing a language it's good practice to write out a formal grammar for it, and then it feels like it should be possible to just feed that grammar to a program and have it spit out a fully functional parser. In practice, parser generators are always at least a little disappointing, but that nagging feeling that it _should_ work remains. Edit: also the other sense of academic, if you have to teach students how to do parsing, and need to teach formal grammar, then getting two birds with one stone is very appealing.
  - zelphirkalt 2y ago
    It is not academic. It is very practical to actually have a grammar and thus the possibility to use any language that has a perser generator. It is very annoying to have a great format, but no parser and no official grammar for the format available and being stuck with whatever tooling exists, because you would have to come up with a completely new grammar to implement a parser.
    - junek 2y ago
zelphirkalt 2y ago
I can only imagine working with generated parsers to become more difficult, if the syntax of a language is highly ad-hoc or irregular, not elegant like concattenative, or lispy languages, or Smalltalk style, which is ironic, given Ruby's history. Maybe they added too many bells and whistles. In every other case having a grammar in form of parser generator macros should be better and preferrred, since it is well portable to other languages and tools and lends itself to be more readable (with good naming).
jjice 2y ago
Good error reporting gets really tricky with generated parsers. That said, it can be a nice time saver for smaller things like DSLs and languages early on. Even then, yacc and bison are pretty solid overall. I believe Postgres still uses a yacc grammar today, as another high profile example. I'd arguebthr parsing of SQL is one or the least interesting thi.gs an RDBMS does, though.
- ljm 2y ago
  To reinforce your point on good error reporting, though, SQL errors are notoriously unhelpful. "Yeah there's an unbalanced parentheses...somewhere near this point... might actually be unbalanced, or you missed a comma or semicolon. You tell me."
norswap 2y ago
The biggest improvement from this (besides maybe performance) is that it should enable much better manually programmed syntax error messages. Those generated by yacc were pretty shit. This is generally my #1 reason for using a manual parser — nobody has yet made a pretty good syntax error handling / reporting for parser generators or parser combinators. It's genuinely very complex — I read the whole literature on that as of 2019 (there's surprisingly little). You basically have to inject custom logic, though there are a few heuristics that you can prepackage and can be useful in a lot of places. But the custom aspect of it means this doesn't play nice with traditional LL/LR parser generators. It could be done for parser combinators (PEG etc) however. Didn't have enough time in my PhD thesis to play with this, and I moved on to other things, but I'm hoping someone will make this eventually.

PittleyDunkin 2y ago

I'm pretty sure the only reason people ever used parser generators is that it allows a language that vaguely resembles the formal description of the target language. I always found them very confusing to write, confusing to debug, and much less efficient than writing your own. It's actually pretty straightforward once you get the tokenization and lookahead working.

pests 2y ago
Agreed. Parser generators are a magic black box. Parsing is not too difficult, there is some actual computer science in some spots, but I think parsing should be a core complacency of a programming language to unlock full potential.
- capitol_ 2y ago
  A very very long list of CVEs disagrees with that parsers are "not too difficult".
  - supriyo-biswas 2y ago
    Binary format parsing != Programming language parsing.
  - Blackthorn 2y ago
    Binary formats are rarely context free.
  - PittleyDunkin 2y ago
    Agreed, but there are different things being prioritized with each approach.
- debo_ 2y ago
  "core complacency" was an excellent typo in the context of this conversation.
  - emptiestplace 2y ago
    It's rather compelling even without the context. :(
cleanerbob 2y ago
[dead]

psychoslave 2y ago

Number of line is as any metrics, it gives you a quick idea of some amount, and that's it. To start having a sense of what it means, you need to be more acquainted with the topic at end. It's not that uncommon to have an implementation with code that is lengthier but with an obvious pattern, while the smarter compressed implementation whose understanding is not necessary trivial to grab even for people seasoned to metaprogramming, reflexivity and so on. Not to say that is what happen here, the point here was to recall that number of lines is not an absolute linear metrics.

IshKebab 2y ago

It's not a "growing list" - the vast majority of languages use hand-written parsers.

viraptor 2y ago

It seems like you're ignoring the context/environment. Ruby has enough advanced developers, large enough test suite and enough people who care about performance, that it can tackle the parser as a longer project regardless of its complexity. The same thing will apply to other popular languages. But it won't apply to smaller projects with very localised parser use. In those cases writing anything custom would be a waste of time (and potential introduce bugs solved years ago in generators).

lolinder 2y ago
Having tried both on solo projects, I disagree: like other commenters here, I've found parser generators to be a big waste of time. Writing a parser by hand requires understanding the theory of parsing and understanding your implementation language. Writing a parser with a parser generator requires understanding the theory of parsing, your implementation language, and a gigantic black box that tries unsuccessfully to abstract away the theory of parsing. The time spent learning and troubleshooting the black box is almost always better spent putting together your own simple set of helper methods for writing a parser and then using them to write your own. The final result ends up being far easier to maintain than the version where you pull in a generator as a dependency.
- plranw 2y ago
  The big plus of parser generators is that they report ambiguities. Handling conflicts is a pain but explicit. Do people who write predictive recursive descent parsers (LL(k)) really calculate first/follow sets by hand? What if the grammar requires backtracking?
  - lolinder 2y ago
    There's nothing to stop you from writing out a grammar in some form that is intelligible to a verification tool and then implementing the grammar by hand. I almost always write out the grammar anyway because that's the design—without it I'm flying blind. The cost of the generator isn't writing out the grammar, it's in using the runtime code it generates, which is optional even if you want to use it for verification.

badsectoracula 2y ago

> I remember being taught to use yacc in our compiler course because "writing it by hand is too hard". But looks like Ruby joins the growing list of languages that have hand-written parsers, apparently working with generated parsers turned out to be even harder in the long run. I've been writing parsers for simple (and sometimes not so simple) languages ever since i was in middle school and learned about recursive descent parsing from a book (i didn't knew it was called like that back then, the book had a section on writing an expression parser and i just kept adding stuff) - that was in the 90s. I wonder why yacc, etc were made in the first place since to me they always felt more complicated and awkward to work with than writing a simple recursive descent parser that works with the parsed text or builds whatever structure you want. Was it resource constraints that by the 90s didn't really exist anymore but their need in previous decades ended up shaping how parsers were meant to be written?

junek 2y ago
My hot take is that the allure of parser-generators is mostly academic. If you're designing a language it's good practice to write out a formal grammar for it, and then it feels like it should be possible to just feed that grammar to a program and have it spit out a fully functional parser. In practice, parser generators are always at least a little disappointing, but that nagging feeling that it _should_ work remains. Edit: also the other sense of academic, if you have to teach students how to do parsing, and need to teach formal grammar, then getting two birds with one stone is very appealing.
- zelphirkalt 2y ago
  It is not academic. It is very practical to actually have a grammar and thus the possibility to use any language that has a perser generator. It is very annoying to have a great format, but no parser and no official grammar for the format available and being stuck with whatever tooling exists, because you would have to come up with a completely new grammar to implement a parser.
  - junek 2y ago

zelphirkalt 2y ago

I can only imagine working with generated parsers to become more difficult, if the syntax of a language is highly ad-hoc or irregular, not elegant like concattenative, or lispy languages, or Smalltalk style, which is ironic, given Ruby's history. Maybe they added too many bells and whistles. In every other case having a grammar in form of parser generator macros should be better and preferrred, since it is well portable to other languages and tools and lends itself to be more readable (with good naming).

jjice 2y ago

Good error reporting gets really tricky with generated parsers. That said, it can be a nice time saver for smaller things like DSLs and languages early on. Even then, yacc and bison are pretty solid overall. I believe Postgres still uses a yacc grammar today, as another high profile example. I'd arguebthr parsing of SQL is one or the least interesting thi.gs an RDBMS does, though.

ljm 2y ago
To reinforce your point on good error reporting, though, SQL errors are notoriously unhelpful. "Yeah there's an unbalanced parentheses...somewhere near this point... might actually be unbalanced, or you missed a comma or semicolon. You tell me."

norswap 2y ago

The biggest improvement from this (besides maybe performance) is that it should enable much better manually programmed syntax error messages. Those generated by yacc were pretty shit. This is generally my #1 reason for using a manual parser — nobody has yet made a pretty good syntax error handling / reporting for parser generators or parser combinators. It's genuinely very complex — I read the whole literature on that as of 2019 (there's surprisingly little). You basically have to inject custom logic, though there are a few heuristics that you can prepackage and can be useful in a lot of places. But the custom aspect of it means this doesn't play nice with traditional LL/LR parser generators. It could be done for parser combinators (PEG etc) however. Didn't have enough time in my PhD thesis to play with this, and I moved on to other things, but I'm hoping someone will make this eventually.