Building a query parser over a weekendPart II
In the previous post I talked about what I wanted to get, and how I decided to use the GOLD parser to formally define the language grammar. However, I had no intention of actually generating the parser, I wanted to write it myself. This is because I have a lot of poor experience with the results of parser generators. They generate horrible code that manages to be both unreadable and force you to go into it frequently enough to be maddening.
In particular, I haven’t been able to find anything that would be good enough as a hand rolled parser in terms of performance, readability of the code and the quality of errors it will generate. The later might sound strange, but a key part of the usefulness of any language is the kind of errors that you get when you give it invalid output.
An important consideration is that I’m intending to accept input over HTTP, so I can assume that my input is already wrapper in a pretty System.String package, which saves a lot of the complications that you usually have to deal with if your input is a streaming medium. Initially I tried to go with a scanner / parser in the same place, but that ended up being a Bad Idea, it was too complex to handle. Instead, I split the responsibility to a scanner and parser classes.
The scanner is responsible for scanning the string and finding the next token. But I decided to make it reactive, so you’ll tell it what you expect, and it will see if the next bit matches. Scanners will typically scan the input and produce a stream of tokens. That works, but it means that you need a lot more state in the scanner, and it can be more complex. I decided to simply if as much as I possible could.
Here is how we find identifiers in the scanner:
You might notice that the code is pretty simply, it runs over the input string (_q) and check if the next token is an identifier based on our rules. That make the parser code easier to handle. Let us consider how we can parse a FROM clause. The formal definition is:
<From> ::= 'FROM INDEX' <From Source> | 'FROM' <From Source>
<From Source> ::= <Simple Field> 'AS' <Simple Field> | <Simple Field>
<Simple Field> ::= Identifier | StringLiteral
If you are familiar with BNF, this is quite readable. Now, how do we parse this? Here is the actual parser code:
As you can see, we start by asking for a FROM token (the scanner is case insensitive, so we don’t need to worry about casing) then check if this is followed by INDEX term then we get actual identifier or string literal to use, and possible alias.
This code can parse the following:
- from Users
- from Users as user
- from index “Users/ByActiveMarker” AS u
You can note that I’m taking full advantage of the possibly of asking the input several questions, because it make my code simpler overall. I’m also not doing any substring operations. Instead, I’m passing indexes into the overall query string that allow me to get the information without paying the price for allocating all those strings.
In this manner, we also get something that is pretty easy to work with, and we can compare it to the formal definition to guide us in the parsing. At the same time, we get code that is readable and has quite good performance.
It looks like your FromClause code is a hybrid between edits - there's a filter variable that is only set to null and included in the 4-tuple at the end but the function is only defined to return a 3-tuple.
Damien, Thanks, I fixed it.
I simplified the syntax a bit for the blog post, and I missed it.
Have you considered a Pratt parser?
I highly recommend the book "Writing an Interpreter in Go" by Thorsten Ball which uses a Pratt parser to create an interpreter. While you're at it, learn a little about the Go programming language. An "interpreter" is really a compiler.
Here is a good tutorial/blog about building an interpreter in python for the pascal programming language. This is good too. So far, there are 14 parts. https://ruslanspivak.com/lsbasi-part1/
If you haven't guessed yet, I like hand-made compilers. I do not like compiler-generators.
Oh, one last thing. Your SQL Parser will NEVER be finished. Ha ha ha... Evil laugh there. There will always be some new feature to implement. Some improvement to be made. Some bug to fix.
Creating a SQL relational database in C# was the best thing I could do to motivate me to build a compiler. I then even created a calculator that turned into my own little language. It was fun.
Again, once you start working on a compiler, you will never finish it... because you will be so motivated by writing it that you won't stop...