4 ms·

(i'm on the supabase team) this is an update from the launch here: https://news.ycombinator.com/item?id=37020610 https://news.ycombinator.com/item?id=37020610

(i'm on the supabase team) this is an update from the launch here: https://news.ycombinator.com/item?id=37020610 https://news.ycombinator.com/item?id=37020610 The focus for the past few months has been getting the Parser right. It has been a lot of work. I'll ping Philipp and get him to join the discussion if there are any questions We'd also love more contributors, if this sort of thing is up your alley

specialist 3y ago
> ...getting the Parser right. It has been a lot of work. True. I have an ANTLR4 grammar for SQL. Am noob. Getting things "correct" was some effort. I have the quixotic goal of accepting multiple dialects. It's a lot of time referencing docs, playing with SQL fiddles, and learning how other grammars work. Now working on performance. Just as tough for noob me. TIL That means removing any potential ambiquities at runtime. ANTLR4's ALL(*) algorithm does some runtime magic whenever the happy path fails. Which tanks performance. Great for making "good enough" grammars. Not so great for chewing thru a corpus of tests. SQLite has a terrific test suite. Including generated 'random' machine queries. My naive grammar took > 1000ms on these monsters, when it worked. After a few, it'd just ABEND with out of memory errors. Whoops! By removing ambiquities, those monsters now take < 100ms. I really shouldn't make any claims until all the tests pass. (I'm still trying to figure out if I can handle both T-SQL style bracketed [names] and Postgres style name[index] array references, in the same grammar, without symmantic predicates.) Any way. This experience has piqued my interest in PEG. I'm worried my LL(k) grammar is too brittle. Making it hard to for any one to maintain and adapt. As you well know, for sure. (For a taste of this challenge, peek at some of the other available ANTLR SQL grammars.) Oh well; that's a concern for later. I'm looking forward to checking out Supabase's grammar. I'll share mine (Show HN) when I think it's good enough.
- steinroe 3y ago
  that's a huge task to take upon, looking forward to go through it! compared to you, we have gone the "easy" way and use the actual parser from the Postgres server. so no grammar definition and the like. our work was mainly around adapting libpg_query (which is build to parse executable SQL) for our use case.
  - CoastalCoder 3y ago
    > use the actual parser from the Postgres server. so no grammar definition and the like. Doesn't Postgres use Lex/Yacc to describe the grammar?
    - sjansen 3y ago
      It actually uses Flex/Bison, and does take advantage of the extended features they provide.
      - CoastalCoder 3y ago
        Thanks for the correction. But either way, doesn't this mean that a formal lexicon/grammar are available for the language server to draw upon?
- atonse 3y ago
  If we're all being postgres-specific, isn't there presumably a grammar somewhere in postgres's code that is used to parse the query SQL? Wouldn't you all want to use that same file as a source so it's 100% identical to what Postgres is actually doing? Genuine question. But maybe the tooling is incompatible. Also, have you looked at Azure Data Studio? I'm wondering how much you can reuse from the work they did.
  - aidos 3y ago
    Yacc, I believe. https://www.postgresql.org/docs/7.1/parser-stage.html https://www.postgresql.org/docs/7.1/parser-stage.html
  - SR2Z 3y ago
    Not necessarily. It might be a recursive descent parser (to generate better error messages).
  - specialist 3y ago
    I'll check out Azure Data Studio, thank you. For a bunch of reasons, probably all bad, I decided to roll my own, using ANTLR. Being just a simple bear, LALR (yacc, bison) is beyond me. With ANTLR4 the parse tree can be pretty close to the desired abstract syntax tree. Which is very nice. Also, ANTLR4 has automagic left-recursion, so grammars can be very similar to the (reference) EBNF. Lastly, ANTLR4 allows grammar inheritance. My hope is to have a subgrammar for each dialect which extends the one amazing core supergrammar. Looking at all the example SQL grammars, they're all pretty different, so it's not immediately clear how to generalize. Which is a bummer.
- _a_a_a_ 3y ago
  Where is the SQLite test suite, please? I'd be very interested. There are already SQL grammars, check https://github.com/antlr/grammars-v4 https://github.com/antlr/grammars-v4 specifically in here I think https://github.com/antlr/grammars-v4/tree/master/sql https://github.com/antlr/grammars-v4/tree/master/sql I contributed to one of them, and I wrote my own for some personal work. Be warned, it's very involved, very complex and MSSQL is rather ill-defined. Names bracket identifiers) in SQL are bloody awful. Sometimes square brackets are even compulsory, and why you can usually replace [...] with the SQL standard "..." , not always! Trust me, it gets worse. I don't find antlr grammars to be brittle, and while they can lose in performance (by how much I don't know, perhaps quite considerably) they are very easy to maintain and I am very fortunate to have antlr to work with. Edit: unless you are very familiar with the SQL and also a masochist, please don't try and write your own grammar. For someone with my background it was very time-consuming, without that background it will be a nightmare. Friendly warning.
  - specialist 3y ago
    > Where is the SQLite test suite Here's the scrapped tests: https://github.com/bkiers/sqlite-parser/tree/master/src/test/resources https://github.com/bkiers/sqlite-parser/tree/master/src/test... I didn't find a scrapper. I was cobbling together my own scrapper when I stumbled onto these files. My scrapper is turrible. This SQLite grammar is included in grammars-v4. Looks like a copy vs a fork. I don't know why these tests weren't copied too. > please don't try and write your own grammar I must be a masochist. Aside: Ages ago, during an job interview, when asked to talk about some of my prior work, I mentioned my SQL grammar. The self-described "bar raiser" cut me off, dismissed my effort as trivial, because the grammar generator (ANTLR) does all the work. I had no response.
    - _a_a_a_ 3y ago
      A, thanks for these tests! That will be really useful for my work. A couple of thoughts: what do you mean by a 'scrapper'? At first I thought you meant scraper, but I don't think it's that. I haven't come across the term before in this context, can you explain please. I'm a bit concerned about the times reported for your parsing. It's unfortunately well-known that the python output of antlr is agonisingly slow – what is your output language? (I don't think that's your problem, but if it is then switching to Java output will fix this immediately).
claytongulick 3y ago
Only tangentially related, but if it's of any interest I'm about 90% done with a PEG grammar for the PostgREST query DSL for similar reasons. Happy to share it if it'd be useful.
- emptysea 3y ago
  Do you have a link to the DSL? Curious to learn more
  - claytongulick 3y ago
    Yep, posted it in response to sibling comment.
- kiwicopple 3y ago
  it would definitely be interesting. if it's private and can't share a link, my email is in my profile
  - claytongulick 3y ago
    Sure, still a WIP but it's getting there [1] [1] https://github.com/superscribe-io/superscribe/blob/development/packages/grammar/postgrest/postgrest.peg-grammar https://github.com/superscribe-io/superscribe/blob/developme...
    - kiwicopple 3y ago
      thanks for sharing - we'll check it out

specialist 3y ago

> ...getting the Parser right. It has been a lot of work. True. I have an ANTLR4 grammar for SQL. Am noob. Getting things "correct" was some effort. I have the quixotic goal of accepting multiple dialects. It's a lot of time referencing docs, playing with SQL fiddles, and learning how other grammars work. Now working on performance. Just as tough for noob me. TIL That means removing any potential ambiquities at runtime. ANTLR4's ALL(*) algorithm does some runtime magic whenever the happy path fails. Which tanks performance. Great for making "good enough" grammars. Not so great for chewing thru a corpus of tests. SQLite has a terrific test suite. Including generated 'random' machine queries. My naive grammar took > 1000ms on these monsters, when it worked. After a few, it'd just ABEND with out of memory errors. Whoops! By removing ambiquities, those monsters now take < 100ms. I really shouldn't make any claims until all the tests pass. (I'm still trying to figure out if I can handle both T-SQL style bracketed [names] and Postgres style name[index] array references, in the same grammar, without symmantic predicates.) Any way. This experience has piqued my interest in PEG. I'm worried my LL(k) grammar is too brittle. Making it hard to for any one to maintain and adapt. As you well know, for sure. (For a taste of this challenge, peek at some of the other available ANTLR SQL grammars.) Oh well; that's a concern for later. I'm looking forward to checking out Supabase's grammar. I'll share mine (Show HN) when I think it's good enough.

steinroe 3y ago
that's a huge task to take upon, looking forward to go through it! compared to you, we have gone the "easy" way and use the actual parser from the Postgres server. so no grammar definition and the like. our work was mainly around adapting libpg_query (which is build to parse executable SQL) for our use case.
- CoastalCoder 3y ago
  > use the actual parser from the Postgres server. so no grammar definition and the like. Doesn't Postgres use Lex/Yacc to describe the grammar?
  - sjansen 3y ago
    It actually uses Flex/Bison, and does take advantage of the extended features they provide.
    - CoastalCoder 3y ago
      Thanks for the correction. But either way, doesn't this mean that a formal lexicon/grammar are available for the language server to draw upon?
atonse 3y ago
If we're all being postgres-specific, isn't there presumably a grammar somewhere in postgres's code that is used to parse the query SQL? Wouldn't you all want to use that same file as a source so it's 100% identical to what Postgres is actually doing? Genuine question. But maybe the tooling is incompatible. Also, have you looked at Azure Data Studio? I'm wondering how much you can reuse from the work they did.
- aidos 3y ago
  Yacc, I believe. https://www.postgresql.org/docs/7.1/parser-stage.html https://www.postgresql.org/docs/7.1/parser-stage.html
- SR2Z 3y ago
  Not necessarily. It might be a recursive descent parser (to generate better error messages).
- specialist 3y ago
  I'll check out Azure Data Studio, thank you. For a bunch of reasons, probably all bad, I decided to roll my own, using ANTLR. Being just a simple bear, LALR (yacc, bison) is beyond me. With ANTLR4 the parse tree can be pretty close to the desired abstract syntax tree. Which is very nice. Also, ANTLR4 has automagic left-recursion, so grammars can be very similar to the (reference) EBNF. Lastly, ANTLR4 allows grammar inheritance. My hope is to have a subgrammar for each dialect which extends the one amazing core supergrammar. Looking at all the example SQL grammars, they're all pretty different, so it's not immediately clear how to generalize. Which is a bummer.
_a_a_a_ 3y ago
Where is the SQLite test suite, please? I'd be very interested. There are already SQL grammars, check https://github.com/antlr/grammars-v4 https://github.com/antlr/grammars-v4 specifically in here I think https://github.com/antlr/grammars-v4/tree/master/sql https://github.com/antlr/grammars-v4/tree/master/sql I contributed to one of them, and I wrote my own for some personal work. Be warned, it's very involved, very complex and MSSQL is rather ill-defined. Names bracket identifiers) in SQL are bloody awful. Sometimes square brackets are even compulsory, and why you can usually replace [...] with the SQL standard "..." , not always! Trust me, it gets worse. I don't find antlr grammars to be brittle, and while they can lose in performance (by how much I don't know, perhaps quite considerably) they are very easy to maintain and I am very fortunate to have antlr to work with. Edit: unless you are very familiar with the SQL and also a masochist, please don't try and write your own grammar. For someone with my background it was very time-consuming, without that background it will be a nightmare. Friendly warning.
- specialist 3y ago
  > Where is the SQLite test suite Here's the scrapped tests: https://github.com/bkiers/sqlite-parser/tree/master/src/test/resources https://github.com/bkiers/sqlite-parser/tree/master/src/test... I didn't find a scrapper. I was cobbling together my own scrapper when I stumbled onto these files. My scrapper is turrible. This SQLite grammar is included in grammars-v4. Looks like a copy vs a fork. I don't know why these tests weren't copied too. > please don't try and write your own grammar I must be a masochist. Aside: Ages ago, during an job interview, when asked to talk about some of my prior work, I mentioned my SQL grammar. The self-described "bar raiser" cut me off, dismissed my effort as trivial, because the grammar generator (ANTLR) does all the work. I had no response.
  - _a_a_a_ 3y ago
    A, thanks for these tests! That will be really useful for my work. A couple of thoughts: what do you mean by a 'scrapper'? At first I thought you meant scraper, but I don't think it's that. I haven't come across the term before in this context, can you explain please. I'm a bit concerned about the times reported for your parsing. It's unfortunately well-known that the python output of antlr is agonisingly slow – what is your output language? (I don't think that's your problem, but if it is then switching to Java output will fix this immediately).

claytongulick 3y ago

Only tangentially related, but if it's of any interest I'm about 90% done with a PEG grammar for the PostgREST query DSL for similar reasons. Happy to share it if it'd be useful.

emptysea 3y ago
Do you have a link to the DSL? Curious to learn more
- claytongulick 3y ago
  Yep, posted it in response to sibling comment.
kiwicopple 3y ago
it would definitely be interesting. if it's private and can't share a link, my email is in my profile
- claytongulick 3y ago
  Sure, still a WIP but it's getting there [1] [1] https://github.com/superscribe-io/superscribe/blob/development/packages/grammar/postgrest/postgrest.peg-grammar https://github.com/superscribe-io/superscribe/blob/developme...
  - kiwicopple 3y ago
    thanks for sharing - we'll check it out