跳转至

这部分内容会介绍一些如何对miniob中的词法语法分析模块进行开发与调试,以及依赖的工具。

简介

SQL 解析分为词法分析与语法分析,与编译原理中介绍的类似。这里主要介绍如何扩展MiniOB的SQL解析器,并对词法分析和语法分析文件做一些简单的介绍。

词法分析

词法分析文件 lex_sql.l

词法分析的基本功能是读取文件或字符串的一个一个字符,然后按照特定的模式(pattern)去判断是否匹配,然后输出一个个的token。比如对于 CALC 1+2,词法分析器会输出 CALC1+2EOF

扩展功能时,我们最关心的是词法分析的模式如何编写以及flex如何去执行模式解析的。 在lex_sql.l文件中,我们可以看到这样的代码:

[\-]?{DIGIT}+  yylval->number=atoi(yytext); RETURN_TOKEN(NUMBER);
HELP           RETURN_TOKEN(HELP);
DESC           RETURN_TOKEN(DESC);
CREATE         RETURN_TOKEN(CREATE);
DROP           RETURN_TOKEN(DROP);

每一行都是一个模式,左边是模式,使用正则表达式编写,右边是我们返回的token,这里的token是枚举类型,是我们在yacc_sql.y中定义的。

[\-]?{DIGIT}+ 就是一个表示数字的正则表达式。 HELP 表示完全匹配"HELP" 字符串。

flex 在匹配这些模式时有一些规则,如果输出的结果与自己的预期不符,可以使用这些规则检查一下,是否自己写的模式和模式中的顺序是否符合这些规则: - 优先匹配最长的模式 - 如果有多个模式匹配到同样长的字符串,那么优先匹配在文件中靠前的模式

另外还有一些词法分析的知识点,都在lex_sql.l中加了注释,不多做赘述,在这里罗列提示一下。 - flex 根据编写的 .l 规则文件,和指定的命令生成.c代码。不过miniob把.c文件改成了.cpp后缀; - %top{} 的代码会放在flex生成的代码最开头的地方; - %{ %} 中的代码会被移动到flex生成的代码中; - flex提供了一些选项,可以在命令行中指定,也可以在.l文件中,使用 %option指定; - flex 中编写模式时,有一些变量是预定义的,yylval就是返回值,可以认为是yacc中使用%union定义的结构; yytext 是解析的当前token的字符串,yyleng 是token的长度,yycolumn 是当前的列号,yylineno 是当前行号; - 如果需要每个token在原始文本中的位置,可以使用宏定义 YY_USER_ACTION,但是需要自己编写代码记录才能传递给yacc; - %% %%之间的代码是模式匹配代码,之后的代码会被复制到生成代码的最后。

语法分析

语法分析文件 yacc_sql.y

语法分析的基本功能是根据词法分析的结果,按照语法规则,生成语法树。

与词法分析类似,语法分析工具(这里使用的是bison)也会根据我们编写的.y规则文件,生成.c代码,miniob 这里把.c代码改成了.cpp代码,因此.y文件中可以使用c++的语法和标准库。

类似词法分析,我们在扩展语法分析时,最关心的也只有规则编写的部分。

在yacc_sql.y文件中,我们可以看到这样的代码:

expression_list:
    expression
    {
      $$ = new std::vector<Expression*>;
      $$->emplace_back($1);
    }
    | expression COMMA expression_list {
      if ($3 != nullptr) {
        $$ = $3;
      } else {
        $$ = new std::vector<Expression *>;
      }
      $$->emplace_back($1);
    }
    ;

这个规则描述表达式列表的语法,表达式列表可以是单个表示,或者"单个表达式 逗号 表达式列表"的形式,第二个规则是一个递归的定义。 可以看到,多个规则模式描述使用 "|" 分开。

为了方便说明,我这里再换一个语句:

create_table_stmt:    /*create table 语句的语法解析树*/
    CREATE TABLE ID LBRACE attr_def attr_def_list RBRACE
    {
      $$ = new ParsedSqlNode(SCF_CREATE_TABLE);
      CreateTableSqlNode &create_table = $$->create_table;
      create_table.relation_name = $3;
      free($3);

      std::vector<AttrInfoSqlNode> *src_attrs = $6;

      if (src_attrs != nullptr) {
        create_table.attr_infos.swap(*src_attrs);
      }
      create_table.attr_infos.emplace_back(*$5);
      std::reverse(create_table.attr_infos.begin(), create_table.attr_infos.end());
      delete $5;
    }
    ;

每个规则描述,比如create_table_stmt 都会生成一个结果,这个结果在.y中以 "$\(" 表示,某个语法中描述的各个token,按照顺序可以使用 "\)1 $2 $3" 来引用,比如ID 就是 $3, attr_def 是 \(5。"\)n" 的类型都是 YYSTYPE。YYSTYPE 是bison根据.y生成的类型,对应我们的规则文件就是 %union,YYSTYPE 也是一个union结构。比如 我们在.y文件中说明 %type <sql_node> create_table_stmt,表示 create_table_stmt 的类型对应了 %union 中的成员变量 sql_node。我们在 %union 中定义了 ParsedSqlNode * sql_node;,那么 create_table_stmt 的类型就是 ParsedSqlNode *,对应了 YYSTYPE.sql_node。

%union 中定义的数据类型,除了简单类型,大部分是在parse_defs.h中定义的,表达式Expression是在expression.h中定义的,Value是在value.h中定义的。

由于在定义语法规则时,这里都使用了左递归,用户输入的第一个元素会放到最前面,因此在计算得出最后的结果时,我们需要将列表(这里很多使用vector记录)中的元素逆转一下。

语法分析中如何使用位置信息

首先我们要在.y文件中增加%locations,告诉bison我们需要位置信息。其次需要与词法分析相配合,需要词法分析返回一个token时告诉语法分析此token的位置信息,包括行号、token起始位置和结束位置。与访问规则结果 $$ 类似,访问某个元素的位置信息可以使用 @$、 @1、@2 等。

词法分析中,yylineno记录当前是第几行,不过MiniOB当前没有处理多行文本。yycolumn记录当前在第几列,yyleng记录当前token文本的长度。词法分析提供了宏定义 YY_USER_INIT 可以在每次解析之前执行一些代码,而 YY_USER_ACTION 宏在每次解析完token后执行的代码。我们可以在YY_USER_INIT宏中对列号进行初始化,然后在YY_USER_ACTION计算token的位置信息,然后使用 yylloc 将位置信息传递给语法分析。而在引用 @$ 时,就是引用了 yylloc。

这些宏定义和位置的引用可以参考lex_sql.l和yacc_sql.y,搜索相应的关键字即可。

如果觉得位置信息传递和一些特殊符号 $\(或 @\) 等使用感到困惑,可以直接看 flex和bison生成的代码,会让自己理解的更清晰。

如何编译词法分析和语法分析模块

在 src/observer/sql/parser/ 目录下,执行以下命令:

./gen_parser.sh

将会生成词法分析代码 lex_sql.h 和 lex_sql.cpp,语法分析代码 yacc_sql.hpp 和 yacc_sql.cpp。

注意:flex 使用 2.5.35 版本测试通过,bison使用3.7版本测试通过(请不要使用旧版本,比如macos自带的bision)。

注意:当前没有把lex_sql.l和yacc_sql.y加入CMakefile.txt中,所以修改这两个文件后,需要手动生成c代码,然后再执行编译。

如果使用visual studio code,可以直接选择 "终端/Terminal" -> "Run task..." -> "gen_parser",即可生成代码。

如何调试词法分析和语法分析模块

代码中可以直接使用日志模块打印日志,对于yacc_sql.y也可以直接使用gdb调试工具调试。

参考