1. 背景介绍
下图展示了SQL语句的执行流程
2. 词法分析及语法分析
2.1 概述
用户输入SQL命令进入分析器,须经过以下大致流程:
- 首先经过词法分析器,其负责识别标识符、SQL关键字等,发现的每个关键字或者标识符都会生成一个记号并且传递给语法分析器。
- 其次经过语法分析器,其包含了一套语法规则和触发规则时执行的动作,会使用语法规则来分析来自词法分析器的记号并创建语法树。语法树对标记施加了分层结构,例如运算符优先级和结合性等。
- 下一步是代码生成,将对语法树进行深度优先遍历以生成代码。一些编译器生成机器代码,一些编译器输出汇编语言。
2.2 词法分析
词法分析使用正则表达式匹配输入的字符串并把它们转换成对应的标记,也就是提取编程语言占用的各种保留字、操作符和特殊符号等元素。
下面给出一个正则表达式简单示例:
^[0-9]+tyy$
其中^ 为匹配输入字符串的开始位置;[0-9]+匹配多个数字, [0-9] 匹配单个数字,+ 用于匹配一个或者多个;tyy$匹配字母 tyy 并以 tyy 结尾,$ 为匹配输入字符串的结束位置。
2.3 语法分析
语法分析器的任务是找出输入记号之间的关系,常见的关系表达式为语法分析树(parsetree),这棵树的每个分支都显示了记号之间或者记号与下面子树的关系。
为了方便理解.y文件的结构,我们在这里对规则段中涉及的特殊符号进行分析。
/* 每个规则对应的动作使用{}框起来,并且使用';'作为此规则结束的符号
* '|'代表该规则对应多个可替代的动作,可选取任意一种动作执行
* prase_toplevel代表非终结符号,':'作为语法分隔符
* stmtmulit代表终结符号,其值通过位置获取
*/
parse_toplevel:
stmtmulti
{
pg_yyget_extra(yyscanner)->parsetree = $1; // 结果最终会返回给raw_parser函数
(void) yynerrs; /* suppress compiler warning */
}
...
/* $N的含义:$$代表冒号:左边记号,$N代表冒号右边第N个位置的记号
* @N的含义:@$代表冒号:左边记号的位置信息,@N代表冒号右边记号的位置信息
*/
stmtmulti: stmtmulti ';' toplevel_stmt
{
if ($1 != NIL)
{
/* update length of previous stmt */
updateRawStmtEnd(llast_node(RawStmt, $1), @2);
}
if ($3 != NULL)
$$(stmtmulit) = lappend($1, makeRawStmt($3, @2 + 1));
else
$$ = $1;
}
| toplevel_stmt
{
if ($1 != NULL)
$$ = list_make1(makeRawStmt($1, 0)); // 将stmt中的值$1作为参数生成SelectStmt并加入到列表中
else
$$ = NIL;
}
;
toplevel_stmt:
stmt
| TransactionStmtLegacy
;
...
stmt:
AlterEventTrigStmt
| AlterCollationStmt
| AlterDatabaseStmt
...
| DeleteStmt
...
| SelectStmt
...
3. 样例
学生表:
入职表:
查询语句:
select name, score
from student, (select * from tyy where tyy.gno = '2023') as sub
where student.sno = sub.sno and sub.department = '数据库'
group by name, score
having score > 80
order by score DESC;
当关键字不止一个时会涉及到list函数,例如target_list
、from_list
等,在此对该逻辑进行一个简单分析
gram.y中target_list的定义
target_list:
target_el { $$ = list_make1($1); }
| target_list ',' target_el { $$ = lappend($1, $3); }
;
首先看lappend:
List *
lappend(List *list, void *datum)
{
Assert(IsPointerList(list));
if (list == NIL)
list = new_list(T_List, 1);
else
new_tail_cell(list);
llast(list) = datum;
check_list_invariants(list);
return list;
}
再看list的定义:
typedef struct List
{
NodeTag type; /* T_List, T_IntList, or T_OidList */
int length; /* number of elements currently present */
int max_length; /* allocated length of elements[] */
ListCell *elements; /* re-allocatable array of cells */
/* We may allocate some cells along with the List header: */
ListCell initial_elements[FLEXIBLE_ARRAY_MEMBER];
/* If elements == initial_elements, it's not a separate allocation */
} List;
和ListCell的定义
typedef union ListCell
{
void *ptr_value;
int int_value;
Oid oid_value;
} ListCell;
new_tail_cell和list_last_cell
static void
new_tail_cell(List *list)
{
/* Enlarge array if necessary */
if (list->length >= list->max_length)
enlarge_list(list, list->length + 1);
list->length++;
}
```
static inline ListCell *
list_last_cell(const List *list)
{
Assert(list != NIL);
return &list->elements[list->length - 1];
}
gram.y中target_list的定义
target_list:
target_el { $$ = list_make1($1); }
| target_list ',' target_el { $$ = lappend($1, $3); }
;
target_list
中的的lappend相当于:$1->elements[list->length - 1]->ptr_value = $3
其中$1
是一个list,$3
是一个ListCell- 从最开始的target_el中list_make1($1)可以知道刚开始elements是指向ListCell,而ListCell的
ptr->valuse
指针指向第一个ResTarget - 此时ResTarget对应的是select id1,id2中的id1
- 如果select的字段不止一个,就会走到
target_list ',' target_el { $$ = lappend($1, $3);}
,也就是说第一个ResTarget已经关联到第二个ResTarget下一篇中将正式开始对上述select语句进行分析