1、编译原理实验报告一 项目目的1. 巩固大三上学期编译原理理论课程的学习成果，加深对编译原理及程序构造过程的理解。2. 增强程序设计能力。二 项目内容要求本次实验分为两部分，第一部分是词法分析生成器 Lex 的构造，第二部分是语法分析生成器 Yacc 的构造。另外，根据自己开发的工具，生成 C 语言子集的词法分析器和语法分析器。具体内容要求如下：1. Lex（1）Lex 输入文件的解析 （2）正规表达式的解析（3）一个正规表达式到 NFA 的转换算法实现（4）多个 NFA 的合并（5）NFA 的确定化和最小化算法实现（6）返回状态与返回内容的对应2.Yacc（1）Yacc 输入文件的解析（2）上
2、下文无关文法到对应 LR(1)文法的下推自动机的构造（3）LR(1)文法的下推自动机到相应分析表的构造（4）LR(1)总控程序的构造（查表程序）（5）LR(1)到 LALR(1)的映射（*）（6）符号表的构建与相应管理程序（7）语义动作程序的加入其中(*)表示是我们未能完成的功能。三 项目中主要数据结构定义本次实验中我们使用了大多数 STL 中的数据结构，具体情况如下：stack,queue,hash_set,hash_map,set,map,vector,list1.LexLex 中主要数据结构就是关于 NFA 和 DFA 图的构造。实验中我们采用自定义结点类Node 来形成图的结点。Nod
3、e 中有两个数据域，一个是边的权值，另一个边所连向的点，而采用有向图来表示 NFA 和 DFA。具体如下：vector nfa,dfa;2.YaccYacc 中的主要数据结构比较多。I.对于读进的符号串，用两张表，一张是终结符符号表，另一张是非终结符符号表，索引值为字符串，内容为对应的符号在程序中的内码值，为 int 型。这种表采用hash_map类型实现。II.对于产生式，采用自定义结构 Producer 定义。具体如下：struct Producer int left; vector right;并在程序中用一个全局数据 vector ProducerSet 来存储所有产生式，而在其它需要
4、使用到产生式的地方全部保存索引值即可，大大缩短所耗内存空间。III.对于项目集构造算法中的项目，采用自定义类实现。具体如下：class Itempublic:friend bool operator const hash_set void move();private:int pn;/存储产生式的编号。int pos;/存储此项目的移进位置。hash_set searchSym;/存储此项目的搜索符，作为公共可以让外部函数 first直接使用;四 主要思路及算法描述1.Lex 部分这部分的主要算法就是按照编译原理书上所给的思路进行正规式到 NFA 的构造，然后是NFA 到 DFA 的转换，DF
5、A 的最小化，最后是 DFA 整合其余部分到词法分析器代码的输出。具体开发思路如下：正规式到 NFA：此部分我们采用的算法是直接从文件中读取字符(当然会有一个控制字符标记开始读取生成)。然后依据读取的字符进行相应的 NFA 的构造。多个 NFA 的合并：此部分的算法是将新生成的 NFA 以一个空串边连接到原 NFA 上即可。NFA 到 DFA：这个转换过程的算法就是采用教材上给的子集构造的算法。最小化 DFA：这部分采用的也是教材上给出的最大划分的方法。在 DFA 的调整过程中，考虑如下算法：A.建立一个以结点编号为索引值的 bool 型数组,用以保存该结点是否需要保留。如需保留，则存储为 t
6、rue；否则为 false。B.建立一个以结点 set 为索引，以结点 vector 为内容的映射 map。用此来实现划分算法。C.在划分完毕后，扫描划分后的数据结构。修改保留结点的 bool 数组。D.开始扫找保留结点表，将对应集合中不属于保留结点的点删除，同时修正 DFA 的链接关系。此过程中每一次划分后的调整算法复杂度为 O(n)。最小化 DFA 到输出文件的生成：通过之前写好的词法分析器的模板代码，再依据最小化 DFA 的图状结构，产生词法分析器的代码。形成一个函数 analysis(char * yytext,int n)，其参数中前者表示符号串，后者表示符号串长。Yacc 部分Ya
7、cc 的主要思想同 Lex 一样，都是采取教材上的算法来实现。Yacc 输入文件的解析过程由于 Yacc 的输入文件格式较为复杂，所以此处采用了状态跳转的方法来进行控制输入。此部分具体所做的工作如下：i.读取定义段，存储语义值类型定义，存储终结符和非终结符语义值类型，算符优先级定义，左右结合性定义。ii.读取规则段，完成产生式集合的生成。如有语义动作，完成语义动作的解析及存储。iii.读取用户自定义段，没什么解析，直接输出到文件。依据第一步生成的各种数据结构，开始内部处理过程。利用 LR(1)分析法，依据产生式集合，进行项目集算法的计算。在计算的过程中，完成语法分析表的构造。完成符号表的构造，
8、并存储好以备输出。利用自己写好的语法分析器的模板程序，以及语法分析表的构造完成，最终生成语法分析器的结果代码。同时，生成符号表文件 signal_table.txt 以及可供词法分析引用的符号串定义头文件 yytab.h。五 项目开发过程中的问题1. 对于文件输入流的分析。一种思路是纯粹依靠条件控制语句进行控制分析，此种方法的缺点是逻辑容易产生混乱，且出错不易检查，健壮性也不强。另一种思路是把它当成一种语法，用语法分析的思想进行处理。这种方法处理起来比较稳妥，易于查错，只是工作量太大。由于时间关系，最终我们采用第一种思路，导致的后果是输入文件一定要符合我们的要求，否则很有可能导致非正常运行。对
9、于 Yacc 中 LALR(1)分析表的构造。由于起初我们的估计不足，并没有真正生成项目集之间的关系表，而只是在生成项目集的过程中就构造出了 LR(1)分析表。故在这种情况下，无法采用教材上所说的第一种思路，即很耗空间的算法，将项目集按同心合并后再输出。而对于算法二，即利用搜索符的推导关系直接导出 LALR(1)分析表的算法，由于我们时间不足，故也来不及完成。所以最终我们只做到了 LR(1)分析表。六 项目总结在本次编译原理 Lex 和 Yacc 项目完成过程中，我们组的成员都对编译原理及程序构造过程有了更深一步的了解。同时，我们也进一步提高了自己编写程序的能力，并且也锻炼了自己与他人合作的能力，为明年或者将来步入社会做了良好的铺垫。
