5 ms·

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 an

by jjice 5y ago

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!

eatonphil 5y ago
What did he want you to do initially? Handwritten?
- jjice 5y ago
  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.
  - stingraycharles 5y ago
    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.
    - stickfigure 5y ago
      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.
      - jjice 5y ago
        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!
      - dtech 5y ago
        to be pair those compilers course should cover much more than parsing. Iirc correctly it was like 10% of the course at my time.
    - jjice 5y ago
      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.
john567 5y ago
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.
- jjice 5y ago
  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.
- mbrodersen 5y ago
  I agree. Lex/yacc is on my “worst software I have ever used” list. Especially given how easy it is to write parsers.
outworlder 5y ago
> 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.
- dboreham 5y ago
  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.
  - gavinray 5y ago
    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.
    - sanxiyn 5y ago
      > 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.
  - chacham15 5y ago
    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.
mbrodersen 5y ago
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.

by jjice 5y ago

eatonphil 5y ago

What did he want you to do initially? Handwritten?

jjice 5y ago
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.
- stingraycharles 5y ago
  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.
  - stickfigure 5y ago
    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.
    - jjice 5y ago
      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!
    - dtech 5y ago
      to be pair those compilers course should cover much more than parsing. Iirc correctly it was like 10% of the course at my time.
  - jjice 5y ago
    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.

john567 5y ago

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.

jjice 5y ago
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.
mbrodersen 5y ago
I agree. Lex/yacc is on my “worst software I have ever used” list. Especially given how easy it is to write parsers.

outworlder 5y ago

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

dboreham 5y ago
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.
- gavinray 5y ago
  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.
  - sanxiyn 5y ago
    > 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.
- chacham15 5y ago
  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.

mbrodersen 5y ago

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.