How to disambiguate a subselect from a parenthesized expression?

user_651174 0
Viewed 187

I have the following expression notation:

expr
    : OpenParen expr (Comma expr)* Comma? CloseParen           # parenExpr
    | OpenParen simpleSelect CloseParen                        # subSelectExpr

Unfortunately, a simpleSelect can also have a parenthetical around it, and so the following statement becomes ambiguous:

 select ((select 1))

Here is the current grammar that I have, simplified down to only showing the issue:

grammar Subselect;
options { caseInsensitive=true; }
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?
    ;

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';

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

Atom: [a-z_0-9]+;
WHITESPACE: [ \t\r\n] -> skip;

And on the parse of select ((select 1)), here is the output:

enter image description here

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 here:

enter image description here

I would be curious whether any of the grammars can solve the issue here: https://github.com/antlr/grammars-v4/tree/master/sql. Maybe the best approach is just to remove duplicate parens before parsing the text? (If so, are there are good tools to do that, or do I need to write an additional antlr parser just to do that?)

antlr4 antlr grammar sql parsing
2 Answers

Your input generates this parse tree:

enter image description 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.

enter image description here

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

user_737640

EDIT:

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

  1. I added Atom as a viable alternative for query_expr since that Atom '1` is being offered as test data. In the full grammar implementation, it's hard to predict if this is necessary, even sufficent. I have only the grammar above with which to test.
  2. I used some semantic predicates to strip parentheses (avoids the effort of writing an additional parser).
  3. 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.

user_57410730
Related