+*编译原理课程实验报告

实验1：词法分析

姓名 陈鄞老师 软件学院三楼机房 出勤、表现得分 操作结果得分 院系 软件学院 指导教师 实验时间 实验报告 得分 学号 郭勇老师 2016/10/23/星期日 实验总分 得分 任课教师 实验地点 实验课表现 一、需求分析 要求：阐述词法分析系统所要完成的功能 词法分析是编译的第一个阶段，主要任务是读入源程序的输入字符，将它们组成词素，生成并输出一个词法单元序列，每个词法单元对应于一个词素。 在本词法单元中，基本功能要求实现以下几类单词： ? 标识符（由大小写字母、数字以及下划线组成，但必须以字母或者下划线开头） ? 关键字（①类型关键字：整型、浮点型、布尔型、记录型；②分支结构中的if和else；③循环结构中的do和while；④过程声明和调用中的关键字） 本词法分析器可以识别C语言的32个关键字，其中包括：\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\, \,\,\,\。 ? 运算符（①算术运算符；②关系运算符；③逻辑运算） 本词法分析器可以识别的运算符： “ * ” 乘法运算符；“ / ” 除法运算符；“ % ” 取余运算符； “ + ” 加法运算符；“ - ” 减法运算符； << 左移运算符；>> 右移运算符；<、<=、>、>= 关系运算符； “ == ” 等于运算符； “ != ” 不等于运算符； “ & ” 按位与运算符 ；“ ∧ ” 按位异或运算符； “ | ” 按位或运算符； “&&” 逻辑与运算符； “ || ” 逻辑或运算符；” ! “ 非运算符； =、 +=、 -=、 *=、 /=、 %=、 &=、 ^=、 |=、 <<=、 >>= 赋值运算符。 ? 界符（①用于赋值语句的界符，如“=”；②用于句子结尾的界符，如“；”；③用于数组表示的界符，如“[”和“]”；④用于浮点数表示的界符“.”） 本词法分析器可以识别的界符： '{','}','[',']','(',')',',',';','.','=','?',':' ? 常数（无符号整数和浮点数，包括科学计数法，字符串常数等） ? 注释（/*??*/形式） ? 八进制数和十六进制数 ? 字符常数 二、文法设计 得分 要求：对如下内容展开描述 （1） 给出各类单词的词法规则描述（正则文法或正则表达式） （2） 各类单词的转换图 （1） 1）标识符的正则定义： letter_ -> [a-zA-Z_] digit -> [0-9] id -> letter_(letter_|digit)* 说明：关键字的正则定义与标识符是一样的，但是为了区别关键字和标识符，我采取初始化时就将各个关键字保留起来，识别时先进行判断是不是关键字，如果不是关键字再进行判断是不是标识符。 2）运算符的正则定义： operator -> + | - | * | / | += | -= | *= | /= | % | ++ | -- | != | == | > | < | >= | <= | >> | << | ^ | | | & | && | || | ! 3) 界符的正则定义： Boundary -> { | } | [ | ] | ( | ) | , | ; | : | ? | ~ 4)常数的正则定义： digit -> [0-9] digits -> digit digit* number -> digits (.digits)? (E [+-]? digits)? 5)注释的正则定义： NOTE -> /*other*/ Other指代任意字符 6）八进制数和十六进制数的正则定义： OCT -> 0(1|2|3|4|5|6|7)（0|1|2|3|4|5|6|7）* HEX-> 0x(1|?|9|a|?|f) (0|?|9|a|?|f)* （2）1）标识符和关键字的转换图 2）运算符的转换图 说明：因为运算符过多，本出的转换图只给出部分，其他可类似构造。 3）界符的转换图 4）常数的转换图 有问题。 5）注释的转换图 6)八进制的转换图： 十六进制的转换图： 字符常量的转换图： 注：状态1到状态3的letter是a-z的字母 状态2到3的letter’是指可以构成转义字符的字母，比如a,t,b等。 三、系统设计 得分 要求：分为系统概要设计和系统详细设计。 （1） 系统概要设计：给出必要的系统宏观层面设计图，如系统框架图、数据流图、功能模块图等以及相应的文字说明。 1） 先给出系统的总体数据流图： 本词法分析器主要针对C语言的源程序进行识别，可以通过在输入区写入程序，也可以通过文件导入的方式导入程序，经过词法分析器的分析以后输出流为词法单元和DFA转换表。 2） 系统框架： 说明：本词法分析器主要包括三大块，分别是符号表（用于储存符号），控制器（核心部分，用于识别各个单词），用户界面（view模块，用于图形化操作），三个大模块下面含各个小模块，图里有详细内容，就不赘述。 （2）系统详细设计：对如下工作进行展开描述 ? 核心数据结构的设计 主要的数据结构有两种，一种是为了识别FA转换表而设计的Tuple类； 1）Tuple类的主要功能：导入FA转换表时，以三元组的形式记录FA转换表的各个过程，所以Tuple类负责储存FA转换表。 Tuple类可以存储三元组Tuple，其中T1表示某状态，T2表示输入的文法符号,T3是T1遇到T2后的状态。 2）第二种数据结构是数组； 数组的功能：充当符号表，为了能够识别关键字，运算符，界符等单词，必须按照其类型将其存储，而这里实现单词存储功能的就是数组，包括char数组和string数组。 ? 主要功能函数说明 本词法分析器核心功能涉及到三个类。 1） IDcontent类 功能：充当符号表的角色，主要是用来保存关键字，运算符，界符，转义字符等各类单词。 主要函数：bool isConstCh(string str)//判断是否转义字符 bool isLetter_(char c)//判断是否字母或下划线 bool isDigit(char c)//判断是否数字 bool isBlank(char c)// 判断是否是空格、制表符、换行、回车 bool isKeyWord(string str)//判断是否关键字 bool isBoundary(char c)// 判断是否是边界符号 bool isOperator(string ch)//判断是否运算符 2） Identifier类 功能：识别单词的核心类 主要函数：string isID(string str, ref int i)//是否是标识符 string isSixteen(string str, ref int i,out bool right)//是否16进制数 string isEight(string str,ref int i,out bool right)//是否8进制数 string isNumber(string str, ref int i, out bool right)//是否是常数 string isOperator(string str, ref int i, out bool right)//是否是运算符 string isNote(string str, ref int i, out bool right)//是否注释 string isBoundary(string str, ref int i,out bool right)//是否界符 string isChar(string str, ref int i, out bool right)//是否字符常数 3） Form1类 功能：负责界面输入和输出，以及判断逻辑的应用 主要函数：void analysis(string str)//负责词法分析逻辑 void addDFAItem(string column1, string column2)//输出DFA转换表 void 帮助ToolStripMenuItem_Click(object sender, EventArgs e)//导入FA转换表 void 操作ToolStripMenuItem_Click_1(object sender, EventArgs e)//导入测试文件 ? 程序核心部分的程序流程图 源程序读入下一个字符是空白或者回车换行符等是是回车换行统计行数否是否是字符或者下划线是读入连续的字母数字或下划线是是否标识符是否是关键字否是是否是数字是否以0开头是是是否8进制数否是否16进制数是否否否是否常数是否界符是否是是否单引号是否字符常量是否是是否 / 是否注释否是是否运算符是输出词法单元和DFA转换表否输出错误信息 说明：进入不同DFA转换表必须使输入的字符满足相应的终结符，所以程序核心部分先进行输入字符的判断，然后再进入相应的DFA转换表进行判断。 注意：为了不使图太复杂和混乱，这里没画出当不满足相应DFA转换表时的输出结果，比如在是否常数判断是，答案是否（即不满足相应的DFA转换表），则输出错误信息，其他判断也是同样的处理方式，不满足相应的DFA转换表时，则输出相应的错误信息。 四、系统实现及结果分析 得分 要求：对如下内容展开描述。 （1） 系统实现过程中遇到的问题； （2） 针对某测试程序输出其词法分析结果； （3） 输出针对此测试程序对应的词法错误报告； （4） 对实验结果进行分析。 注：其中的测试样例自行产生。 （1） 系统实现过程中遇到的主要问题 1） 如何导入FA转换表进行基于DFA的词法分析器设计 问题描述：如何设计转换表的格式，使其能够被程序识别，识别以后如何基于FA转换表，设计词法分析器？ 解决：为了能够识别FA转换表，转换表的格式设计为三元组的形式，即待输入状态->终结符->输出状态，这样子便能将整个FA转换表识别。同时设计了Tuple的数据结构用来保存FA转换表，Tuple是一个三元组的数据结构，T1表示待输入状态，T2表示输入的字符，T3表示输出状态。 为了基与DFA转换表设计词法分析器，我采用查表的方式实现，根据起始状态和输入字符查询三元组，得到输出状态，再以输出状态作为下一次的输入状态，再加上输入的字符去查DFA转换表，以此来实现基于DFA的词法分析器。 2） 如何根据输入的程序，识别各类单词 问题描述：当读入源程序后，如何分割各个字符，使其进入正确的DFA转换表进行识别，然后分别进行识别输出？ 解决：为了能够识别各类单词，使其进入正确的DFA转换表进行识别，我采用逐个字符读入的方式，根据读入的起始字符进入相应的DFA转换表，如果未达到DFA转换表的终止状态，则报错，显示输入的错误单词和相应的行号，如果成功达到终止状态则退出转换表并显示识别的单词和Token序列 3） 单词识别时，如何用程序表示DFA转换表 问题描述：因为要基于DFA设计词法分析器，DAF转换表中主要对应的各个状态应该如何表示？ 解决：采用switch的结构，其中使用switch的各个case对应于DFA转换表的各个状态，然后状态的改变，通过case的改变来实现。 （2） 正确的测试用例 输出结果： （3） 错误的测试用例 输出结果： 正确部分： 错误显示区： （4） 实验结果分析： 本词法分析器读入源程序后，对于各类正确单词能够成功地进行识别，并进行输出Token序列、单词类别、相应的DFA转换表。 对于错误的输入，本词法分析器能够进行成功的识别，并在错误显示区进行输出，同时输出对应的行号，便与使用者清楚地知道错误的位置和原因。 指导教师评语： 日期：