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

1,编译原理上机内容,上机目的题目与要求参考解决方案数据库存储结构CREATE TABLE词法语法分析SELECT词法语法分析,2,1 上机目的,通过做上机题加深对编译原理和数据库管理系统的理解，巩固所学知识。学会使用LEX&YACC进行词法语法分析；学会如何编写一个简单的SQL解释器；数据库管理系统与编译原理的联系：我们在vc+下编写程序，可是数据库的语言是SQL语句，vc+的编译器是无法识别SQL语句的，所以我们要动手实现一个简单的SQL解释器。这就要结合编译原理所学的知识。,3,2 题目与要求,题目：简易数据库管理系统的实现 编写一个简单的数据库管理系统，该系统可以接受一些基本SQL语句，经过词法和语法分析后，解释该SQL语句，并进行相应操作。目的：1）通过自己动手实现数据库管理系统，掌握如何通过LEX或者完全手动编写词法语法分析器。,4,2 题目与要求,两种方法的语义部分基本相同，主要区别在于词法和语法分析器的构造是手工完成还是借助于工具完成。,词法分析器语法分析器语义子程序,C/C+编译器,SQL解释器,(c)工具生成,词法分析器(*.l文件)语法分析器(*.y文件),LEX编译器,YACC编译器,C/C+编译器,语义子程序,(b)手工编写,SQL语句,SQL解释器,SQL语句执行结果,(a)解释器工作原理,SQL解释器,5,2 题目与要求,SQL解释器支持如下语句及功能：1.CREATE DATABASE 创建数据库2.USE DATABASE 选择数据库3.CREATE TABLE创建表4.SELECT FROM WHERE 查询5.INSERT INTO VALUES 插入元组6.DELETE删除元组7.DROP TABLE 删除表8.SHOW TABLES 显示所有表的名称9.QUIT 退出数据库 10.支持的数据类型：INT CHAR(N)11.选作项目：主码、外码、索引、安全性、事务、日志等等,6,3 参考解决方案,上边这个数据库包括哪些信息？表名，列数，列长度，每一列的列名，每一列的列类型，每行的数据长度，每行的数据，以及每列在表中的顺序。,学籍管理数据库,学生表,课程表,7,3.1 数据库存储结构设计,数据库表字典表,数据库列字典表,数据库各个表的数据,8,3.1 数据库存储结构设计,综上所述，数据库的信息分为三部分：1.数据库表字典表2.数据库的列字典表3.数据库各个表的数据 我们可以发现表字典表，列字典表和学生表，课程表一样都是表，所以表字典表和列字典表都可以按照表的方式来存储。这会不会造成无限递归？答：不会，因为表字典表、列字典表两者与学生表有一个重要的区别。表字典表，列字典表的结构是固定的。,9,3.1 数据库存储结构设计,数据库存储结构设计参考方案：每个数据库均包含一个.db文件和一个.dat文件。1.以.db为后缀的文件负责存储：Max_tab_id(4B)表字典表的起始块firsttable列字典表的起始块firstcolumn,10,3.1 数据库存储结构设计,2.以.dat为后缀的文件负责存储所有表的具体数据。数据文件由多个数据块组成，每个数据块大小为1024B，即1KB。数据块分为数据块头部和数据区。数据块头部用来存储数据块的说明信息，数据区用来存储表中的数据。每个数据块的结构如下：,注：Flag 标志该数据块是否已被占用。,数据区格式：,注：Flag 标志该数据是否有效。,数据块头部 占24B，数据区为1000B。现对数据块头部的结构体变量说明如下：flag:标志该数据库是否被用，flag=1表示数据块已被 用，flag=0表示未被用。next_block:表示 与该数据块连接的下一数据块的位置。next_free_addr:表示该数据块的空闲起始位置。last_block:值为1表示是最后一个数据块，为0表示后面还有数据块。如此，各表的数据分别存储在不同的数据块，同一个表的数据块用指针串接。形成的数据链表如下图所示：,11,12,13,3.1 数据库存储结构设计,综上所述，建立一个表时有以下2步：1.将表对应的表字典表的数据插入.dat文件中，也就是向表字典表中添加一条记录。例如：,2.将表对应的列字典表的数据插入.dat文件中，即向列字典表中添加表的各列对应的记录。例如：,14,3.1 数据库存储结构设计,执行CREATE TABLE操作时的具体步骤：1.打开.db文件，取出表字典表和列字典表的起始位置；2.打开.dat文件，遍历表字典表，查看该表是否已经存在，若存在退出，并通知用户；若不存在执行下一步；3.读取.db文件中的Max_tab_id，并填充表字典结构数据tab_dic_type，将其插入到表字典表中；修改.db文件中的Max_tab_id，将其加1。4.填充列字典表结构数据col_dic_type，并将其插入到列字典表中。5.关闭.db文件；关闭.dat文件。,15,3.1 数据库存储结构设计,注意：将一个元组插入到一个表中，其实就是Insert语句要实现的过程，大致如下：1.查找该表的最后一个数据块，看是否有空间存储数据，若有执行第3步，否则执行2；2.修改当前最后一个数据块的头部，next_block,last_block，将next_block指向下一个空闲块，填写下一个空闲块头部；3.在头部next_free_addr所指的位置填写数据，同时修改next_free_addr。,16,3.1 数据库存储结构设计,补充1：数据库管理系统中除了用户自定义数据库外，还有系统数据库。系统数据库主要包括系统表，用户表，权限表等部分，负责对所有数据库进行管理。例如下边是一个非常简单的系统数据库，只有系统表一张表。系统表包括信息：,如何存储系统数据库？系统数据库也是一个数据库，其存储方式可以完全按照用户自定义数据库的存储方式来存储。,17,3.1 数据库存储结构设计,补充2：.db文件结构很简单，也可以将其放到.dat文件头，但是为了以后的扩展，我觉得还是单独存放比较好。例如以后添加索引，视图，列级约束等功能时，单独存放比较好扩展。,SQL解释器部分：词法分析 语法分析,18,19,3.2 词法分析器,1.词法分析器的三个任务：滤掉源程序中的无用成分；输出记号供语法分析器使用；识别非法输入，标记为出错记号。2.记号的组成：记号的类别和属性。3.记号的数据结构：struct Token/记号的数据结构Token_Type type;/类别 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 IDENTIFIERfieldsdefinition field_type|fieldsdefinition,field_typefield_type field typefield 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,tabletable_fieldstable_field|table_fields,table_fieldtable_fieldfield|table.fieldtable IDENTIFIERfield 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_conditionsstruct _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,