编译器入门指南（一）：词法分析与扫描器

我进入编译器世界的旅程，始于我想弄清楚依赖静态代码分析的 Angular AOT 编译究竟是怎么工作的。调试一番之后我发现它严重依赖 TypeScript 编译器，于是就开始了对它的逆向工程之旅。 有意思的是，大多数编译器都是基于同一套原理实现的，这些原理统称为编译器理论。 想理解一个编译器的内部机制，扎实掌握这套理论是不可或缺的。

本文是系列文章的第一篇，这个系列会总结我在逆向 TypeScript 编译器过程中学到的一切。这里我会介绍理解每个编译器第一阶段——词法分析——所需的重要概念。文章只包含最低限度的理论和形式化内容，但最终还是以理论为主。最后一章我会展示 TypeScript 扫描器是如何实现的，并给出相关链接。

TypeScript 的文法基于 ECMAScript（JavaScript）规范，我希望你能好奇到愿意顺着文中的链接去熟悉一下规范。如果你这么做了，你应该就能读懂文法，并在 MDN 讲解之前很久就学会 JavaScript 新特性的语法。如果你能读到文章结尾，可以自我检验一下：试着理解装饰器规范中描述的装饰器语法。

文章相当长，因此并不适合一口气读完。一点一点读，给这些概念留出在脑中沉淀的时间。如果你一直想学会读 ECMAScript 规范，或者想理解编译器（扫描器）是怎么工作的，这篇文章就是为你写的。

通用阶段

编译器是把用一种语言写的程序翻译成另一种语言程序的计算机程序。编译器必须先理解它作为输入接收的源语言程序，然后把它的功能映射到目标语言程序上。由于这两项任务性质迥异，把编译器的功能拆成两大块是合理的：前端（front-end）和后端（back-end）。前者的主要任务是理解源语言程序，后者则专注于把它转换成目标语言程序。

每一块都由若干阶段依次组成，每个阶段从上一阶段取得输入，对其加以修改，产出自己那一份源程序表示，再传给下一阶段。前端包括三个主要阶段，分别叫做词法分析、语法分析和语义分析。第一个阶段把源代码当作字符流，识别出其中一个个独立的词（token），例如变量名、关键字和标点符号。第二个阶段判定程序的语法组织是否合法，并生成抽象语法树（AST）。语义分析则检查 AST 是否遵循语言的规则（类型检查、名称解析）。

本文关注的是第一个阶段——词法分析——以及它的主角：扫描器（scanner），又称识别器（recognizer）。

形式语言与文法

在进入扫描器的实现之前，有必要先聊一点自然语言、形式语言以及它们的文法。自然语言，比如英语或法语，主要用于交流，是自然演化而来的。形式语言则相反，是人们为特定用途设计出来的——编程语言用来表达计算，数学记号用来表示数之间的关系，等等。

自然语言和形式语言都可以用文法来描述。文法是一组规则，描述如何把符号——字符、词（token）或句子（语句）——组合成符合该语言语法的序列。自然语言的文法极其复杂，只能通过实证研究去发现。而形式语言的文法（形式文法）通常相当简单，可以按我们的需要来定义。根据我们想为哪一类符号定义规则，可以区分出几种文法类型。

词法文法描述语言词汇表的结构，也就是该语言中所有能使用的 token（词）。例如在 JavaScript 中，\ 和 d 都属于该语言的字母表，但文法并没有定义任何规则，能让紧跟着 d 的 \ 在正则表达式字面量之外被识别为一个合法 token，所以如果你执行下面这段代码 \d，就会得到「无效 token」的语法错误：

\d
Uncaught SyntaxError: Invalid or unexpected token

句法文法定义语言的结构，也就是 token（词）可以怎样排列以构成语句（句子）。例如 JavaScript 的词法文法定义了 var 和 const 两个 token，但并没有规则说 var 后面可以跟 const，所以如果你执行下面这段代码，就会得到「意外 token」的语法错误：

var const
Uncaught SyntaxError: Unexpected token const

按照 ECMAScript 的句法文法，这是一条结构上非法的语句，因此编译器并不期望在我们上面写的语句里 const 这个 token 紧跟在 var 之后。也请注意错误消息中 unexpected（意外的）与 invalid（无效的）之间的区别。

词法分析

词法分析是编译器理解输入程序所用的三段式流程中的第一个阶段。词法分析的职责是把程序源代码切分成称为 token 的子串，并按各自的角色（token 类别）对每个 token 加以分类。执行这项分析的程序叫做扫描器或词法分析器。它读取字符流，并按照词法文法（也称为词法规范）定义的规则把字符组合成 token。如果没有规则定义某个特定的字符序列，扫描器就报错。我们那个示例字符串 \d 正是如此，它产生了 Invalid or unexpected token 语法错误。

对每个识别出的 token，扫描器都会依据文法给它指定一个句法类别。ECMAScript 的类别（即 token 类）列表相当长，其中包括 Identifier、NumericLiteral、StringLiteral 等类别，以及 ConstKeyword、LetKeyword、IfKeyword 等各种关键字。

所以词法分析阶段的输出通常是一串 token，每个 token 都有一个关联的类别和一个子串，后者通常称为词素（lexeme）：

{class: SyntaxKind.ConstKeyword, lexeme: 'const'}

如果你好奇 ECMAScript 定义了哪些 token，可以看 TypeScript 实现中的 SyntaxKind 枚举（看到 // Parse tree nodes 注释为止）。

词法分析器可以实现为扫描整个源程序并产出完整的 token 序列，也可以实现为逐步扫描、一次识别一个 token。在解析器运行之前就把整个源程序转成 token 数组的扫描器相当少见，因为那样会白白消耗内存。所以扫描器通常实现为只在解析器请求时才产出 token，TypeScript 的扫描器也是如此。TS 扫描器还有另一个有趣之处。JavaScript 的语法定义了几种会带来解析歧义的语言构造，例如正则表达式和模板字面量，于是扫描器可能会根据解析上下文识别出不同的 token 集合。由于这个解析上下文是解析器在请求 token 时设定的，某种意义上可以说 TS 扫描器是由解析器驱动的。我会在「多个目标符号」一节解释这个语言上的微妙之处。

定义 token

我们用 JavaScript 中声明变量这个熟悉的例子，来演示文法规则是怎么起作用的。在 JavaScript 中我们可以像这样用 const 声明来声明一个变量：

const v = 3

为简化起见，假设初始化值只能是数值字面量。看这段源代码时，你清楚地看到 const 这个词声明了变量 v、赋值运算符 =，以及作为变量初始值的数值字面量 3。不出意外，扫描器可不是这么看的。由于 ECMAScript 用 Unicode 符号来定义程序源码，编译器看到的是下面这串码点：

c   o    n    s    t        v        =       3
99, 111, 110, 115, 116, 32, 118, 32, 61, 32, 51

现在它的任务是把这个表达式切分成 token 并加以归类，于是产出下面这份 token 列表：

{class: SyntaxKind.ConstKeyword, lexeme: 'const'}
{class: SyntaxKind.Identifier, lexeme: 'v'}
{class: SyntaxKind.EqualsToken, lexeme: '='}
{class: SyntaxKind.NumericLiteral, lexeme: '3'}

如果我们用的是 let 而不是 const，第一个 token 就会是 SyntaxKind.LetKeyword。token 一被识别出来，扫描器就把它的值（词素）存进 tokenValue 属性，可以通过 getTokenValue 方法访问。

正则文法

ECMAScript 用正则文法来定义把 Unicode 符号输入识别为 token 的规则。按乔姆斯基文法分类，正则文法是限制最强、表达能力最弱的一类。它只适合描述 token 可以怎样构造，不能用来描述句子结构。不过，对文法的限制越多，描述和解析起来就越容易。而既然本章我们关心的是定义和解析 token，那它就是最理想的文法。

在本系列的下一篇文章中，我们会认识上下文无关文法（类型 2）。这类文法允许递归构造，用于定义程序（语句）的结构。乔姆斯基分类中另外两类文法——无限制文法和上下文相关文法——比类型 2 和 3 更强大，但实用性差得多，因为我们无法为它们构造高效的解析器。

要指出的是，大多数教学材料在讲解扫描器时并不使用正则文法，而是用正则表达式来给出词法规范。不过，既然 ECMAScript 为此用的是正则文法，本文我就按正则文法来讲。

熟悉文法

现在我们来看看，怎样构造出帮助 TypeScript 识别上面那份 token 列表的文法和规则。这里再给出一次——我们需要为语句中的每个 token 定义识别规则：

const v = 3
{class: SyntaxKind.ConstKeyword, lexeme: 'const'}
{class: SyntaxKind.Identifier, lexeme: 'v'}
{class: SyntaxKind.EqualsToken, lexeme: '='}
{class: SyntaxKind.NumericLiteral, lexeme: '3'}

文法中的每条规则都用产生式（production）来定义。产生式是一条替换规则，规定可以递归执行哪些替换来生成新的符号序列。在 JavaScript 中我们可以用 const 或 let 这两个 token 来声明变量，所以可以为符号 Keyword 定义如下规则：

Keyword ::
    const
    let

符号 Keyword 的这条规则有两个产生式（产生式规则），表示符号 Keyword 可以被替换成 const 或 let 字符串。Keyword 是一个人造变量，称为非终结符，意思是它有产生式、可以被替换（替换过程不会终止于它）。这些替换通常称为推导（derivation）。这个符号所拥有的产生式 const 和 let 称为终结符，因为它们没有任何推导。没有任何产生式的终结符，就是能在源程序中真正找到的那些字符串。人造的非终结符在文法中只用于定义替换规则，永远不会在源程序中被识别为合法 token。ECMAScript 还为非终结符 Keyword 定义了许多其他产生式，例如：if、else、for、do、while、function、class 等等。

为定义文法，ECMAScript 使用如下自定形式：

non_terminal_symbol ::
  symbol1 symbol2  （产生式规则 1：Symbol1，后面跟着 Symbol2）
  symbol3 symbol4  （产生式规则 2：Symbol3，后面跟着 Symbol4）

:: 左边的符号称为左部，右边的符号称为右部。对正则文法和上下文无关文法来说，产生式规则的左部只能是一个非终结符。右部则可以同时指定终结符和非终结符，不过正则文法受限于只能是以下两种之一：

  • 只有终结符
  • 或者终结符加上唯一一个非终结符，且它总在开头（左线性）或总在末尾（右线性）：
non_terminal_symbol ::
  terminal_symbol
non_terminal_symbol ::
  terminal_symbol non_terminal_symbol   （右线性）
non_terminal_symbol ::
  non_terminal_symbol terminal_symbol   （左线性）

上下文无关文法更宽松，允许右部有任意数量的终结符和非终结符。正则文法和上下文无关文法都可以为每个左部符号提供任意数量的可选项（产生式）：

non_terminal_symbol ::
  产生式规则 1
  产生式规则 2
  ...
  产生式规则 n

还有其他文法记法，例如巴科斯-诺尔范式（BNF），它使用如下语法：

nonterminal_symbol ::= symbol1 | symbol2

那么我们为 Keyword 写的文法规则就会写成：

Keyword ::= const | let

另一些替代记法把 ::= 换成 ->，规则就长这样：

Keyword -> const | let

在这一点上，ECMAScript 使用的是上面解释过的自定格式。文法记法的细节在 Grammar Notation 一节有描述，我强烈建议读一读。以下是一些重要片段：

终结符……以等宽字体显示，非终结符以斜体显示……该非终结符的一个或多个可选右部依次列在随后的各行……非终结符的定义由该非终结符的名字引出，后面跟着一个或多个冒号。ECMAScript 用双冒号表示词法文法，用单冒号表示句法文法。

应用产生式规则

对某个符号应用一条产生式规则，就是把该规则左部的一处出现替换成这条规则的右部。这么说有点绕，我们看个例子。假设你想定义一个由保留字组成的语言。这种语言的文法会从非终结符 ReservedWord 开始。ECMAScript 为它定义了如下产生式：

ReservedWord ::
  Keyword
  FutureReservedWord
  NullLiteral
  BooleanLiteral

但我们现在只限于 Keyword：

ReservedWord ::
  Keyword

前面我们这样定义了 Keyword 的文法：

Keyword ::
    const
    let

于是，先把 ReservedWord 替换成 Keyword，再把 Keyword 替换成它的产生式，我们就能得到一个只有两个词的语言——const 和 let。这样的语言我们称为有穷的，因为它最多只能包含 2 个不同的字符串。所有现存的语言都是无穷的，因为它们可以包含的组合数量是潜在无限的。等我们看到标识符的文法时，很快就会明白为什么会这样。

在上面的文法中，ReservedWord 称为起始符号，因为我们正是从这个符号开始生成字符串的。ECMAScript 文法定义了多个起始符号，并称之为目标符号（goal symbol）。文章后面我会解释为什么需要这样。

让我们从起始符号 ReservedWord 出发、最终得到字符串 const 或 let 的这个过程，称为推导（derivation）。某个文法下一个字符串的推导，是一串文法规则的应用，把起始符号变换成该字符串。推导证明了这个字符串属于该文法的语言。例如，我们知道 const 是一个合法表达式，因为 ReservedWord 可以展开为 Keyword，而每个 Keyword 都可以展开为字符串 const 或 let。

文法的递归本性

文法的递归本性可以用变量名来演示，在编译器语境里变量名通常称为标识符。如你所知，在我们的例子 const v = 3 中，变量名 v 被识别为 Identifier。ECMAScript 把 Identifier 定义为：

Identifier ::
    IdentifierName but not ReservedWord

这基本上是在告诉我们，保留字是 IdentifierName 的子集，因此识别标识符名和保留字的规则是一样的。这意味着扫描器一旦识别出 IdentifierName，如果它不在保留字之列，就应把它标记为 Identifier；否则就给它指定 ReservedWord 类别下相应的类。TypeScript 编译器在 getIdentifierToken 函数中干的正是这件事。保留字列表主要由我们上面见过的关键字组成，例如 const、let、if、else、for 等，再加上 null、true 和 false 这几个字面量。

那么 IdentifierName 的文法该怎么定义呢？你大概知道，某些字符（比如数字）不能出现在变量名开头，而名字本身却可以包含范围宽得多的字符集，数字也包括在内。所以需要把名字能以什么开头、能以什么继续区分开来。因此文法需要用两个依次排列的非终结符来定义：

IdentifierName ::
    IdentifierStart IdentifierPart

要注意的是，IdentifierStart 和 IdentifierPart 各表示标识符名中相应位置所用的 Unicode 码点集合中的单个字符。这里我不细说，如果你好奇，可以读读 Valid JavaScript variable names in ECMAScript 5。而既然 IdentifierStart 和 IdentifierPart 都展开为所定义字母表中的单个字符，上面这个定义就意味着任何 IdentifierName 名字都是两个字符长。这可不是我们想要的。如果你去看 ECMAScript 的文法，会看到下面这个定义：

IdentifierName ::
    IdentifierStart
    IdentifierName IdentifierPart

我们来拆解一下。第一个产生式说，标识符名可以是 IdentifierStart 所定义字符集中的一个字符那么长。如果你把第二个产生式递归推导几次，就会看到它可以展开成任意多的字符，以 IdentifierStart 开头，后面接着 IdentifierPart：

IdentifierStart IdentifierPart IdentifierPart … IdentifierPart

这正是递归派上用场的地方。通过把 IdentifierName 递归替换为第二个产生式 IdentifierName IdentifierPart，我们就能匹配任意长度的字符串。

有趣的是，某些文法记法引入了非标准的重复运算符，例如 * 或 {…}，那会得到这样的文法：

IdentifierName ::
    IdentifierStart IdentifierPart*
IdentifierName ::
    IdentifierStart {IdentifierPart}

空白字符的意义

对文法的某些部分来说，空白字符扮演着重要角色，帮助扫描器把一个 token 与另一个区分开。看看下面这段代码以及产生的 token：

newObject
{class: SyntaxKind.Identifier, lexeme: 'newObject'}

这里 newObject 被指定为 Identifier 类别。这是通过像上面那样递归推导 IdentifierPart 产生式做到的；由于 newObject 这个词中每个字符都落在 IdentifierPart 符号所定义的字符集内，扫描器就把整个字符串识别为一个单独的 token。再看另一个例子：

new Object
{class: SyntaxKind.NewKeyword, lexeme: 'new'}
{class: SyntaxKind.Identifier, lexeme: 'Object'}

现在字符虽然相同，但由于存在空格，它们被解析成了两个独立的 token。扫描器之所以能切分 token，是因为在推导 IdentifierPart 产生式时，它不把空格当作 IdentifierPart 的合法字符，于是产出词素为 new、长度 3 个字符的 IdentifierName token。接着它在关键字列表中查找 new 这个 token，并把它标记为 NewKeyword（这个查找我稍后解释）。

在其他时候，像 ( 这类不能用作 IdentifierPart 的字符也能帮助切分 token：

if(s=3){...}
IfKeyword OpenParenToken ...

空白字符还被列为目标符号 InputElementDiv 下的一个单独 token 类别：

InputElementDiv::
    WhiteSpace
    LineTerminator
    ...

定义赋值运算符和数字字面量的规则

我已经展示了 const 关键字和标识符 v 的文法是怎么定义的。现在剩下的就是为等号和数字 3 定义规则：

ConstToken Identifier = 3

等号就是我们在 JavaScript 中用来给变量赋值的东西。还有许多其他赋值运算符，它们都被很方便地归在 AssignmentOperator 这个符号之下：

AssignmentOperator : one of
    *= /= %= += -= <<= >>= >>>= &= ^= |= **=

最后一块拼图——数字 3。在 JavaScript 中，数字可以用多种形式表示：带小数部分的十进制字面量 1.58、二进制 0b11 或十六进制 0x11 字面量、指数形式 5e2 等等。把这些统统归到 NumericLiteral 符号之下是合理的：

NumericLiteral::
  DecimalLiteral
  BinaryIntegerLiteral
  OctalIntegerLiteral
  HexIntegerLiteral

这些全都是非终结符。你可以点开链接，把每个非终结符的产生式一路追到终结符。

多个目标符号

在探究推导过程时我们了解到，它是从目标（起始）符号开始的。而 ECMAScript 的词法文法正是在这里变复杂的：它定义了好几个目标符号。看下面这段代码：

/foo/g

如果 ECMAScript 扫描器用主目标（起始）符号 InputElementDiv 来推导下面这条语句，其产生式规则如下：

InputElementDiv ::
    WhiteSpace
    LineTerminator
    Comment
    CommonToken
    DivPunctuator
    RightBracePunctuator

那它会识别出下面这串 token：

/             foo            /             g
DivPunctuator IdentifierName DivPunctuator IdentifierName

然而，如果你写 JS 写得够久，一定知道 /foo/g 表示的是正则字面量。所以它应该按下面这条文法规则被识别为一个 RegularExpressionLiteral token：

RegularExpressionLiteral ::
    / RegularExpressionBody / RegularExpressionFlags

基本的目标符号 InputElementDiv 没有任何推导能把扫描器引向 RegularExpressionLiteral 符号。所以我们需要定义一个新的目标符号 InputElementRegExp，其中带有正则字面量的产生式：

InputElementRegExp ::
    WhiteSpace
    ...
    RegularExpressionLiteral

用这个目标符号，扫描器就能正确地把 /foo/g 识别为 RegularExpressionLiteral。但现在你可能会问：扫描器在解析 token 时怎么知道该用哪个目标符号？正如我在文章前面提到的，目标符号（上下文）是由解析器设定的。解析器一个一个地向扫描器请求 token，如果当前解析上下文允许使用 InputElementRegExp 目标符号，解析器就请求扫描器用这个目标符号来识别 token。

例如，假设解析器当前正在解析 PrimaryExpression，它的文法如下：

PrimaryExpression :
    this
    IdentifierLiteral
    …
    RegularExpressionLiteral

文法表明正则表达式字面量可以从主表达式推导出来，所以解析器为扫描器定义了 InputElementRegExp 目标符号。TypeScript 编译器的实现方式是：如果检测到当前上下文允许除主目标符号 InputElementDiv 之外的目标符号，就重新扫描当前 token。ECMAScript 还定义了另外几个目标符号——想了解更多，可以看 StackOverflow 上这个很棒的回答。

正则表达式

有时词法文法是用重复运算符而不是递归来给出的。例如，下面就是 Java 8 文法定义 IdentifierChars 符号的方式，它等价于 ECMAScript 中带递归产生式的 IdentifierName 符号：

IdentifierChars:
    JavaLetter {JavaLetterOrDigit}
JavaLetter:
    any Unicode character that is a "Java letter"
JavaLetterOrDigit:
    any Unicode character that is a "Java letter-or-digit"

JavaLetterOrDigit 外面的花括号是重复记法，文法文档中如此解释：

产生式右部的语法 {x} 表示 x 出现零次或多次。

这种给出文法的方式有一个特殊性质：把每个非终结符（根非终结符除外）都用它的右部替换掉，你就能把它归约成根符号的单一产生式，右部只剩终结符。这个归约后的表达式随后就很容易转换成正则表达式（regex）。例如对 IdentifierChars 我们会得到：

[range of Java letter][range of Java letter-or-digit]*

在正则文法规则中用重复运算符而不是递归结构并不是惯例。如果文法是用带递归结构的标准记法给出的，把文法机械地转换成正则表达式就不那么简单了：你得先把文法转换成非确定有限自动机（NFA，下面会解释），再把 NFA 转换成正则表达式。不过，靠「逻辑思考」想出一个等价的正则表达式，往往要容易得多。

正则文法和正则表达式都能描述取自固定集合的字符序列，两者可以互换使用。正因如此，人们常常用正则表达式而不是正则文法来给出词法规范。例如 Flex 这类词法分析器（扫描器）生成工具就是这么做的。

有限自动机

除了正则文法和正则表达式，还有另一种给出词法规范的方式——有限自动机（FA）。它们只是做同一件事的三种不同形式化手段——识别字符集合。我们之所以有三种方式做同一件事，根本原因在于它们是各自独立发展出来的。不过 FA 为描述扫描器的实现提供了最好的心智模型，我们就用它来做这件事。

自动机可以用一个逐字符识别单词的算法来解释。假设我们想识别 const 这个 token。我们需要写代码，检查 c，接着是 o，接着是 n，如此下去直到最后一个字符 t。如果把程序的每一步画成状态转移图，就会得到下面这些状态。

识别 const 关键字的 DFA 状态转移图

每个自动机都有状态，在图上画作圆圈。本文我只讨论状态数有限的自动机（所以叫有限自动机）。用双线标出的最后那个状态称为接受状态。一个自动机可以有任意多个接受状态。如果读完输入后自动机停在接受状态，这段输入就被识别为合法的字符序列。

有限自动机有两类——确定型（DFA）和非确定型（NFA）。两者最大的区别在于，对 DFA 来说每个输入都唯一确定要转移到哪个状态（所以叫确定型）。而在 NFA 中，某些输入可能允许在多个结果状态之间选择（所以叫非确定型）。

NFA 与 DFA 对比图

另外，DFA 只能在读取输入之后改变状态，而 NFA 可以被构造成完全不读取任何输入就转移到某个新状态。存在把一类 FA 转换成另一类的算法。NFA 和 DFA 在表达能力上是等价的，任何 DFA 都是 NFA 的一个特例。

有时扫描器会碰到有歧义的情形。我们知道 =、/=、*=、+= 这些运算符中任何一个都会被识别为合法 token，但扫描器怎么知道该把字符串 += 识别成单个 += token，还是识别成一个 + token 后面跟一个 = token 呢？这类歧义用最长匹配优先规则来解决，所以字符串 += 被识别为一个 token，运行时解释为加法赋值运算符。

实现 DFA

DFA 可以实现为表驱动扫描器，也可以实现为手写扫描器。表驱动扫描器通常由 Flex 这样的专用工具生成。由于在 DFA 中每个输入都唯一确定要转移到的状态、且它从不回溯，DFA 是生成式扫描器实现的首选模型。通常的流程是先把词法规范（正则文法或正则表达式）转换成 NFA，再把 NFA 转换成 DFA。

流程：词法规范 → NFA → DFA → 实现

不过，大多数商业和开源编译器用的都是手写扫描器。这类扫描器比生成的扫描器更快，因为在实现时可以去掉生成式扫描器中必须存在的一些额外开销。TypeScript 编译器实现的就是这种扫描器。手写扫描器时，通常不需要把文法／正则表达式显式转换成 DFA，因为完全可以直接照着词法规范手工实现扫描算法。这样的手写实现自然就会像一个 DFA 那样工作。

表驱动扫描器和手写扫描器的工作方式类似，都是在模拟 DFA。它们反复读取输入中的下一个字符，并模拟该字符引发的 DFA 转移。读取输入之后，扫描器检查是否存在该输入可用的转移。如果找到了转移，就沿它走下去，扫描器进入新状态。如果没有可用的转移，扫描器就检查当前状态是否为接受状态。若是，扫描器就识别出了这个词，并把词素及其句法类别返回给调用过程。否则扫描器判断自己在走到当前状态的路上是否经过过接受状态。如果曾遇到接受状态，扫描器就把内部状态（当前字符位置）回退到那一点并报告成功。否则就报错。

TypeScript 扫描器的实现

TypeScript 扫描器的实现可以在 scanner.ts 文件里看到。通过读取输入并转移到下一状态来模拟 DFA 的主要逻辑实现在 scan 方法中。这份实现的要点是一个无限 while 循环：检查输入字符，处理由该字符出发的所有可能转移，设置当前位置，并在识别出 token 时返回它的类别：

const pos;
while (true) {
    tokenPos = pos;
    if (pos >= end) {
        return token = SyntaxKind.EndOfFileToken;
    }
    let ch = text.charCodeAt(pos);
    switch(ch) {
        case CharacterCodes.exclamation:
            ...
            pos++;
            return token = SyntaxKind.ExclamationToken;
        case CharacterCodes.openParen:
            ...
            pos++;
            return token = SyntaxKind.OpenParenToken;
        ...

由于它模拟的是 DFA，扫描器从不回溯。

我们看个例子。ECMAScript 定义的各种标点符号中包括下面这些：

Punctuator ::
    !  !=  !==  -  --  -=

这条规则很容易转换成正则表达式：

/!==|!=|!|--|-=|-/
标点符号的 DFA：!、!=、!==、-、--、-=

注意除起始状态之外的所有状态都是接受状态。这正是文法和正则表达式告诉我们的。

TypeScript 对上面这个 DFA 的实现如下：

case CharacterCodes.exclamation:
    if (text.charCodeAt(pos + 1) === CharacterCodes.equals) {
        if (text.charCodeAt(pos + 2) === CharacterCodes.equals) {
            pos += 3;
            return token = SyntaxKind.ExclamationEqualsEqualsToken;
        }
        pos += 2
        return token = SyntaxKind.ExclamationEqualsToken;
    }
    pos++;
    return token = SyntaxKind.ExclamationToken;
case CharacterCodes.plus:
    if (text.charCodeAt(pos + 1) === CharacterCodes.plus) {
        pos += 2;
        return token = SyntaxKind.PlusPlusToken;
    }
    if (text.charCodeAt(pos + 1) === CharacterCodes.equals) {
        pos += 2
        return token = SyntaxKind.PlusEqualsToken;
    }
    pos++;
    return token = SyntaxKind.PlusToken;

从 TS 的实现和 DFA 都能看出，扫描器会尽量匹配最长的字符串。

处理关键字

我们已经看到 ECMAScript 把 const、let、if 这类关键字放在它自己的 Keyword 类别下。识别它们的一种办法是为它们定义显式的正则表达式，并为 DFA 生成相应的路径。不过，既然按文法定义关键字是所有标识符的子集：

Identifier:
    IdentifierName but not ReservedWord

那就还有另一种策略——把关键字先归类为标识符，再检验某个标识符是不是关键字。TypeScript 扫描器采用的正是这种做法。它把所有关键字连同其他字面量 token 一起放在 textToToken 映射里，一旦识别出标识符，就用这个映射取得正确的 token 类别，它可能是关键字，也可能不是：

default:
    if (isIdentifierStart(ch, languageVersion)) {
        pos++;
        while (isIdentifierPart(ch = text.charCodeAt(pos))) pos++;
        tokenValue = text.substring(tokenPos, pos);
        return token = getIdentifierToken();
    }

function getIdentifierToken(): SyntaxKind {
    if (...) {
        return token = textToToken.get(tokenValue);
    }
    return token = SyntaxKind.Identifier;
}

想了解更多？

我正在写第二部分，探讨上下文无关文法背后的理论、AST 的构造以及解析器的实现算法。第二部分会展示 TypeScript 解析器是如何实现的、用了哪些算法。

另外，这里还有几个我推荐的非常好的资料，可以获取更多关于本文所讲主题的信息：

  • Stanford CS143 (Compilers)
  • Engineering: A Compiler