《编译原理》第三章词法分析

词法分析是编译的第一步，词法分析器的主要任务是读入源程序的输入字符，将他们组成词素，生成并输出一个词法序列，每个词法单元对应于一个词素。词法分析器通常还需要跟符号表进行交互，当词法分析器发现了一个标识符的词素时，它要将这个词素添加到符号表中。在某些情况下，词法分析器会从符号表中读取有关标识符种类的信息，以确定向语法分析器传送哪个词法单元

通常，交互式由语法分析器来实现的，语法分析器会通过调用词法分析器的getMextToken获取下一个词素，同时词法分析器通常会完成下面两个任务：

过滤源程序找那个的注释和空白
将编译生成的错误消息和源程序位置联系起来

为什么将词法分析和语法分析进行分开

简化编译器的设计
提高编译效率，将词法分析器独立出来我们能够使用专用语法分析任务、不进行语法分析技术，此外，我们还可以使用相关缓冲技术提高整体编译速度
增强编译器的可移植性，输入设备相关的特殊性可以被限制在词法分析器中（重要）

词法单元、模式、词素

词法单元：一个词法单元名+可选属性值组成

模式：描述了一个词法单元的词素可能具有的形式

词素：源程序中的一个字符序列，他和某个词法单元的模式匹配，并被词法分析器识别为该词法单元的一个实例

输入缓冲

这是一种安全处理向前看多个符号的问题的方法，我们称之为双缓冲方案，然后我们会考虑一种改进方法，我们称之为“哨兵标记”来节约用于检查缓冲器末端的时间

1. 双缓冲方案

由于在编译一个大型源程序时需要处理大量的字符，处理这些字符需要很多的时间，因此开发了一些特殊的缓冲技术来减少单个输入字符的时间开销，一种重要的机制就是利用两个交替读入的缓冲区，通常我们设置每个缓冲器长度为N（4096）字节，只要我们从不需要越过实际的词素向前看的很远，以至于这个词素的长度加上我们向前看的距离大于N，我们就决不会在识别这个词素之前覆盖掉这个尚在缓冲区的词素

2. 哨兵标记

如果我们采用上一节中描述的方案，那么每次在向前移动forward指针时，我们都必须检查是否达到了缓冲器末尾，若是，那么我们需要加载另一个缓冲区。因此每读入一个字符，我们都需要做两次测试：一次是检查是否达到缓冲区末尾？一次是确定读入的字符是什么？

如果我们扩展缓冲区，使他们在末尾包含一个“哨兵”，我们就可以把缓冲区末端的测试合二为一，这个哨兵字符是一个不会在源程序中出现的特殊字符，一个自然的选择就是”eof“，具体优化代码如下:

switch(*forward++) {
  case eof:
      if (forward 在第一个缓冲区末尾) {
        装载第二个缓冲区；
        forward = 第二个缓冲区的开头
      }
      else if (forward 在第二个缓冲区末尾) {
        装载第一个缓冲区；
        forward = 第二个缓冲区的开头
      }
     else break;
   其他字符情况
}

词法单元的规约

正则表达式是一种用于描述词素模式的重要表示方法，虽然正则表达式不能表达出所有可能的模式，但是他们可以高效的描述在处理词法单元时需要用到的模式类型

1、串和语言

串

语言

2、语言上的运算

语法分析中最重要的语言上的运算时并、连接和闭包运算，并运算是常见的集合运算。语言的连接运算就是以各种可能的方式，从第一个语言中任取一个串，在从第二个语言中任取一个串，然后将他们连接后得到所有窜的集合。一个语言L的Kleene闭包（closure），记为L*，就是将L连接0次或者多次得到的串集。注意，L0，即”将L连接0次得到的集合“，被定义为空，同时，L的正闭包和Kleen闭包基本相同，只是不包含L0

3、正则表达式

人们常常利用一种称之为正则表达式的表示方法来描述语言，正则表达式可以描述所有通过对某个字母表上符号应用这些运算符而得到的语言。

4、正则定义

为了方便表示，我们可能希望给某些正则表达式命名，并在之后的正则表达式中像使用符号一样使用这些名字。那么我们定义了一些如下的定义序列，我们称之为正则定义

5、正则表达式的扩展

一个或者多个实例，单目后缀运算符+表示一个正则表达式及其语言的正闭包
零个或者一个实例，单目后缀运算符？
字符类，一个正则表达式如a|b|c|d|e 可以缩写成为[a-e]

词法单元的识别

我们通过正则描述单个词法模式用来匹配词素，并且我们将模式转化为具有特定风格的流图，我们称之为状态转化图

1、状态转化图

2、保留字和标识字符的识别

我们可以使用两种方式来处理那些看起来很想标识符的保留字

（1）初始化时就将各个保留字填入符号表中，符号表条目的某个字段会指明这些串并不是普通的标识符，并指出他们所代表的词法单元。

（2）为每个关键字建立单独的状态转化图，如果采用这种方式，我们必须设定词法单元之间的优先级，使得当一个词素同时匹配id的模式和关键字的模式时，优先识别保留字词法单元，而不是id词法单元

3、例子

我们将建立一个无符号数字的状态转化图，如下

4、relop的转化图的概要实现

图3-13 词法单元relop的状态转化图

TOKEN getRelop() {
  TOKEN retToken = new(RELOP);
  while(1) {
    switch(state) {
      case 0: c = nextChar();
            if(c == '<') state = 1;
        else if (c == '=') state = 5;
        else if (c == '>') state = 6;
        else fail();
        break;
      case 1: .....
      ....
      case 8: retract();
                    retToken.attribute = GT;
                    return(retToken)
    }
  }
}

为了适当的地方模拟适当的状态转化图，我们考虑几种将如图代码集成到整个词法分析器中的方法

（1）我们可以让词法分析器顺序的尝试各个词法单元的状态转化图，然后，在每次调用fail()时，它重置forward指针并启动下一个状态转化图

（2）我们可以并行的运行各个状态转化图，同时存在多个匹配的情况，整体时取最长的和某个模式相匹配的输入前缀

（3）将所有的状态转化图合并为一个图，我们允许合并后的状态尽量读取输入，知道不存在下一个状态为止，然后取最长的和某个模式相匹配的前缀（后续最常用）

词法分析器生成工具Lex

这个工具在最近的实现中也称之为Flex，它支持使用正则表达式来描述各个词法单元的模式。Lex工具输入表示方法称之为Lex语言，而工具本身称之为Lex编译器，在它核心部分，Lex编译器将输入的模式转化为一个状态转化图，并生成相应的实现代码，并存放到文件lex.yy.c中。

在计算机科学里面，lex是一个产生词法分析器（lexical analyzer，"扫描仪"（scanners）或者"lexers"）的程序。[1][2] Lex常常与yacc 语法分析器产生程序（parser generator）一起使用。Lex(最早是埃里克·施密特和迈克·莱斯克制作）是许多UNIX系统的标准词法分析器（lexical analyzer）产生程序，而且这个工具所作的行为被详列为POSIX标准的一部分。 Lex读进一个代表词法分析器规则的输入字符串流，然后输出以C语言实做的词法分析器源代码。

1、Lex的使用

2、Lex程序的结构

3、Lex中冲突的解决

当输入多个前缀与一个或者多个模式匹配时，Lex用如下规则选择正确的词素

（1）总是选择最长的前缀

（2）如果最长的可能前缀与多个模式匹配，总是选择在Lex程序中最先被列出的模式

4、向前看运算符

某些时候，我们希望仅当词素的后面跟随着特定的其他字符时，这个词素才能和某个特定模式相匹配，在这种情况下，我们可以在模式中用斜线来指明该模式中和词素实际匹配的部分的结尾，斜线之后的内容表示一个附加的模式，只有附加模式和输入匹配之后，我们才可以确定已经看到了要寻找的词法单元的词素，但是和这个第二个模式匹配的字符并不是这个词素的一部分

有穷自动机

现在我们揭示Lex是如何将它的输入程序变成一个词法分析器，转化的核心是被称之为有穷自动机（finite automata）的表示方法，这些自动机在本质上是与状态转化图类似的图，但是有几点不同

（1）有穷状态机是识别器，他们只能对每个可能的输入串简单的回答”是“或”否“

（2）有穷状态机分为两类：

不确定的有穷自动机（Nondeterministic Finite Automata, NFA）对其边上的标号没有任何限制，一个符号标记离开同一状态的多条边，并且空串也可以作为标号
对于每个状态及自动机输入字母表中每个符号，确定的有穷自动机（Deterministic Finite Automata，DFA）有且只有一条离开该状态、以该符号为标号的边

从正则表达式到自动机

如何将NFA转化为DFA
如何将正则表达式转化为NFA

1、从NFA到DFA的转化

这个我们称之为子集构造算法，基本思想是：让构造得到的DFA的每个状态对应于NFA的一个状态集合，DFA的状态有可能是NFA状态的指数，然而基于自动机的词法分析方法的处理能力来源如下事实：对于一个真实的语言，它的NFA和DFA的状态数量大致相同，状态数量呈指数关系的情形尚未在实践中出现过，具体实现算法如下（算法3.20）

2、NFA的模拟

许多文本编辑程序使用的策略是根据一个正则表达式构造出相应的NFA，然后使用类似于on-the-fly（即边构造边使用的）的子集构造法来模拟这个NFA的执行。如图3-37所示

3、NFA模拟的效率

4、从正则表达式构造NFA

现在我们给出一个算法，他可以将任意正则表达式转化为一个接受相同语言的NFA，这个算法名称为：McMaugthon-Yamada-Thompson算法，算法的基本思路如下：

首先对正则表达式进行语法分析，分解出组成它的子表达式。构造一个NFA的规则分为基本规则和归纳规则，基本规则处理不包含运算符的子表达式，而归纳规则则根据一个给定的表达式的直接子表达式的NFA构造出这个表达式的NFA

5、字符串处理算法的效率

支持使用NFA模拟的论据之一是子集构造法在最坏的情况下可能会使状态个数呈指数增长，虽然原则上DFA的状态数不会影响算法的运行时间，但是假如状态数大到一定程度，以至于转化表超过了主存容量时，那么真正的运行时间就必须加上磁盘读写时间，从而使运行时间显著增加

词法分析器生成工具的设计

我们将讨论两种分别基于NFA和DFA的方法，后者实际上就是Lex的实现

1、生成词法分析器的结构

表示自动机的一个转化表
由Lex编译器从Lex程序中直接拷贝到输出文件的函数
输入程序定义的动作，这些动作是一些代码片段，将在适当的时候由自动机模拟器调用

在构建自动机时，我们首先用算法将Lex程序中每个正则表达式模式转化为一个NFA，我们需要使用一个自动机来识别所有与Lex程序中模拟相匹配的词素，因此我们将这些NFA合并为一个NFA，合并的方法是引入一个新的开始状态，从这个新的开始状态到各个对应与模式Pi的NFA Ni的开始状态有一个空转化

2、基于NFA的模式匹配

和前面寻找词素相同

3、词法分析器使用的DFA

另一种体系结构和Lex的输出相似，但是它使用子集构造法将表示所有的模式转化为等价的DFA。在DFA的每个状态中，如果该状态包含一个或者多个NFA的接受状态，那么就要确定那些模式的接受状态出现在此DFA状态中，并找出第一个这样的模式，然后将该模式作为这个DFA状态的输出

4、实现向前看运算符

实际上，这个末尾是在此NFA进入满足如下条件的状态s的地方

s在（假想上）/有一个空转化
有一条从NFA的开始状态到状态s的路径
有一条从s到NFA接受状态上的路径
在所有满足条件1~3的xy中x尽可能的长

基于DFA的模式匹配器的优化

第一个优化直接用于Lex编译器，直接通过正则表达式生成DFA
第二个优化是优化生成的DFA，将任何具有相同未来行为的多个状态合并，从而使该DFA的状态数量减到最少
第三个算法是生成比标准二维表更加紧凑的转化表的表示方式

1、NFA的重要状态

在谈第一个优化的时候我们需要分析生成的NFA过程，如果一个NFA状态有一个标号为非空的离开状态，那么我们就称这个状态时重要状态，同时，两个NFA状态集合可以被认为一致的条件是他们：

具有相同的重要状态
要么都包含接受状态，要么都不包含接受状态

2、根据抽象语法树计算得到的函数

3、根据正则表达式构建DFA

4、最小化一个DFA的状态数

5、词法分析器的状态最小化

词法分析器中生成的DFA具有多个，初始分划

6、DFA模拟中的时间和空间权衡

由于词法分析器的DFA中通常包含数百个状态，并且涉及到ASCII字母表中的128个字符，因此这个数组需要的空闲时间少于一兆字节。但是在一些小型的设备找那个也可能使用编译器，对于这些设备来说，即使一兆的内存也显得太大了，对于这种情况，可以应用很多方法来压缩转化表

（1）可以使用一个转化链表来表示每个状态，这个转化链表由字符-状态对组成。我们在链表的最后存放一个默认状态：对于没有出现在这个链表中的字符，我们总是选择这个状态作为目标状态

（2）第二个数据结构，即利用了数组的表示法的访问速度，又利用了带默认值的链表的压缩特性。

Genluo / Precipitation-and-Summary