编译原理课程设计报告SeuLex

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

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

3、A比对中止状态确定规约的表达式编号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 语句LexFihReader3概要设计与详细设计基衣狀态盘、壮态虫总昱tn(Merg 歸UFA )DFAr-a'ysis. cpp（由总到分地介绍SeuLex和SeuYACC勺设计，包括模块间的关系，具体的算法 等。采用面向对象方法的，同时介绍类（或对象）之间的关系。在文字说明的同 时，尽可能多采用规的图示方法。）3.1概要设计（以描述模块间关系为主）mglci值包运算Spufl AYnf中 U（圆角

5、框粗体为5个主要模块，方框为交互的对象实例。*中缀转后缀集成在FileReader 中）3.2详细设计（以描述数据结构及算法实现为主）LexFileReader :数据结构：RandomAccessFile :随机字节读取，用于跳过部分数据，和读取一行算法：1. 根据各部分不同的分隔符 “、%、%来读取某一部分的数据，头区域、规则定义、子 程序；2. 根据每行不同数据（表达式、动作）的分隔符“ t ”，将表达式和数据分别放到不同的数组存放；3. 对含有正则表达式的表达式预先记录，如果读取到就按照正则表达式规则扩展。In fix2Postfix数据结构：Stack :用栈将中缀表达式转化为后缀表

6、达式算法：1. 区分有几种运算符 （+、？、*、|、.），分别表示（1或多、0或1、0或多、或、与）；其中（+、？、*）是集合符号，针对单个或是（）中的字符个数进行定义；而 |（I、）是对两 个字符的并与关系描述；因此只需要将（|、.）后缀即可；2. 对连续的多个字符需要添加 AND （优先级高）即|“. ”是后期自动加入：if （ i 是字符）s+=i ；if （ i+1是字符）弹出栈中操作符 压入.'3. 对含括号（扩展的），因为括号和AND优先级高：if （i是（'）压入左括号i ；if （i是）弹出栈中所有操作符抛弃（if （ i 是'+、？、*'） s

7、+=i ；if （i是| ）弹出栈中已有的高优先级（左结合）将|压入栈中；4. 为了区分原有的符号，将（+、？、*、|、.）正规表达式运算符设置为128-132，避免冲突。NFA数据结构：StateTable : NFA状态转换表，行为状态数，列对应0-127的各个字符算法：1. 根据书上的正规表达式转NFA算法，将每一个正规表达式都转换成一个NFA2. 读取-> 字符：0-c->1，构造出一个有两个状态的NFA3. 读取-> 运算符：（+、？、*、|、.），如书上所示，进行 NFA（ StateTable ）的扩展、修改。MergedNFA数据结构：StateTable算法

8、：把多个NFA连接到一起，第一个NFA状态（0->n ），则第二个为（n->n+m）,依次修改状态数， 并复制原来的table到新的位置。DFA数据结构：StateTable : MergedNFANFA专换表Lin kedList<Set<l nteger>> Unm arkedDFAstates:新产生的还未进行闭包运算的状态集HashMap<Set<l nteger>, I nteger> DFAstates:产生的状态集编号HashMap<Set<lnteger>, Set<Integer>>

9、; DFAtrsTable:最终的 DFA状态转换表算法：1. 针对MergedNFA求epsilon 闭包，也就是可达路径查询。如书。2. 从状态0出发求epsilon 闭包，将集合放入 DFAstates，编号为0（10）;3. 对状态集I0寻找所有可能的跳转路径move（l0,c）,并求epsilon闭包，得到新的集合I :if（I 已经存在）在DFA状态表中改写上对应的（In,c）=m ;if（I不存在）将I加入未标记 和编号组（自动编号）4. 对未标记的状态集进行步骤2,直到全部都标记好CodeGen算法：将所有的规则、转换表写入cpp文件。驱动程序：1. 按照最大匹配串的原则；2.

10、 读取目标文件，用字符指针进行读取；3. 每读取一个，就在规则表（DFA状态表）上找到跳转的状态，如果这个状态可归约（属于 StatePatten ）,则记录下状态 matchedState和匹配字符的长度 matchedLength4. 如果跳转的状态为终止状态（-1 ）,无法进行下去，则回溯找到最长的匹配长度和相应的 状态，并进行表达式对应的动作（ cout ）。4使用说明4.1 SeuLex使用说明直£ e uLexAn a ly5 i s2015/5/22 15：5G1S2 KEQ test2015/5/23 15;46C Source1 KB一般使用：将Seu_Lex_An

11、alysis.exe 和目标test.c 文件（默认文件名为test ）放在同 一目录下。双击Seu_Lex_Analysis.exe即可看到分析结果。0 Lex_5ou rce_Cod e2015/5/； 3 15：SS I.交眸4 ICE*+ Seu.Lex.Analysis2915/5/23 15:55 O十 Sour«47 ICE修改规则：修改Lex_Source_Code.l的规则，然后运行java程序得到新的cpp代码。 重新编译运行cpp,就可以得到新的Seu_Lex_Analysis.exe词法分析器。5测试用例与结果分析 : -: - 二 - » S 二a

12、 ifelsepeturn3iIQI12 2Type： Type : Type： Typo : type； 1 YPe : Tppe : Type : Tpe： Tvpe： T vpe : Type : Type： Type： Type： Type： Tpo： Type - Type :; t： Type : Tvpe -I den t If ie rFlow Contrciller SevaratinQf Character I don 11£ zcpRelallon DjjeraCui' NuntberLogical Operator I ntrernal Con咅七玄n

13、it Sepa.z'aLimij Cliaj'Aiictcr" identic ierAssign Operator Numbe i'Scpcurat; iny Chaiac-1cr" Flow Controller Ident if ierAssign Operatov Murnhe i*SejparaLCJiaA'dcter Flow Contro丄Iei*Nil ruberSeparat in田 Ch-ai*actei* SjEpafating* Character'23：Lexing awdid CaiTipLeteTypeI

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