Presto 設計與實作（十）：SQL 文法分析

#暑期創作大賽#

SQL 語句經過詞法分析解析後，會轉化成 Token 序列作為文法分析器的輸入，文法分析器加載所有的文法規則，根據内部定義的解析政策對 Token 序列進行解析，對于 SQL 查詢語句，常見的文法錯誤：

關鍵字拼寫錯誤；
關鍵字先後順序錯誤；
關鍵字、UNRECOGNIZED 、表達式和函數之間缺少空格；
使用了未知的函數名稱、特殊符号或某些符号使用了全角；
分号或括号未成對出現。

下面是 SqlBase.g4 關于查詢文法定義的片段：

# 比對 SQL 查詢片段
querySpecification
    : SELECT setQuantifier? selectItem (',' selectItem)* # 帶分隔符的序列模式
      (FROM relation (',' relation)*)?                   # 嵌套模式
      (WHERE where=booleanExpression)?
      (GROUP BY groupBy)?
      (HAVING having=booleanExpression)?
    ;

# 選擇模式：從 DISTINCT 和 ALL 選擇 1 個
setQuantifier
    : DISTINCT
    | ALL
    ;    

selectItem
    : expression (AS? identifier)?  # 别名
    | qualifiedName '.' ASTERISK    # 某個表的所有列
    | ASTERISK                      # 所有列
    ;

expression
    : booleanExpression
    ;
 
# 帶分隔符的序列模式
qualifiedName
    : identifier ('.' identifier)*
    ;
   
# 選擇模式
identifier
    : IDENTIFIER            
    | QUOTED_IDENTIFIER      
    | nonReserved           
    | BACKQUOTED_IDENTIFIER 
    | DIGIT_IDENTIFIER      
    ;
    
IDENTIFIER
    : (LETTER | '_') (LETTER | DIGIT | '_' | '@' | ':')*
    ;
    
fragment DIGIT
    : [0-9]
    ;

fragment LETTER
    : [A-Z]
    ;

relation
    : left=relation
      ( CROSS JOIN right=sampledRelation
      | joinType JOIN rightRelation=relation joinCriteria
      | NATURAL joinType JOIN right=sampledRelation
      )                                         
    | sampledRelation                            
    ;
    
sampledRelation
    : aliasedRelation (
        TABLESAMPLE sampleType '(' percentage=expression ')'
      )?
    ;
    
aliasedRelation
    : relationPrimary (AS? identifier columnAliases?)?
    ;
  
# 選擇模式
relationPrimary
    : qualifiedName                                                   
    | '(' query ')'                                                  
    | UNNEST '(' expression (',' expression)* ')' (WITH ORDINALITY)? 
    | LATERAL '(' query ')'                                           
    | '(' relation ')'                                              
    ;

将上面的文法規則轉為思維導圖，可以直覺的檢視文法規則的詳細分支：

文法分析器使用 LL 最左推導由上到下的解析過程：

文法分析器首先會加載所有已定義的文法規則；
對 Token 序列進行周遊解析；
文法分析器按照預設的文法規則向下進行比對；
首個 Token 比對到 SELECT 非保留字，接着會對 id,name,address,age 7 個 Token進行校驗：比對到路徑 selectItem (',' selectItem)* -> selectItem -> booleanExpression -> valueExpression -> primaryExpression -> identifier -> IDENTIFIER -> LETTER，校驗通過；
比對到 FROM 非保留字，接着會對 mysql.ice.user 進行校驗：比對到路徑 sampledRelation -> aliasedRelation -> relationPrimary -> qualifiedName -> identifier ('.' identifier)*，校驗通過；
比對到 WEREH 非保留字，接着會比對後面的表達式；
周遊到末尾，解析工作結束。