编译原理经典算法的可视化实现 rate所对应的符号表中的条目。
（6）“/”是一个词素，经分析后会被映射成词法单元.
（7）50是一个词素，经分析后会被映射成词法单元<50>。其实从理论上说，也应该建立一个形如
图2.2给出，赋值语句newCount=oldCount+rate/50,经过词法分析之后生成的词法单元序列：
newCount=oldCount+rate/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
编译原理经典算法的可视化实现 #include
9
编译原理经典算法的可视化实现
3 词法分析器动态演示的设计与实现
3.1 词法分析器描述语言
目前有很多通过基于正规表达式构建词法分析器的工具。前面我们已经知道了可以用Lex工具来构建词法分析器。Lex可以广泛地应用于各种预言词法分析器的描述。我们称这种工具为Lex编译器，而Lex编译器的输入称为Lex语言。我们将使用类Lex语言类说明词法分析器，并存储中间结果，用于词法分析器的动态演示。 3.1.1 Lex说明
一个Lex程序由如下三部分组成：
声明部分 %% 转换规则 %% 辅助过程
声明部分包括变量声明，符号常量声明和正规定义。（符号常量是被声明来表示常数的标识符。）正规定义就作为转换规则中正规表达式中的部分。
Lex程序的转换规则是如下形式的语句： P1 {action1} P2 {action2} … …
Pn {actionn}
其中每个pi是一个正规表达式，每个actioni表示当模式i匹配上一个词素后词法分析器要执行的程序段。在Lex中，这些action是用C语言编写的，当然也可以用其他语言来实现。
我们将action所需要的辅助过程放在Lex的第三部分。这些过程也可以单独编译，
10
编译原理经典算法的可视化实现 并与词法分析器一起装载。
由Lex自动生成的词法分析器与语法分析器共同工作的方式如下：首先，语法分析器调用词法分析器后，词法分析器从还未扫描的输入字符串中读字符，而每次读入一个字符，这个过程直到发现能与某个正规表达式匹配的最长前缀。接下来，词法分析器执行那些动作（action）。通常那些动作也会将控制交给语法分析器。接下来，假设不将控制交给语法分析器，那么词法分析器可以继续发现更多的词素，直到某个操作将控制交给语法分析器。词法分析器的这种不断查找词素，直到以显式的调用结束工作的方式，使其可以方便地处理换行、空白符和注释。而词法分析器只返回记号给语法分析器，带有与词素相关信息的属性值是通过全局变量yylval传递的。 3.1.2 超前扫描操作
对于某些程序设计语言结构，词法分析器需要超前扫描词素后面的若干字符来确定一个记号。假设有这样的Fortran语句例子： DO 5 I = 1.25 DO 5 I = 1,25
在Fortran中，除了在注释和Hollerith串中之外，空格不代表任何意义。我们可以认为在词法分析器开始工作时，所有的空格都已经去掉。这样，上面的两个语句就变为如下形式：
DO5I=1.25 DO5I=1,25
在第一个语句中，直到词法分析器发现了小数点后才可以断定DO是标识符DO5I的一部分。在这个语句中，DO是关键字。
在Lex中我们将模式写成y1/y2的形式，其中的y1和y2是正规表达式。而它的意思是当一个字符串与y1匹配时，还需要其后的字符串与y2匹配。这样才算该字符串与y1匹配成功。在超前扫描操作符/后面的正规表达式y2表示需要进一步匹配的内容，这里它只是匹配模式的一个限制，而不是匹配的一部分。例如，将上述语句中的DO识别为关键字的说明如下：
DO/({letter}|{digit})*=({letter}|{digit})*,
根据这个说明，词法分析器在输入缓冲去超前地扫描一串字母或数字，接着扫描等
11