资源预览内容
第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
第9页 / 共9页
亲,该文档总共9页全部预览完了,如果喜欢就下载吧!
资源描述
编译原理课程设计设计报告 组长:廖桉冬 成员:陈世宇 涂佳辰 东南大学计算机科学与工程学院二0 1 5年5月设计任务名称SeuLex完成时间5.22验收时间本组成员情况学 号姓 名承 担 的 任 务成 绩廖桉冬整体设计、代码实现RE到NFA、NFA到DFA、DFA最小化、状态转换表的设计、cpp文件驱动陈世宇.l解析涂佳辰.cpp文件输出注:本设计报告中各部分如果页数不够,请自行扩页。原则是一定要把报告写详细,能说明本组设计的成果和特色,能够反映小组中每个人的工作。报告中应该叙述设计中的每个模块。设计报告将是评定各人成绩的重要依据之一。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:确定化NFA状态、闭包运算、最小化DFA,比对中止状态确定规约的表达式编号7. CodeGen:将数据代码化写入cpp,添加头部、驱动程序2. 主要特色1. 正规定义段只接受形如A-Z的定义2. 规则段中.表示所有单个字符3. 规则段中*表示闭包运算4. 规则段中+表示一个或一个以上的重复5. 规则段中?表示空或一次6. 规则段中|表示或7. 规则段中连接运算符省略8. 规则段中表示或,如果里面有形如 A-Z 的内容则表示 A|B|。 。 。|Z9. 规则段中表示花括号内为正规定义,需要到正规定义段寻找其含义10. 规则段中”表示引号中的内容是定义的完整字符11. 规则段中()表示优先级12. 规则段中如果想将上述符号当作字符来看待,则需要在该字符前加上转义符13. 生成的 C+程序文件名为 Seu_Lex_Analysis.cpp14. 生成程序中有 seuLex()函数以供调用,其返回值为 int 型15. 用户可以在规则段加入 return 语句3 概要设计与详细设计(由总到分地介绍SeuLex和SeuYACC的设计,包括模块间的关系,具体的算法等。采用面向对象方法的,同时介绍类(或对象)之间的关系。在文字说明的同时,尽可能多采用规范的图示方法。)3.1 概要设计(以描述模块间关系为主)(圆角框粗体为5个主要模块,方框为交互的对象实例。*中缀转后缀集成在FileReader中)3.2 详细设计(以描述数据结构及算法实现为主)LexFileReader:数据结构:RandomAccessFile:随机字节读取,用于跳过部分数据,和读取一行算法:1.根据各部分不同的分隔符“%、%、%”来读取某一部分的数据,头区域、规则定义、子程序;2.根据每行不同数据(表达式、动作)的分隔符“t”,将表达式和数据分别放到不同的数组存放;3.对含有正则表达式的表达式预先记录,如果读取到就按照正则表达式规则扩展。Infix2Postfix:数据结构:Stack:用栈将中缀表达式转化为后缀表达式算法:1. 区分有几种运算符(+、?、*、|、.),分别表示(1或多、0或1、0或多、或、与);其中(+、?、*)是集合符号,针对单个或是()中的字符个数进行定义;而(|、.)是对两个字符的并与关系描述;因此只需要将(|、.)后缀即可;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,避免冲突。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:数据结构:StateTable:MergedNFANFA转换表LinkedListSet UnmarkedDFAstates:新产生的还未进行闭包运算的状态集HashMapSet, Integer DFAstates:产生的状态集编号HashMapSet, Set DFAtrsTable:最终的DFA状态转换表算法:1. 针对MergedNFA,求epsilon闭包,也就是可达路径查询。如书。2. 从状态0出发求epsilon闭包,将集合放入DFAstates,编号为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和匹配字符的长度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 测试用例与结果分析 可以看到最后单独“dd”字符串在C程序编写中并不完整也没有意义,词法分析器只用于分析语句中的词性,对语句的正确与否并无法判断。 所以词法分析器要和语法分析器一起使用,才能检测代码的正确与否。6 课程设计总结(包括设计的总结和需要改进的内容)本次课程设计主要进行Lex的设计,了解了编译器的工作原理以及动态构造编译器的方法。词法分析器对代码中的词句进行分析分类,与模式匹配有所类似。本次试验中,将任意的词句规则转化为正规表达式RE,然后就可以构造出NFA-DFA转换表,应用在编译器中就可以动态的识别这一词句。难点主要在于:将自然语言的词句或者正则表达式转换成RE,需要添加一些计算机可以识别的计算符;将RE-NFA-DFA的转换图、转换表映射到代码算法中,不止有table表格,还需要用到集合Set和栈Stack辅助操作;最小化划分时,因为有多个终止状态对应着不同的表达式,所以对终止状态需要分开。改进:对自然语言的识别使用的是关键字,如“、t等特殊分隔符,当规则复杂时,需要遍历每行的字符,因此可以使用定长的格式规则,使用字节读取。对于状态转换,每一个可能跳转的状态都用SetInteger表示,但实际上只有epsilon会有多个跳转的可能,其他都是单一状态。7 教 师 评 语签名: 附:包含源程序、可运行程序、输入数据文件、输出数据文件、答辩所做PPT文件、本设计报告等一切可放入光盘的内容的光盘。电视墙也就是电视背景装饰墙,是居室装饰特别是大户型居室的重点之一,在装修中占据相当重要的地位,电视墙通常是为了弥补客厅中电视机背景墙面的空旷,同时起到修饰客厅的作用。因为电视墙是家人目光注视最多的地方,长年累月地看也会让人厌烦,所以其装修就尤为讲究
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号