使用lex与yacc词法语法工具进行简单的SQL语义检查

浅浅的花香味﹌ 2023-10-02 20:31 23阅读 0赞

### 一、lex使用指南 ###

#### 结构介绍 ####

[第一部分：定义段]
    
    %%
    
    第二部分：词法规则段
    
    %%
    
    第三部分：辅助函数段

###### 1）第一部分定义段的写法： ######

第一小部分以符号%\{和%\}包裹，里面为以C语法写的一些定义和声明：例如，文件包含，宏定义，常数定义，全局变量及外部变量定义，函数声明等。这一部分被Lex翻译器处理后会全部拷贝到文件lex.yy.c中。

%{
        
     #define LT 1
      intyylval;
    %}

第二小部分是一组正规定义和状态定义。正规定义是为了简化后面的词法规则而给部分正规式定义了名字。每条正规定义也都要顶着行首写。例如下面这组正规定义分别定义了letter和digit所表示的正规式：  
即运用正规定义，简化了后续使用上的复杂描述，用简单定义去替换。

letter       [A-Za-z]
    digit        [0-9]

状态定义也叫环境定义，它定义了匹配正规式时所处的状态的名字。状态定义以%s开始，后跟所定义的状态的名字，注意%s也要顶行首写。

%s COMMENT BAD

###### 2) 第二部分词法规则段的写法： ######

词法规则段列出的是词法分析器需要匹配的正规式，以及匹配该正规式后需要进行的相关动作。  
也可以若干个正规式匹配同一条语义动作，此时正规式之间要用 | 分隔。

###### 3) 第三部分辅助函数段的写法： ######

辅助函数段用C语言语法来写，辅助函数一般是在词法规则段中用到的函数。这一部分一般会被直接拷贝到lex.yy.c中。

###### 4) Lex源程序中常用到的变量及函数： ######

yyin和yyout：这是Lex中本身已定义的输入和输出文件指针。这两个变量指明了lex生成的词法分析器从哪里获得输入和输出到哪里。默认：键盘输入，屏幕输出。
    yytext和yyleng：这也是lex中已定义的变量，直接用就可以了。
    
    yytext：指向当前识别的词法单元（词文）的指针
    
    yyleng：当前词法单元的长度。
    
    ECHO：Lex中预定义的宏，可以出现在动作中，相当于fprintf(yyout, “%s”,yytext)，即输出当前匹配的词法单元。
    
    yylex()：词法分析器驱动程序，用Lex翻译器生成的lex.yy.c内必然含有这个函数。
    
    yywrap()：词法分析器遇到文件结尾时会调用yywrap()来决定下一步怎么做：
    
    若yywrap()返回0，则继续扫描
    
    若返回1，则返回报告文件结尾的0标记。
    
    由于词法分析器总会调用yywrap，因此辅助函数中最好提供yywrap，如果不提供，则在用C编译器编译lex.yy.c时，需要链接相应的库，库中会给出标准的yywrap函数（标准函数返回1）

### 二、yacc使用指南 ###

在使用flex分析出一段文本中的各个单元后，我们就要使用bison对这些单元间的联系进行分析，也就是语法分析。通常来说，bison/yacc会与flex/lex一同使用——如果你没有使用flex，你就要在bison代码中自己编写yylex()函数，这说明了两个工具的使用通常是密不可分的。

#### 结构介绍 ####

第一部分：定义
    %%
    第二部分：规则
    %%
    第三部分：代码

###### 1）第一部分定义的写法： ######

%{
        
    #include <stdio.h>
    #include <string.h>
    int yylex(void);
    void yyerror(char *);
    %}
    
    %token NUM ADD SUB MUL DIV VAR CR

在本部分中，我们定义了yylex()函数和yyerror()函数，它们都是我们此前已经讲过的函数，yylex就是flex中的词法分析函数。我们需要定义这两个函数，否则可能会报警告。  
此外，在C代码外，我们看到了bison的定义方式（之一）。  
在%token后面，跟着一些字符串，我们就是在这里定义了这些符号，它们会被翻译成C头文件，被flex引用，然后又通过yylex()函数return回来。  
如果你已经成功编译了这两个文件，那么打开y.tab头文件，观察里面的内容，在大约第50行，你可以看到如下内容：

/* Tokens.  */
    #define NUM 258
    #define ADD 259
    #define SUB 260
    #define MUL 261
    #define DIV 262
    #define VAR 263
    #define CR 264

这就是各个符号被定义的常数，当然，我们实际上完全不需要去关注它们具体的值是多少。我们也称这些符号为“标记”。如果你在flex中匹配的是单个字符，其实可以直接返回\*yytext，而不必返回一个符号，这是完全能行的。

###### 2）第二部分规则的写法： ######

%%
     line_list: line
                    | line_list line
                    ;
    				
    	       line : expression CR  {
        printf("YES\n");}
    
          expression: term 
                    | expression ADD term
    				| expression SUB term
                    ;
    
                term: single
    				| term MUL single
    				| term DIV single
    				;
    				
    		  single: NUM
    				| VAR
    				;
    %%

前置知识：BNF（巴克斯范式）

将单词归类为动名等词的动作是由flex完成的（通常将这些不可再分的类称为终结符）；而将这些终结符不断“合成”（归约），最后变成<句子>（这些需要被合成的类被称为非终结符）的任务，则是由bison来做，如果按照规则无法归约成句子，则说明输入是非法的。

此时我们再看这部分代码，为了方便区分，我们把非终结符全部大写，终结符全部小写。而|号则表示这个非终结符有不同的归约方法。

expression: expression '+' expression
    		  | expression '-' expression
    		  | NUM
    		  ;

上面这个BNF就表达了这样的规则：一个数字是一个表达式；表达式+表达式还是表达式；表达式-表达式还是表达式。  
这其实是我们常常能在一些计算机书籍中见到的递归定义，这也是数学表达式定义的一小部分。  
接下来，请读者自行阅读理解第二部分代码的含义。即使有些疑惑也没有关系，在编写代码时能写出自己想要的BNF即可。

###### 3）第三部分代码的写法： ######

void yyerror(char *str){
        
        fprintf(stderr,"error:%s\n",str);
    }
    
    int yywrap(){
        
        return 1;
    }
    int main()
    {
        
        yyparse();
    }

很明显，这里给出了yyerror具体的报错操作；yywrap函数同之前在flex的讲述；而yyparse函数就是bison的语法分析函数。

### 三、编写框架 ###

test.l

%{
        
    #include "y.tab.h"
    void yyerror(char *);
    %}
    
    %%
    
    %%

test.y

%{
        
    int yylex(void);
    void yyerror(char *);
    %}
    %token 
    
    %%
    
    %%
    void yyerror(char *str){
        
        fprintf(stderr,"error:%s\n",str);
    }
    
    int yywrap(){
        
        return 1;
    }
    int main()
    {
        
        yyparse();
    }

###### 上述举例介绍的全部代码： ######

这个程序的功能是：判断一个算式是否合法。我们规定一个算式由single单元和运算符组成，single单元可以是正整数或是变量名，运算符为加减乘除。如果合法则输出YES，否则报错退出。  
test.l

/*test.l*/
    %{
        
    #include <stdio.h>
    #include "y.tab.h"`在这里插入代码片`
    void yyerror(char *);
    %}
    NUM [1-9]+[0-9]*|0
    %%
    
    {
        NUM}		                return NUM;
    "+"							return ADD;
    "-"							return SUB;
    "*"							return MUL;
    "/"							return DIV;
    [a-zA-Z_$]+[a-zA-Z_$0-9]*	return VAR;
    \n                          return CR;
    [ \t]+                     /* ignore whitespace */;
    .
    %%

test.y

/*test.y*/
    %{
        
    #include <stdio.h>
    #include <string.h>
    int yylex(void);
    void yyerror(char *);
    %}
    
    %token NUM ADD SUB MUL DIV VAR CR
    
    %%
           line_list: line
                    | line_list line
                    ;
    				
    	       line : expression CR  {
        printf("YES\n");}
    
          expression: term 
                    | expression ADD term
    				| expression SUB term
                    ;
    
                term: single
    				| term MUL single
    				| term DIV single
    				;
    				
    		  single: NUM
    				| VAR
    				;
    %%
    void yyerror(char *str){
        
        fprintf(stderr,"error:%s\n",str);
    }
    
    int yywrap(){
        
        return 1;
    }
    int main()
    {
        
        yyparse();
    }

###### 运行环境：Linux Ubuntu 16发行版 ######

###### 运行命令： ######

flex test.l     //生成lex.yy.c
    yacc -d test.y   //生成y.tab.h 和 y.tab.c
    gcc -o examples y.tab.c lex.yy.c  //生成可执行文件examples
    ./examples   //运行文件

###### 执行结果： ######

![在这里插入图片描述][67fe70c69c8c47bc83c56b48347c0cc8.png]

### 四、SQL语义检查 ###

test.l

%{
        
    #include <stdio.h>
    #include "y.tab.h"
    %}
    
    %%
    #DDL、DML语句保留字
    [Cc][Rr][Ee][Aa][Tt][Ee] return CREATE;
    [Tt][Aa][Bb][Ll][Ee] return TABLE;
    [Ss][Ee][Ll][Ee][Cc][Tt] return SELECT;
    [Ff][Rr][Oo][Mm] return FROM;
    #定义的约束
    [Cc][Hh][Ee][Cc][Kk]  return CHECK; 
    [Dd][Ee][Ff][Aa][Uu][Ll][Tt]  return DEFAULT;
    [Dd][Ii][Ss][Tt][Ii][Nn][Cc][Tt]  return DISTINCT;
    [Uu][Nn][Ii][Qq][Uu][Ee]  return UNIQUE;
    [Pp][Rr][Ii][Mm][Aa][Rr][Yy]  return PRIMARY;
    [Ff][Oo][Rr][Ee][Ii][Gg][Nn]   return FOREIGN;
    [Kk][Ee][Yy][Ss]    return KEYS;
    [Ii][Ss]      return IS;
    [Nn][Uu][Ll][Ll]    return NULLX;
    CHAR(ACTER)?  return CHAR;
    VARCHAR(ACTER)?  return VARCHAR;
    INT4?|INTEGER  return INTEGER;
    [Dd][Rr][Oo][Pp]   return DROP; 
    
    
    #DDL、DML语句正则匹配
    [0-9]+ return NUMBER;
    [a-zA-Z0-9]*  return WORDS;
    $|$ return  PARENTHESES;
    
    [[a-zA-Z0-9]*]|\* return ALL;
    
    \n /* ignore end of line */;
    [ \t]+ /* ignore whitespace */
    %%

test.y

%{
        
    #include <stdio.h>
    #include <string.h>
    
    //在lex.yy.c里定义，会被yyparse()调用。在此声明消除编译和链接错误。
    extern int yylex(void); 
    
    // 在此声明，消除yacc生成代码时的告警
    extern int yyparse(void); 
    
    int yywrap()
    {
        
    	return 1;
    }
    
    // 该函数在y.tab.c里会被调用，需要在此定义
    void yyerror(const char *s)
    {
        
    	printf("[error] %s\n", s);
    }
    
    int main()
    {
        
    	yyparse();
    	return 0;
    }
    %}
    %token NUMBER
    %token CREATE TABLE WORDS PARENTHESES ALL SPACE
    %token SELECT FROM 
    
    %token CHECK DEFAULT DISTINCT UNIQUE PRIMARY FOREIGN KEYS IS NULLX CHAR VARCHAR INTEGER DROP
    
    %%
    commands:
    | commands command
    ;
    
    command: ddl|dml ;
    
    ddl:
    CREATE TABLE WORDS PARENTHESES WORDS WORDS PARENTHESES NUMBER PARENTHESES PARENTHESES
    {
        
    	printf("\tTHIS IS DDL SQL\n");
    };
    
    dml:
    SELECT ALL FROM WORDS
    {
        
    	printf("\tTHIS IS DML SQL\n");
    };
    %%

###### 运行命令： ######

flex test.l
    yacc -d test.y
    gcc lex.yy.c y.tab.c -o examples
    ./examples

###### 运行结果： ######

可以输入ddl语句：（目前只限制格式如下的sql语句分析）
    CREATE TABLE Employees (
      Eid   char(10)  )
    或者输入 dml语句：(这里正则有点问题，现在还只能匹配*,后续会做完善)
    SELECT * FROM DSA

![!\[在这里插入图片描述\](https://img-blog.csdnimg.cn/24265baefcb042bd83eacc80454a84b7.png][https_img-blog.csdnimg.cn_24265baefcb042bd83eacc80454a84b7.png]

[67fe70c69c8c47bc83c56b48347c0cc8.png]: https://img-blog.csdnimg.cn/67fe70c69c8c47bc83c56b48347c0cc8.png
[https_img-blog.csdnimg.cn_24265baefcb042bd83eacc80454a84b7.png]: https://img-blog.csdnimg.cn/b21b115e7344435995a4302f10ca1460.png