Lexical Analysis

3.1 The Role of the Lexical Analyzer

作为编译的第一阶段，词法分析器的主要任务是读取源程序的输入字符，将它们分组为lexemes，然后为源程序中的每一个词位产生一系列标记作为输出。标记流被送到解析器进行语法分析。词法分析器通常也与symbol table交互。当词法分析器发现构成标识符的lexeme时，它需要将该lexeme输入到symbol table中去。有些时候，词法分析器可以从符号表中读取某种标识符，以帮助它确定必须传递给解析器的正确标记。
这些交互被展示在Fig. 3.1中。通常，交互是通过让解析器用词法分析器来实现的。该调用由getNextToken命令发起，它使词法分析器从其输入中读取字符，直到它可以识别下一个lexeme并为其生成下一个标识，并将其分别返回给解析器。

Fig 3.1 Interactions between the lexical analyzer and the parser

由于词法分析器是编译过程中读取源文本的一部分，因此除了lexemes识别之外，它还可以执行其他任务。其中一个这样的任务就是去掉注释和空格（blank,newline,tab 和一些其他的用于在输入中分隔标记的字符）。另一个任务就是将编译器生成的错误信息与源程序关联起来。例如，词法分析器可以跟踪看到的换行字符的数量，因此它可以将行号与每个错误消息相关联。在某些编译器中，词法分析器复制源程序，并在适当的位置插入错误信息。如果源程序使用宏预处理器(macro-preprocessor)，则宏的扩展也可以由词法分析器执行。
有时，词法分析器被分为两个过程的级联：
a) 扫描(Scanning)由简单的过程组成，这些过程不需要输入的标记化，例如删除注释和将连续的空格字符压缩为一个。
b) 词法分析(Lexical analysis)本身是更复杂的部分，扫描器在这里生成标记序列作为输出。

3.1.1 Lexical Analysis Versus Parsing

通常将编译器的分析阶段分为词法分析和句法分析两个阶段的原因有很多。

1. 设计的简单性是最重要的考量。词法和语法分析的分离通常允许我们简化这些任务中的至少一个。比如，一个解析器必须将注释和空格作为语法单元处理，必然比一个在词法分析器中就将它们移除了的解析器要复杂。如果我们要设计一种新的语言，那么将词法和语法问题分离的可以带来更清晰的整体语言设计。
2. 编译的效率会提高。一个分离的词法分析器允许我们应用专门的技术，这些技术只服务于词法任务，而不是解析任务。
   3.编译器的可移植性得到了加强。特定于输入设备的特性可以仅限于词法分析器。

3.1.2 Tokens, Patterns, and Lexemes

在讨论词法分析器时，会使用到的三个相关但不同的术语：

• token：一个token是一个token名称和可选属性值组成的一对。token的名字是一种抽象符号，表示一种词汇单位，例如，一个特定的关键字，或表示标识符的输入字符序列。token是解析器处理的输入符号。在下面的内容中，我们通常用黑体字写一个token的名称。我们通常用token name来指代它。
  -* pattern*:pattern是对token的lexeme可能采用的形式的描述。在将关键字作为token的情况下，pattern只是构成关键字的字符序列。对于表示符和一些其他标记，pattern是由许多字符串匹配的更复杂的结构。
• lexeme：lexeme是源程序中与标记模式匹配的字符序列，由词法分析器标识为该标记的实例。
  Example 3.1:Figture 3.2给出了一些典型的tokens，它们的非正式的patterns和一些示范lexemes。看它们在C语言的描述中是如何使用的：

printf("Total = %d\n",score);

• both printf and score are lexemes matching the pattern for token id,and "Total = %d\n" is a lexeme matching literal.(这是什么意思？)
  在许多编程语言中，以下的类涵盖了大量或全部的tokens：
  Figture 3.2: Examples of tokens

1. 每个关键字一个token。关键字的pattern与关键字本身相同。
2. 运算符的tokens，可以是单独的也可以是分类的，如Figture 3.2中提到的token comparison
3. 一个代表所有标识符的token
4. 一个或多个代表常量的标记，如numbers和literal strings
5. 每个标点符号的token，如左括号和右括号、逗号和分号

3.1.3 Attributes for Tokens

当一个以上的lexeme可以匹配一个pattern时，词法分析器必须为后续的编译器阶段提供有关匹配的特定词素的其他信息。例如，number的pattern同时匹配0和1，但是对于代码生成器来说，知道在源程序中找到了哪个lexeme是极其重要的。因此，在许多情况下，词法分析器不仅仅返回给解析器一个token name还有一个用来描述token代表的lexeme的属性值(attribute value)。token name影响解析决策，而属性值影响解析后的tokens转换。我们假设tokens至多有一个关联属性值，尽管此属性可能具有组合多条信息的结构。最重要的例子是token id,我们需要将大量信息与token相关联。一般来说，有关于一个标识符的信息，比如：它的lexeme，它的type，和首次找到它的位置（以防必须发出关于改识别符的错误信息），保存在symbol table中。因此，标识符的适当属性值是指向该标识符的符号表条目的指针。

• 识别Tokens时的棘手问题
  通常，给定描述标记lexeme的pattern，当匹配的lexeme出现在输入时识别它们相对简单。然后，在一些语言中，当我们看到的是一个对应于token的lexeme实例时，这并不是一目了然的。下面的实例取自Fortran,采用Fortran90中仍然允许的固定模式

DO 5 I = 1.25

直到我们看到1后面的圆点，才能明显看出第一个lexeme是D05I，这是标识符标记的实例。请注意，固定格式的Fortran中的空格将被忽略（这是一种过时的约定）。如果我们看到的不是圆点而是一个逗号，我们就会有一个do-语句

DO 5 I=1,25

在这里第一个lexeme的关键字就是DO。

Example 3.2：对于Fortran表达的token name 和相关联的属性值

E = M * C ** 2

以成对序列的形式写在下面:
<id,pointer to symbol-table entry for E>
<assign_op>
<id,pointer to symbol-table entry for M>
<mult_op>
<id,pointer to symbol-table entry for C>
<exp_op>
<number,integer value 2>

注意到，在一些特定的对里面，特别是运算符、标点符号和关键字，是没有必要有一个属性值的。在这个例子中，token number被给予了一个整数值的属性值。在实际中，一个典型的编译器会存储表示常量的字符串，并将其用作对指向该字符串的指针的属性值。(这地方不太懂)

3.1.4 Lexical Errors

对于词法分析器来说没有其他部件的帮助去找到一个源程序中的错误是非常困难的。例如，在上下文的C程序中第一次遇到字符串fi：

fi ( a == f(x))  ...

词法分析器无法判别fi是一个拼写错误的关键字if还是一个未声明的函数标识符fi。因为fi对token id来说是一个有效的lexeme，词法分析器必须返回token id给解析器并让一些编译的其他阶段——在这个例子中也许是解析器，去处理这个由于字母调换而造成的错误。
然而，假设出现词法分析器无法继续的情况，因为没有一个标记的模式与剩余输入的任何前缀匹配。最简单的恢复策略是"panic mode"恢复。我们删除剩余输入的连续字符，直到词法分析器可以在剩余输入的开头找到格式良好的标记。这种恢复技术或许会使解析器感到困惑，但在交互式计算环境中，它可能已经足够了。
其他可能的错误恢复动作：

1. 从剩下的输入中删除一个字符。
2. 向剩下的输入中插入一个丢失的字符。
3. 用一个其他的字符替换一个字符。
4. 调换两个相邻的字符。
   可以尝试这样的转换来尝试修复输入。最简单的这类策略是查看是否可以通过一次转换将剩余输入的前缀转换为有效的lexeme。这种策略是有意义的，因为实际上大多数词汇错误都涉及单个字符。一种更一般的纠正策略是找到将源程序转换为只包含有效lexeme的程序所需的最少转换次数，但这种方法在实践中被认为代价太高，不值得努力。

3.3 Specification of Tokens

正则表达式(regular expression)是指定lexeme pattern的一个重要符号。当他们不能表示所有可能的模式时，它们在验证我们实际需要用于tokens的那些类型的模式时非常有效。在本节中我们将研究正则表达式的形式化表示法，在3.5节中，我们将了解如何在词法分析器生成器中使用这些表达式。然后，第3.7节将展示如何通过将正则表达式转换为执行指定标记识别的自动机来构建词法分析器。

3.3.1 Strings and Languages

字母表是任何有限的符号集。符号的典型例子有字母、数字和标点符号。集合{0，1}是二进制字母表。ASCII是一个重要的字母表的例子，它通常被用在许多软件系统中。Unicode包含来自世界各地的字母表中的大约1000,000个字符，它是字母表的另一个重要的例子。字母表上的字符串是从该字母表中提取的有限符号序列。在语言理论中"sentence"和"word"经常被用作"string"的同义词。字符串s的长度，通常被写作|s|,是符号在s中出现的次数。比如，banana是一个长度为6的字符串。表示为ε的空字符串，是长度为0的字符串。
语言是固定字母表上的任意可数字符串集。这个定义非常宽泛。像0（空集）或{ε}（只包含空字符串的集合）这样的抽象语言就是这个定义下的语言。因此，所有语法上格式正确的C程序集合以及所有语法正确的英语句子的集合也是如此，尽管后两种语言很难准确指定。请注意，“language”的定义并不要求将任何意义归因于该语言的字符串。Chapter 5讨论了定义字符串意义的方法。
如果x和y是字符串，则x和y的串联（表示为xy）是将y附加到x形成的字符串。比如x=dog，y=house，那么xy=doghouse。和空字符串有关的串联，对于任何字符串s来说，εs=sε=s。
如果我们把串联看作一个乘积，我们可以定义字符串的“指数化”，如下例所示。Define S⁰ to be ε, and for all i > 0, define s^​i to be s ^{i- ​1}s.
Since εS= s, it follows that s¹= s. Then s^​2 = SS, s³ = sss, and so on.

3.3.2 Operations on Languages

在词法分析中，对语言而言最重要的操作是并集(union)、连接(concatenation)和闭包(closure)，这些操作在Fig.3.6中有正式的定义。并集是在集合上的操作。语言的连接是通过以所有可能的方式获取来自第一种语言的字符串和第二种语言的字符串并将它们连接在一起而形成的所有字符串。语言L的闭包（Kleene），表示为L，是通过串联0次L或更多次而得到的字符串集。注意到L⁰，即“L的零次串联”，被定义为{ε}，而且归纳起来，Lⁱ就是L^i-1L。最后正闭包表示为L⁺与Kleene闭包相同，但没有L⁰这一项。也就是说除非ε本身在L中，否则ε不会在L+中。

Figure 3.6: Definitions of operations on languages
Example 3.3：L是字母集合{A,B,...,Z,a,b,...,z}，D是数字集合{0,1,,...,9}.我们可以用两种相同的方式来考虑L和D，本质上是等价的。一种方法是L和D分别是大写字母和小写字母以及数字的字母表。第二种方法是L和D都是语言，它们的字符串长度恰好都为1。这里有一些其他的语言，可以从L和D*使用Figture 3.6中的运算符进行构造。

1. LD是字母和数字的集合，严格地说是一种语言，有62个字符串，每个字符串都是一个字母或一个数字。
2. LD是一个由520个长度为2的字符串组成的集合，每个字符串由一个字母后面跟一个数字组成。
3. L⁴是所有四个字母的字符串的集合。
4. L^*是所有由字母组成的字符串的集合，包括空字符串ε。
5. L(L D)^*是以字母开头的所有字母和数字字符串的集合。
6. D⁺是一个或多个数字的所有字符串的集合。

3.3.3 Regular Expressions

假设我们要描述一组有效的C标识符。它几乎是上面第(5)项中描述的语言；唯一的区别是字母之间包含下划线。
在示例3.3中我们能够通过给字母和数字的集合命名，并使用语言操作符做并集、连接、和闭包来描述标识符。这一过程非常有用，以至于一种称为正则表达式的符号已被广泛使用，用于描述可以从应用于某些字母符号的这些运算符构建的所有语言。在这种表示法中，如果letter _ 表示任何字母或下划线，digit _ 表示表示任何数字，那么我们能够通过以下方式描述C标识符的语言：
letter_(letter_|digit)^*
上面的竖线表示union，括号用于分组子表达式，星号表示“零次或多次出现”，letter_与表达式其余部分并列表示连接。
正则表达式是使用下面描述的规则从较小的正则表达式递归构建的。每个正则表达式r表示语言L(r),它也是从r的子表达式表示的语言递归定义的。下面是在上定义正则表达式的规则和一些字母表∑。以及这些表达式所表示的语言。
基础：这里有两个规则构成基础：

1. ε是一个正规表达式，L(ε)是{ε}，即唯一的成员是空字符串的语言。
2. 如果a是∑中符号，则a是正则表达式，且L(a)={a},是具有一个长度为1的字符串的语言，其中a在一个位置。注意，按照惯例，我们用斜体表示符号，用粗体表示相应的正则表达式。
   归纳法：归纳法有四个部分，其中较大的正则表达式是从较小的正则表达式中生成的。假设r和s分别是语言L(r)和L(s)的正则表达式。
3. (r)|(s)是一个正则表达式代表语言L(r)L(s)
4. (r)(s)是一个正则表达式代表语言L(r)L(s)
5. (r)是一个正则表达式代表语言(L(r))
6. (r)是一个正则表达式代表语言L(r)。最后一条是说我们可以在表达式周围添加额外的括号对，而不必更改它们所表示的语言。

正如定义的那样，正则表达式通常包含不必要的参数对。如果我们采用如下的规定，我们可能会丢弃某些括号对：
a) 一元运算符具有最高优先级，并且是左结合的。
b) 连接具有第二高优先级，并且是左结合的。
c) |的优先级是最低的，而且是左结合的。
在这些约定下，举个例子，我们可以将正则表达式(a)|((b)c)替换为a|b^*c。这两个表达式都表示一组字符串，它们要么是一个单独的a，要么是0个或多个b，然后是一个c。
Example 3.4：让∑={a,b}

1. 正则表达式a|b 代表语言{a,b}
2. (a|b)(a|b)代表{aa,ab,ba,bb},字母表∑上所有长度为2的字符串的语言。同一个语言的另一个正则表达式是aa|ab|ba|bb
3. a^*代表0个或多个a的所有字符串组成的语言，即{ε,a,aa,aaa...}
4. (a|b)表示由a或b的零个或多个实例组成的所有字符串的集合，即a和b的所有字符串：{ε,a,b,aa,ab,ba,bb,aaa,...}。同一个语言的另一个正则表达式是(ab).
5. a|a^*代表语言{a,b,ab,aab,aaab,...},也就是说，字符串a和所有由0个或多个a组成并以b结尾的字符串。

能用正则表达式定义的语言就被称为regular set（正则集），如果两个正则表达式r和s表示相同的正则集，我们说它们是等价的，记为r=s。例如，(a|b)=(b|a)。正则表达式有许多代数定律，每一定律都断言两种不同形式的表达式是等价。Figture 3.7中显示了适用于任意正则表达r、s和t的一些代数定律。

Figture 3.7:Algebraic laws for regular expression

3.3.4 Regular Definitions

为了便于标注，我们可能希望给某些常规表达式命名，并在后续表达式中使用这些名称，就好像这些名称本身就是符号一样。如果∑是一个基本符号的字母表，那么一个常规定义就是一系列形式定义：
d1 ——> r1
d2 ——> r2
...
dn ——> rn
这里：

1. 每个d_{i<>是一个新符号，不在∑中，也不与任何其他d相同，并且}
2. 每个ri是字母表∑ {d₁,d₂,...,d_i-1}

通过将ri限制为∑和先前定义的d's，我们避免了递归定义，并且我们可以仅在∑上构造正则表达式，对于每个ri，我们首先在R2中替换d1的用法（它不能使用d's，除了d1），然后用r1和（被替换的）r2替换r3中的d1和d2，以此类推。最后，在rn中，对于i=1，2，...，n-1我们替换每个di,由替换版本的ri表示，每个版本只有∑的符号。

3.3.5 Extensions of Regular Expressions

自从Kleene在20世纪50年代引入了带有union、concatenation和kleene闭包的基本运算符的正则表达式以来，许多扩展被添加到正则表达式中，以增强他们指定字符串模式的能力。在这里，我们提到最初并入unix实用程序（如Lex）中的一些符号扩展，它们在规范词法分析器中特别有用。本章的参考文献包含对目前使用的一些正则表达式变体的讨论。

1. 一个或多个实例。一元后缀运算符⁺表示正则表达式及其语言的正闭包。也就是说，如果r是正则表达式，那么(r)⁺表示语言(L(r))⁺。运算符⁺与运算符具有相同的优先级和关联性。两个有用的代数定律r=r⁺ε和r⁺=rr=rr将Kleene闭包和正闭包联系起来。
2. 零个或一个实例。一元后缀运算符？代表“零次或一次事件”。那就是，r?等价于r|ε,或者换句话说，L(r?)=L(R){ε}。？运算符与^*和⁺具有相同的优先级和结合性。
3. 字符类。正则表达式a₁|a₂|...a_n,其中a_i的每个都是字母表的符号，可以由速记[a₁a₂...a_n]代替。更重要的是，当a₁a₂...a_n形成了一种逻辑序列，如连续的大写字母、小写字母或数字，我们可以用a₁-a_n替换它们，也就是说，只有第一个和最后一个用连字符隔开。因此，[abc]是a|b|c的简写，而[a-z]是a|b|...|z的简写。
   Example 3.7:使用这些简写，我们可以将例3.5中的常规定义重写：
   letter_ ——> [A-Z a-z]
   digit ——> [0-9]
   id ——>letter_(letter|digit)
   3.6中的常规定义也可以被简化：
   digit ——> [0-9]
   digits ——>digit⁺
   number ——> digits(.digits*)?(E[+-]? digits)?