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

《编译原理第六章上机辅导.ppt》由会员分享，可在线阅读，更多相关《编译原理第六章上机辅导.ppt（52页珍藏版）》请在装配图网上搜索。

1、1,编译原理上机内容,上机目的 题目与要求 参考解决方案 数据库存储结构 CREATE TABLE词法语法分析 SELECT词法语法分析,2,1 上机目的,通过做上机题加深对编译原理和数据库管理系统的理解，巩固所学知识。 学会使用LEX// 类别 char char_var; char *yych; int yyint; ...... ; 4. SQL语言中记号的分类：关键字、标示符、数字、其它符号。,20,3.2 词法分析器,SQL语句中的记号： 例 CREATE TABLE Student ( Sno CHAR(9), Sname CHAR(20), Ssex CHAR(2), S

2、age INT ); 上边的SQL语句包括哪些记号？ 关键字：CREATE TABLE CHARINT 标示符：Student Sno Sname Ssex Sage 数字： 9，20，2 其他符号： ( ) , ; ,,LEX源程序基本结构如下： 声明 %% 翻译规则 %% 用户定义子程序,21,22,3.2 词法分析器,用正则式识别记号 CREATE TABLE对应的LEX源程序: CREATEreturn CREATE; TABLEreturn TABLE; CHARreturn CHAR; INTreturn INT; A-Za-zA-Za-z0-9_*yylval

3、.yych=(char *)malloc(strlen(yytext)+1); strcpy(yylval.yych,yytext); return IDENTIFIER;,23,3.2 词法分析器,0-9+yylval.yych=(char *)malloc(strlen(yytext)+1); strcpy(yylval.yych,yytext); return NUMBER; ;| (| )| ,return yytext0; 经过词法分析，CREATE TABLE语句被识别为： CREATE TABLE IDENTIFIER1 (IDENTIFIER2 CHAR(NUMBER), ID

4、ENTIFIER3 CHAR(NUMBER), IDENTIFIER4 CHAR(NUMBER), IDENTIFIER5 INT);,24,3.3 语法分析器,语法分析器的任务：分析语言的结构 为句子构造语法树； 检查输入序列中的错误。 主要工作： 设计SQL语言的文法； 设计语法树的节点，用于存放表达式的语法树； 利用YACC工具分析SQL语句，并构造语句的语法树； 设计测试程序和测试用例，检验分析器是否正确。,25,3.3 语法分析器,1. 设计CREATE TABLE语言的文法 statement createsql | selectsql | ...... createsql

5、 CREATE TABLE table ( fieldsdefinition ) ; table IDENTIFIER fieldsdefinition field_type | fieldsdefinition , field_type field_type field type field IDENTIFIER type CHAR ( NUMBER ) | INT,26,3.3 语法分析器,2. 设计CREATE TABLE语法树的节点 typedef struct_createstruct/*create语法树根节点*/ char*table; _createfieldsdef_ty

6、pe*fdef; _createstruct_type; typedef struct _createfieldsdef/*create语句中的字段定义*/ char*field; enum TYPE type; intlength; struct _createfieldsdef *next_fdef; _createfieldsdef_type; enum Type INT,CHAR;/*字段类型*/,27,YACC源程序基本结构如下： 声明 %% 翻译规则 %% 用户定义子程序 我们来看一个具体例子：,28,3.3 语法分析器,CREATE TABLE对应的yacc源程序： %

7、 _createfieldsdef_type*cfdef_end; % %union/*定义yylval的格式*/ charchar_var; char*yych; intyyint; /*属于create语法树的类型*/ _createfieldsdef_type*cfdef_var; _createstruct_type*cs_var; ,29,3.3 语法分析器,%start statement %tokenCREATE TABLE CHAR INT %typeIDENTIFIERNUMBER %typetablefield %typetype %typefieldsdefinitio

8、nfield_type %typecreatesql %% --声明部分,30,3.3 语法分析器,statement:selectsql |createsql create_table($1); | ......; createsql: CREATE TABLE table ( fieldsdefinition ) ; $$=(_createstruct_type *)malloc( sizeof(_createstruct_type)); $$-table=$3; $$-fdef=$5; ;,31,3.3 语法分析器,table

9、: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:field type $$=(_createfieldsdef_type *)malloc( sizeof(_createfieldsdef_type)); $$-field=$1; if (strlen($2)==0) /

10、*表示类型为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.4 SELECT 语句的实现,词法分析部分： SELECTreturn SELECT; FROMret

11、urn FROM; WHEREreturn WHERE; ANDreturn AND; ORreturn OR; ;| (| )| ,| | .| =| return yytext0;,35,3.4 SELECT 语句的实现,1.设计SELECT语言文法 select 语句文法： statementselectsql| ...... selectsqlSELECT fields_star FROM tables ; | SELECT fields_star FROM tables WHERE conditions ; fields_startable_fields | * tablest

12、able | tables , table table_fieldstable_field | table_fields , table_field table_fieldfield | table . field table IDENTIFIER field IDENTIFIER,36,3.4 SELECT 语句的实现,设计语法树的节点，用于存放表达式的语法树； typedefstruct_selectedfields/*select语句中选中的字段*/ char *table; char *field; struct _selectedfields*next_sf; _selectedfi

13、elds_type; typedef struct_selectedtables/*select语句中选中的表*/ char*table; struct_selectedtables*next_st; _selectedtables_type; typedef struct_selectstruct/*select语法树的根节点*/ _selectedfields_type *sf; _selectedtables_type*st; _conditions_type*cons; _selectstruct_type;,37,3.4 SELECT 语句的实现,typedef struct_con

14、ditions struct _conditions*left; struct _conditions*right; char comp_op;/*(a--and),(o--or), , = */ char type;/*2--是表的字段，1--是字符串型，0--是整型*/ char *table;/*不为NULL就存放表名*/ char *value;/*存放字段名，字符串或整数的值，要看type的值*/ intintval;/*用于以后计算的时候存储结果*/ _conditions_type;,38,3.4 SELECT 语句的实现,下边是语法分析部分需要用到的中间变量 /*select语

15、句中选中的字段*/ _selectedfields_type*sf_var1,*sf_end; /*select语句中选中的表*/ _selectedtables_type*st_var1,*st_end;,39,3.4 SELECT 语句的实现,%union/*定义yylval的格式*/ char char_var; char *yych; int yyint; /*属于select语法树的类型*/ _selectedfields_type*sf_var; _selectedtables_type*st_var; _selectstruct_type*ss_var; ,40,3.4 SELE

16、CT 语句的实现,%token SELECTFROMWHERE %token IDENTIFIERNUMBER %typeselectsql %typefields_startable_fieldstable_field %typetables %typetablefield %left OR %leftAND %typeconditioncomp_leftcomp_right %typetable_field_conditions %typecomp_op,41,3.4 SELECT 语句的实现,selectsql:SELECT fields_star FROM tables; $$=(_s

17、electstruct_type *)malloc(sizeof(_selectstruct_type)); $$-sf=$2; $$-st=$4; $$-cons=NULL; printf(SELECTSQLn); |SELECT fields_star FROM tables WHERE conditions ; $$=(_selectstruct_type *)malloc(sizeof(_selectstruct_type)); $$-sf=$2; $$-st=$4; $$-cons=$6;;,42,3.4 SELECT 语句的实现,fields_star:table_fields/*

18、如果输入了具体的字段名称*/ $$=$1; printf(fields_starn); |*/*如果输入了星号*/ $$=(_selectedfields_type *)malloc(sizeof(_selectedfields_type)); $$-table=NULL; $$-field=*; $$-next_sf=NULL; printf(fields_starn); ;,43,3.4 SELECT 语句的实现,tables:table/*第一个表*/ $$=(_selectedtables_type *)malloc(sizeof(_selectedtables_type)); $$-

19、table=$1; $$-next_st=NULL; st_end=$$; printf(tables %s n,$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.4 SELECT 语句的实现,table_fi

20、elds: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.4 SELECT 语句的实现,table_field:field $$=(_selectedfields_type *)malloc(sizeof(_selectedfields_type)); $$-table=(char *)

21、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.4 SELECT 语句的实现,conditions:condition(文法还有问题，

22、原子条件必须加括号？) $$=$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.4 SELECT 语句的实现

23、,condition:comp_left comp_op comp_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.4 SELECT 语句的实现,comp_right:table_field_ $$=$1; $$-comp_op=0; $$-type=2;

24、$$-left=NULL; $$-right=NULL; | IDENTIFIER $$=(_conditions_type *)malloc(sizeof(_conditions_type)); $$-left=NULL; $$-right=NULL; $$-comp_op=0; $$-type=1; $$-value=$2;,49,3.4 SELECT 语句的实现,| NUMBER $$=(_conditions_type *)malloc(sizeof(_conditions_type)); $$-left=NULL; $$-right=NULL; $$-comp_op=0; $$-ty

25、pe=1; $$-value=$2; |NUMBER $$=(_conditions_type *)malloc(sizeof(_conditions_type)); $$-left=NULL; $$-right=NULL; $$-type=0; $$-value=$1; $$-intval=atoi($1);;,50,3.4 SELECT 语句的实现,table_field_:field $$=(_conditions_type *)malloc(sizeof(_conditions_type)); $$-table=(char *)malloc(sizeof(10));/*为以后填上表名预

26、留空间*/ $$-table0=0; $$-value=$1; |table . field $$=(_conditions_type *)malloc(sizeof(_conditions_type)); $$-table=$1; $$-value=$3; ;,51,3.4 SELECT 语句的实现,comp_op: $$=; |= $$==; ;,备注：,1.数据库管理系统的重点在于物理结构的设计。良好的物理结构可以使数据存储、查询和删除容易进行。 2.使用lex和yacc工具实现词法和语法分析，可以去网上下载lex和yacc工具。此处建议使用集成的工具Parser Generator。注意配置Parser Generator和VC++。具体配置见word文档。 3.若只进行词法和语法分析，不用设计数据库的物理结构；若要实现DBMS的功能，则要设计物理结构。 4.推荐书籍：数据库系统实现，MySQL技术内幕：Innodb存储引擎，教材。,52,