编译原理课程设计报告SeuLex

1、编译原理课程设计设计报告 组长：廖桉冬 09012431 成员：陈世宇 09012430涂佳辰 09012429东南大学计算机科学与工程学院二0 1 5年5月设计任务名称SeuLex完成时间5.22验收时间本组成员情况学 号姓 名承 担 的 任 务成 绩09012431廖桉冬整体设计、代码实现RE到NFA、NFA到DFA、DFA最小化、状态转换表的设计、cpp文件驱动09012430陈世宇.l解析09012429涂佳辰.cpp文件输出注：本设计报告中各部分如果页数不够，请自行扩页。原则是一定要把报告写详细，能说明本组设计的成果和特色，能够反映小组中每个人的工作。报告中应该叙述设计中的每个模块。

2、设计报告将是评定各人成绩的重要依据之一。1 编译对象与编译功能1.1 编译对象（作为编译对象的C语言子集的词法、语法描述）./SeuLex/Lex_Source_Code.l 是lex的源代码文件，也是Lex解析的目标文件1.2 编译功能（所完成的项目功能及对应的程序单元）1. SeuLex：主控程序入口2. LexFileReader：对lex输入文件的解析，得到正规表达式3. Infix2Postfix：便于状态集计算，中缀转后缀，并将运算符(| * + ? .)特殊化4. NFA：对单一正规表达式，构造NFA5. MergedNFA：多个NFA合并到一起，标记中止状态6. DFA：确定化

3、NFA状态、闭包运算、最小化DFA，比对中止状态确定规约的表达式编号7. CodeGen：将数据代码化写入cpp，添加头部、驱动程序2. 主要特色1. 正规定义段只接受形如A-Z的定义2. 规则段中.表示所有单个字符3. 规则段中*表示闭包运算4. 规则段中+表示一个或一个以上的重复5. 规则段中?表示空或一次6. 规则段中|表示或7. 规则段中连接运算符省略8. 规则段中表示或，如果里面有形如 A-Z 的内容则表示 A|B|。 。 。|Z9. 规则段中表示花括号内为正规定义，需要到正规定义段寻找其含义10. 规则段中”表示引号中的内容是定义的完整字符11. 规则段中()表示优先级12. 规则

4、段中如果想将上述符号当作字符来看待，则需要在该字符前加上转义符13. 生成的 C+程序文件名为 Seu_Lex_Analysis.cpp14. 生成程序中有 seuLex()函数以供调用，其返回值为 int 型15. 用户可以在规则段加入 return 语句3 概要设计与详细设计（由总到分地介绍SeuLex和SeuYACC的设计，包括模块间的关系，具体的算法等。采用面向对象方法的，同时介绍类（或对象）之间的关系。在文字说明的同时，尽可能多采用规范的图示方法。）3.1 概要设计（以描述模块间关系为主）（圆角框粗体为5个主要模块，方框为交互的对象实例。*中缀转后缀集成在FileReader中）3.

5、2 详细设计（以描述数据结构及算法实现为主）LexFileReader：数据结构：RandomAccessFile：随机字节读取，用于跳过部分数据，和读取一行算法：1.根据各部分不同的分隔符“%、%、%”来读取某一部分的数据，头区域、规则定义、子程序；2.根据每行不同数据（表达式、动作）的分隔符“t”，将表达式和数据分别放到不同的数组存放；3.对含有正则表达式的表达式预先记录，如果读取到就按照正则表达式规则扩展。Infix2Postfix：数据结构：Stack：用栈将中缀表达式转化为后缀表达式算法：1. 区分有几种运算符（+、？、*、|、.），分别表示（1或多、0或1、0或多、或、与）；其中（

6、+、？、*）是集合符号，针对单个或是（）中的字符个数进行定义；而（|、.）是对两个字符的并与关系描述；因此只需要将（|、.）后缀即可；2.对连续的多个字符需要添加AND（优先级高）即“.”是后期自动加入: if（i是字符） s+=i ； if（i+1是字符） 弹出栈中操作符 压入.3.对含括号（扩展的），因为括号和AND优先级高： if（i是(） 压入左括号i ； if（i是)） 弹出栈中所有操作符 抛弃( if（i是+、？、*）s+=i； if（i是|）弹出栈中已有的高优先级（左结合） 将|压入栈中；4.为了区分原有的符号，将（+、？、*、|、.）正规表达式运算符设置为128-132，避免冲

7、突。NFA：数据结构:StateTable：NFA状态转换表，行为状态数，列对应0-127的各个字符算法：1. 根据书上的正规表达式转NFA算法，将每一个正规表达式都转换成一个NFA2. 读取->字符：0-c->1，构造出一个有两个状态的NFA。3. 读取->运算符：（+、？、*、|、.），如书上所示，进行NFA（StateTable）的扩展、修改。MergedNFA：数据结构:StateTable算法：把多个NFA连接到一起，第一个NFA状态（0->n），则第二个为（n->n+m），依次修改状态数，并复制原来的table到新的位置。DFA：数据结构:StateT

8、able：MergedNFANFA转换表LinkedList<Set<Integer>> UnmarkedDFAstates：新产生的还未进行闭包运算的状态集HashMap<Set<Integer>, Integer> DFAstates：产生的状态集编号HashMap<Set<Integer>, Set<Integer>> DFAtrsTable：最终的DFA状态转换表算法：1. 针对MergedNFA，求epsilon闭包，也就是可达路径查询。如书。2. 从状态0出发求epsilon闭包，将集合放入DFAs

9、tates，编号为0(I0)；3. 对状态集I0寻找所有可能的跳转路径move(I0,c)，并求epsilon闭包，得到新的集合I： if(I已经存在) 在DFA状态表中改写上对应的(In,c)=m；if(I不存在) 将I加入未标记 和编号组（自动编号）4.对未标记的状态集进行步骤2，直到全部都标记好CodeGen：算法：将所有的规则、转换表写入cpp文件。驱动程序：1. 按照最大匹配串的原则；2. 读取目标文件，用字符指针进行读取；3. 每读取一个，就在规则表（DFA状态表）上找到跳转的状态，如果这个状态可归约（属于StatePatten），则记录下状态matchedState和匹配字符的长

10、度matchedLength4. 如果跳转的状态为终止状态（-1），无法进行下去，则回溯找到最长的匹配长度和相应的状态，并进行表达式对应的动作（cout）。4 使用说明4.1 SeuLex使用说明 一般使用： 将Seu_Lex_Analysis.exe和目标test.c文件（默认文件名为test）放在同一目录下。双击Seu_Lex_Analysis.exe即可看到分析结果。修改规则： 修改Lex_Source_Code.l的规则，然后运行java程序得到新的cpp代码。 重新编译运行cpp，就可以得到新的Seu_Lex_Analysis.exe词法分析器。5 测试用例与结果分析 可以看到最后单

11、独“dd”字符串在C程序编写中并不完整也没有意义，词法分析器只用于分析语句中的词性，对语句的正确与否并无法判断。 所以词法分析器要和语法分析器一起使用，才能检测代码的正确与否。6 课程设计总结（包括设计的总结和需要改进的内容）本次课程设计主要进行Lex的设计，了解了编译器的工作原理以及动态构造编译器的方法。词法分析器对代码中的词句进行分析分类，与模式匹配有所类似。本次试验中，将任意的词句规则转化为正规表达式RE，然后就可以构造出NFA-DFA转换表，应用在编译器中就可以动态的识别这一词句。难点主要在于：将自然语言的词句或者正则表达式转换成RE，需要添加一些计算机可以识别的计算符；将RE-NFA-DFA的转换图、转换表映射到代码算法中，不止有table表格，还需要用到集合Set和栈Stack辅助操作；最小化划分时，因为有多个终止状态对应着不同的表达式，所以对终止状态需要分开。改进：对自然语言的识别使用的是关键字，如“、t等