在连接子句处卡住解析 SQL Select 语句（包括 BNF 语法）

Question

我正在努力理解如何使用此 SQL 语法从解析器解析下面显示的 SQL 语句。我被困在 'Table reference' 和 'join' 构造之后找到 WHERE 标记。

BNF: http://www.contrib.andrew.cmu.edu/~shadow/sql/sql2bnf.aug92.txt

<table reference> ::=
         <table name> [ <correlation specification> ]
     | <derived table> <correlation specification>
     | <joined table>

 <joined table>    ::=
         <cross join>
     | <qualified join>
     | <left paren> <joined table> <right paren>

<cross join>    ::=
         <table reference> CROSS JOIN <table reference>

<qualified join>    ::=
         <table reference> [ NATURAL ] [ <join type> ] JOIN <table reference> [ <join specification> ]

<join type>    ::=
         INNER
     | <outer join type> [ OUTER ]
     | UNION

<outer join type>    ::=   LEFT | RIGHT | FULL

<join specification>    ::=   <join condition> | <named columns join>

<join condition>    ::=   ON <search condition>

<named columns join>    ::=   USING <left paren> <join column list> <right paren>

SQL:

SELECT p.Name, v.Name
FROM Production.Product p
JOIN Purchasing.ProductVendor pv
ON p.ProductID = pv.ProductID
JOIN Purchasing.Vendor v
ON pv.BusinessEntityID = v.BusinessEntityID
WHERE ProductSubcategoryID = 15
ORDER BY v.Name;

跳转到 FROM 子句。这里有一个 TableName，后面跟着两个 JOIN。

如果您查看 'Table reference'，您会发现其中包含 'Table name'。这个我能理解。

<table reference>    ::=
         **<table name> [ <correlation specification> ]**
     | <derived table> <correlation specification>
     | <joined table>

但是要获得连接，解析器必须到达 'Joined table' 而它不能，因为它已准备好读取 'table name'。

要到达连接，解析器必须到达 'Qualified join'，但它不能，因为 BNF 中没有重复。如果它以某种方式到达 'Join table' 元素，那么 if 会非常失望，因为下一次读取将再次是 'Table reference' 然后它会再次到达 'Qualifed join'，然后......然后你得到一个堆栈溢出。

  <joined table>    ::=
         <cross join>
     | <**qualified join>**
     | <left paren> <joined table> <right paren>

**<qualified join>**    ::=
         <table reference> [ NATURAL ] [ <join type> ] JOIN <table reference> [ <join specification> ]

我没有得到什么？我敢肯定其中有诀窍，但我就是没看到。

我希望你们中的一些人能向我解释一下这个对我来说不可能的语法是怎么回事。

如何构建一个比方说递归下降解析器来解决这个语法问题？

解析器需要遵循哪些步骤 and/or 规则？

Answer 1

该语法不是 LL(1)，而 LL(1) 正是您构建递归下降解析器所需要的。我怀疑 SQL 是否有 LL(1) 文法，特别是是否有可以生成正确解析树的文法。幸运的是，这并不重要，因为有更强大的解析技术。

您很可能可以使用该语法构建 LALR(1) 解析器，使用像 bison/yacc 这样的工具。或者查看 sqlite source code，其中包括 LALR(1) 语法和名为 "lemon" 的 LALR(1) 解析器生成器。

Answer 2

问这个问题已经有一段时间了，但由于 ANTLR 的 performance/memory 问题，我正在考虑将我的 ANTLR4 SQL 解析器重写为 RDP。

因此，我（在精神上）解决 JOIN 问题的方法是，我将它们视为运算符，因为它们就是这样（至少这是我的印象）。

基本表达式语法既适合普通表达式又适合JOIN：

ex
    : '(' ex ')'
    | ex OPERATOR ex
    | TERMINAL
    ;

在 JOIN 情况下，您的 OPERATOR 变为 JOIN，而 TERMINAL 变为 table 参考。

现在，这种左递归文法不是 LL 文法，但它可以转换为 LL 文法，ANTLR4 会自动转换。

在连接子句处卡住解析 SQL Select 语句（包括 BNF 语法）

Stuck parsing SQL Select statement at the join clause (BNF grammar included)

sql

parsing

bnf