编译原理专业课程设计方案报告SeuLex.doc

编译原理课程设计设计报告 组长：廖桉冬 09012431 成员：陈世宇 09012430涂佳辰 09012429东南大学计算机科学与工程学院二0 1 5年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转换表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文献、本设计报告等一切可放入光盘内容光盘。