实现C语言的词法分析器

1、编译原理实验二一 学习经典的词法分析器。a) 实验分析：词法分析器，有的教材又称扫描器，我倒是觉得扫描器更加符合其本意，因为词法分析器的主要作用是将文本代码流解析成一个个记号，供语法分析使用。由于上一次实验，TINY编译器已经相对比较熟悉，这一次主要关注词法分析器的部分，即SCAN.C。就词法分析器本身的写法而言，并没有所谓的标准代码，不过经典代码还是很有参考价值的，而修改经典的过程也是体会经典的最佳形式。b) 实验过程：1. 阅读已有编译器的经典词法分析源程序：我选择的仍然是TINY编译器，它的词法分析部分是SCAN.C文件。i. 调用词法分析器的形式：在主函数中有如上语句是调用SCAN.C

2、中的getToken()函数。getToken()即词法分析器进行状态转换的核心部分。ii. 词法分析器中的常量：1） 状态枚举：枚举的最大好处在于能够用字符（状态）代替数字，而且将这些封装在一个结构中。2） TokenString是为了存储保留字的标识符3） 以下变量是为了处理输入缓存以及当前指针位置的相关存储：4） 保留字的结构体，这一部分可以清晰的看到所有保留字：iii. 词法分析器的相关函数：1) 处理文件输入相关：这两个函数是一对，前者是从缓存中读取下一个字符，后者则将当前读取的字符重新放回缓存。后者存在的最大的价值在于，当用下一字符的情况判断将跳转到什么状态时，如果该字符不属于当前

3、标示符，则放回缓存，以保证下一标示符的获取不受影响。 2) 判断字符是否为保留字：对于读入的单词，我们需要知道其到底是一个变量名还是一个保留字，这个时候就需要调用该函数。利用for循环在所有保留字中搜寻，有匹配的就说明是一个保留字，否则就是变量名。3) DFA实现算法：TINY采用的是while和多层switch判断相结合的跳转形式，这种写法和EDA实验中的状态装换如出一辙，非常简便而且容易理解。但是缺点也很明显：不容易扩充，显得比较杂乱。其逻辑很清楚：从START状态开始，每获取一个字符，就根据字符情况跳转到相应的下一状态，如果跳转到接受态DONE，则输出。输出是调用UTIL.C文件完成的。

4、可以看到的是，如果一个语言越复杂，其包含的字符形式越多，这种case讨论将会越复杂，至此我已经可以想象得到C语言词法分析器的“宏伟”程度了。2. 改变DFA的实现算法：通过分析TINY的词法分析器，我们很快可以找到我们的DFA实现形式与其的差别。我们是建立了一个状态转换表，并将其存储在了一个二维结构中，通过输入与当前状态的对应得到下一状态的，并将这一状态变成当前状态，反复进行上述操作，直到进入接受态。如果要改变DFA的实现算法，过程很明显：建立二维结构存储状态转移，查表进行状态转移。接下来将进行操作和分析：1） 在修改之前，先观察原有的词法分析器正常运行的结果，以便修改后比对：为了测试输出结果

5、，我们在主函数（TINY_XH）中将词法分析追踪（TraceScan）赋值为TRUE，这样在进行编译的输出中就可以看到词法分析的结果，方便用来对比。TraceScan一旦使能，这里就可以输出到屏幕上。在修改程序之前，截屏如上，左边是源程序，右边是编译的词法分析的结果2） 建立状态转换表，通过分析源程序可知如下状态转换图：（该图是我用VISIO绘制）原程序使用while大循环下的switch和case进行状态转换，这里完全可以换成上次我们写的通用DFA形式。所谓通用DFA就是指状态转换的核心部分不会随着状态或者输入的改变而改变，状态转换的跳转和状态存储的二维表有关，只用修改存储状态的二维表，既可

6、以方便的修改或者扩充编译器的词法处理能力。状态图转换成状态表可得：通过状态转换情况，将其保存在状态转换表中，具体形式如上。就二维表而言，有很多种写法，比如我把一些输入合并到other类型，是为了减轻状态表的冗余状态数量。这个二维表中没有冗余状态。判断冗余的方法很简单，如果有两列/两行完全相同，这两列/两行就可以合并成一列/一行。3） 修改状态转换代码以及附属属性部分的实现：有了状态转换表，状态转移只用一句话就可以解决：可以说就状态转移这一部分而言，非常简单。但是为了方便输出，需要知道获取的标示符是什么类型的，因此需要进行赋值。比如如下修改：4） 测试结果：（和修改前完全一致）c) 实验问题：1

7、） 程序进入死循环，或者一直报错：程序不能正确执行，肯定出在细节处，我开始以为是逻辑处出错，一直在检查语句，结果很长时间都没有发现问题。后来排除了所有可能，我检查了一下最开始制作的二维状态转移表，果然就发现了问题的所在：状态转换中本应跳转到DONE，因为失误写成了START，结果跳转到了START。纠正结果后，程序完全正确，但是这个错误确实消耗了我很长的时间去检查。d) 实验结果：对SCAN.C的解释，在上面的报告中已经给出。SCAN.C的修改版本在CODE文件夹中。如果要运行完整的程序，在“CODE完整的VS工程”目录中，可以用Visual Studio运行，其中sample.tny在该工程

8、的debug文件夹下，方便用CMD运行。e) 实验心得：由于有了第一次的实验的基础，转化成一个DFA的思想是非常清晰而简单的，然而实现的过程不是一帆风顺的，中间任何一个环节都可能会出现很多小问题，一个小细节没有处理好，可能会导致整个程序的崩溃，所以需要耐心和细心。我在做的过程中，曾经因为一个状态打错，导致跳转时有误，开始一直怀疑是逻辑问题，不曾检查状态表的错误，导致延误了很久。我觉得纠错的过程就像是推理和演绎，虽然有DEBUG，不过我使用的比较少，单纯通过输出推测出错的地方会是哪里，我喜欢这个过程。当一个完整的词法分析结果出现在CMD中时，突然觉得这是最美的文字。二 实现一门语言的词法分析器a

9、) 实验分析：通过上面的实验我们已经了解了简单的词法分析器，实战莫过于新编一个语言的编译器。而一个语言的词法分析器，我们首先要知道它含有什么关键字，有哪些专用符号，什么是特殊标记，以及其他符号或者注释情况。b) 实验过程：1. 语言确定：我选择C-语言，因为要在以后的实验中继续完善其他部分，所以我希望按照一个完整的工程制作。因此仿照TINY编译器的形式，将每一部分的功能集中在一个文件中，有globals文件对全局变量进行定义，有util专职输出，有C_XH文件作为主函数，调用其他的函数。然后定义SCAN函数进行词法分析。我希望这种高耦合低内聚的形式成为我以后编码的风格和习惯。2. 编写词法分析

10、器：1） 确定C-语言的惯用词法，并在globals.c文件中定义：一、定义关键字，关键字都是保留字：else if int return void while1在globals.h里面写入保留字信息2在scan里面选择关键字信息更改二、专用符号：+ - * / < <= > >= = != = ; , ( ) /* */三、其他标记是I D和N U M，通过下列正则表达式定义：四、空格由空白、换行符和制表符组成。当然这些是要被忽略的。五、注释用符号/ * . . . * /围起来。完成了常量的定义之后，应该是如下图的形式（在GLOBALS.C文件中）。其中，尤其需要注

11、意，MAXRESERVED变量必须有一个值，否则在检查保留字的时候，会出现循环访问范围有误。由于我们一共有6个保留字，所以赋值为6。2） 状态转移分析：由于C-的词法更加复杂，所以状态也比TINY多很多，我定义了11个状态。主要因为以下标示符是由多字符组成，所以不得不为每一种生成状态记录：字母，数字，<=，>=，=，！=，/*，*/在SCAN.C中的状态定义如下：状态图大致如上，这个图只有大致的轮廓，限于篇幅，这里有很多自环没有画出，而且一些状态转移可能看不清楚。其中最下面的一串状态转移，与上次试验中的下图类似：事实上，这个正是用来判断注释部分的状态转移。/* oooooooooo

12、ooooo */（注：除了这张图是从老师的文档中拷来，其他全部是自己创作，工具是VISIO）3） DFA实现代码：这一次采用TINY的switch-case格式，因为这种形式更加方便。部分代码如上。由于无论是字符还是状态都增加了很多，代码量也稍有增加。4） 加上主函数，调用词法分析器：由于只做了词法分析器，所以只调用了getToken()5） 修改输出函数：UTIL.C文件中的关键语句关系到词法分析的输出，因此需要重新写。以便能够在CMD中看到词法分析的结果。由于篇幅比较长，因此只截取部分如下：3. 至此C-的一个编译器C_XH制作好了，运行结果如下：左图是一个C-语言的源程序。词法分析结果如

13、下，正确性已经得到了我的验证：有一个有趣的测试数据：（注释代码中含有中文）结果表明注释中出现的中文对结果没有影响。c) 实验问题：1. 其实原本可以自己写一个简单的主函数调用Scan和一些有用的参数即可。但是为了试验的可延续性，我保持TINY的风格，将数据变量全部储存在Globals中，util用来输出，scan进行词法分析。不过这样做也是有代价的，就是写起来工程量比较大，于是我参考着TINY，经过多次修改错误，才算完成。2. 就词法分析器本身而言，并不一定要按照TINY的形式写，其实可以自己创造数据存储格式，自己逐单词判断，比如用hash表来实现存储，以此实现DFA。只不过不好继续扩展。我本想自己重新用一种方法，后来发现时间有限，就放弃了。3. 不该显示的部分显示在结果中，原因在注释的DFA状态跳转错误。为了方便看，我故意用了中文，注释部分总是会有输出。开始我百思不得其解，还以为是输出部分没有写好，后来才发现是跳转错误。得到注释结束后，不应该跳往DONE，这样表示找到一个标示符，需要输出。由于注释是完全屏蔽的，所以应该在注释结束后直接跳往start而是不是done状态。接受到“注释部分”结束