编译原理经典算法的可视化实现 词法分析器是编译器读入源程序的阶段，所以它还要完成另外一些与之相关的辅助任务。一个任务是将源程序中的空格、注释、换行符、制表符过滤掉；而另一个任务是让编译器将发现的错误信息与之相对应的出错位置显示出来，这样就能方便源程序的编写。例如，我们在词法分析器中设置一个变量来记录遇到的换行符的个数，这样就能将行号与出错信息关联起来。而在另外一些编译器中，词法分析器会拷贝一份源程序，而且将出错信息加入其中，这样就能直接在源程序中看到出错信息。如果要求词法分析阶段有预处理功能，我们就需要源语言支持宏预处理器功能才行。

有时，我们将词法分析器分为两个阶段：第一阶段是扫描阶段，而扫描程序就负责完成一些简单的任务。另外一个阶段则是词法分析阶段。

2.2词法分析中的问题

把编译过程的分析阶段划分为词法分析和语法分析的原因如下：

（1）最重要的考虑是怎样才能简化编译器的设计。而词法分析和语法分析这一分离可以简化它们的设计。例如，如果把空白符和注释等的处理放在在语法分析而不是由词法分析器来完成时，这样将会使设计语法分析器变得十分复杂。因此，从语法分析中分离出词法分析会有利于编译器的设计

（2）能有效提高编译器的工作效率。我们将词法分析独立出来，这样就能构造专门的更有效的处理器。而编译时间的大部分消耗在源程序的读入并将其切分为记号方面。并采用专用的缓存技术来读取输入字符串和处理记号，这样可以有效地提高编译器的性能。

（3）增强编译器的可移植性。与设备有关的特征以及语言的字符集的特殊性的处理可以被限制在词法分析器中。而把词法分析和语法分析分开后，可以借助很多工具来自动地构造它们。如lex和yacc工具。

2.3 词法分析中的术语

在词法分析的讨论中，我们使用术语 ”模式“﹑“记号“﹑”词素“表示规定的含义。通常，在输入的一组字符串中可能会产生一样的记号来作为输出，而一个与该记号相关联的称为模式的规则来描述这个字符串组成的集合。这个模式被说成匹配该集合中的每个字符串，词素是源程序的字符序列，由一个记号的模式来匹配。把记号作为源语

5

编译原理经典算法的可视化实现 言文法的终结符，有记号的模式所匹配的词素表示源程序的字符串，即词法单位，而记号的返回通常是通过传递代表这个记号的证书来实现的。我们将模式定义为描述源程序中表示特定记号的词素集合的规则。我们仅仅通过词法单元来表示词素是不够的，还必须指明词素内容是什么类型的，不同类型的词素对应不同类型的模式，所以模式往往有比较复杂的数据结构。而词素就是从源程序中提取出的一个字符的序列，源程序中往往会表明一个数据的类型，就对应在词法分析时的模式，而源程序通过类型匹配之后被拆分成一个一个的字符串就是词素。

由于不同的词素可能有着相同的类型，也就是它们能被同一个模式所匹配，这种情况下后面的编译阶段就无法区分这些词素了，所以词法分析器必须向编译器的后续阶段提供有关被匹配词素的附加信息。例如，1和2都能和词法单位number的模式匹配，但是对于代码生成器而言，至关重要的是知道在源程序中找到了哪个词素。所以，词法分析器如果仅仅只返回词法单元的名字是不够的，在这种情况下，我们给每个词法单元外附件属性值，词法单元的名字主要实在词法分析过程中构造语法分析树之时用到，而这个属性值则将在将语法分析树翻译成计算能够理解的底层程序语言时才用到。

词法分析作用举例如下：

假设在源程序中有这样的一条语句：newCount=oldCount+rate/50

当语句中的字符经过词法分析器分析之后将会被组合成以下的词素，并会映射成下面的词法单位。

（1）newCount是一个词素，将被映射成词法单位,其中id表示的是标识符的抽象符号，而1就是指向其在符号表中所对应的条目。当然，这个1为方便说明，自己给定的。但是经过分析后这个值就是固定的。一个标识符的有关信息将被存放在该标识符所对应的符号表的条目中。

（2）赋值符号“=”是一个词素，经分析后会生成词法单元<=>。我们知道，这个词法单元不需要属性值，这里为在使用和阅读上方便，就把词素本身来作为抽象符号的名字。

（3）oldCount是一个词素，经分析后会生成词法单元，同样，这里的2就是该词素所对应的符号表中的条目。

（4）“+”是一个词素，经分析后生成词法单元<+>.

（5）rate是一个词素，经分析后生成词法单元,同理，其中3表示的就是指向

6

编译原理经典算法的可视化实现 rate所对应的符号表中的条目。

（6）“/”是一个词素，经分析后会被映射成词法单元.

（7）50是一个词素，经分析后会被映射成词法单元<50>。其实从理论上说，也应该建立一个形如的词法单元，而其中4指向整数50所指向的符号表中的条目。

图2.2给出，赋值语句newCount=oldCount+rate/50,经过词法分析之后生成的词法单元序列： <=> <+> < id,3> <*> <50>

newCount=oldCount+rate/50词法分析器< =><+><*><50>

图2.2 词法分析过程

词法分析将所有单词分为五类：保留字，标识符，界符，数字，运算符。词法分析器用记号的属性来收集与记号有关的信息。记号对语法分析有着影响，而属性也影响那些记号的翻译。在实际实现时，那些记号通常仅有一个属性，而那个属性就是指向符号表中一个表项的指针，与记号有关的信息保存在这对应的表项中。

2.4 词法错误

由于词法分析器考察源程序不是从全局的角度考虑的，所以能在词法分析中找到的错误也是有限的。如果词法分析器在C代码中读取到一条语句：fro（a==g(x)），在这个语句第一次遇到fro时，词法分析器没有办法分辨出fro是关键字for写错了还是一个没有声明的函数标示符。由于fro是合法的标识符，词法分析器必须返回该标识符的所对应的记号，而让这种错误给编译器的其他阶段去处理。

有时会出现由于剩余输入的前缀不能和任何任何记号的模式匹配而使词法分析器无法处理的情况。此时，最简单的错误恢复策略也许是“紧急方式“恢复，即反复删掉剩余输入最前面的字符，直到词法分析器能发现一个正确的记号为止。这种恢复技术虽然会给语法分析带来一些麻烦，但在交互计算环境中是非常有效的。

而其他错误恢复动作包括：

7

编译原理经典算法的可视化实现 （1）删除一个多余的字符。 （2）插入一个遗漏的字符。

（3）用一个正确的字符代替一个不正确的字符。 （4）交换两个相邻的字符。

2.5 词法分析生成工具

词法分析器自动产生工具Lex是一个能产生词法分析器的程序，它是许多Unix系统的标准词法分析器产生程序，常常与yacc语法分析器产生程序一起使用。现在在Windows平台下也有其版本，另一个有名的Lex公开源代码版本是flex，代表\快速的词法分析器\。Lex的功能是读进一个代表词法分析器规则的输入字符串流，然后输出以C语言实做的词法分析器源代码。它的描述规则采用的是正则表达式。首先我们编写Lex的源程序，文件可以自己定义，然后经过Lex编译后,就会生成一个lex.yy.c文件，然后我们借助C编译器(比如gcc)编译此时就会生成一个词法分析器。过程如图2.3所示：

Lex source fileLex compiler Lex.yy.cC compilera.outInput streama scannerSequence of token

图2.3 Lex编译过程

Lex文件结构简单，分为三个部分，分别是声明，转换规则和其它函数。声明段包括变量的声明，符号常量的声明和正则表达式声明。规则段是由正则表达式和相应的动作组成的。而如果希望在目标C源码中的代码，则用%{?%}括在一起。比如： %{

8