编译原理上机报告.doc

编译原理上机报告DBMS的设计与实现即miniSQL专 业： 计算机科学与技术 班 级： 030814 2011年 05月 08日目 录1 项目概况31.1 人员组成及分工31.2 项目完成情况42 项目实现方案编译部分52.1 编程环境及工具52.2 词法分析52.3 语法分析63 项目实现方案DBMS部分123.1 物理结构123.2 主要功能154 报告总结184.1 上机心得181 项目概况1.1 人员组成及分工项目miniSQL实现简单的SQL语句功能，数据类型仅支持INT CHAR类型。以学会yacc & lex的使用，加深对于数据库管理系统的理解。项目分为词法分析、语法分析、存储结构设计与语义实现四个方面。其中黄建财负责词法分析，王志彪负责语法分析，袁兆祎设计数据库系统的存储结构以及语法数结构，刘德龙完成数据库的语义实现和报告的撰写。项目总体流程：词法分析输出词法单元语法分析语法树存储信息语法树结构到物理结构的转换利用结构信息处理执行语句语义分析阶段1.2 项目完成情况语法分析阶段实现识别上机要求的全部SQL语句。miniSQL实现语句有：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 对于删除语句：6. DELETE删除元组7. DROP TABLE 删除表数据库系统对于表和元组的删除操作和操作系统类似，并为真正删除而是设置删除标记，这就需要前期数据结构设计增加标志域。删除数据时只需设标志域为0（假设1数据有效）。2 项目实现方案编译部分2.1 编程环境及工具Lex & Yacc工具：parser generatorC编译器：visual c+ 6.02.2 词法分析词法分析不仅要实现识别miniSQL的关键字，还需识别相关符号以及标识符和数字。符号正规式：; | ( | ) | | | = | ! | * | | | , 空白符正规式，即忽略空格数字：0-9+标识符： A-Za-za-zA-Z0-9_.*关键字正规式：create | CREATEreturn CREATE;DATABASE | databasereturn DATABASE;DATABASES | databasesreturn DATABASES;use | USEreturn USE;table | TABLEreturn TABLE;tables | TABLESreturn TABLES;select | SELECTreturn SELECT;from | FROMreturn FROM;where | WHEREreturn WHERE;AND| andreturn AND;OR | orreturn OR;insert | INSERTreturn INSERT;into | INTOreturn INTO;values | VALUESreturn VALUES;update | UPDATEreturn UPDATE;set | SETreturn SET;delete | DELETEreturn DELETE;drop | DROPreturn DROP;show | SHOWreturn SHOW;quit | q | QUITreturn QUIT;help| HELPreturn HELP;INT| intreturn INT;CHAR | charreturn CHAR;2.3 语法分析语句产生式和语法树结构说明： 语句create 和 use database较简单，只需记录数据库名db_name；1 CREATE DATABASE 创建数据库sql_create_db : CREATE DATABASE db_name;db_name : ID ;2 USE DATABASE 选择数据库sql_use_db : USE db_name ; ;db_name : ID ;3 CREATE TABLE创建表create table语法树结构，存储 字段名和表名struct Table /create 根节点char *tab_name;struct Column* root_col;struct Column / 表中字段定义char *col_name;int type;int length;struct Column *next_col;struct Tabs /表名char* tab_name;struct Tabs* next_tab;文法：sql_create_tab : CREATE TABLE tab_name ( col_fld ) ;tab_name : ID;col_fld : col_type| col_fld , col_type;col_type : ID type;type : CHAR ( NUMBER ) | INT;4 SELECT FROM WHERE 查询select语法树结构，存储 表名，字段和条件struct Select / select 根节点struct Tabs *tabs; struct Cols *cols;struct Condition *cons;struct Tabs / select 表结构，存储表名char* tab_name;struct Tabs* next_tab; / 指向下一表名（用于多表查询）;struct Cols / 列结构，char* col_name;struct Cols* next_col;struct Condition / select 条件结构char* col_name; / 字段char op; / 操作符struct Values* values; / 值struct Condition* next_ORcon; / 指向下一条件struct Condition* next_ANDcon;struct Values / values结构存储 值（int 或char类型）int type;unionchar* str; int num;val;struct Values* next_val;文法：sql_select : SELECT select_fld FROM tables ; /No where选择所有元组 | SELECT select_fld FROM tables WHERE conditions ; ;tables : tab_name | tables , tab_name;select_fld : columns | *; /符号 * 选择所有字段columns : col_name | columns , col_name;col_name : ID;conditions : condition | conditions OR condition / 目前只能实现两个条件查询 | conditions AND condition;condition: s1 | ( condition );s1 : ID op values; 条件中的字段和值op : = | | ! = ;5 INSERT INTO VALUES 插入元组insert语法树结构，存储表名，字段，值struct Insert char* tab_name;struct Cols* cols;struct Values* values;struct Values / values结构和select中的相同int type;unionchar* str; int num;val;struct Values* next_val;文法：sql_insert : INSERT INTO tab_name ins_cols VALUES ( ins_values ) ; ; / 重要的是记录 valuesins_cols :| ( columns );ins_values : values | ins_values , values ;6 DELETE删除元组sql_delete : DELETE FROM tab_name WHERE conditions ; ;条件结构conditions和select的相同7 DROP TABLE 删除表sql_drop : DROP TABLE tab_name ; ;8 SHOW TABLES 显示当前数据库中表信息，sql_show : SHOW TABLES show_name ; | SHOW TABLE show_name ; ;show_name : / show_name为空时列出所有表信息| ID; / 否则列出 表名为ID的表信息9 QUITsql_quit : QUIT ; 3 项目实现方案DBMS部分3.1 物理结构(1)、DBMS物理结构的特点数据库系统对于信息的处理主要是表的处理。表结构由字段和元组构成，当表建立时每一元组的大小即确定了。数据库处理的都是确定大小的信息，为了便于管理和扩展把一个数据库文件分成若干块，数据库的所有信息数据库名字、表名、字段名、元组等加入数据结构头后写入相应的文件块中。下面是数据库结构的图形说明：0 1 2 3 127 128( 1024B )head 数据区( 24B )flag data flag data 1 块使用分配为简便起见，假设数据库文件128K。每文件块大小为1024B,每个表至少分配一个文件块。其中：第0块，用一个数组管理128块的使用情况，0表示为使用，1已使用。在地址128，132,136处分别存放freeid,表个数，第1块，第2块，分别存放表信息和字段信息。第3到到第127块，存放表元组。2 数据区结构data数据是在文件块中，最重要的信息。每一个data都会附带一个flag信息，标识此data是否有效。flag的值同时还是data在数据区的标号。当flag0 数据有效 flag=0 没有数据 flag2 的效果。同时也是社会化大分工的效率与成效的提升，每个人