实验一符号表设计与实现

实验一符号表设计与实现院系信息科学与工程学院班级学号.姓名1.实验目的了解符号表的作用、组织和数据结构，设计和实现一个符号表。2.实验要求a)针对四则运算，写出字符集∑、相应的词法单元集合、词法单元对应的正则表达式集合b)合理有效地设计符号表可存储四则运算中的各种词法单元及其属性等信息c)列出关键算法的具体实现的思路3.实验原理及内容（1）符号表的作用符号表用于登记词法单元名字、属性等信息。由于在编译的各个阶段都要对符号表进行频繁操作（查表和填表），在整个编译时间中占了较大比例，因此如何有效合理地组织符号表并选择好的填表和查表方式，对于提高编译器的工作效率有很大影响。（2）符号表的组织每个词法单元在符号表中都有1个条目，一般由两部分组成：名字栏和信息栏。如果一个语言对标识符的最大长度有限制，可设计名字栏的域大小为最大长度来容纳整个标识符；若该语言对标识符最大长度无限制或最大长度较大（如：32），为节省存储空间，可另用一个字符数组存储标识符，在名字栏域中存储其起始地址和长度（字符个数）。运算表达式中的词法单元与具有某种类型属性的数据对象相关联。同一个标识符在不同位置被说明时代表不同的数据对象。当出现对一个标识符的引用时，需根据运算规则查符号表获取正确的符号表条目。（3）符号表的数据结构由于线性表的访问复杂度为O（n），效率较低，符号表常采用效率更高的哈希技术进行实现：当出现标识符id的定义时，计算哈希函数H(id)，获取其在哈希表的存储位置，如该位置为空，则直接存储，否则应用冲突消解方法来获取其存储位置；当出现对标识符id的引用时，计算哈希函数H(id)，获取其在哈希表的存储位置。4.实验软硬件环境C++MicrosoftVisualStudio6.05.符号表的设计与实现的算法思想由于线性表的访问复杂度为O（n），效率较低，符号表常采用效率更高的哈希技术进行实现：当出现标识符id的定义时，计算哈希函数H(id)，获取其在哈希表的存储位置，如该位置为空，则直接存储，否则应用冲突消解方法来获取其存储位置；当出现对标识符id的引用时，计算哈希函数H(id)，获取其在哈希表的存储位置。（1）主程序示意图如图所示：置初值调用switch选择要进行的操作调用不同case中的方法（2）Insert分析程序示意图如图所示：否是（3）Find分析程序示意图如图所示：否是结束调用insert函数是否存在表调用read读入函数将表信息存入哈希表中出错处理输入表名是否存在表调用find函数在哈希表中找到表信息提示不存在结束返回表信息（4）Remove分析程序示意图如图所示：否是（5）Show分析程序示意图如图所示：6.符号表设计与实现主要代码输入表名（key）是否存在表调用remove函数提示删除失败结束显示删除成功调用show结束显示哈希列表中表信息1.代码：boolCHashTable::Insert(CRecord&record)//在哈希表中插入表{listCRecord&OldList=m_Array[MyHash(record.GetKey())];if(find(OldList.begin(),OldList.end(),record)!=OldList.end()){returnfalse;}OldList.push_back(record);m_nCurrentSize++;returntrue;}boolCHashTable::Find(char*key)//通过关键字在哈希表中找到表，显示表信息{listCRecord&OldList=m_Array[MyHash(key)];listCRecord::iteratorit;for(it=OldList.begin();it!=OldList.end();it++){if(strcmp(key,it-GetKey())==0){system(cls);cout查找结果：endl;this-PrintHead();it-Show();returntrue;}}returnfalse;}boolCHashTable::Remove(char*key)//输入关键字，删除哈希列表中的表及信息{listCRecord&OldList=m_Array[MyHash(key)];listCRecord::iteratorit;for(it=OldList.begin();it!=OldList.end();it++){if(strcmp(key,it-GetKey())==0){OldList.erase(it);m_nCurrentSize--;returntrue;}}returnfalse;}voidCHashTable::Show()//打印哈希列表中的表及其表信息{for(inti=0;i101;i++){listCRecord::iteratorit;for(it=m_Array[i].begin();it!=m_Array[i].end();it++){it-Show();}}}2.结果分析插入表信息：查询表信息：删除表：打印表：3.总结通过本次试验，了解了如何有效合理地组织符号表并选择好的填表和查表方式，符号表常采用效率更高的哈希技术进行实现：当出现标识符id的定义时，计算哈希函数H(id)，获取其在哈希表的存储位置，如该位置为空，则直接存储，否则应用冲突消解方法来获取其存储位置；当出现对标识符id的引用时，计算哈希函数H(id)，获取其在哈希表的存储位置。