How to disambiguate a subselect from a parenthesized expression?-CodePudding

The

What would be a possible way to disambiguate this?

I suppose the main thing is here:

'(' query_statement ')'

Since that recursively calls itself -- is there a way to do indirection or something else such that a query_statement called from within parens can never itself have parens?

Also, maybe this is a common thing? I get the same ambiguous output when running this on the official MySQL grammar

I would be curious whether any of the grammars can solve the issue here:

That's a reasonable interpretation of your input and it is identified as a subSelect expr. It's a subSelect nested in a parenExpr (both of which are exprs).

If I switch up your rule a bit:

expr: '(' query_expr ')' # subSelect | '(' expr ')' # parenExpr | Atom # identifier ;

Now it's a subSelect that interprets the nested (select 1) as a query expression.

It's ambiguous because the outer parenthesized expression could match either of the first two alternatives resulting in different parse trees.

In ANTLR, ambiguities in alternatives are resolved by "using" the first alternative that matches. In this way ANTLR has deterministic behavior where you can control which interpretation is used (with alternative order). It's not uncommon for ANTLR grammars to have ambiguities like this.

IMHO, the IntelliJ plugin has caused many people to stumble over this as an indication that something is "wrong" with the grammar. There's a reason that ANTLR itself does not report an error in this situation. It has defined, deterministic behavior.

So far as "resolving" this ambiguity: the simple fact that the syntax uses parentheses to indicate two different "things" indicates that it is inherently ambiguous, so I don't believe you can "fix" the grammar ambiguity without modifying the syntax. (I might be wrong about this, and would find it interesting if someone provides a refactoring that manages to remove the ambiguity.)

CodePudding user response：

EDIT:

After trying an earlier solution that proved incorrect with some additional test data, I've tried a different approach.

I added Atom as a viable alternative for query_statement.

I used some semantic predicates to strip parentheses.

For testing purposes only, I added SQL-style line comments so that I could test many different inputs quickly.

The following SQL statements were tested, showing no ambiguity.

select 1 select (1) select ((select 1)) select ((select (abc))) select abc from ((select 1 from (select((select(1)))))) (select 1 from (select((select(1))))) ((select (xyz) from (select (((((foo))))) from tableX))) select a from (select x from xyz) union select b from abc select a from ((select x from xyz )) intersect ((select b from foo)) select a from (select x from xyz ) intersect (select b from foo)

The grammar is as follows:

grammar Subselect; options { caseInsensitive=true; } @header { import java.util.*; } @parser::members { String stripParens(String phrase) { String temp1 = phrase.substring[1]; temp2 = temp1.substring(0, s.length()-1); return temp2; } } statement: query_statement EOF; query_statement : query_expr # simple | query_statement set_op query_statement # set ; query_expr : with_clause? ( select | '(' query_statement ')' ) limit_clause? | Atom ; select : select_clause (from_clause where_clause?)? ; with_clause: 'WITH' expr 'AS (' select ')'; select_clause: 'SELECT' expr (',' expr)*; from_clause: 'FROM' expr; where_clause: 'WHERE' expr; limit_clause: 'LIMIT' expr; set_op: 'UNION'|'INTERSECT'|'EXCEPT'; lrpExpr : {stripParens(_input.LT[1].getText())}? query_expr ; expr : '(' lrpExpr ')' # parenExpr | Atom # identifier ; //--------------------------------------------- Atom: [a-z_0-9] ; WHITESPACE: [ \t\r\n] -> skip; LineComment : '--' ~[\r\n]* -> skip ;

I'm not including images of parse trees in this edit to conserve space. However, from the inputs I tested, lrpExpr, being a separate rule, would give e.g. a Visitor class to evaluate what is inside the parentheses before moving further down the parse tree, so order of evaluation e.g. mathematical operator precedence could still be honored.

All still fast and with zero ambiguity.

I hope this suits your needs better.

Attribution: I used this answer as a starting point for the Java code for the semantic predicate.