Ubiquitous SQL Grammar

ngx

Hi, sorry to be a bit slow replying. I only saw that you had put up the question today. Let's see... as for supporting multiple SQL dialects in a maintainable way, I suppose you realize that this kind of problem is pretty much intractable with the legacy JavaCC. It's really too under-powered since it is missing certain very basic features you would need to organize the code.

JavaCC 21 (or we should maybe get used to calling it CongoCC) does have certain key features that would allow you to attack the problem. It's still not so easy, of course, but you have a lot more degrees of freedom to organize your code in a maintainable way.

Specifically, for example, there is a preprocessor, see: https://javacc.com/2021/02/01/javacc-21-has-a-preprocessor/

So you can turn on/off parts of your grammar conditionally based on preprocessor symbols.

Also, the ability to have context-sensitive tokenization could be quite useful, as described here: https://javacc.com/2021/06/13/activating-de-activating-tokens/

Also, having an INCLUDE directive would make a big difference. So you could have a master generic SQL grammar and, in conjunction with the preprocessor, conditionally include different subgrammar files.

So, I guess the answer to your question is that what you are thinking about can be envisaged, yes. The machinery is there that you could attack the problem.

So, basically: go for it!

By the way, if you do, you could consider donating the result to this project. I think it would be quite attractive to have a real-world-useful SQL grammar in our examples directory!

And, of course, your authorship would attributed and you would be able to use it in your own projects just the same, so... Something to bear in mind.

ngx

Okay, as regards this case:

select HIGH_PRIORITY bla from table1

one way to deal with this situation with a lookahead would be to write a production that is specifically only used in lookahead, i.e. something like:

  SelectHighPriorityLA#scan :
       <SELECT> <IDENTIFIER> 
       ASSERT {currentLookaheadToken.getImage().equalsIgnoreCase("HIGH_PRIORITY")}
       <IDENTIFIER>
  ;

(Note, BTW that the #scan annotation means that the production is only used in a lookahead, so no regular parsing production is generated or any skeletal node class.)

And then this can be used in a lookahead like:

          SCAN SelectHighPriorityLA
          => <SELECT> ACTIVATE_TOKENS HIGH_PRIORITY (<HIGH_PRIORITY>)
                <IDENTIFIER> <FROM> <IDENTIFIER>
          |
          ... (other choices)

So, you see, the lookahead SelecthighPriorityLA actually scans ahead and if the token after <SELECT> is not "HIGH_PRIORITY" then the lookahead fails and it goes to the next choice.

You can see this being used in the current Java grammar here: https://github.com/javacc21/javacc21/blob/master/examples/java/Java.javacc#L174

Since "record" is a soft keyword, i.e. it is a keyword in this context of a type declaration but elsewhere can just be a regular identifier, we have this trick, which is basically the same thing as what I propose above. Note that this is a little tricky because the lookahead is scanning the string "record" as an identifier but then when it actually goes into the RecordDeclaration production (see line 276 of the same file) it actually rescans the "record" as a <RECORD> token.

Note also that for this to work, we need what is on line 48 of that file, i.e.

  DEACTIVATE_TOKENS=RECORD, VAR, YIELD, SEALED, NON_SEALED, PERMITS;

The various soft tokens are de-activated by default and only activated in the spot where they are realy not just identifiers.

Actually, another example that I think worthy of study would be how certain roughly similar things are dealt with in the C# grammar I wrote recently. See here: https://github.com/javacc21/javacc21/blob/master/examples/csharp/CSharp.javacc#L1017
and: https://github.com/javacc21/javacc21/blob/master/examples/csharp/CSharp.javacc#L859

So, you see, there is this machinery to deal with context-sensitive tokenization. It is still a bit tricky because you have to be cognizant of when a token type is activated or not. So you can write a lookahead that is based on the token type not being active but then when you actually go and parse, the ACTIVATE_TOKEN actually rolls back any cached tokens from the lookahead and rescans it as the appropriate token type, so it's in the AST as that (soft) token type, not just an identifier.

ngx

Let's see... Offhand, I guess what you need to do is consume tokens until you can actually parse an expression, so it might be something like:

   (
          SCAN ~(Expression)
          => LeadingToken
   )*

Though, that said, my intuition would be that you might end up defining some separate production solely for the Expression lookahead, so you might end up with

     (  SCAN ~(ExpressionLA) => LeadingToken )*

But the idea would be that if the input that follows can't be parsed an expression, we just consume the token that follows, which I assume would be maybe one of several types.

Actually, it occurs to me that you might actually need a sort of compound lookahead, because you also want to check whether the next token is one of the appropriate leading token types, no? So you'd have maybe something like:
(
SCAN {getToken(1).getType() == SOME_TYPE || getToken(1).getType() == SOME_OTHER_TYPE}
_ExpressionLA
=> <SOME_TYPE>|SOME_OTHER_TYPE>
)*

ngx You already hinted well on the negative SCAN approach but I wonder if this may not be not efficient enough.

Well, the only way to know whether the approach is efficient enough would be to try it. My intuition is that, most likely, you'll be quite pleasantly surprised. Just thinking about this (though obviously you need to try it) If the lookahead usually fails and it fails in the first... I dunno... two or three tokens, it might not be very expensive at all -- especially if the tokens you're scanning ahead are cached.

The thing about activating/deactivating token types OR just switching lexical states is that one ends up throwing away any cached tokens, so the machinery has to retokenize, so that could be a wee bit costly. But if you're not resetting the cached tokens, then just thinking about this offhand, then it's probably all pretty cheap.

And, that said, even retokenizing the input is not even terribly expensive! As things stand, the generated parsing/lexing code is pretty efficient. Not that we are getting that much feedback (I'd like to get more and I'm pretty happy to be "bombarded" as you say) but there is some feedback and I can't recall anybody saying they have some big performance problem. OTOH, with the main competing tool, ANTLR, it's entirely different. You can see just how much buzz there is about performance issues. In fact, that's probably why the old legacy JavaCC is still fairly widely used after so many years of abandonment. People try to switch to ANTLR and the performance hit is just terrible.

ngx Root :
(ChainedStmt)+ ! <EOF>;

Well, yeah, first of all, I guess you figured out that, unless you put in some resync points with the !, fault-tolerant doesn't do anything! (Well, hold on, actually it does, because the various one-off token skipping tricks are in operation, but that's separate from the resync point concept... so if you don't define any resync point...)

Now, I guess you've probably also figured out that lookahead and fault-tolerant are basically orthogonal. I mean, fault-tolerant behavior only applies when you're in regular parsing, not when you're in a lookahead. So, the line above basically means that if we hit a problem when parsing a ChainedStmt construct, we're going to go into some recovery routine that tries to get back on the rails either by finding the start of a new ChainedStmnt or an EOF (since that is what the following construct is). So in this case, there could be a megabyte of unparseable goo between the last ChainedStmt and the end of the file, and it just gets discarded basically. Well, turned into an InvalidNode object, right? (It's been so long since I actually looked at this that I have to think back...)

I completed the coding of this whole fault-tolerant thing over a year ago but it's still not very mature or anything. I finished that off but sort of left it in an unpolished state because I then turned to rewriting the tokenizer part and meant to get back to really getting that into shape and never did.

Well, in short, I'm very interested in feedback from people trying to use it. There isn't really a fleshed out API for identifying the problematic parts of the AST, even though that is not really very hard to do. Or, another way to look at this is that the advantage of the current state of affairs is that you have a chance to have some serious input into how the final version works.