Hacker News Reader

Comment by jjice | Hacker News Reader

Part 3.1.1 is about the parser, which uses lex and yacc. I actually used it as a source to convince a professor to let us use lex and yacc to build our lexer and parser for a SQL engine for a DB implementation class I took. His expectations were a bit unrealistic for what a bunch of seniors would be able to accomplish in three weeks in C (other similar level of difficulty classes and job searching weigh a real burden), and he initially said no to me asking if we could use lex and yacc. Postgres's source made a convincing enough argument. Gave me a reason to learn lex and yacc, as well as making a much easier to modify parser. I wrote the parser for my group, and we were the only group that finished the parser in time, and at all.

Just an anecdote with some fond memories that were made possible by Postgres and its internals. Postgres has a place in my heart for that, and being a damn fine DB of course!

View on HN

I think it's important to write your own parser, at some point. Though, for the purpose of learning you need someone to guide you.

If you're learning this stuff you need a simple challenge to work through the end.

With regards to lex and yacc, I absolut detest these tools. They are horrible but they do work. And if you just want a functioning parser they'll do. My main criticism of these tools are the horrible errors you might end up with and the lack of sensible extension points.

If it is your first foray into parsers, I do think a simple grammar and handwritten lexer/parser is a good first step. Iterate some on that, then use tools to help with the verbose stuff.

Though to be honest, I enjoy writing parsers by hand. So, I'm a bit biased.

So we did build the DDL handwritten and did well on that portion of the product, but given the constraint of me being the only person to write the parser for the DML, along with having to be done and error free in three weeks where I was also occupied, all while being written in C, I felt yacc really helped a lot there.

The big thing for this particular project was all the pitfalls of C with having to track memory allocations and passing arrays of pointers around and mentally keeping track. Yacc streamlined this a lot. If this was a production project and not a class I took along side four other, hand writing would be a serious option I'd consider (mostly for error reporting purposes like you mentioned), but I might even lean towards getting an MVP done in a parser generator and eventually converting over to handwritten if the need arose.

I agree. Lex/yacc is on my “worst software I have ever used” list. Especially given how easy it is to write parsers.

> and he initially said no to me asking if we could use lex and yacc

What?

On my compilers class, I was explicitly asked to use lex and yacc. Sure, for the very first assignment on that class we were asked to write the lexer by hand. But when it came to actually do the interesting parts, lex and yacc it was.

This seems to have been subject to waxing and waning fashion. I had a similar experience recently -- someone sent me a PR with a hand-written parser. I commented "do people write parsers by hand any more?". After some push back, I searched online and found a ton of articles "why you should write your own parser and not use a parser generator". Still beats me as to why though.

I've tried to write PEG grammars/parsers and found that I am not quite smart enough to figure it out.

Hand-written lexer/parser means you can be dumb as a doornail and just walk through the logic.

As an aside, it also gives you a better ability to write error messages, and an easier time debugging compared to autogenerated solutions.

> it also gives you a better ability to write error messages

This is not true. Instead of trying to use error recovery feature of parser genrator, you can just add error case to your grammar, and it works as well as hand-written parser. Parser generator error recovery is pure bonus on top.

> and an easier time debugging compared to autogenerated solutions

This is also not true. Most parser generators (certainly lex/yacc) have good enough debug support that you never see generated code while you debug.

There are a few reasons for this. Some languages arent Context Free Grammars (the classic example for this is "A * B;" is this multiplication of the A and B variables or is it a declaration of the B variable with the type being a pointer to an A) which make writing the grammar much harder in the first place. Some solutions to this are using a GLR parser instead, but that has the downside of super high execution time in the worst case. Lastly, even if you overcome all of these with the proper structure and hints, you run into pretty bad error cases. I.e. handing an invalid input is hard and giving an error to the user that makes sense is even more difficult. (which of the possible branches in the grammar rules is the one thats wrong? in simpler grammars you can probably give a good error, but a C grammar is going to have a much harder time) This is why gcc moved away from using a grammar to a custom parser IIRC.

I've heard the "useful error message" argument, but my personal experience coding modern languages suggests that not much progress has been made on that front. The compiler error message is almost never "useful".

You might want to check out the Elm compiler: https://elm-lang.org/news/compilers-as-assistants

In my compilers class at university we wrote a recursive descent parser by hand but we wrote the LALR and LL parsers using yacc or bison I think - that was what the three assignments said to do and the professor said using a parser generator was the only sensible approach for LALR and LL parsers.

You must be from the same vintage as me!

This was around a decade ago but my professor was not a young man (early 60s I'd guess).

I write parsers all the time. It is quick for me to do and it has many advantages. Including much better error messaging and easy to debug code. The code generated by most parser generators are not really human readable. Making fixing complicated parsing bugs super hard.

I highly recommend not using lex/yacc. I wrote an SQL parser in a day for a custom DB at work. It’s super easy to write recursive descendent parsers once you know how to do it. So just learn it by starting with something simple. XML, Lisp or JSON for example.

What did he want you to do initially? Handwritten?

Handwritten. It worked for the first portion of the parser (DDL), but it was a real pain to debug and build while keeping track of mallocing and freeing along the way.

We got an A on that first parser that was hand written as well, but once we got to DML, I felt like we could really use tools given our time frame.

It sounds a bit silly to implement a parser for a DB internals course, though. You'll end up teaching lexing and parsing (something which the professor wasn't too familiar with himself it seems?), rather than db internals.

Implementing your own WAL + storage API for example, is more something along the lines I would expect.

Agreed. At my university, in my era (almost 30 years ago), the compilers sequence was two full quarters and generally considered to be the hardest classes in the CSc major. I really loved it but it would have been a huge distraction mixed in with the DB classes.

Those compilers classes turned out to be pretty useful. I ended up having to build custom parsers several times in my career... including an SQL parser.

I actually took my university's compiler course at the same time as this DB course, and that was my favorite class out of all four years, hands down. Honestly, the parsing portion of my DB class was helped out by the knowledge I got from the compiler class earlier in the semester, so at least it worked out!

to be pair those compilers course should cover much more than parsing. Iirc correctly it was like 10% of the course at my time.

Absolutely. That was one of my complaints with the class. I have an interest in compilers and the process, but I took this course to learn about storage and efficient lookups.

Reply on news.ycombinator.com