编译原理第六章上机辅导.ppt

1,编译原理上机内容,上机目的题目与要求参考解决方案数据库存储结构CREATETABLE词法语法分析SELECT词法语法分析,2,1上机目的,通过做上机题加深对编译原理和数据库管理系统的理解，巩固所学知识。学会使用LEX/类别charchar_var;char*yych;intyyint;.;4.SQL语言中记号的分类：关键字、标示符、数字、其它符号。,20,3.2词法分析器,SQL语句中的记号：例CREATETABLEStudent(SnoCHAR(9),SnameCHAR(20),SsexCHAR(2),SageINT);上边的SQL语句包括哪些记号？关键字：CREATETABLECHARINT标示符：StudentSnoSnameSsexSage数字：9，20，2其他符号：(),;,LEX源程序基本结构如下：声明%翻译规则%用户定义子程序,21,22,3.2词法分析器,用正则式识别记号CREATETABLE对应的LEX源程序:CREATEreturnCREATE;TABLEreturnTABLE;CHARreturnCHAR;INTreturnINT;A-Za-zA-Za-z0-9_*yylval.yych=(char*)malloc(strlen(yytext)+1);strcpy(yylval.yych,yytext);returnIDENTIFIER;,23,3.2词法分析器,0-9+yylval.yych=(char*)malloc(strlen(yytext)+1);strcpy(yylval.yych,yytext);returnNUMBER;|(|)|,returnyytext0;经过词法分析，CREATETABLE语句被识别为：CREATETABLEIDENTIFIER1(IDENTIFIER2CHAR(NUMBER),IDENTIFIER3CHAR(NUMBER),IDENTIFIER4CHAR(NUMBER),IDENTIFIER5INT);,24,3.3语法分析器,语法分析器的任务：分析语言的结构为句子构造语法树；检查输入序列中的错误。主要工作：设计SQL语言的文法；设计语法树的节点，用于存放表达式的语法树；利用YACC工具分析SQL语句，并构造语句的语法树；设计测试程序和测试用例，检验分析器是否正确。,25,3.3语法分析器,1.设计CREATETABLE语言的文法statementcreatesql|selectsql|.createsqlCREATETABLEtable(fieldsdefinition);tableIDENTIFIERfieldsdefinitionfield_type|fieldsdefinition,field_typefield_typefieldtypefieldIDENTIFIERtypeCHAR(NUMBER)|INT,26,3.3语法分析器,2.设计CREATETABLE语法树的节点typedefstruct_createstruct/*create语法树根节点*/char*table;_createfieldsdef_type*fdef;_createstruct_type;typedefstruct_createfieldsdef/*create语句中的字段定义*/char*field;enumTYPEtype;intlength;struct_createfieldsdef*next_fdef;_createfieldsdef_type;enumTypeINT,CHAR;/*字段类型*/,27,YACC源程序基本结构如下：声明%翻译规则%用户定义子程序我们来看一个具体例子：,28,3.3语法分析器,CREATETABLE对应的yacc源程序：%_createfieldsdef_type*cfdef_end;%union/*定义yylval的格式*/charchar_var;char*yych;intyyint;/*属于create语法树的类型*/_createfieldsdef_type*cfdef_var;_createstruct_type*cs_var;,29,3.3语法分析器,%startstatement%tokenCREATETABLECHARINT%typeIDENTIFIERNUMBER%typetablefield%typetype%typefieldsdefinitionfield_type%typecreatesql%-声明部分,30,3.3语法分析器,statement:selectsql|createsqlcreate_table($1);|.;createsql:CREATETABLEtable(fieldsdefinition);$=(_createstruct_type*)malloc(sizeof(_createstruct_type);$-table=$3;$-fdef=$5;,31,3.3语法分析器,table:IDENTIFIER$=$1;fieldsdefinition:field_type$=$1;cfdef_end=$1;|fieldsdefinition,field_type$=$1;cfdef_end-next_fdef=$3;cfdef_end=$3;,32,3.3语法分析器,field_type:fieldtype$=(_createfieldsdef_type*)malloc(sizeof(_createfieldsdef_type);$-field=$1;if(strlen($2)=0)/*表示类型为int的时候，用INT表示类型，长度定为4*/$-type=INT;$-length=4;$-next_fdef=NULL;,33,3.3语法分析器,else/*类型为CHAR：用CHAR表示类型，长度定为$2*/$-type=CHAR;$-length=atoi($2);$-next_fdef=NULL;field:IDENTIFIER$=$1;type:CHAR(NUMBER)$=$3;|INT$=0;,34,3.4SELECT语句的实现,词法分析部分：SELECTreturnSELECT;FROMreturnFROM;WHEREreturnWHERE;ANDreturnAND;ORreturnOR;|(|)|,|.|=|returnyytext0;,35,3.4SELECT语句的实现,1.设计SELECT语言文法select语句文法：statementselectsql|.selectsqlSELECTfields_starFROMtables;|SELECTfields_starFROMtablesWHEREconditions;fields_startable_fields|*tablestable|tables,tabletable_fieldstable_field|table_fields,table_fieldtable_fieldfield|table.fieldtableIDENTIFIERfieldIDENTIFIER,36,3.4SELECT语句的实现,设计语法树的节点，用于存放表达式的语法树；typedefstruct_selectedfields/*select语句中选中的字段*/char*table;char*field;struct_selectedfields*next_sf;_selectedfields_type;typedefstruct_selectedtables/*select语句中选中的表*/char*table;struct_selectedtables*next_st;_selectedtables_type;typedefstruct_selectstruct/*select语法树的根节点*/_selectedfields_type*sf;_selectedtables_type*st;_conditions_type*cons;_selectstruct_type;,37,3.4SELECT语句的实现,typedefstruct_conditionsstruct_conditions*left;struct_conditions*right;charcomp_op;/*(a-and),(o-or),=*/chartype;/*2-是表的字段，1-是字符串型，0-是整型*/char*table;/*不为NULL就存放表名*/char*value;/*存放字段名，字符串或整数的值，要看type的值*/intintval;/*用于以后计算的时候存储结果*/_conditions_type;,38,3.4SELECT语句的实现,下边是语法分析部分需要用到的中间变量/*select语句中选中的字段*/_selectedfields_type*sf_var1,*sf_end;/*select语句中选中的表*/_selectedtables_type*st_var1,*st_end;,39,3.4SELECT语句的实现,%union/*定义yylval的格式*/charchar_var;char*yych;intyyint;/*属于select语法树的类型*/_selectedfields_type*sf_var;_selectedtables_type*st_var;_selectstruct_type*ss_var;,40,3.4SELECT语句的实现,%tokenSELECTFROMWHERE%tokenIDENTIFIERNUMBER%typeselectsql%typefields_startable_fieldstable_field%typetables%typetablefield%leftOR%leftAND%typeconditioncomp_leftcomp_right%typetable_field_conditions%typecomp_op,41,3.4SELECT语句的实现,selectsql:SELECTfields_starFROMtables;$=(_selectstruct_type*)malloc(sizeof(_selectstruct_type);$-sf=$2;$-st=$4;$-cons=NULL;printf(SELECTSQLn);|SELECTfields_starFROMtablesWHEREconditions;$=(_selectstruct_type*)malloc(sizeof(_selectstruct_type);$-sf=$2;$-st=$4;$-cons=$6;,42,3.4SELECT语句的实现,fields_star:table_fields/*如果输入了具体的字段名称*/$=$1;printf(fields_starn);|*/*如果输入了星号*/$=(_selectedfields_type*)malloc(sizeof(_selectedfields_type);$-table=NULL;$-field=*;$-next_sf=NULL;printf(fields_starn);,43,3.4SELECT语句的实现,tables:table/*第一个表*/$=(_selectedtables_type*)malloc(sizeof(_selectedtables_type);$-table=$1;$-next_st=NULL;st_end=$;printf(tables%sn,$1);|tables,table/*后面的表*/$=$1;st_var1=(_selectedtables_type*)malloc(sizeof(_selectedtables_type);st_var1-table=$3;st_var1-next_st=NULL;st_end-next_st=st_var1;/*建立表名的连接*/st_end=st_var1;printf(tablesn);,44,3.4SELECT语句的实现,table_fields:table_field$=$1;sf_end=$;/*第一个字段名称*/printf(table_fieldsn);|table_fields,table_field/*后面的字段*/$=$1;sf_end-next_sf=$3;/*建立字段名的连接*/sf_end=$3;printf(table_fieldsn);,45,3.4SELECT语句的实现,table_field:field$=(_selectedfields_type*)malloc(sizeof(_selectedfields_type);$-table=(char*)malloc(sizeof(10);/*为以后填上表名预留空间*/$-table0=0;$-field=$1;$-next_sf=NULL;printf(table_field:%sn,$1);|table.field$=(_selectedfields_type*)malloc(sizeof(_selectedfields_type);$-table=$1;$-field=$3;$-next_sf=NULL;printf(table_fieldn);,46,3.4SELECT语句的实现,conditions:condition(文法还有问题，原子条件必须加括号？)$=$1;|(conditions)AND(conditions)$=(_conditions_type*)malloc(sizeof(_conditions_type);$-left=$2;$-right=$6;$-comp_op=a;|(conditions)OR(conditions)$=(_conditions_type*)malloc(sizeof(_conditions_type);$-left=$2;$-right=$6;$-comp_op=o;,47,3.4SELECT语句的实现,condition:comp_leftcomp_opcomp_right$=(_conditions_type*)malloc(sizeof(_conditions_type);$-left=$1;$-comp_op=$2;$-right=$3;comp_left:table_field_$=$1;$-comp_op=0;$-type=2;$-left=NULL;$-right=NULL;,48,3.4SELECT语句的实现,comp_right:table_field_$=$1;$-comp_op=0;$-type=2;$-left=NULL;$-right=NULL;|IDENTIFIER$=(_conditions_type*)malloc(sizeof(_conditions_type);$-left=NULL;$-right=NULL;$-comp_op=0;$-type=1;$-value=$2;,49,3.4SELECT语句的实现,|NUMBER$=(_conditions_type*)malloc(sizeof(_conditions_type);$