基于C++设计实现词语法分析器(编译原理实验)【100012204】

# 一、词法分析 ## 1 **实验目的：** 通过该实验，让同学们自己独立自主的设计词法分析器，使得同学们可以更好的掌握词法分析程序设计的原理及相应的程序设计方法，对编译这门课程也可以有更加深刻理解，同时还可以锻炼编程能力。 ## 2 **实验内容：** 实现求n！的极小语言的词法分析程序，返回二元式作为输出。 ## 3 **实验器材：** 操作系统：Windows 10 IDE： VS 2017 ## 4 **实验步骤：** 1. 在VS 2017中创建工程； 1. 编写文件输入输出； 1. 建立相应的单词符号与种别表，根据状态转换图编写函数； 1. 运行程序生成二元式文件； 1. 更改测试程序文件，编写出错处理函数； ## 5 **实验原理：** 状态转换图，是一张有限方向图，是设计与实现词法分析器的一大利器。在状态转换图中，结点代表状态，用圆圈表示。状态之间用有向弧线连接。弧线上的标记（字符）代表在射出状态下可能出现的输入字符或者字符类。状态转换图具有一个初态和若干终态，代表了转换图的一个启动条件和若干结束条件。通过状态转换图中各状态的转换可以识别出一定的字符串。通过种别表中定义的各种别可输出后续语法分析时需要的二元式。此次实验的词法分析的状态转换图如下：   图1. 状态转换图 单词符号是程序设计的最基本符号，为便于语法分析，通常将分为标识符、基本字、常数、运算符、界符五类。对于一种语言而言，基本字、运算符以及界符的数目都是确认的，而标识符与常数均由用户定义。种别表中定义了语言中各种单词符号的类别与编码。通过查表即可获得扫描而来的单词符号的类别与相应编码输出到二元式中。  图2. 种别表 二元式是词法分析器输出文件格式，其格式一般为: (单词类别，单词属性)。 第一元用于区分单词所属的类别，以整数编码表示。第二元用于区分单词符号的值。单词的编码随着类别的不同而不同，可通过种别表进行查询。 ## 6 **实验数据及结果分析：** 正确的源程序文件如下  图3.正确的源程序文件 对于词法正确的程序文件，程序会在工作文件夹生成相应的dyd二元式文件，用记事本打开后如下：  图4. 输出的二元式文件 对于存在词法错误的程序文件，在生成dyd文件的同时还会生成相应的err文件，文件中指出了词法错误存在的位置以及错误的类型，下图是错误程序文件源文件及其生成地dyd和err文件：  图5. 错误文件及输出 ## **7 实验结论：** 词法分析器的功能是：从左到右逐个的扫描源程序的字符串，按照词法规则，识别出单词符号作为输出，对识别过程中发现的词法错误，输出有关的错误信息。 # 二、语法分析 ## **1 实验目的** 通过本次设计递归下降分析器的设计与实现实验，使同学们掌握自上而下的递归分析法的语法分析原理和程序设计方法，了解掌握递归下降分析方法。 ## 2 **实验内容** 根据给定的方法，编写相应的递归下降的语法分析程序，实现对词法分析后的单词序列的语法检查和程序结构的分析，生成相应的变量名表和过程名表，并将编译中语法检查出来的错误写入相应的文件。 语法错分类: (1)缺少符号错; (2)符号匹配错 (3)符号无定义或重复定义。  ## **3 实验器材** 操作系统：Windows 10 IDE： VS 2017 ## **4 实验步骤** 1. 在VS 2017中创建工程； 1. 编写文件输入输出； 1. 对输入数据进行处理，按空格分成语句和种别码两部分； 1. 实现递归下降分析器，初步完成语法的分析； 1. 添加变量名表的相关功能； 1. 添加过程名表的相关功能； 1. 更改测试程序文件，编写出错处理函数； 1. 添加出错处理功能。 ## **5 实验原理** 左递归：当文法中出现如下的无限推导而不能匹配任何输入字符的情形成为左递归：AÞAaÞAaaÞAaaaÞ…Þ 左递归分为直接左递归和间接左递归。直接左递归是在文法中直接出现左递归，即有形如A->Aa的产生式;间接左递归则是通过推导产生的左递归。要通过递归下降分析法实现语言的语法分析需要先消除文法中所有的左递归。文法消除左递归后的文法如下： **<程序>→<分程序>** **<分程序>→begin <说明语句表>；<执行语句表> end** **<说明语句表>→<说明语句><说明语句表>’** **<说明语句表>’ →；<说明语句><说明语句表>’|ɛ** **<说明语句>→<变量说明>│<函数说明>** **<变量说明>→integer <变量>** **<变量>→<标识符>** **<标识符>→<字母><标识符>‘** **<标识符>‘→<字母><标识符>‘|<数字><标识符>’|ɛ** **<字母>→a│b│c│d│e│f│g│h│i│j│k│l│m│n│o│p│q │r│s│t│u│v│w│x│y│z** **<数字>→0│1│2│3│4│5│6│7│8│9** **<函数说明>→integer function <标识符>（<参数>）；<函数体>** **<参数>→<变量>** **<函数体>→begin <说明语句表>；<执行语句表> end** **<执行语句表>→<执行语句><执行语句表>’** **<执行语句表>’→ ；<执行语句><执行语句表>’|ɛ** **<执行语句>→<读语句>│<写语句>│<赋值语句>│<条件语句>** **<读语句>→read(<变量>)** **<写语句>→write(<变量>)** **<赋值语句>→<变量>:=<算术表达式>** **<算术表达式>→<项><算术表达式>’** **<算术表达式>’ →-<项><算术表达式>’|ɛ** **<项>→<因子><项>’** **<项>’ →\*<因子><项>’| ɛ** **<因子>→<变量>│<常数>│<函数调用>** **<常数>→<无符号整数>** **<无符号整数>→<数字><无符号整数>’** **<无符号整数>’ →<数字><无符号整数>’|ɛ** **<函数调用>→<标识符>(算术表达式）** **<条件语句>→if<条件表达式>then<执行语句>else <执行语句>** **<条件表达式>→<算术表达式><关系运算符><算术表达式>** **<关系运算符> →<│<=│>│>=│=│<>** 当文法改造为无公共左因子,无左递归时,让每个非终结符对应一个过程，该过程对相应的非终结符产生式的右部短语进行语法分析，这种分析方法称为递归下降分析法。这样的分析程序称为递归下降分析器。 ## 6 **实验数据及结果分析**  图1. 正确的语法分析输入文件及语法输出  图2. 语法分析变量名表与过程名表输出  图3. 错误源文件及错误输出 ## 7 **实验结论** 本次实验实现了语法分析器，实现了语法分析器的功能，更加深刻地理解了递归下降分析法。 # 相关说明 1. 文件夹 文件夹|说明 |:--:|:--:| Output|输出文件 Src|代码文件（包括词法分析的两个输入文件） Project|完�