Presto 设计与实现（九）：SQL 词法分析

#挑战30天在头条写日记#

一条 SQL 语句在实际执行前，会经过一系列处理，其中开始阶段的词法分析、语法分析和生成 AST 的过程尤为重要。

语法分析相关术语

开始之前，先介绍下与语法分析相关的术语，这里摘录自 《ANTLR 4 权威指南》：

• 语言： 一门语言是一个有效语句的集合。语句由词组组成，词组由子词组组成，子词组又由更小的子词组组成，依此类推。
• 语法：语法定义了语言的语义规则。语法中的每条规则定义了一种词组结构。
• 语义树或语法分析树：代表了语句的结构，其中的每个子树的根节点都使用一个抽象的名字给其包含的元素命名。即子树的根节点对应了语法规则的名字。树的叶子节点是语句中的符号或者词法符号。
• 词法符号：词法符号就是一门语言的基本词汇符号，它们可以代表像是“标识符”这样的一类符号，也可以代表一个单一的运算符，或者代表一个关键宇。
• 词法分析器或者词法符号生成器：将输入的字符序列分解成一系列词法符号。一个词法分析器负责分析词法。
• 语法分析器：语法分析器通过检查语句的结构是否符合语法规则的定义来验证该语句在特定语言中是否合法。语法分析的过程好比是走迷宫，通过比较语句中和地板上的单词来从入口走到出口。ANTLR能够生成被称为ALL（+）的自顶向下的语法分析器，ALL（+）是指它可以利用剩余的所有输入文本来进行决策。自顶向下的语法分 析器以结果为导向，首先匹配最粗粒度的规则，这样的规则通常命名为program或者inputFile。
• 递归下降的语法分析器：这是自顶向下的语法分析器的一种实现，每条规则都对应语法分析器中的一个函数。
• 前向预测：语法分析器使用前向预测来进行決策，具体方法是：将输入的符号与每个备选分支的起始符号进行比较。

词法分析

进行词法分析前，需要定义词法符号（Token）的匹配模式，主要根据词法符号的含义和作用，例如在 SQL 查询语句中：

• 关键字 SELECT、FROM 和 WHERE 等；
• 表相关：表名、别名、表的列和表的关联等；
• 操作符号：>、<、 = 和 != 等；
• 内置函数：COUNT、 GETDATE、ROUND 和 LEN 等；
• 注释：-- 匹配单行和 /* 匹配多行 */；
• 可忽略的符号：空格、Tab 制表符、换行符和 ; 等。

Presto 使用 antlr4 定义的 SQL 词法和语法规则，完整规则存储在 presto-parser 模块内 SqlBase.g4 文件中，这里摘取了词法规则分析片段：

// 1. 下面是能够直接作为标识符的非保留关键字nonReserved    : ADD | ADMIN | ALL | ANALYZE | ANY | ARRAY | ASC | AT    | BERNOULLI    | CALL | CALLED | CASCADE | CATALOGS | COLUMN | COLUMNS | COMMENT | COMMIT | COMMITTED | CURRENT | CURRENT_ROLE    | DATA | DATE | DAY | DEFINER | DESC | DETERMINISTIC | DISTRIBUTED    | EXCLUDING | EXPLAIN | EXTERNAL    | FETCH | FILTER | FIRST | FOLLOWING | FORMAT | FUNCTION | FUNCTIONS    | GRANT | GRANTED | GRANTS | GRAPHVIZ | GROUPS    | HOUR    | IF | IGNORE | INCLUDING | INPUT | INTERVAL | INVOKER | IO | ISOLATION    | JSON    | LANGUAGE | LAST | LATERAL | LEVEL | LIMIT | LOGICAL    | MAP | MATERIALIZED | MINUTE | MONTH    | NAME | NFC | NFD | NFKC | NFKD | NO | NONE | NULLIF | NULLS    | OFFSET | ONLY | OPTION | ORDINALITY | OUTPUT | OVER    | PARTITION | PARTITIONS | POSITION | PRECEDING | PRIVILEGES | PROPERTIES    | RANGE | READ | REFRESH | RENAME | REPEATABLE | REPLACE | RESET | RESPECT | RESTRICT | RETURN | RETURNS | REVOKE | ROLE | ROLES | ROLLBACK | ROW | ROWS    | SCHEMA | SCHEMAS | SECOND | SECURITY | SERIALIZABLE | SESSION | SET | SETS | SQL    | SHOW | SOME | START | STATS | SUBSTRING | SYSTEM    | TABLES | TABLESAMPLE | TEMPORARY | TEXT | TIME | TIMESTAMP | TO | TRANSACTION | TRUNCATE | TRY_CAST | TYPE    | UNBOUNDED | UNCOMMITTED | USE | USER    | VALIDATE | VERBOSE | VIEW    | WORK | WRITE    | YEAR    | ZONE    ;// 2. 下面是具体值ADD: 'ADD';ADMIN: 'ADMIN';ALL: 'ALL';ALTER: 'ALTER';ANALYZE: 'ANALYZE';AND: 'AND';ANY: 'ANY';ARRAY: 'ARRAY';AS: 'AS';ASC: 'ASC';AT: 'AT';BERNOULLI: 'BERNOULLI';BETWEEN: 'BETWEEN';BY: 'BY';CALL: 'CALL';CALLED: 'CALLED';CASCADE: 'CASCADE';CASE: 'CASE';CAST: 'CAST';CATALOGS: 'CATALOGS';COLUMN: 'COLUMN';COLUMNS: 'COLUMNS';COMMENT: 'COMMENT';COMMIT: 'COMMIT';COMMITTED: 'COMMITTED';CONSTRAINT: 'CONSTRAINT';CREATE: 'CREATE';CROSS: 'CROSS';CUBE: 'CUBE';CURRENT: 'CURRENT';CURRENT_DATE: 'CURRENT_DATE';CURRENT_ROLE: 'CURRENT_ROLE';CURRENT_TIME: 'CURRENT_TIME';CURRENT_TIMESTAMP: 'CURRENT_TIMESTAMP';CURRENT_USER: 'CURRENT_USER';DATA: 'DATA';DATE: 'DATE';DAY: 'DAY';DEALLOCATE: 'DEALLOCATE';DEFINER: 'DEFINER';DELETE: 'DELETE';DESC: 'DESC';DESCRIBE: 'DESCRIBE';DETERMINISTIC: 'DETERMINISTIC';DISTINCT: 'DISTINCT';DISTRIBUTED: 'DISTRIBUTED';DROP: 'DROP';ELSE: 'ELSE';END: 'END';ESCAPE: 'ESCAPE';EXCEPT: 'EXCEPT';EXCLUDING: 'EXCLUDING';EXECUTE: 'EXECUTE';EXISTS: 'EXISTS';EXPLAIN: 'EXPLAIN';EXTRACT: 'EXTRACT';EXTERNAL: 'EXTERNAL';FALSE: 'FALSE';FETCH: 'FETCH';FILTER: 'FILTER';FIRST: 'FIRST';FOLLOWING: 'FOLLOWING';FOR: 'FOR';FORMAT: 'FORMAT';FROM: 'FROM';FULL: 'FULL';FUNCTION: 'FUNCTION';FUNCTIONS: 'FUNCTIONS';GRANT: 'GRANT';GRANTED: 'GRANTED';GRANTS: 'GRANTS';GRAPHVIZ: 'GRAPHVIZ';GROUP: 'GROUP';GROUPING: 'GROUPING';GROUPS: 'GROUPS';HAVING: 'HAVING';HOUR: 'HOUR';IF: 'IF';IGNORE: 'IGNORE';IN: 'IN';INCLUDING: 'INCLUDING';INNER: 'INNER';INPUT: 'INPUT';INSERT: 'INSERT';INTERSECT: 'INTERSECT';INTERVAL: 'INTERVAL';INTO: 'INTO';INVOKER: 'INVOKER';IO: 'IO';IS: 'IS';ISOLATION: 'ISOLATION';JSON: 'JSON';JOIN: 'JOIN';LANGUAGE: 'LANGUAGE';LAST: 'LAST';LATERAL: 'LATERAL';LEFT: 'LEFT';LEVEL: 'LEVEL';LIKE: 'LIKE';LIMIT: 'LIMIT';LOCALTIME: 'LOCALTIME';LOCALTIMESTAMP: 'LOCALTIMESTAMP';LOGICAL: 'LOGICAL';MAP: 'MAP';MATERIALIZED: 'MATERIALIZED';MINUTE: 'MINUTE';MONTH: 'MONTH';NAME: 'NAME';NATURAL: 'NATURAL';NFC : 'NFC';NFD : 'NFD';NFKC : 'NFKC';NFKD : 'NFKD';NO: 'NO';NONE: 'NONE';NORMALIZE: 'NORMALIZE';NOT: 'NOT';NULL: 'NULL';NULLIF: 'NULLIF';NULLS: 'NULLS';OFFSET: 'OFFSET';ON: 'ON';ONLY: 'ONLY';OPTION: 'OPTION';OR: 'OR';ORDER: 'ORDER';ORDINALITY: 'ORDINALITY';OUTER: 'OUTER';OUTPUT: 'OUTPUT';OVER: 'OVER';PARTITION: 'PARTITION';PARTITIONS: 'PARTITIONS';POSITION: 'POSITION';PRECEDING: 'PRECEDING';PREPARE: 'PREPARE';PRIVILEGES: 'PRIVILEGES';PROPERTIES: 'PROPERTIES';RANGE: 'RANGE';READ: 'READ';RECURSIVE: 'RECURSIVE';REFRESH: 'REFRESH';RENAME: 'RENAME';REPEATABLE: 'REPEATABLE';REPLACE: 'REPLACE';RESET: 'RESET';RESPECT: 'RESPECT';RESTRICT: 'RESTRICT';RETURN: 'RETURN';RETURNS: 'RETURNS';REVOKE: 'REVOKE';RIGHT: 'RIGHT';ROLE: 'ROLE';ROLES: 'ROLES';ROLLBACK: 'ROLLBACK';ROLLUP: 'ROLLUP';ROW: 'ROW';ROWS: 'ROWS';SCHEMA: 'SCHEMA';SCHEMAS: 'SCHEMAS';SECOND: 'SECOND';SECURITY: 'SECURITY';SELECT: 'SELECT';SERIALIZABLE: 'SERIALIZABLE';SESSION: 'SESSION';SET: 'SET';SETS: 'SETS';SHOW: 'SHOW';SOME: 'SOME';SQL: 'SQL';START: 'START';STATS: 'STATS';SUBSTRING: 'SUBSTRING';SYSTEM: 'SYSTEM';TABLE: 'TABLE';TABLES: 'TABLES';TABLESAMPLE: 'TABLESAMPLE';TEMPORARY: 'TEMPORARY';TEXT: 'TEXT';THEN: 'THEN';TIME: 'TIME';TIMESTAMP: 'TIMESTAMP';TO: 'TO';TRANSACTION: 'TRANSACTION';TRUE: 'TRUE';TRUNCATE: 'TRUNCATE';TRY_CAST: 'TRY_CAST';TYPE: 'TYPE';UESCAPE: 'UESCAPE';UNBOUNDED: 'UNBOUNDED';UNCOMMITTED: 'UNCOMMITTED';UNION: 'UNION';UNNEST: 'UNNEST';USE: 'USE';USER: 'USER';USING: 'USING';VALIDATE: 'VALIDATE';VALUES: 'VALUES';VERBOSE: 'VERBOSE';VIEW: 'VIEW';WHEN: 'WHEN';WHERE: 'WHERE';WITH: 'WITH';WORK: 'WORK';WRITE: 'WRITE';YEAR: 'YEAR';ZONE: 'ZONE';// 3. 操作符号EQ  : '=';NEQ : '<>' | '!=';LT  : '<';LTE : '<=';GT  : '>';GTE : '>=';PLUS: '+';MINUS: '-';ASTERISK: '*';SLASH: '/';PERCENT: '%';CONCAT: '||';// 4. 数值fragment DIGIT    : <0-9>    ;// 5. 字符fragment LETTER    :     ;// 6. 单行注释SIMPLE_COMMENT    : '--' ~<\r\n>* '\r'? '\n'? -> channel(HIDDEN)    ;// 7. 多行注释BRACKETED_COMMENT    : '/*' .*? '*/' -> channel(HIDDEN)    ;// 8. 空白处理WS    : < \r\n\t>+ -> channel(HIDDEN)    ;// 9. 预定义范围之外的，用于还原原始文本UNRECOGNIZED    : .    ;

通过一个具体的例子加深下理解，从 user 表中查询 id 等于 1 的用户：

SELECT id,name,address,age FROM mysql.ice.user WHERE id = 1;

词法分析器解析流程：

1. 初始化 token 索引和类型；
2. 开始遍历 char 数组，更新 token 索引；
3. 根据定义的词法规则进行匹配，获取匹配结果；
4. 校验匹配的 token 类型，执行后续操作：如果可忽略继续执行；如果解析到末尾退出；其他情况继续执行。
5. 遍历结束完成词法解析工作。