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

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), Sage 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.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), IDENTIFIER3 CHAR(NUMBER), IDENTIFIER4 CHAR(NUMBER), IDENTIFIER5 INT);,24,3.3 语法分析器,语法分析器的任务：分析语言的结构 为句子构造语法树； 检查输入序列中的错误。 主要工作： 设计SQL语言的文法； 设计语法树的节点，用于存放表达式的语法树； 利用YACC工具分析SQL语句，并构造语句的语法树； 设计测试程序和测试用例，检验分析器是否正确。,25,3.3 语法分析器,1. 设计CREATE TABLE语言的文法 statement createsql | selectsql | . createsql 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_type*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源程序： % _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 %typefieldsdefinitionfield_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: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) /*表示类型为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; FROMreturn 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 | * tablestable | 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; _selectedfields_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_conditions 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语句中选中的字段*/ _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 SELECT 语句的实现,%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; $=(_selectstruct_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/*如果输入了具体的字段名称*/ $=$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); $-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_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.4 SELECT 语句的实现,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.4 SELECT 语句的实现,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.4 SELECT 语句的实现,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; $-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; $-type=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);/*为以后填上表名预留空间*/ $-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,