Обсуждение: Recursive query syntax ambiguity

Woah, I just realized it's much worse than that. I think the syntax in the
ANSI is not parsable in LALR(1) at all. Note the following:

WITH RECURSIVE foo (a,b) AS (subq) SEARCH BREADTH FIRST BY a,b,c(x,z),d(y,z) AS (subq) SELECT ...

To determine whether "c" is the name of a new <with list element> it has to
scan as far ahead as the "," before the "d". Note that "d" here is in fact not
part of the <search clause> at all, it's the name of a second <with list
element>.

bleagh.

--  Gregory Stark EnterpriseDB          http://www.enterprisedb.com

Gregory Stark wrote:
> Woah, I just realized it's much worse than that. I think the syntax in the
> ANSI is not parsable in LALR(1) at all. Note the following:
>
> WITH RECURSIVE foo (a,b) AS (subq) SEARCH BREADTH FIRST BY a,b,c(x,z),d(y,z) AS (subq) SELECT ...
>
> To determine whether "c" is the name of a new <with list element> it has to
> scan as far ahead as the "," before the "d". Note that "d" here is in fact not
> part of the <search clause> at all, it's the name of a second <with list
> element>.
>
> bleagh.
>
>   

Can you post the rules you have so far that you're playing around with? 
(Also maybe the rules from the standard - I don't have a copy handy).

cheers

andrew

"Andrew Dunstan" <andrew@dunslane.net> writes:

> Can you post the rules you have so far that you're playing around with? (Also
> maybe the rules from the standard - I don't have a copy handy).

This is the best compromise I've come up with so far. It makes CYCLE a
reserved word and requires a CYCLE clause if there's a SEARCH clause.


Here are the grammar rules from the spec (I've attached PDFs of the syntax
pages for the two productions I'm describing since the text copy/paste comes
out pretty poorly)



7.13 <query expression>
Function
Specify a table.
Format
<query expression> ::=
[ <with clause> ] <query expression body>
<with clause> ::=
WITH [ RECURSIVE ] <with list>
<with list> ::=
<with list element> [ { <comma> <with list element> }... ]
<with list element> ::=
<query name> [ <left paren> <with column list> <right paren> ]
AS <left paren> <query expression> <right paren> [ <search or cycle clause> ]
<with column list> ::= <column name list>
<query expression body> ::=
<query term>
| <query expression body> UNION [ ALL | DISTINCT ]
[ <corresponding spec> ] <query term>
| <query expression body> EXCEPT [ ALL | DISTINCT ]
[ <corresponding spec> ] <query term>
<query term> ::=
<query primary>
| <query term> INTERSECT [ ALL | DISTINCT ]
[ <corresponding spec> ] <query primary>
<query primary> ::=
<simple table>
| <left paren> <query expression body> <right paren>
<simple table> ::=
<query specification>
| <table value constructor>
| <explicit table>
<explicit table> ::= TABLE <table or query name>
<corresponding spec> ::=
CORRESPONDING [ BY <left paren> <corresponding column list> <right paren> ]
<corresponding column list> ::= <column name list>

7.14 <search or cycle clause>
Function
Specify the generation of ordering and cycle detection information in the result of recursive query expressions.
Format
<search or cycle clause> ::=
<search clause>
| <cycle clause>
| <search clause> <cycle clause>
<search clause> ::=
SEARCH <recursive search order> SET <sequence column>
<recursive search order> ::=
DEPTH FIRST BY <sort specification list>
| BREADTH FIRST BY <sort specification list>
<sequence column> ::= <column name>
<cycle clause> ::=
CYCLE <cycle column list> SET <cycle mark column> TO <cycle mark value>
DEFAULT <non-cycle mark value> USING <path column>
<cycle column list> ::=
<cycle column> [ { <comma> <cycle column> }... ]
<cycle column> ::= <column name>
<cycle mark column> ::= <column name>
<path column> ::= <column name>
<cycle mark value> ::= <value expression>
<non-cycle mark value> ::= <value expression>





--
  Gregory Stark
  EnterpriseDB          http://www.enterprisedb.com

Ok, looking at your example:

WITH RECURSIVE foo (a,b) AS (subq) SEARCH BREADTH FIRST BY a,b , c(x,z),d(y,z) AS (subq) SELECT ...

What you're trying to say is that the c is a <with list element>,
not a <cycle column>. But the parser will see that as soon as it hits
the open parenthesis, since a <cycle column> is always just a column
name.

Also, the AS is the <with list element> doesn't appear to be optional,
I assume you left that out after the c(x,z) for clarity.

I think bison should be able to handle this as long as the "name" in
common_table_expression matches exactly the same things as whatever
columnList uses. It can the merge the two parse paths, allowing it to
"see" further.

Have a nice day,
--
Martijn van Oosterhout   <kleptog@svana.org>   http://svana.org/kleptog/
> From each according to his ability. To each according to his ability to litigate.