Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Postgres Language Server: Implementing the Parser

supabase.com

Post reply on HN
Print view View original

11–20 of 47 posts

Re: Postgres Language Server: Implementing the Parser

#11

Post by kageiit »

steinroe wrote: post #3

hey, author here. Thanks for posting it! A bit of background: a few months ago we announced a Postgres language server[0]. A language server adds features like syntax error diagnostic and autocomplete to your editor (vscode, neovim, etc). We have iterated a lot on the parser over the past few months and want to share an update today. the parser is a core piece of any language server that constructs syntax trees from…

Have you considered using something like a treesitter grammar? It could solve the editor specific uses cases like highlighting and even linting as it creates asts that are more amenable for a language server implementation

Re: Postgres Language Server: Implementing the Parser

#13

Post by steinroe »

epgui wrote: post #12

Out of curiosity, why are parser combinators not the choice approach for something like this? Is it mainly a performance thing? PS— this is super exciting!

in our specific case, we needed something handwritten for the statement-level parser anyways. And the requirements for the LL parser are very simple: extract individual sql statements from a source input. we just compare the next n tokens with a list of tokens from which any statement starts, which is straightforward to implement with a handwritten LL parser.

so after all, I would say its a decision based on the special requirements we have working around the limitation of libpg_query. I think its also the fastest one, but this was not the main reason.

Re: Postgres Language Server: Implementing the Parser

#14

Post by chatmasta »

kageiit wrote: post #11
steinroe wrote: post #3

hey, author here. Thanks for posting it! A bit of background: a few months ago we announced a Postgres language server[0]. A language server adds features like syntax error diagnostic and autocomplete to your editor (vscode, neovim, etc). We have iterated a lot on the parser over the past few months and want to share an update today. the parser is a core piece of any language server that constructs syntax trees from…

Have you considered using something like a treesitter grammar? It could solve the editor specific uses cases like highlighting and even linting as it creates asts that are more amenable for a language server implementation

At Splitgraph we compiled tree-sitter to wasm for Postgres autocomplete. Indeed, one major reason we opted for it is that it has error handling so it can work with incomplete syntax (which is what your code is 90% of the time you're editing it).

https://www.splitgraph.com/blog/parsing-pgsql-with-tree-sitt...

Re: Postgres Language Server: Implementing the Parser

#15

Post by specialist »

kiwicopple wrote: post #2

(i'm on the supabase team) this is an update from the launch here: 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

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

Re: Postgres Language Server: Implementing the Parser

#16

Post by steinroe »

specialist wrote: post #15
kiwicopple wrote: post #2

(i'm on the supabase team) this is an update from the launch here: 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

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

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.

Re: Postgres Language Server: Implementing the Parser

#17

Post by gen220 »

steinroe wrote: post #3

hey, author here. Thanks for posting it! A bit of background: a few months ago we announced a Postgres language server[0]. A language server adds features like syntax error diagnostic and autocomplete to your editor (vscode, neovim, etc). We have iterated a lot on the parser over the past few months and want to share an update today. the parser is a core piece of any language server that constructs syntax trees from…

Thank you for doing this!

Every year I get frustrated with a PostgreSQL formatter, look out into the webs for hope, and begrudgingly return to my sub-par editing experience.

Please take your time to do a good job, and thank you, again!

Re: Postgres Language Server: Implementing the Parser

#18

Post by anarazel »

2mm3mm3 wrote: post #6

When will PG finally start using tasks instead of superheavyweight threads? When will they automatically precompile/hash statements to avoid reparsing? And when materialized views will be automatically updated? Where is an alternative to SQL Server Always On Availability Group released >10 years ago? PostgreSQL is the only database where guys recommend you to configure a separate connection pooler, because their data…

When will you contribute?

Re: Postgres Language Server: Implementing the Parser

#19

Post by epgui »

steinroe wrote: post #13
epgui wrote: post #12

Out of curiosity, why are parser combinators not the choice approach for something like this? Is it mainly a performance thing? PS— this is super exciting!

in our specific case, we needed something handwritten for the statement-level parser anyways. And the requirements for the LL parser are very simple: extract individual sql statements from a source input. we just compare the next n tokens with a list of tokens from which any statement starts, which is straightforward to implement with a handwritten LL parser. so after all, I would say its a decision based on the spec…

Thanks for your response!

I'm a little confused by it though... Maybe I am misunderstanding what you're telling me.

I would definitely consider a parser implemented with parser combinators to be "handwritten". The main difference for me is that parser combinators allow you to express a language grammar in a more declarative way, which makes refactoring and correctness verification much simpler. I think what you describe as "straightforward" without combinators would be "completely trivial" with combinators.

I know from reading recent comp sci papers (particularly in the Journal of Functional Programming) that "the parser problem" is not fully solved yet (!) and that there are various theoretical limits to all currently known formal approaches. I suspect that performance could be a limiting factor for certain types of syntaxes, although I'm not sure if Postgres' would be particularly problematic in this regard.

Re: Postgres Language Server: Implementing the Parser

#20

Post by steinroe »

chatmasta wrote: post #14
kageiit wrote: post #11

Earlier quoted context omitted.

Have you considered using something like a treesitter grammar? It could solve the editor specific uses cases like highlighting and even linting as it creates asts that are more amenable for a language server implementation

At Splitgraph we compiled tree-sitter to wasm for Postgres autocomplete. Indeed, one major reason we opted for it is that it has error handling so it can work with incomplete syntax (which is what your code is 90% of the time you're editing it). https://www.splitgraph.com/blog/parsing-pgsql-with-tree-sitt...

thanks for the link, very interesting read! and you are right, libpg_query has its limitations.

the idea is to first implement the parser with libpg_query and work around its limitations as good as possible. Since the scan api also returns all tokens for invalid sql, the language server will then have basic features and syntax error diagnostics for invalid statements, and advanced features for valid ones. once the server itself is done, we want to go back to the parser and replace the libpg_query-based parser with a more resilient alternative statement by statement. ultimately, the libpg_query-based parser should just be the fallback.

that being said, very excited that there is so much development in postgres dx.

Post reply on HN