编译原理专业课程设计方案报告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：对单一正规表达式，构造NFA
5. MergedNFA：各种NFA合并到一起，标记中断状态
6. DFA：拟定化NFA状态、闭包运算、最小化DFA，比对中断状态拟定规约表达式编号
7. CodeGen：将数据代码化写入cpp，添加头部、驱动程序
2. 重要特色
1. 正规定义段只接受形如[A-Z]定义
2. 规则段中.表达所有单个字符
3. 规则段中*表达闭包运算
4. 规则段中+表达一种或一种以上重复
5. 规则段中?表达空或一次
6. 规则段中|表达或
7. 规则段中连接运算符省略
8. 规则段中[]表达或，如果里面有形如 A-Z 内容则表达 A|B|。 。 。|Z
9. 规则段中{}表达花括号内为正规定义，需要到正规定义段寻找其含义
10. 规则段中””表达引号中内容是定义完整字符
11. 规则段中()表达优先级
12. 规则段中如果想将上述符号当作字符来看待，则需要在该字符前加上转义符\
13. 生成 C++程序文献名为 Seu_Lex_Analysis.cpp
14. 生成程序中有 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算法，将每一种正规表达式都转换成一种NFA
2. 读取->字符：0-c->1，构造出一种有两个状态NFA。
3. 读取->运算符：（+、？、*、|、.），如书上所示，进行NFA（StateTable）扩展、修改。

MergedNFA：
数据构造:
StateTable
算法：
把各种NFA连接到一起，第一种NFA状态（0->n），则第二个为（n->n+m），依次修改状态数，并复制本来table到新位置。

DFA：
数据构造:
StateTable：MergedNFANFA转换表
LinkedList<Set<Integer>> UnmarkedDFAstates：新产生尚未进行闭包运算状态集
HashMap<Set<Integer>，Integer> DFAstates：产生状态集编号
HashMap<Set<Integer>，Set<Integer>[]> 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和匹配字符长度matchedLength
4. 如果跳转状态为终结状态（-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等特殊分隔符，当规则复杂时，需要遍历每行字符，因而可以使用定长格式规则，使用字节读取。
对于状态转换，每一种也许跳转状态都用Set[Integer]表达，但事实上只有epsilon会有各种跳转也许，其她都是单一状态。
7 教 师 评 语

签名：

附：包括源程序、可运营程序、输入数据文献、输出数据文献、答辩所做PPT文献、本设计报告等一切可放入光盘内容光盘。