代码链接：https://pan.baidu.com/s/1gFiTt1XQP-CLTDr1qOqXtA
提取码：9kqc

一、实验目的

学习和掌握词法分析程序手工构造状态图及其代码实现方法。

二、实验任务

1.观察各种词法分析器与语法分析器，了解词法分析过程；
2.阅读已有编译器的经典词法分析源程序；
3.用C或C++语言编写一门语言的词法分析器。

三、实验内容

1.在虚拟机中观察各种词法/语法分析器

1.1.虚拟机实验环境安装

环境：64 位 Ubuntu 16.04 系统，5.4.0Gcc 版本
虚拟机安装过程省略，以下为环境的查看：
getconf 指令查看系统的位数，int型为32，long型为64，为64位系统；

gcc -v查看Ubuntu和gcc版本位16.04与5.4.0；

1.2.TINY编译器与TM虚拟机

从sample.tny中的tny程序可以看出，该程序的主要功能是实现一个阶乘，源码如下：

运行tiny编译器生成sample.tiny的可执行程序sample.tm，接下来在tm虚拟机中运行该程序，我输入的数字是6，因此运行得到结果为6的阶乘720；

1.3.手写词法分析器cifa

进入cifa文件夹后通过make编译所有文件，接着直接通过运行cifa.exe程序对sample.tny文件中的tiny程序进行词法分析，分析结果显示在屏幕上。

1.4.flex构造词法分析器与bison构造语法分析器

上面的cifa是手工构造的词法分析器，而flex与bison可自动生成词法分析与语法分析程序：

不同的是cifa与flex对词素的输出格式稍微不同，而bison输出的是语法树。

2.阅读已有编译器的经典词法分析源程序。

2.1.选择TINY编译器，阅读并分析其词法分析源程序

2.1.1.TINY编译器词法分析部分相关的文件结构与相关变量函数的功能：
①Globals.h文件

此外是在main函数中定义的文件变量声明：
extern FILE* source 源代码文件
extern FILE* listing 输出tsxt文件
extern FILE* code 中间代码文件
extern int lineno 当前行号
③main.c文件
定义读取源文件所需的上述变量并初始化编译器的相关参数，分行读取源文件传递给词法分析器进行词法分析；
②scan.h文件与scan.c
词法分析的关键文件，提供词法分析功能，相关变量与函数功能如下：

2.1.2.TINY编译器的词法分析程序理解：
词法分析程序使用了3个全程变量：文件变量s o u r c e和l i s t i n g，在g l o b a l s . h中声明且在m a i n . c中被分配和初始化的整型变量l i n e n o。 表r e s e r v e d W o r d s 和过程r e s e r v e d L o o k u p完成位于由g e t T o k e n的主要循环识别的标识符之后的保留字的查找， c u r r e n t T o k e n的值也随之改变。
标志变量s a v e被用作指示是否将一个字符增加到t o k e n S t r i n g中；由于需要包括空白格、注释和非消耗的先行，所以这些都是必要的。
扫描程序的字符输入由g e t N e x t C h a r函数提供，该函数将一个2 5 6 -字符缓冲区内部的l i n e B u f中的字符取到扫描程序中。如果已经耗尽了这个缓冲区，且假设每一次都获取了一个新的源代码行（以及增加的 l i n e n o），那么g e t N e x t C h a r就利用标准的C过程f g e t s从s o u r c e文件更新该缓冲区。虽然这个假设允许了更简单的代码，但却不能正确地处理行的字数超过 2 5 5个字符的 T I N Y程序。
最后，T I N Y中的数与标识符的识别要求从 I N N U M和I N I D到最终状态的转换都应是非消耗的（即DFA中的other边）。可以通过提供一个u n g e t N e x t C h a r过程在输入缓冲区中反填一个字符来完成这一任务，但对于代码行很长的程序而言，这也不是很好。

2.2.理解词法分析程序的手工构造方法——状态图代码化

在TINY编译器的词法分析程序中，根据DFA图定义了词素以及状态后，程序获得词素token的方法为：
①初始化当前状态为START
②根据getNextChar函数得到的字符以及当前状态进行下一状态的转移以及当前token的赋值（对于二元特殊符号符号或标识符），注释与空格无需计入；
③如果此时进入DONE，则说明字符为一元特殊字符或则遇到文件结尾或错误词素，对于后者将当前token置为ENDFILE或ERROE，对于前者则直接将当前token置为对应的词素，并判断token是否是保留字即可；
④若此时不是DONE状态则说明无法确定当前token，那么需要回到②进行处理；
难点：对于注释、ERROR不能识别为token，那么无需保存字符，对应的save变量要及时设置为FALSE，注释有可能直接达到文件结尾而没有结束的 } 标志，此时直接将从开始的 { 字符到文件结尾所有字符都当作注释，遇到 } 则将状态转回START；
对于标识符如ID和NUM，当读到非字母/数字结束当前token的读取时，需要将多用的一个字符ungetNextChar返回，以便当作下一个词素的第一个字符。

2.3.整个词法分析程序的构造方法总结（心得）

手工构造词法分析器步骤如下：
A.分析语言的完整记号（保留字、特殊符号、标识符），确定关键字表以及token类型；
B.构建DFA状态图
根据关键字表画出所有识别的词法单元以及注释对应的DFA图；
对于画出的所有DFA可以进行合并，确定一个最终的接收状态DONE，根据到达DONE的路径确定返回的token；
空白符（制表符、空格、回车）的处理过程在初始状态，如果输入的符号为空白符，那么当前状态仍为初始状态。即不将空白符当做一个词法单元处理。
不单独为保留字设置DFA状态图，创建枚举类型来保留关键字；读取由字符构成的ID，该ID识别结束后，在枚举类型中查找是否是保留字，如果是保留字，则做特殊处理。
第一种是直接消耗掉输入符号，如果在识别一个记号的过程中，读到某一个符号就能确定该记号读取完毕，那么该符号是可以被直接消耗掉的；第二种是不消耗输入符号，如果在识别一个记号的过程中，读到某一个输入符号能确定该记号读取完毕，但是该符号并不属于该记号时，该符号不能被消耗。
C.使用while+switch双循环的方式代码化DFA
词法识别主要用到的函数是getToken，每执行一次，返回一个词法单元。
外层while循环为：当前状态不为接受状态时，每次循环获取一个字符；直到到达接受状态，说明一个词法单元识别完毕。将该词法单元存储，并打印出来。
内层switch循环为：判断当前状态，依据当前输入的符号进行状态的切换，同时选择该符号是否被存储、该字符是否被回吐以及在接受状态下设定当前词法单元的类型。

3.确定今后其他实验中要设计编译器的语言

确定选择C-语言作为接下来编译原理实验要设计编译器的语言；
c-语言词法定义如下：

3.1.根据该语言的词法确定关键字表，画出所有词法单元和注释对应的DFA图

3.1.1.符号表

3.1.2.关键字表

3.1.3.其它符号
ID、NUM
3.1.4.DFA图
单个特殊字符字符： 注释与空白符：

单个特数字符因为可以通过读入一个字符即确定token因此单独画出来；
注释需要注意的是读入字符为 ‘/’ 的话并不确定就是注释的开始符号，因此进入一个中间状态，如果下一个字符读入‘’那么进入注释的中间状态，否则读出词素为DIV；
在注释的中间状态读入‘’也不代表到达了注释的结束符，所以也做一个中间状态，如果下一个字符为‘/’那么注释结束回到起始状态，否则再次回到注释状态。

加上标识符与二元特殊字符得到总的DFA：

其中从初始状态读取‘！’符号进入INNE状态后如果下一字符为‘=’说明token为NE，但如果不是‘=’那么说明这里的词素无法判断。
其余的二元特殊符号如>=、<=、==也都需要一个中间状态，但在中间状态如果没有接受到第二个符号那么说明token为第一个符号的如<、>、=的词素，若接收到第二个字符则得到两个字符组成的如<=、 >=、 ==这样的词素。

3.2.仿照前面学习的词法分析器，编写C-语言的词法分析器

根据上诉手工构造词法分析器的步骤，现在只需要进行C-语言的DFA代码化即可；
我在这里选择模仿TINY编译器的文件结构与构造方法来进行构造，这样的好处是后面可以格式化构造出C-语言的整个编译器。
词法分析部分需要的文件如下；
3.2.1. myglobals.h文件
与TINY编译器的Globals.h功能和内容相同，为分析程序提供词素枚举类型：


此外，TINY编译器用于追踪分析过程的一些变量对于词法分析暂时无用，因此先删除，等进行语法分析用到时再加上，词法分析只需要两个变量；

3.2.2. myscan.h文件
与TINY编译器的scan.h相同即可，主要提供词法分析程序的接口；

3.2.3. main.c文件
分配并初始化读取文件的全局变量、追踪分析的变量；
读取文件，逐行进行词法分析（getToken函数）；

3.2.4. myscan.c文件
词法分析主要文件，内含所有词法分析相关变量、函数；
根据DFA图进行getToken函数的编写，结构如下；

根据结构与上面提到的DFA代码化方法，将DFA中的所有状态转移全部参照TINY语言的getToken转化为代码；
以注释为例：
参照DFA：

转化为：

注释一共需要4个状态（如果加上符号‘/’那么需要5个），从START开始如果读入‘/’进入INCOML状态；
在INCOML状态如果读入‘’那么转移到INCOMMENT状态，SAVE标志置0，即此时进入注释，否则说明读入‘/’符号，将当前词素赋值为DIV，状态变为DONE；
在INCOMMENT状态如果读入‘’，那么可能要结束注释，进入INCOMR状态；
在INCOMR状态如果读入‘/’，那么结束注释，回到START状态，否则前一个‘*’并不是结束符，回到INCOMMENT注释状态；
要注意可能读入文件结束符；

其它的状态转移不再分析，大致方法相同。

其中最后一句输出词素的实现如上图，需要注意，根据TraceScan的标志，决定打印出该行的所有token；

文件读取的相关变量lineBud、linepos、bufsize、EOF_flag以及获取下一字符的函数getNextChar、将符号回吐的函数ungetNextChar、查看当前词素是否为保留字的reservedLookup与上述TINY编译器词法分析的scan.c中的相同，因此这里不再复述。

3.3.准备2~3个测试用例，要求包含正例和反例，测试编译结果

3.3.1.正确用例test1.c_与测试结果

测试结果正确；

3.3.2.错误用例test2.c_与测试结果：

分析：
其中源文件错误的地方主要是“x ！ y”，这里故意少写一个=号，读取词素！=失败应该报错，程序结果报错了；
在最后面的注释没有结束的 */ 标志，因此应该将后面的所有内容当作注释直到文件结束，程序是这样做的，它将第6行的 } 和第7行的 }都当作了注释，包括第六行的空白符也当作注释不进行处理。

四、思考

在充分理解状态转换图代码化思想的基础上，不同的程序设计语言从词法角度有什么区别？
通过整个实验文档我们可以很轻易发现不同语言在词法上的区别，最主要的就是词素的不同以及DFA图的不同，我们整个词法分析程序都是围绕着词素DFA来进行的，词素和DFA的不同使得我们填充getToken函数结构的不同。

五、总结

本次实验分为两个部分，第一部分是对Tiny的词法分析器中源代码进行学习；第二部分是自己构建C-语言的词法分析。原本是想自己来尝试以自己的思路去编写，但是学习了Tiny的源代码之后发现其使用的方法更高效、更标准。
词法分析器的难点部分在于状态转换图，如果能够清晰的画出状态转换图，词法分析器的手动构造就完成了一大半。此次DFA构造过程较为简单，这是因为C-语言的语法已经是非常简单的了。但在代码实现DFA的过程中，还是有一些难点，例如，/ 与/*的分析，前者是除号会被保存在词法单元，后者是注释的开始符号将被词法分析器忽视，那么对他们的处理就是再建立一个中间状态。
通过这次实验更好的理解了词法分析器的工作原理。学会了如何将DFA状态图代码化，完成了一个进阶的学习。