Postgresql源码（44）server端语法解析流程分析
Postgresql源码（44）server端语法解析流程分析
mingjie
发布于 2022-07-14 13:48:12
发布于 2022-07-14 13:48:12
相关： 《Postgresql源码（44）server端语法解析流程分析》 《Postgresql源码（50）语法解析时关键字判定原理（函数名不能使用的关键字为例）》
一、语法解析整体流程
语法解析封装的函数比较多看起来不太容易理解，其实核心逻辑比较简单：
1、raw_parser作为高层入口
2、raw_parser初始化后，通过base_yyparse进入yacc框架
3、yacc框架中调用base_yylex进入lex拿一个token（正常用框架是每次拿一个，PG通过对lex函数的封装可以拿后面多个，有些语法需要看到后面多个一块解析）
4、拿回来token后，进入语法树开始递归（有点像后续遍历，从底层开始向上构造语法节点，实际是用两个堆栈解析每一层语法规则，原理也比较简单，见第二节）。
5、从语法树底层节点向上reduce，识别收集文本中的目标信息，创建对应的stmt结构体，填入数据，返回上层。
执行流程如下图：
二、base_yylex解析实例
1、流程总结
（1）base_yylex函数进入时会优先check有没有预读的token，检查base_yy_extra_type的几个ahead变量即可。
（2）如果有预读的token就直接用了，不再重新解析
（3）如果没有预读的token，调core_yylex从lex拿一个token出来，如果是普通token直接返回yacc继续reduce
（4）如果不是普通token（目前定义了一些即not like、with time等等），再调一次core_yylex把下一个token读出来，同时记录到ahead的几个变量中。
（5）然后把curr token和next token放在一起做一些处理，例如not本来要返回NOT，预读到下一个是like，则本次返回NOT_LA。
2、测试SQL
select * from sbtest1 where c not like '%68487932199%';
620 42 427 258 708 258 524 588
SELECT * FROM IDENT WHERE IDENT NOT LIKE3、从524（NOT）开始，会进入函数的Look ahead逻辑，这里做一些分析：
关键数据结构，除了解析过程必须的core_yy_extra、parsetree，中间的几个变量都用来向前看token。
typedef struct base_yy_extra_type
{
/*
* Fields used by the core scanner.
*/
core_yy_extra_type core_yy_extra;
/*
* State variables for base_yylex().
*/
bool have_lookahead; /* is lookahead info valid? */
int lookahead_token; /* one-token lookahead */
core_YYSTYPE lookahead_yylval; /* yylval for lookahead token */
YYLTYPE lookahead_yylloc; /* yylloc for lookahead token */
char *lookahead_end; /* end of current token */
char lookahead_hold_char; /* to be put back at *lookahead_end */
/*
* State variables that belong to the grammar.
*/
List *parsetree; /* final parse result is delivered here */
} base_yy_extra_type;函数流程分析，从not like '%68487932199%';开始：
int
base_yylex(YYSTYPE *lvalp, YYLTYPE *llocp, core_yyscan_t yyscanner)
{
base_yy_extra_type *yyextra = pg_yyget_extra(yyscanner);
int cur_token;
int next_token;
int cur_token_length;
YYLTYPE cur_yylloc;
if (yyextra->have_lookahead)
{
cur_token = yyextra->lookahead_token;
lvalp->core_yystype = yyextra->lookahead_yylval;
*llocp = yyextra->lookahead_yylloc;
if (yyextra->lookahead_end)
*(yyextra->lookahead_end) = yyextra->lookahead_hold_char;
yyextra->have_lookahead = false;
}
else
/* 走这个分支拿到`NOT` */
cur_token = core_yylex(&(lvalp->core_yystype), llocp, yyscanner);
/* 只有前面集中情况需要Look ahead，其他情况直接返回给语法树即可 */
/* 这里cur_token=NOT，不直接返回 */
switch (cur_token)
{
case NOT:
cur_token_length = 3;
break;
case NULLS_P:
cur_token_length = 5;
break;
case WITH:
cur_token_length = 4;
break;
case UIDENT:
case USCONST:
cur_token_length = strlen(yyextra->core_yy_extra.scanbuf + *llocp);
break;
default:
return cur_token;
}
// (gdb) p yyextra->core_yy_extra.scanbuf
// $39 = 0x2ebfbc8 "select * from sbtest1 where c not"（缓存的字符串）
// (gdb) p *llocp
// $40 = 30（当前token的起始位置！）
// (gdb) p cur_token_length
// $41 = 3（在上面switch中设置的token长度）
yyextra->lookahead_end = yyextra->core_yy_extra.scanbuf +
*llocp + cur_token_length;
Assert(*(yyextra->lookahead_end) == '\0');
/* 当前look ahead相关变量的状态 */
// 5: yyextra->lookahead_hold_char = -37 '\333'
// 4: yyextra->lookahead_end = 0x2ebfbe9 ""
// 3: yyextra->lookahead_yylval = {ival = -830157632, str = 0x7ffece84ccc0 "\351\373\353\002", keyword = 0x7ffece84ccc0 "\351\373\353\002"}
// 2: yyextra->lookahead_token = 0
// 1: yyextra->have_lookahead = false
/* 保存一下当前的位置：30（到NOT前） */
cur_yylloc = *llocp;
/* lex的参数含义见下一节 */
next_token = core_yylex(&(yyextra->lookahead_yylval), llocp, yyscanner);
yyextra->lookahead_token = next_token;
yyextra->lookahead_yylloc = *llocp;
// 拿到新的next_token = 488
// gram.c： LIKE = 488
// 恢复第一个token:not的位置30
*llocp = cur_yylloc;
/* Now revert the un-truncation of the current token */
yyextra->lookahead_hold_char = *(yyextra->lookahead_end);
*(yyextra->lookahead_end) = '\0';
yyextra->have_lookahead = true;
/* 到这里look ahead的工作做完了，成功读了一个后面的token，并记录到相关变量中了 */
/*
5: yyextra->lookahead_hold_char = 32 ' '
4: yyextra->lookahead_end = 0x2ebfbe9 ""
3: yyextra->lookahead_yylval = {ival = 14065479, str = 0xd69f47 <ScanKeywords_kw_string+1639> "like", keyword = 0xd69f47 <ScanKeywords_kw_string+1639> "like"}
2: yyextra->lookahead_token = 488
1: yyextra->have_lookahead = true
*/
/* Replace cur_token if needed, based on lookahead */
switch (cur_token)
{
case NOT:
/* Replace NOT by NOT_LA if it's followed by BETWEEN, IN, etc */
switch (next_token)
{
case BETWEEN:
case IN_P:
case LIKE:
case ILIKE:
case SIMILAR:
/* 当前：NOT 下一个：LIKE */
/* 当前更换为：NOT_LA */
cur_token = NOT_LA;
break;
}
break;
...
...
}
return cur_token;
}三、lex初始化
1、初始化传入extra结构体给scanner，extra中保存用户自定义解析所需变量
2、scanner是lex初始化生成的结果，可以理解为lex的抽象
3、gram.y生成gram.c在shift/reduce语法树的过程中，调用base_yylex获取token
4、base_yylex的第三个参数就是初始化的scanner，里面可以取出extra
5、base_yylex的前两个参数是lex框架定义的，保存了解析所需
6、core_yylex是scan.l生成scan.c中提供的函数，功能就是scan.l中编写的匹配规则
7、core_yylex可以自己在scan.l中自定义其他同参函数，例如my_yylex，可以在base_yylex中替代core_yylex来使用
四、yacc的工作原理、实例
总结：
1、整个语法树的解析过程从叶子节点逐层向上构造，中间使用base_yylex获取新的token决定匹配拿一个语法分支。
2、yacc的工作原理以下面为例：c not like '%68487932199%';
a_expr: a_expr NOT_LA LIKE a_expr %prec NOT_LA
{
$$ = (Node *) makeSimpleA_Expr(AEXPR_LIKE, "!~~",
$1, $4, @2);
}工作过程
第一步：符号从左到右依次入栈，shift操作
符号堆栈 值堆栈
| | | |
| a_expr | | c |
| LIKE | | LIKE |
| NOT_LA | | NOT_LA |
| a_expr | | %68487932199% |
---------| ----------------|
第二步：a_expr NOT_LA LIKE a_expr符号全部入栈完成，开始reduce操作，执行{...}代码，并全部出栈，然后将$$重新入值堆栈，a_expr入符号堆栈
符号堆栈 值堆栈
| | | |
| | | |
| | | |
| | | |
| a_expr | | $$=makeSimpleA_Expr |
---------| ------------------------|
第三步：a_expr作为单个语法节点，返回继续上一层树的解析3、语法树的最上层会把最终 reduce的结果保存到parsetree中作为最终结果。
解析过程：
解析c not like '%68487932199%';的大致流程，省略了base_yylex的调用，从c开始：
（1）匹配c，构造ColId
ColId: IDENT { $$ = $1; }
| unreserved_keyword { $$ = pstrdup($1); }
| col_name_keyword { $$ = pstrdup($1); }
;
==========================================
（2）匹配c，用ColId构造columnref
columnref: ColId
{
$$ = makeColumnRef($1, NIL, @1, yyscanner);
// makeColumnRef (colname=0x2ebfe68 "c", indirection=0x0, location=28, yyscanner=0x2ebfab0)
}
| ColId indirection
{
$$ = makeColumnRef($1, $2, @1, yyscanner);
}
;
==========================================
Sconst: SCONST { $$ = $1; };
==========================================
AexprConst: Iconst
{
$$ = makeIntConst($1, @1);
}
| FCONST
{
$$ = makeFloatConst($1, @1);
}
（3）走这里匹配like 后面的%68487932199%
| Sconst
{
$$ = makeStringConst($1, @1);
}
==========================================
（4）有AexprConst了构造c_expr
c_expr: columnref { $$ = $1; }
| AexprConst { $$ = $1; }
==========================================
（5）用 c_expr构造a_expr
a_expr: c_expr { $$ = $1; }
==========================================
（6）base_yylex解析token=59（ascii字符到最后的分号了）
==========================================
| a_expr NOT_LA LIKE a_expr
{
$$ = (Node *) makeSimpleA_Expr(AEXPR_LIKE, "!~~",
}
==========================================
where_clause:
WHERE a_expr { $$ = $2; }
==========================================
group_clause:
| /*EMPTY*/
having_clause:
| /*EMPTY*/
window_clause:
| /*EMPTY*/
==========================================
simple_select:
SELECT opt_all_clause opt_target_list
into_clause from_clause where_clause
group_clause having_clause window_clause
{
SelectStmt *n = makeNode(SelectStmt);
n->targetList = $3;
n->intoClause = $4;
n->fromClause = $5;
n->whereClause = $6;
n->groupClause = ($7)->list;
n->groupDistinct = ($7)->distinct;
n->havingClause = $8;
n->windowClause = $9;
$$ = (Node *)n;
}
==========================================
select_no_parens:
simple_select { $$ = $1; }
==========================================
stmt:
AlterEventTrigStmt
| AlterCollationStmt
| AlterDatabaseStmt
| AlterDatabaseSetStmt
| AlterDefaultPrivi
...
| VariableShowStmt
| ViewStmt
| /*EMPTY*/
{ $$ = NULL; } // 走这里
;
==========================================
stmtmulti: stmtmulti ';' toplevel_stmt
{
if ($1 != NIL)
{
/* update length of previous stmt */
updateRawStmtEnd(llast_node(RawStmt, $1), @2);
}
if ($3 != NULL)
$$ = lappend($1, makeRawStmt($3, @2 + 1));
else
$$ = $1;
}
==========================================
（7）最后的结果存入parsetree
parse_toplevel:
stmtmulti
{
pg_yyget_extra(yyscanner)->parsetree = $1;
} core_yylex函数
lex函数一般不必深究内部调用流程，实际指向的是在scan.c生成文件中的函数，代码可读性比较差，位置：
scan.c
/** The main scanner function which does all the work.
*/
YY_DECL
{
..
}需要记住的是接口的定义，
extern int core_yylex(core_YYSTYPE *lvalp, YYLTYPE *llocp, core_yyscan_t yyscanner);
- ore_YYSTYPE *lvalp： 输出值，记录ival、str、keyword
- YYLTYPE *llocp：输出值，记录当前解析的token的起始位置
- core_yyscan_t yyscanner：输入例如解析token：not和like
next_token = core_yylex(&(yyextra->lookahead_yylval), llocp, yyscanner);
//select * from sbtest1 where c not like
// | |
// llocp 30 |
// |
// llocp 34
// 解析not
(gdb) p lvalp->core_yystype
$54 = {ival = 14065726, str = 0xd6a03e <ScanKeywords_kw_string+1886> "not", keyword = 0xd6a03e <ScanKeywords_kw_string+1886> "not"}
// 解析like
(gdb) p yyextra->lookahead_yylval
$55 = {ival = 14065479, str = 0xd69f47 <ScanKeywords_kw_string+1639> "like", keyword = 0xd69f47 <ScanKeywords_kw_string+1639> "like"}ps
**YY_START：**返回int值表示当前激活的%x，例如在处理""的解析中，第一个"激活`%x xd`，xd在第三位，所以处理过程中如果拿到YY_START就等于3。
**FILE \*yyin:** **FILE \*yyout：** 这是Lex中本身已定义的输入和输出文件指针。这两个变量指明了lex生成的词法分析器从哪里获得输入和输出到哪里。默认：键盘输入，屏幕输出
**char \*yytext：**当前匹配的词法单元的指针，比如`{identifier}`匹配了select单词，那么`yytext="select"`
**int yyleng：**当前词法单元的长度
**yylineno** 提供当前的行数信息
**ECHO：**Lex中预定义的宏，可以出现在动作中，相当于`fprintf(yyout, “%s”,yytext)`，即输出当前匹配的词法单元
**yyless：** 把指定的几个字符重新推回缓冲区
@1字符位置本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-06-09，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录