编译原理课程设计报告SeuLex

编译原理课程设计设计报告组长：廖桉冬09012431成员：陈世宇09012430涂佳辰09012429东南大学计算机科学与工程学院二015年5月设计任务名称SeuLex完成时间5.22验收时间本组成员情况学号姓名承担的任务成绩09012431廖桉冬整体设计、代码实现{RE到NFA、NFA到DFA、DFA最小化、状态转换表的设计、cpp文件驱动}09012430陈世宇.l解析09012429涂佳辰.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转换表LinkedListSetIntegerUnmarkedDFAstates：新产生的还未进行闭包运算的状态集HashMapSetInteger,IntegerDFAstates：产生的状态集编号HashMapSetInteger,SetInteger[]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.1SeuLex使用说明一般使用：将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等特殊分隔符，当规则复杂时，需要遍历每行的字符，因此可以使用定长的格式规则，使用字节读取。对于状态转换，每一个可能跳转的状态都用Set[Integer]表示，但实际上只有epsilon会有多个跳转的可能，其他都是单一状态。7教师评语签名：附：包含源程序、可运行程序、输入数据文件、输出数据文件、答辩所做PPT文件、本设计报告等一切可放入光盘的内容的光盘。