实现C-语言的词法分析器.doc

编译原理 实验二 一． 学习经典的词法分析器。 a) 实验分析： 词法分析器，有的教材又称扫描器，我倒是觉得扫描器更加符合其本意，因为词法分析器的主要作用是将文本代码流解析成一个个记号，供语法分析使用。 由于上一次实验，TINY编译器已经相对比较熟悉，这一次主要关注词法分析器的部分，即SCAN.C。就词法分析器本身的写法而言，并没有所谓的标准代码，不过经典代码还是很有参考价值的，而修改经典的过程也是体会经典的最佳形式。 b) 实验过程： 1. 阅读已有编译器的经典词法分析源程序： 我选择的仍然是TINY编译器，它的词法分析部分是SCAN.C文件。 i. 调用词法分析器的形式： 在主函数中有如上语句是调用SCAN.C中的getToken()函数。 getToken()即词法分析器进行状态转换的核心部分。 ii. 词法分析器中的常量： 1） 状态枚举：枚举的最大好处在于能够用字符（状态）代替数字，而且将这些封装在一个结构中。 2） TokenString是为了存储保留字的标识符 3） 以下变量是为了处理输入缓存以及当前指针位置的相关存储： 4） 保留字的结构体，这一部分可以清晰的看到所有保留字： iii. 词法分析器的相关函数： 1) 处理文件输入相关： 这两个函数是一对，前者是从缓存中读取下一个字符，后者则将当前读取的字符重新放回缓存。后者存在的最大的价值在于，当用下一字符的情况判断将跳转到什么状态时，如果该字符不属于当前标示符，则放回缓存，以保证下一标示符的获取不受影响。 2) 判断字符是否为保留字： 对于读入的单词，我们需要知道其到底是一个变量名还是一个保留字，这个时候就需要调用该函数。利用for循环在所有保留字中搜寻，有匹配的就说明是一个保留字，否则就是变量名。 3) DFA实现算法： TINY采用的是while和多层switch判断相结合的跳转形式，这种写法和EDA实验中的状态装换如出一辙，非常简便而且容易理解。 但是缺点也很明显：不容易扩充，显得比较杂乱。 其逻辑很清楚：从START状态开始，每获取一个字符，就根据字符情况跳转到相应的下一状态，如果跳转到接受态DONE，则输出。输出是调用UTIL.C文件完成的。 可以看到的是，如果一个语言越复杂，其包含的字符形式越多，这种case讨论将会越复杂，至此我已经可以想象得到C语言词法分析器的“宏伟”程度了。 2. 改变DFA的实现算法： 通过分析TINY的词法分析器，我们很快可以找到我们的DFA实现形式与其的差别。 我们是建立了一个状态转换表，并将其存储在了一个二维结构中，通过输入与当前状态的对应得到下一状态的，并将这一状态变成当前状态，反复进行上述操作，直到进入接受态。 如果要改变DFA的实现算法，过程很明显：建立二维结构存储状态转移，查表进行状态转移。接下来将进行操作和分析： 1） 在修改之前，先观察原有的词法分析器正常运行的结果，以便修改后比对： 为了测试输出结果，我们在主函数（TINY_XH）中将词法分析追踪（TraceScan）赋值为TRUE，这样在进行编译的输出中就可以看到词法分析的结果，方便用来对比。 TraceScan一旦使能，这里就可以输出到屏幕上。 在修改程序之前，截屏如上，左边是源程序，右边是编译的词法分析的结果 2） 建立状态转换表，通过分析源程序可知如下状态转换图： （该图是我用VISIO绘制） 原程序使用while大循环下的switch和case进行状态转换，这里完全可以换成上次我们写的通用DFA形式。所谓通用DFA就是指状态转换的核心部分不会随着状态或者输入的改变而改变，状态转换的跳转和状态存储的二维表有关，只用修改存储状态的二维表，既可以方便的修改或者扩充编译器的词法处理能力。 状态图转换成状态表可得： 通过状态转换情况，将其保存在状态转换表中，具体形式如上。 就二维表而言，有很多种写法，比如我把一些输入合并到other类型，是为了减轻状态表的冗余状态数量。这个二维表中没有冗余状态。 判断冗余的方法很简单，如果有两列/两行完全相同，这两列/两行就可以合并成一列/一行。 3） 修改状态转换代码以及附属属性部分的实现： 有了状态转换表，状态转移只用一句话就可以解决： 可以说就状态转移这一部分而言，非常简单。但是为了方便输出，需要知道获取的标示符是什么类型的，因此需要进行赋值。 比如如下修改： 4） 测试结果：（和修改前完全一致） c) 实验问题： 1） 程序进入死循环，或者一直报错： 程序不能正确执行，肯定出在细节处，我开始以为是逻辑处出错，一直在检查语句，结果很长时间都没有发现问题。后来排除了所有可能，我检查了一下最开始制作的二维状态转移表，果然就发现了问题的所在： 状态转换中本应跳转到DONE，因为失误写成了START，结果跳转到了STAR