#编译原理上机评测报告

1 / 13 编译原理上机报告 DBMS 勺设计与实现即 miniSQL 专 业：计算机科学与技术 班 级：030814 2018 年 05 月 08 日 目录 1 项目简况 1 1.1 人员组成及分工 1 1.2 项目完成情况 4 2 项目实现方案一一编译部分 5 2.1 编程环境及工具 5 2.2 词法分析 5 2.3 语法分析 6 3 项目实现方案一一 DBMS 部分 12 3.1 物理结构 12 3.2 主要功能 15 4 报告总结 18 4.1 上机心得 18 1项目简况 1.1 人员组成及分工 项目 miniSQL 实现简单的 SQL 语句功能，数据类型仅支持 INT CHAR 类型。以学会 yacc & lex 的使用，加深对于数据库管理系统的理解。 项目分为词法分析、语法分析、存储结构设计与语义实现四个方面。其 中黄建财负责词法分析， 王志彪负责语法分析， 袁兆祎设计数据库系统的 存储结构以及语法数结构，刘德龙完成数据库的语义实现和报告的撰写 项目总体流程： 6. DELETE 删除元组 9. QUIT 对于删除语句： 6. DELETE 7. DROP TABLE 数据库系统对于表和元组的删除操作和操作系统类似，并为真正删除而 2 / 137. DROP TABLE 删除表 8. SHOW TABLES 显示所有表的名称 删除元组 删除表 4 / 13 是设置删除标记，这就需要前期数据结构设计增加标志域。删除数据时只 需设标志域为 0假设 1 数据有效） 2 项目实现方案 编译部分 2.1 编程环境及工具 Lex & Yacc 工具：parser generator C 编译器：visual c+ 6.0 2.2 词法分析 词法分析不仅要实现识别 miniSQL 的关键字，还需识别相关符号以及标识符 和数字。 符号正规式： = | ! | * | | | , 空白符正规式，即忽略空格 数字： 0-9+ 标识符： A-Za-za-zA-Z0-9_.* 关键字正规式： I! I! I 。 | ( | | HIH | | 5 / 13 create | CREATE DATABASE | database DATABASES | databases use | USE return CREATE。 return DATABASE 。 return DATABASES 。 return USE。 6 / 13 table | TABLE return TABLE 。 tables | TABLES return TABLES 。 select | SELECT return SELECT 。 from | FROM return FROM 。 where | WHERE return WHERE 。 AND | and return AND 。 OR | or return OR。 insert | INSERT return INSERT。 into | INTO return INTO 。 values | VALUES return VALUES 。 update | UPDATE return UPDATE 。 set | SET return SET。 delete | DELETE return DELETE 。 drop | DROP return DROP 。 show | SHOW return SHOW 。 quit | q | QUIT return QUIT 。 help | HELP return HELP 。 INT | int return INT 。 CHAR | char return CHAR 。 2.3 语法分析 语句产生式和语法树结构说明： 语句 create 禾口 use database 较简单，只需记录数据库名 db_name 7 / 13 CREATE DATABASE 创建数据库 sql_create_db : CREATE DATABASE db_name db_name : ID 。 USE DATABASE 选择数据库 sql_use_db : USE db_name。 。 db_name : ID 。 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 。 8 / 13 col_fld : col_type | col_fld , col_type 。 col_type : ID type 。 type : CHAR （ NUMBER | INT 。 SELECT FROM WHERE 查询 selec 语法树结构，存储表名，字段和条件 struct Select / select 根节点 struct Tabs *tabs。 struct Cols *cols。 struct Condition *cons。 。 struct Tabs / select 表结构，存储表名 char* tab_name。 struct Tabs* next_tab。 / 指向下一表名 。 s1 : ID op values 。 条件中的字段和值 op : = | | ! = 。 INSERT INTO VALUES 插入元组 in sert 语法树结构，存储表名，字段，值 struct Insert char* tab_name。 struct Cols* cols。 struct Values* values。 。 struct Values / valueS 吉构和 select 中 的相同 int type。 union char* str。int num。val。 struct Values* next_val。 。 文法： sql_insert : INSERT INTO tab_name ins_cols VALUES ( ins_values 。 。 / 重要的是记录 values ins_cols : | ( columns ins_values : values | ins_values , values 。 11 / 13 DELETE 删除元组 sql_delete : DELETE FROM tab_name WHERE conditions 。 。 条件结构 conditions 和 selec 的相同 DROP TABLE 删除表 sql_drop : DROP TABLE tab_name 。 。 SHOW TABLES 显示当前数据库中表信息， sql_show : SHOW TABLES show_name 。 | SHOW TABLE show_name 。 。 show_ name : / show_ name 为空时列出所有表信息 | ID 。 / 否则列出 表名为 ID 的表信息 QUIT sql_quit : QUIT 。 3 项目实现方案 DBMS 部分 3.1 物理结构 (1 、DBMS 物理结构的特点 数据库系统对于信息的处理主要是表的处理。表结构由字段和元组构成， 当表建立时每一元组的大小即确定了。数据库处理的都是确定大小的信息，为 了便于管理和扩展把一个数据库文件分成若干块，数据库的所有信息 12 / 13 数据库名字、表名、字段名、元组等加入数据结构头后写入相应的文件块中 分配一个文件据区。其中: (24B 第 3 到到第 127 块，存放表元组。 数据区结构 data 数据是在文件块中，最重要的信息。每一个 data 都会附带一个 flag 信 息，标识此 data 是否有效。flag 的值同时还是 data 在数据区的标号。 当 flag0 数据有效 flag=0 没有数据 flag 记录条数 记录存放文件块号 保留空间 char tab_name20。 int tab_id。 int col_cnt。 int row_length。 int row_cnt。 int start_block。 char f8 。 15 / 13 字段结构 struct Block_col int flag。 flag 标识 o 是 use db 否 合e d分配 。 言息写入字 件块 是 性_ (2)、物理结构的优点、缺点分析 此结构对于数据库相关信息的存放(存于第 0 块 ，没有结构性太凌乱。对 于 data 的标识 flag 不是一般的 0、1,而采用 0、正数、负数，这样在 select updata 等有条件查询的语句中会更便利 3.2 主要功能 在此选取了 create selec 和 update 三个语句。 create 功能流程图 int tab_id。 所属表 id int cold。 字段 id char col_ name20。 字段名 int type。 字段类型 int col_size。 字段大小 int col_offset。 字段在 data 中的偏移 char f8。 保留空间 输入表名和字段 select 流 程图 update 流程图输入表名、字段条件“否，没有执行use操作 输入表名、字段条件 是 No，还没选择数据 输出提示信 息并推出 No，还没选择 / 12/43 17 / 13 4 报告总结 4.1 上机心得 1、 miniSQL 项目是团体项目，是集体智慧的结晶，是大家奋战日日夜夜的成 果。任何一个成绩都不是一个人的功劳，即便有了明确的分工，也离不开大家 的讨论研究，以及对设计方案的完善。这次项目很好的体现了 1+12 的效果。同时也是社会化大分工的效率与成效的提升，每个人负责一块，专注 于所擅长的，会导致最终成果的翻番。 2、 题目是编译原理上机 一一DBMS 的设计与实现。而编译原理课程用于 设计编译器，包括词法分析、语法分析、语义分析、中间代码生成、代码优化 和目标代码六个部分。 严格说 DBMS 的设计与实现只是用到了词法分析、 语法 分析、语义实现，仅仅是编译原理的一小部分。 词法语法分析部分并不是太难，DBMS 更多的放在语义上：语法树结构 、物理结构的设计与实现上。这个上机更多的是学会了 lex yac c 的使用，了解了数据库管理的流程。