编译原理与实践-词法分析器的识别技术

1.输入和预处理

词法分析器工作的第一步是输入源程序字符串，它们一般被存放在输入缓冲区中。单词识别的工作可以直接在这个输入缓冲区中进行，但是，为了使得单词识别的工作更容易，在识别前先要对输入串进行预处理。

对于许多程序设计语言来说，空白符、跳格符、回车符、换行符以及注释等字符对执行源程序没有作用，其作用仅仅在于改善程序的易读性和易理解性。对于这些字符，可以构造一个预处理子程序，在预处理时将其删除。在删除过程中，如果字符串后有以上提到的符号时，都用一个空格代替。另外，像C语言有宏定义、文件包含、条件编译等语言特性，为了减轻词法分析器的负担，源程序从输入缓冲区进入词法分析器之前，要先对源程序进行预处理，一般完成以下工作：（1）滤掉源程序中的注释；（2）去掉源程序中的无用字符；（3）进行宏替换；（4）实现文件包含的嵌入和条件编译的嵌入等。

每当词法分析器需要分析源程序时，就调用预处理子程序处理一串长度为N（如4096个字节）的输入字符，然后，将经过预处理的字符串装入扫描缓冲区，词法分析器可以在此缓冲区直接进行单词的识别工作，而不必再进行烦琐的处理工作。

扫描器对缓冲区进行扫描时一般使用两个指针：一个指向当前正在识别的单词的起始位置，另一个用于向前搜索以寻找该单词的终点，两个指针之间的符号串就是要识别的单词符号。无论扫描缓冲区设计得多大都不能保证单词符号不会超过其边界，因此，它通常使用一分为二的两个区域（如图3-2所示），这两个区域长度相同，互补使用。如果单词搜索指针从单词起点出发搜索到半区的边界仍未达到单词的结尾，那么，就应该调用预处理程序，将后续N个输入字符装进另外的半区。从而保证能在扫描缓冲区中获取到整个单词。

图3-2　扫描缓冲区一分为二的两个区域

2.单词符号的识别

词法分析器对单词符号的识别是在对源程序的扫描过程中实现的。我们已经知道，单词的类型分为五种，分别是关键字、标识符、常数、界符和算符。词法分析器如何识别不同的单词，下面将分别介绍。

（1）标识符和关键字的识别

假设在L语言中，关键字和标识符是以字母开头的“字母/数字”串，其识别过程是：当从扫描缓冲区读入的单词首字符是字母时，开始识别标识符或关键字，边拼写边从缓冲区读入下一字符，列计数加1；当读入的字符为非字母数字时，标识符识别完成，但此时已多读入一个符号，所以必须将该字符回退到缓冲区，列记数减1。识别出来的单词是否为关键字，必须查关键字表进行判断。若是关键字，返回该关键字的种别编码；否则，识别的单词就是标识符，返回标识符的种别编码。

（2）数值型常数的识别

数值型常数是以数字开头的“数字串”，若为实型常数则可能包含“.”、“E/e”和“+/-”，其识别过程是：当从扫描缓冲区读入的单词首字符是数字时，开始识别整数或实数；继续读入下一字符，列计数加1，当遇到“.”时，还要继续读入该常数（该字符串可能是实数）；如果遇到E或e，要识别带指数的常数；当遇到其他非数字字符时，数值常数识别完毕，此时已多读入了一个字符，需要回退给缓冲区，列计数减1。最后，返回整型常数或实型常数的种别编码。

（3）字符型常数的识别

在L语言中，字符常数是由两个单引号引起的字符，其识别过程是：当读入的单词首字符是单引号时，忽略单引号，开始识别字符常数，读入下一符号，列计数加l；搜索下一个单引号，当再读到引号时，字符常数识别结束。最后，返回该字符常数及字符常数的种别编码。(www.xing528.com)

（4）算符和界符的识别

在算符和界符的识别过程中，当读入的首字符是“/”时，需继续读入下一符号；如果下一符号是数字，则需回退一个字符到缓冲区，同时返回算符“/”的种别编码；如果读入的下一符号是“*”，则开始识别注释，直到界符“*/”出现为止，此时不需多读入一个符号，列计数不变，没有返回值。若读入的单词首字符是除了“/”和“”以外的其他界符或算符，对于＜、＞、：等符号，还需再读入一个符号，判别是否为双界符；若是双运算符，则查表返回其种别编码；若不是，则列计数减1，返回该单词的种别编码。

（5）超前搜索和最长匹配

在单词符号的识别过程中，如何找到一个单词的起点和终点，比如，在C++语言中，比较运算符“＜=”和“＜”以及“=”都是一个单词符号，如何识别是“＜=”而不是“＜”和“=”？

词法分析器运用了两个基本技术，它们是超前搜索和最长匹配。这两项技术通常相互补充、共同使用，其含义是：为了识别一个更有意义的单词符号，在找到了可能是单词符号的起点或者构成了部分单词时，扫描器并不满足，还要继续读入输入串，看是否能找到由更多符号所组成的单词（即最长匹配），有时可能要扫描到一个可以“断句”的符号（超前搜索），才能决定最后一个扫描的符号不属于之前的符号串所构成的单词。例如，在识别“for”的时候，要扫描到左括号“（”时才知道它不是标识符；当读到了“＜”的时候，扫描器期望再读入一个“=”，以便构造出小于等于“＜=”的比较运算符，否则，就构造小于运算符。

超前搜索符号通常是最长匹配单词的结束标志，可以是空格符、回车符、制表符等一些可以被预处理的符号，也可能是下一个单词符号的起始符。因此，需要退还给扫描缓冲区，并且把搜索指针的位置减1。根据语言的语法规则或单词匹配模式，词法分析器可以知道什么时候应该继续超前搜索。

3.符号表及其操作

在词法分析阶段，将识别出来的某些单词（如标识符和常数）及其相关的属性填写到符号表中。以便在语义分析及生成目标代码阶段使用。标识符和常数的相关信息将被保存在一张或多张符号表中。

符号表的每一项包含两部分内容，一部分是用于存放标识符名称的名字栏，另一部分是用于存放标识符有关信息的信息栏，其中，信息栏包括类型、值、内存地址等。

符号表的内容只有一小部分可以在词法分析阶段填写，如单词的名字和长度等，许多内容需要在编译的后续阶段填写，如值和类型在语义分析阶段填写，内存地址在目标代码生成阶段填写等。符号表的实现可使用记录结构来完成，在词法分析阶段符号表的操作主要包含两个：插入和查找。具体的符号表实现及操作方式参见第7章。

4.错误处理

一个好的编译程序在每次编译源程序时应尽量发现更多的错误，并应能准确地通知出错位置和错误类型，这样，用户就可以迅速地改正程序错误，加快程序的调试速度。词法错误通常有以下几种情况：（1）非法字符，是指程序语言的字符集以外的字符。例如，@对L语言是非法的。为了检查非法字符，编译程序需要保持一张合法字符集表，每当读入一个字符时，首先判断该字符是否属于合法字符集。当通知非法字符时，需指出其行列位置。（2）关键字拼写错误，例如，than（其实应该是then）。关键字拼错这种错误在词法分析时无法发现，通常把它当作标识符处理，待到语法分析阶段才能发现。（3）注释或字符常数不闭合，例如，/*…，ABC…等。为了防止这种错误产生，一般限定注释或字符串常数的长度，或者注释只到本行为止。（4）变量说明有重复，如“int c；”和“char c；”。在语义分析阶段时才能发现重复说明的错误。

对词法错误的校正一般做法是：删除一个字符、插入一个字符或替换一个字符等。大部分情况下，编译程序只是输出校正信息，供程序员校正时参考。

至此，对词法分析器的详细设计过程有了深入的了解，下面将介绍状态转换图，它是一种设计词法分析器的很好的工具。