Hexo

LEX&YACC

简介

Lex & Yacc 是用来生成词法分析器和语法分析器的工具。

Lex （A Lexical Analyzer Generator）用于生成词法分析器，用于把输入分割成一个个有意义的词块（称为token）。

Yacc（Yet Another Compiler-Compiler）用于生成语法解析器，用于确定上述分隔好的token之间的关联

Lex

Lex结构

lex文件内容分为三个段分别为：定义段、规则段、用户子程序段

三个段用 %% 进行分隔:

/* 定义段 */
%{
...
%}
...

%%
    /* 规则段 */
...

%%
    /* 用户子程序段 */
...

第1段是声明段，包括：
1-C代码部分：include头文件、函数、类型等声明，这些声明会原样拷到生成的.c文件中。

%{
#include<string.h>
#include<stdio.h>
#include "yacc_sql.tab.h"
extern int atoi();
extern double atof();
char * position = "";

#ifdef YYDEBUG
#define debug_printf  printf
#else
#define debug_printf(...)
#endif // YYDEBUG

#define RETURN_TOKEN(token) debug_printf("%s\n",#token);return token
%}

​ 2-状态声明，如%x COMMENT。

状态声明将会在第二段用到，例如：
若当读到//注释符时忽略该行输入则可以使用%x标记一个状态，当读到//符时切换到该状态，后续只能匹配到该状态相应的规则，读到换行符后再返回原状态。以达到忽略注释行的目的。
切换状态通过BEGIN实现,初始态为INITIAL
"//"    				{    //遇到串"//"，表明要开始一段注释，直到行尾
            			BEGIN COMMENT;//用BEGIN宏切换到注释状态，去过滤这段注释，下一次lex将只匹配前面带有<COMMENT>的正则式
        				}
        				
 <COMMENT>\n    {    //注释状态下的规则，只有当前切换到COMMENT状态才会去匹配
            			BEGIN INITIAL;//在注释状态下，当遇到换行符时，表明注释结束了，返回初始态
      				  }

​ 3-正则式定义，如ID [A-Za-z_]+[A-Za-z0-9_]*。

WS      [\ \t\b\f]
DIGIT   [0-9]+
ID      [A-Za-z_]+[A-Za-z0-9_]*
DOT     \.
QUOTE   [\'\"]

第2段是规则段，是lex文件的主体，包括每个规则是如何匹配的，以及匹配后要执行的C代码动作。

{WS}                    /* ignore whitespace */;
[Ss][Ee][Ll][Ee][Cc][Tt]                 position=strdup(yytext);RETURN_TOKEN(SELECT);
[Ff][Rr][Oo][Mm]                      	 position=strdup(yytext);RETURN_TOKEN(FROM);
[Ww][Hh][Ee][Rr][Ee]                  	 position=strdup(yytext);RETURN_TOKEN(WHERE);
[Aa][Nn][Dd]                             position=strdup(yytext);RETURN_TOKEN(AND);
[Oo][Rr][Dd][Ee][Rr]										 position=strdup(yytext);RETURN_TOKEN(ORDER);
[Bb][Yy]                                 position=strdup(yytext);RETURN_TOKEN(BY);
{ID}                                             
{ yylval.string=strdup(yytext);position=strdup(yytext);RETURN_TOKEN(ID);}


lex匹配优先规则：
数据流进入后进行逐字符匹配，若加入下一个字符可以匹配到规则则压入字符，当达到最大匹配长度后若能匹配多个规则，则执行位置较前的规则。
如select * from t;
读第一个字符's'能匹配到id，但是加上后续字符'e'仍满足条件则继续压栈，直到栈里为select此时已是能匹配的最大长度（加入空格后不能匹配到规则），这时能匹配到两个规则
[Ss][Ee][Ll][Ee][Cc][Tt]                 position=strdup(yytext);RETURN_TOKEN(SELECT);
{ID}                                             
{ yylval.string=strdup(yytext);position=strdup(yytext);RETURN_TOKEN(ID);}
因为select字段的规则在前，因此不会匹配成id，而是匹配select规则返回SELECT TOKEN。

第3段是C函数定义段，如yywrap()的定义，这些C代码会原样拷到生成的.c文件中，该段内容可以为空。

yywrap()
当词法分析程序遇到文件结尾时，它调用例程yywrap()来找出下一步要做什么，如果返回0，扫描程序继续扫描，如果返回1，扫描程序就返回报告文件结尾需标记。
lex库中yywrap()的标准版本总是返回1，如果yywrap()返回指示有更多的输入0，那么它首先需要调整指向新的文件yyin,可能使用fopen()。

int yywrap(void)
{
    return 1;//返回1表示读取全部结束。如果要接着读其它文件，可以这里fopen该文件，文件指针赋给yyin，并返回0
}

lex文件中其他常见函数和变量

lex不仅返回相应的token，同时还会向yacc传递相应数据，如：
create table stu(id int,old int);
不仅需要返回create table int等关键字的token，同时还要把表名、列名等字符串传给yacc

yytext
每当词法分析程序匹配标记时，标记的文本就存储在以空字符结尾的字符串yytext中
每次匹配一个新的标记时，就要替换yytext的内容，如果yytext的内容还要使用，通过strdup()或者自己申请内存来保存字符串拷贝，从而使字符串的拷贝拷贝位于刚刚分配的内存中。
{ID}                                             
{ yylval.string=strdup(yytext);position=strdup(yytext);RETURN_TOKEN(ID);}

yylval变量
extern YYSTYPE yylval
lex将数据流中的数据赋给yylval变量相应字段，从而传递给yacc
YYSTYPE在yacc文件中定义结构，默认为int，后续在yacc部分详解

Yacc

简介

yacc(Yet Another Compiler Compiler)，是Unix/Linux上一个用来生成编译器的编译器（编译器代码生成器）。
使用巴克斯范式(BNF)定义语法，能处理上下文无关文法(context-free)。出现在每个产生式左边(left-hand side：lhs)的符号是非终端符号，出现在产生式右边(right-hand side：rhs)的符号有非终端符号和终端符号，但终端符号只出现在右端。

x

举个例子：
在中文语法里，一个句子一般由“主语”、“谓语”和“宾语”组成，主语可以是名词或者代词，谓语一般是动词，宾语可以使形容词，名词或者代词。那么“主语”、“谓语”和“宾语”就是非终止符，因为还可以继续由“名词”、“代词”、“动词”、“形容词”等替代。

例1. <句子> ::= <主语><谓语><宾语>

例2. <主语> ::= <名词>|<代词>

例3. <谓语>::=<动词>

例4. <宾语>::=<形容词>|<名词>|<代词>

例5. <代词>::=<我>

例6. <动词>::=<吃>

例7. <动词>::=<喜欢>

例8. <名词>::=<车>

例9. <名词>::=<肉>

如上，在::=左边的就是non-terminal非终止符，右边的就是replacement，可以是一系列的非终止符，如例1中的replacement便是后面例234左边的非终止符，也可以是终止符，如例56789的右边，找不到别的符号来进一步代替。
因此，终止符永远不会出现在左边。一旦我们看到了终止符，这个描述过程就结束了。

语法结构

yacc语法包括三部分：定义段、规则段和用户子例程段

...定义段...

%%

...规则段...

%%

...用户子例程段...

各部分由以两个百分号开头的行分开，尽管某一个部分可以为空，但是前两部分是必须的，第三部分和前面的百分号可以省略。

定义段：

1、C代码部分：include头文件、函数、类型等声明，这些声明会原样拷贝到生产的.c文件中

2、记号声明，如%token

3、类型声明，如%type

%{

#include "handler/handler_defs.h"
// #include "common/log/log.h" // TODO 包含C++中的头文件

extern char * position;
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
extern int yylex(void);
....
....
int compOpT;
void yyerror(const char *str) {

	ssql->flag=0;
	whereleng=0; 
  fromleng=0;
  selectleng=0;
	valueleng=0;
  ssql->sstr.ins.nValues=0;
	ssql->sstr.errors=position;
	printf("parse sql failed. error=%s", str);
}

%}

yyerror会对无法解析的语句进行处理

//标识tokens
%token  SEMICOLON
        CREATE
        DROP
        TABLE
        TABLES
        INDEX
        SELECT
        DESC
        SHOW
        SYNC
        INSERT
.....
%union {
    struct _Attr *attr;
	  struct _Condition *condition1;
  	struct _Value *value1;
    char *string;
  //  char *ssss;
    int number;
    float floats;
}
%union字段定义了YYSTYPE的结构体类型，定义后lex文件中就可以使用yylval变量的相应部分进行传输数据

%token <number> NUMBER
%token <floats> FLOAT 
%token <string> ID
%token <string> SSS
%token <string>  STAR
这种方式可以把标志（token）绑定到YYSTYPE的某个域。这样在后面规则部分直接使用$x就可以得到token的值，而不需要使用$x.number/string这种方式

规则段：

规则段由语法规则和包括C代码的动作组成。

规则中目标或非终端符放在左边，后跟一个冒号（：），然后是产生式的右边，之后是对应的动作（用{}包含）。

%%

commands:     //commands or sqls. parser starts here.
    /* empty */
    | commands command
    ;

command:
     select  
   | insert
   | update
   | delete
   | create_table
...
   ;
commands规则中的第一条为空非常重要，否则commands没有递归的出口

以select语句的解析为例
select:				/*  select 语句的语法解析树*/
    SELECT select_attr FROM ID rel_list where SEMICOLON {
      
            ssql->sstr.sel.relations[fromleng++]=$4;

            for(i=0;i<whereleng;i++){
              ssql->sstr.sel.conditions[i]=wherecondi[i];
            }

            ssql->flag=SCF_SELECT;//"select";
            ssql->sstr.sel.nSelAttrs=selectleng;
            ssql->sstr.sel.nRelations=fromleng;
            ssql->sstr.sel.nConditions=whereleng;

            //临时变量清零
            whereleng=0;
            fromleng=0;
            selectleng=0;
        }
        ;
        

select_attr:
    STAR {  // TODO 处理这里的内存泄露问题
         ssql->sstr.sel.selAttrs[selectleng].attrName="*";
         ssql->sstr.sel.selAttrs[selectleng++].relName=NULL;
       }
    | ID attr_list {
        ssql->sstr.sel.selAttrs[selectleng].attrName=$1;
        ssql->sstr.sel.selAttrs[selectleng++].relName=NULL;
      }
  	| ID DOT ID attr_list {
        ssql->sstr.sel.selAttrs[selectleng].attrName=$3;
        ssql->sstr.sel.selAttrs[selectleng++].relName=$1;
      }
    ;

attr_list:
    /* empty 递归出口*/
    | COMMA ID attr_list {
     	  ssql->sstr.sel.selAttrs[selectleng].relName = NULL;
        ssql->sstr.sel.selAttrs[selectleng++].attrName=$2;
      }
    | COMMA ID DOT ID attr_list {
        ssql->sstr.sel.selAttrs[selectleng].attrName=$4;
        ssql->sstr.sel.selAttrs[selectleng++].relName=$2;
  	  }
  	;
  	
rel_list:
    /* empty */
    | COMMA ID rel_list {	
				ssql->sstr.sel.relations[fromleng++]=$2;
		  }
    ;
    
where:
    /* empty */ 
    | WHERE condition condition_list {	
				wherecondi[whereleng++]=*$2;
			}
    ;
    
condition_list:
    /* empty */
    | AND condition condition_list {
				wherecondi[whereleng++]=*$2;
			}
    ;
condition:
    ID comOp value {
									$$ = ( Condition *)malloc(sizeof( Condition));
									$$->bLhsIsAttr = 1;
									$$->lhsAttr.relName = NULL;
									$$->lhsAttr.attrName = $1;
									$$->op = compOpT;
									$$->bRhsIsAttr = 0;
									$$->rhsAttr.relName = NULL;
									$$->rhsAttr.attrName = NULL;
									$$->rhsValue = *$3;

								    }
		|value comOp value {
									$$ = ( Condition *)malloc(sizeof( Condition));
									$$->bLhsIsAttr = 0;
									$$->lhsAttr.relName=NULL;
									$$->lhsAttr.attrName=NULL;
									$$->lhsValue = *$1;
									$$->op = compOpT;
									$$->bRhsIsAttr = 0;
									$$->rhsAttr.relName = NULL;
									$$->rhsAttr.attrName = NULL;
									$$->rhsValue = *$3;

								    }
		|ID comOp ID {
									$$=( Condition *)malloc(sizeof( Condition));
									$$->bLhsIsAttr = 1;
									$$->lhsAttr.relName=NULL;
									$$->lhsAttr.attrName=$1;
									$$->op=compOpT;
									$$->bRhsIsAttr = 1;
									$$->rhsAttr.relName=NULL;
									$$->rhsAttr.attrName=$3;

								    }
    |value comOp ID{
									$$=( Condition *)malloc(sizeof( Condition));
									$$->bLhsIsAttr = 0;
									$$->lhsAttr.relName=NULL;
									$$->lhsAttr.attrName=NULL;
									$$->lhsValue = *$1;
									$$->op=compOpT;
									
									$$->bRhsIsAttr = 1;
									$$->rhsAttr.relName=NULL;
									$$->rhsAttr.attrName=$3;
								
								    }
    |ID DOT ID comOp value{
									$$=( Condition *)malloc(sizeof( Condition));
									$$->bLhsIsAttr = 1;
									$$->lhsAttr.relName=$1;
									$$->lhsAttr.attrName=$3;
									$$->op=compOpT;
									$$->bRhsIsAttr = 0;   //属性值
									$$->rhsAttr.relName=NULL;
									$$->rhsAttr.attrName=NULL;
									$$->rhsValue=*$5;			
							
    											}
    |value comOp ID DOT ID{
									$$=( Condition *)malloc(sizeof( Condition));
									$$->bLhsIsAttr = 0;//属性值
									$$->lhsAttr.relName=NULL;
									$$->lhsAttr.attrName=NULL;
									$$->lhsValue = *$1;
									$$->op=compOpT;
									$$->bRhsIsAttr = 1;//属性
									$$->rhsAttr.relName = $3;
									$$->rhsAttr.attrName = $5;
									
    						}
    |ID DOT ID comOp ID DOT ID{
									$$=( Condition *)malloc(sizeof( Condition));
									$$->bLhsIsAttr = 1;		//属性
									$$->lhsAttr.relName=$1;
									$$->lhsAttr.attrName=$3;
									$$->op=compOpT;
									$$->bRhsIsAttr = 1;		//属性
									$$->rhsAttr.relName=$5;
									$$->rhsAttr.attrName=$7;								
    											}
    ;

comOp:
  	  EQ { compOpT = EQual; }
    | LT { compOpT = LEqual; }
    | GT { compOpT = GreatT; }
    | LE { compOpT = LessT; }
    | GE { compOpT = GEqual; }
    | NE { compOpT = NEqual; }
    ;


							 

以下面这个select语句解析为例

select name,old from stu where old>10;

lex会将该句分解为以下token序列
SELECT ID COMMA ID FROM ID WHERE ID 

token序列进入yacc后会进行规则解析，然后触发相应动作，最终形成在后续使用的ssql结构体

赏

谢谢你请我吃糖果