4 ms·

I love how the SQLite author is so committed to the quality of his tools that he _wrote his own text editor_ as part of the project. In about 99% of cases, for

I love how the SQLite author is so committed to the quality of his tools that he _wrote his own text editor_ as part of the project. In about 99% of cases, for 99% of people, this is the wrong thing to do - but DRH pulled it off. On the "why use flex/yacc ... when you can roll your own", I think the tradeoff is: if you have a deep understanding of theory of parsing and parser generators, then it's actually less mental effort for you to write your own from scratch, than it would be to learn the exact syntax and quirks and possibly bugs of someone else's implementation. Or to find out that some feature that's easy to implement from scratch, doesn't exist in the library. I wonder, do we teach "classical" parsing that well anymore, in a way that could create the next generation's DRH?

deleted 4y ago
[deleted]
emrah 4y ago
Doing is the best way to learn. The mind looks over gaps in understanding which are revealed when trying to build. I think DRH picked a self-imposed constraint that sqlite would not have any external dependencies. A lot of his decisions are due to this constraint.
specialist 4y ago
> ...than it would be to learn the exact syntax and quirks and possibly bugs of someone else's implementation... Yup. Also, having deep knowledge of the language is required. SQLite's grammar is neat, modest. Creating a compatible parser would make a fun project. Here's a pretty good example: https://github.com/bkiers/sqlite-parser https://github.com/bkiers/sqlite-parser (Actual ANTLR 4 grammar: https://github.com/bkiers/sqlite-parser/blob/master/src/main/antlr4/nl/bigo/sqliteparser/SQLite.g4 https://github.com/bkiers/sqlite-parser/blob/master/src/main... ) Postgres, which tries to be compliant with the latest standards, however... SQL-2016 is a beast. Not to mention all the dialects. I'm updating my personal (soon to be FOSS) SQL DML grammar from ANTLR 3 LL(k) to ANTLR 4 ALL(Star). I've long had a working knowledge of SQL-92, with some SQL-1999 (eg common table expressions). But all the new structures and extensions are a bit overwhelming. Fortunately, ANTLR project has ~dozen FOSS grammars to learn from. https://github.com/antlr/grammars-v4/tree/master/sql https://github.com/antlr/grammars-v4/tree/master/sql They mostly mechanically translate BNFs to LL(k) with some ALL(Star). Meaning few take advantage of left-recursion. https://github.com/antlr/antlr4/blob/master/doc/left-recursion.md https://github.com/antlr/antlr4/blob/master/doc/left-recursi... Honestly, I struggled to understand these grammars. Plus, not being conversant with the SQL-2016 was a huge impediment. Just finding a succinct corbis of test cases was a huge hurdle for me. Fortunately, the H2 Database project is a great resource. https://github.com/h2database/h2database/tree/master/h2/src/test/org/h2 https://github.com/h2database/h2database/tree/master/h2/src/... Now for the exciting conclusion... My ANTLR grammar which passes all of H2's tests diverges significantly from the official or product specific BNFs. Mostly wrt recursion. Further, I found discrepancies between misc product's BNFs and their implementations. So a lot of trial & error is required for a "real world" parser. Which would explain why the professional SQL parsing tools ask for money. I still think creating a parser for SQLite is a great project. Hand-made or using grammar toolkit of choice. (I hope to play around with Pratt and PEG parsers some day.)
- osdotsystem 4y ago
  Thank you for the resources and insights. H2 is a great implementation!
legulere 4y ago
Using parser generators is not easier, it’s just less work. Recursive descent parsing is very easy and is the best option if you want good error handling for parsing. It’s very time-consuming though.
srcreigh 4y ago
Every UWaterloo CS student has to take CS241 (2nd year class, 4 months after learning C). Each student must write tokenizer and parser by hand. The full assignments include about 8 programs in binary and MIPS assembly, a MIPS assembler including support for labels, a scanner for subset of C, SLR(1) parsing, type checking, code gen including pointers and dynamic memory allocation. In my day there was a unit on compiler optimization, with a code size contest. Constant propagation, register allocation, dead code elimination. Now it seems they replaced that with a section involving writing a loader for a ELF-like file format in assembly language https://student.cs.uwaterloo.ca/~cs241/assignments/ https://student.cs.uwaterloo.ca/~cs241/assignments/
- tinco 4y ago
  It's a long time ago but I'm pretty sure we had similar assignments at utwente. I'm not so sure it's such a must know thing though. Lexers are fairly trivial to write by hand, and parsers are just annoying without code generation. We don't use tools like yacc because parsers are particularly difficult or complex, we use them because there's just a lot to gain from optimisations and fancy features, and without a generator or very powerful language features parsers will be too much work to maintain. Frankly, I'd expect someone who's never implemented a compiler before make the mistake of not using a parser generator because they are daunted by yacc and think their language is not going to need the complexity of an extra compile step. By the way if you don't need very fancy features, writing parsers with parser combinators is very easy and fun and doesn't require any metaprogramming tools. You can even write your own little parser combinator library because the concept is so simple.
  - ytygg775 4y ago
    I'm surprised nobody has mentioned ANTLR yet. That's the modern way of doing this.
  - foldr 4y ago
    > and without a generator or very powerful language features parsers will be too much work to maintain. Hand-written recursive descent parsers are quite commonly used in production compilers (e.g. GCC, Rust). See e.g. here: https://softwareengineering.stackexchange.com/questions/254694/why-did-gcc-switch-from-bison-to-a-recursive-descent-parser-for-c-and-c https://softwareengineering.stackexchange.com/questions/2546... They don’t seem to be particularly difficult to maintain.
kuwoze 4y ago
> if you have a deep understanding of theory of parsing and parser generators No deepness needed, the only thing you need to know is recursion. Also SQL is even better than that because every query is it's own statement, so the parsing is dead simple. I totally get why he did it this way.
MonkeyClub 4y ago
> he _wrote his own text editor_ as part of the project. I’ve not spotted that - and I have a thing for bespoke editors! Could somebody link me up to the editor? A few cursory searches didn’t prove fruitful.
- red_admiral 4y ago
  Unfortunately, it just says > And the text editor that I used to write SQLite is one that I wrote myself. [10] But with no more details.
- CGamesPlay 4y ago
  Based on the rest of GP's comment, I think he meant to say "parser" rather than "text editor". And that's referring to lemon: https://en.wikipedia.org/wiki/Lemon_(parser_generator) https://en.wikipedia.org/wiki/Lemon_(parser_generator)
- osdotsystem 4y ago
  If you read reference [10] on the book, he says he did not release the source of the editor.
  - MonkeyClub 4y ago
    Hm yeah I didn’t, I left the book for when I’m on a computer - thanks for spotting it! Obviously, now I’m curiouser about the secret editor :)
    - osdotsystem 4y ago
      Oh i wrote the book ^^, that's why.
osdotsystem 4y ago
Just a note that DRH's doctorate was in computational linguistics. This is reflected on SQLite in the sense that the part he likes working on the most is the front-end as opposed to features like concurrency for example. So, i guess a deep dive into the topic is required. What the above comments showed in terms of what is taught at unis seem to be great starting points. Since he already knew classical stack-based VMs from the start, this maybe shows he learnt it at uni. Would love to ask him about it!

deleted 4y ago

[deleted]

emrah 4y ago

Doing is the best way to learn. The mind looks over gaps in understanding which are revealed when trying to build. I think DRH picked a self-imposed constraint that sqlite would not have any external dependencies. A lot of his decisions are due to this constraint.

specialist 4y ago

> ...than it would be to learn the exact syntax and quirks and possibly bugs of someone else's implementation... Yup. Also, having deep knowledge of the language is required. SQLite's grammar is neat, modest. Creating a compatible parser would make a fun project. Here's a pretty good example: https://github.com/bkiers/sqlite-parser https://github.com/bkiers/sqlite-parser (Actual ANTLR 4 grammar: https://github.com/bkiers/sqlite-parser/blob/master/src/main/antlr4/nl/bigo/sqliteparser/SQLite.g4 https://github.com/bkiers/sqlite-parser/blob/master/src/main... ) Postgres, which tries to be compliant with the latest standards, however... SQL-2016 is a beast. Not to mention all the dialects. I'm updating my personal (soon to be FOSS) SQL DML grammar from ANTLR 3 LL(k) to ANTLR 4 ALL(Star). I've long had a working knowledge of SQL-92, with some SQL-1999 (eg common table expressions). But all the new structures and extensions are a bit overwhelming. Fortunately, ANTLR project has ~dozen FOSS grammars to learn from. https://github.com/antlr/grammars-v4/tree/master/sql https://github.com/antlr/grammars-v4/tree/master/sql They mostly mechanically translate BNFs to LL(k) with some ALL(Star). Meaning few take advantage of left-recursion. https://github.com/antlr/antlr4/blob/master/doc/left-recursion.md https://github.com/antlr/antlr4/blob/master/doc/left-recursi... Honestly, I struggled to understand these grammars. Plus, not being conversant with the SQL-2016 was a huge impediment. Just finding a succinct corbis of test cases was a huge hurdle for me. Fortunately, the H2 Database project is a great resource. https://github.com/h2database/h2database/tree/master/h2/src/test/org/h2 https://github.com/h2database/h2database/tree/master/h2/src/... Now for the exciting conclusion... My ANTLR grammar which passes all of H2's tests diverges significantly from the official or product specific BNFs. Mostly wrt recursion. Further, I found discrepancies between misc product's BNFs and their implementations. So a lot of trial & error is required for a "real world" parser. Which would explain why the professional SQL parsing tools ask for money. I still think creating a parser for SQLite is a great project. Hand-made or using grammar toolkit of choice. (I hope to play around with Pratt and PEG parsers some day.)

osdotsystem 4y ago
Thank you for the resources and insights. H2 is a great implementation!

legulere 4y ago

Using parser generators is not easier, it’s just less work. Recursive descent parsing is very easy and is the best option if you want good error handling for parsing. It’s very time-consuming though.

srcreigh 4y ago

Every UWaterloo CS student has to take CS241 (2nd year class, 4 months after learning C). Each student must write tokenizer and parser by hand. The full assignments include about 8 programs in binary and MIPS assembly, a MIPS assembler including support for labels, a scanner for subset of C, SLR(1) parsing, type checking, code gen including pointers and dynamic memory allocation. In my day there was a unit on compiler optimization, with a code size contest. Constant propagation, register allocation, dead code elimination. Now it seems they replaced that with a section involving writing a loader for a ELF-like file format in assembly language https://student.cs.uwaterloo.ca/~cs241/assignments/ https://student.cs.uwaterloo.ca/~cs241/assignments/

tinco 4y ago
It's a long time ago but I'm pretty sure we had similar assignments at utwente. I'm not so sure it's such a must know thing though. Lexers are fairly trivial to write by hand, and parsers are just annoying without code generation. We don't use tools like yacc because parsers are particularly difficult or complex, we use them because there's just a lot to gain from optimisations and fancy features, and without a generator or very powerful language features parsers will be too much work to maintain. Frankly, I'd expect someone who's never implemented a compiler before make the mistake of not using a parser generator because they are daunted by yacc and think their language is not going to need the complexity of an extra compile step. By the way if you don't need very fancy features, writing parsers with parser combinators is very easy and fun and doesn't require any metaprogramming tools. You can even write your own little parser combinator library because the concept is so simple.
- ytygg775 4y ago
  I'm surprised nobody has mentioned ANTLR yet. That's the modern way of doing this.
- foldr 4y ago
  > and without a generator or very powerful language features parsers will be too much work to maintain. Hand-written recursive descent parsers are quite commonly used in production compilers (e.g. GCC, Rust). See e.g. here: https://softwareengineering.stackexchange.com/questions/254694/why-did-gcc-switch-from-bison-to-a-recursive-descent-parser-for-c-and-c https://softwareengineering.stackexchange.com/questions/2546... They don’t seem to be particularly difficult to maintain.

kuwoze 4y ago

> if you have a deep understanding of theory of parsing and parser generators No deepness needed, the only thing you need to know is recursion. Also SQL is even better than that because every query is it's own statement, so the parsing is dead simple. I totally get why he did it this way.

MonkeyClub 4y ago

> he _wrote his own text editor_ as part of the project. I’ve not spotted that - and I have a thing for bespoke editors! Could somebody link me up to the editor? A few cursory searches didn’t prove fruitful.

red_admiral 4y ago
Unfortunately, it just says > And the text editor that I used to write SQLite is one that I wrote myself. [10] But with no more details.
CGamesPlay 4y ago
Based on the rest of GP's comment, I think he meant to say "parser" rather than "text editor". And that's referring to lemon: https://en.wikipedia.org/wiki/Lemon_(parser_generator) https://en.wikipedia.org/wiki/Lemon_(parser_generator)
osdotsystem 4y ago
If you read reference [10] on the book, he says he did not release the source of the editor.
- MonkeyClub 4y ago
  Hm yeah I didn’t, I left the book for when I’m on a computer - thanks for spotting it! Obviously, now I’m curiouser about the secret editor :)
  - osdotsystem 4y ago
    Oh i wrote the book ^^, that's why.

osdotsystem 4y ago

Just a note that DRH's doctorate was in computational linguistics. This is reflected on SQLite in the sense that the part he likes working on the most is the front-end as opposed to features like concurrency for example. So, i guess a deep dive into the topic is required. What the above comments showed in terms of what is taught at unis seem to be great starting points. Since he already knew classical stack-based VMs from the start, this maybe shows he learnt it at uni. Would love to ask him about it!