编译原理实习报告—C-Minus语言的编译实验解读.docx

编译原理上机实习报告 实验一题目编号A003：C-Minus语言的编译实验实验目的要求用C或C++语言描述及上机调试，实现一个 C-Minus 小编译程序（包括词法分析，语法分析等重要子程序），使学生将理论与实际应用结合起来，受到软件设计等开发过程的全面训练，从而提高学生软件开发的能力。要求：（1）设计词法分析器设计各单词的状态转换图，并为不同的单词设计种别码。将词法分析器设计成供语法分析器调用的子程序。功能包括：a. 具备预处理功能。将不翻译的注释等符号先滤掉，只保留要翻译的符号串，即要求设计一个供词法分析调用的预处理子程序；b. 能够拼出语言中的各个单词；c. 返回（种别码， 属性值）。（2）C－惯用的词法1、语言的关键字：else if int return void while2、专用符号：+ - * / = = == != = ; , ( ) [ ] { } /* */3、其他标记是ID和NUM，通过下列正则表达式定义：ID = letter letter*NUM = digit digit*letter = a|..|z|A|..|Zdigit = 0|..|94、空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开ID、NUM关键字。5. 注释用通常的C语言符号/ * . . . * /围起来。注释可以放在任何空白出现的位置(即注释不能放在标记内)上，且可以超过一行。注释不能嵌套。我们小组具体分工如下： 191142第三组?组长：马烨斌 正则表达式转NFA：张念?高坤 NFA转DFA：彭玉?阿米尔江·阿不来提 DFA最小化：张雅娴?袁野 DFA模拟、架构界面：马烨斌 需求分析：输入一个正则表达式，进行词法分析，识别输入符号串，根据相关规则构造NFA。：在NFA的基础上，使用子集法构造DFA。：使用状态划分法，将DFA最小化。：搭建一个可视化界面，将整个过程进行可视化输出。设计 2.1总体设计 2.11设计思想：根据实验需求，需要写出至少四个模块，综上所述：为了可视化的实现和方便总体框架连贯性要求，我们采用JAVA语言编写应用程序，搭建可视化平台2.12数据结构由于输入串长度和NFA、DFA中状态数的不确定性，所以就用向量来存储，同时，由于不实现了解转换进行的维数个具体过程，所以得用多维向量保证存储的正确性。1. 对正则表达式的处理：private String strProduction;//正则表达式首先存入一个String类型的变量privateVector[] vecGrammar; //对输入字符串处理，去除无用信息后存入初始化向量中，作为构造NFA的基础* vecGrammar vector来定义四元组的文法* vecGrammar[0]非终极符号* vecGrammar[1]表示终极符号* vecGrammar[2]表示产生式* vecGrammar[3]表示开始符号2.生成NFA的储存结构privateVector[] vecNFA; //NFA储存向量privateVector[][] vecStateConvertTable;//状态转换表存储向量矩阵 * 文法 G=(V,T,P,S)* 生成状态集合,终态使用Z* NFAM=(k,∑,f,p,Z) k状态集合,∑字母表，f转换函数，p开始状态，Z终结状态集3.NFA转DFA存储结构privateVector[] vecDFA,vecOldDFA; //DFA存储向量Private Vector[][] vecDFAStateConvertTable;//NFA状态转化表向量Private Vector[][]vecOldDFAStateConvertTable;//old 保存转换前的DFA* create DFA 对产生的NFA处理，生成DFA* NFA N=(k,∑,f,p,Z) k状态集合,∑字母表，f转换函数，p开始状态，Z终结状态集* DFA M=(S,∑,D,B,E) * S为vector类型的集合状态的集合，它是K的子集构成的集合，字母表保持不变，* D按照下面算法构造的二维集合数组,Z为S的子集　任意R属于E　R∩Z!=Ф4.DFA最小化存储结构privateVector[] vecMinDFA; //最小化DFA存储向量privateVector[][] vecMinDFAStateConvertTable;//最小化DFA状态转换表2.13 文件结构总共16个JAVA源文件2.2自己负责的模块设计——正则表达式转NFA过程或函数调用关系图（流程