Hacker News Reader

Comment by omoikane | Hacker News Reader

I am most excited about the parser change, previously discussed here:

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

[2] https://github.com/ruby/prism/blob/main/src/prism.c

View on HN

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).

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.

Parser generators handle a lot of edge cases for you and are battle tested.

Unless I had a relatively simple grammar or had very strict performance requirements (like in the case of Ruby), I would not trust a hand rolled parser on a CFG by someone who isn’t dedicated to the craft. (PEGs are simpler so maybe).

I’ve written recursive descent parsers by hand and they look very simple until you have to deal with ambiguous cases.

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?

Arbitrary backtracking in a recursive descent parser is very easy with exceptions.

However, there's also an argument here that if the grammar is too complicated to be parsed with recursive descent, it's probably just too complicated in general and should be simplified if possible. Obviously you don't always have this option when you're dealing with an external grammar, but for your own PL, you can design around that. Most Wirth's languages are good examples; Pascal is famously LL(1).

Recursive descent parsers can have ambiguities, but like PEGs, they just resolve the ambiguity by arbitrarily picking one of the alternatives.

A famous example is ALGOL 60, which had the dangling else ambiguity (https://en.wikipedia.org/wiki/Dangling_else), but this was not discovered until the language had already been published. If they had been using a parser generator tool, it would have warned them that the grammar was not LL or LR.

Overall I do still prefer hand-written recursive descent parsers, but I do find this to be one of the biggest downsides of not using parser generators.

Of course the Algol 60 committee could not have used a parser generator tool because they were not invented until later in the 1960s, but your point is valid for anyone developing a language after that time.

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.

Ruby's syntax is also not trivial to parse and isn't set in stone either. At some point it was simply decided that trying to maintain the status quo was worse than attempting a rewrite which could bring in some extra gains, either through performance or having an easier time tweaking the grammar.

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.

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.

A very very long list of CVEs disagrees with that parsers are "not too difficult".

Binary format parsing != Programming language parsing.

Binary formats are rarely context free.

Agreed, but there are different things being prioritized with each approach.

"core complacency" was an excellent typo in the context of this conversation.

It's rather compelling even without the context. :(

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.

> 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?

Parser generators will tell you whether the grammar given to it is well-formed (according to whatever criteria the parser generator uses).

When hand-rolling a parser, there could be accidental ambiguities in the definition of your grammar, which you don't notice because the recursive descent parser just takes whatever possibility happened to be checked first in your particular implementation.

When that happens, future or alternative implementations will be harder to create because they need to be bug-for-bug compatible with whatever choice the reference implementation takes for those obscure edge cases.

> When hand-rolling a parser, there could be accidental ambiguities in the definition of your grammar, which you don't notice because the recursive descent parser just takes whatever possibility happened to be checked first in your particular implementation.

Is that a problem? Just use a grammar formalism with ordered choice.

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.

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.

> It is very practical to actually have a grammar

I fully agree that you need to have a grammar for your language.

> and thus the possibility to use any language that has a perser generator.

See, this is where it falls down in my experience. You can't just feed "the grammar" straight into each generator, and you need to account for the quirks of each generator anyway. So the practical, idk, "reusability"... is much lower than it seems like it should be.

If you could actually just write your grammar once and feed it to any parser generator and have it actually work then that would be cool. I just don't think it works out that way in practice.

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.

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."

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

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.

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).

Reply on news.ycombinator.com