深入编译器——第一部分：词法解析和Scanner（介绍ECMAScript的词法规范和TypeScr

摘要：词法分析对构成源程序的字符流进行扫描然后根据构词规则识别单词也称单词符号或符号。语义分析是编译过程的一个逻辑阶段语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查进行类型审查，审查抽象语法树是否符合该编程语言的规则。

我对编译器的深入了解起源于一条推特中的问题：Angular是如何用Angular预先编译器（AOT）对静态代码进行解析工作的。在进行一些debugging后，我发现AOT非常依赖TypeScript编译器，所以我开始对它进行反编译（reverse-engineer）。有趣的是，大部分编译器都使用一样的规则，这些规则被广泛的认为是编译器理论。在理解编译器的内部机制时，对这些理论一窥究竟是非常有必要的。
接下来我将描述对每个编译器的第一阶段都非常重要的词法分析
这篇文章尽量少的参入理论和教条主义，不过大部分依然是理论性的。在最后一章，我将展示TypeScript scanner是如何工作的并提供相关的链接。

TypeScript 语法是基于ECMAScript 规范的，我希望读者们能够保持足够的好奇心查看文章中的链接，并且熟练掌握这些规范。 如果你能做到这些，你就会知道这些语法，并且在JavaScript的新特新被写入MDN之前就学习到了。如果你读完了这篇文章，可以通过理解装饰器（decorator）规范里描述的装饰器的语法特性来测试自己。
这篇文章比较长，因此你不需要一次性全部读完。一点一点的读这篇文章，有足够的时间记住文章里的内容。如果你一直想知道ECMAScript 规范或者想弄清楚编译器是如何工作的，那就开始读这篇文章吧！

编译器就是把一个用一种编程语言写成的程序编译成另一种语言的电脑程序。编译器首先需要理解原来的输入的编程语言 ，然后把它编译成目标语言。由于这两种不同的特性，需要把编译器的功能分成两大块：前端（a front-end）和后端（a back-end.）。前段处理输入源程序，后端处理输出目标代码。

编译器可以看成是一个由多个阶段构成的流水线结构，上一步的结果输入到下一步，然后下一步再优化代码并且转化成这一步的需要的代码，最后又传给下一步。前端包括三个主要的阶段就是词法分析，语法分析和语义分析。

词法分析对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。

语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，并生成抽象语法书（AST）.语法分析程序判断源程序在结构上是否正确。

语义分析是编译过程的一个逻辑阶段. 语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查, 进行类型审查，审查抽象语法树是否符合该编程语言的规则。

这篇文章主要目的在于介绍词法分析。

在我们开始谈词法分析之前，我们需要聊一点自然语言和形式语言（Formal language
是用精确的数学或机器可处理的公式定义的语言）和他们的语法。像英语和法语这样的自然语言通常用于日常交流，而且自然发展而来的。形式语言，一方面。是由人类设计用来特殊的用途的——比如编程语言用来表示计算机的语言，数学符号表示数字之间的关系等等。
无论是自然语言还是形式语言都可以用语法来描述。语法指该语言中的句子、短语、词汇的逻辑、结构特征以及构成方式，而语法包括对语法规律进行的总结描述或对语言使用的规范或限定。自然语言的语法是非常复杂的，并通过经验主义的方式来研究的。另一方面，形式语言通常都是简单的，并根据我们的需求定义的。取决于我们可以通过怎样的方式分辨几种语法来定义规则。

词法描述了一种语言的词汇结构，就是语言中每个单词（符号）。比如， 和 d都是JavaScript 的字母，但是语法并没有定义在正常语句中后面跟d的规则，所以当你执行d的代码的时候，我们会得到无效符号的语法错误：

d
Uncaught SyntaxError: Invalid or unexpected token

语法定义了语句的结构，就是单词符号在一条语句中组合方式。例如，JavaScript词法定义的 var和const,在语法中没有var后面跟着const，所有当下面这样使用时就会出现语法错误：

var const
Uncaught SyntaxError: Unexpected token const

上面的结构根据ECMAScript语法规范是无效的，所以编译器并不会识别var后面跟着const这样的语句。

词法分析是编译器在处理源代码时三个阶段中的第一个阶段。词法分析的作用就是把源代码分解成被称为是标记（token）的子字符串，并且对每个标记进行分类，进行词法分析的程序或者函数叫作词法分析器（lexical
analyzer，简称lexer），也叫扫描器（scanner）。它们读取输入字符流，按照词法生成标记，这个过程叫做标记化（tokenization）。如果一组字符串没有匹配的规则扫描器就会报错。这就是我们例子中d出现报错的原因。

扫描器对每一个被识别的标记都会按语法分配一个语句范畴（syntactic category）。这个范畴或者说ECMAScript的标记种类非常广泛，包括但不限于识别码（Identifier），数字文字（NumericLiteral），字符串文字（StringLiteral ）和各种不同的像const、let、if这样的关键字。

所以词法分析阶段的输出通常是由带有对应类型的标记和带有词位的子字符串组成的队列：

{class: SyntaxKind.ConstKeyword, lexeme: ‘const’}

如果你对ECMAScript 定义的标记类型的感兴趣，可以查看SyntaxKind的列举。

词法分析器可以扫描整个源代码然后输出完整的标记队列，或者缓慢的扫描一次输出一个标记。扫描器把在解析前将整个源代码转化成标记序列而消耗不必要的内存是不常见的。所以扫描器只有在代码需要被解析时才工作，TypeScript 扫描器也一样。TS扫描器在另一方面也非常有趣。JavaScript 语法只定义了一些语言结构，如常用表达和模板文字，这将导致解析的歧义，所以需要扫描器根据解析上下文来识别不同的字符集。
由于解析上下文是由解析器定义的，当请求一个标记时，TS扫描器可以被称为解析驱动。我会在多个目标符号部分详解这个复杂的问题。

我们用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

Now its job is to split the expression into tokens and categorize them so the following list of tokens is produced:

现在编译器的工作就是对这段表达式分割成标记，并且对它们进行分类，然后就生成了下面的这组符号：

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

如果用let替代const第一个标记应为SyntaxKind.LetKeyword。

ECMAScript 就是解析用Unicode 的符号作为标记的规则的正常语法。根据Chomsky对语法的分类，常规语法是最受约束的并且最缺乏表达能力的语法。它仅适合于描述标记是如何被组合的，但不能描述句子的结构。然而，一个语法规则越不自由越容易描述和解析。因为我们如此关心定义和解析标记，所以这是一个理想的语法。
这个系列的下一篇文章我们将会了解上下文无关文法（context-free grammar）。这类语法允许递归的结构，并且用来定义程序的结构。
值得注意的是，很多教育资料在解释扫描器并不用常规语法，而是用常规表达定义定义常规规范。但是，由于ECMAScript 用了常规语法，我会在这篇文章中解释它。

Now, let’s try to see how we can construct the grammar and the rules that help TypeScript identify the list of tokens I showed above. Here it is again and we need to define rules for recognizing each token in the statement:
现在，让我们尝试看看我们怎样构建语法和规则来帮助TypeScript我在上面列出的标记。下面又是我们需要在表达式中识别的每一个符号：

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

语法中的每一项规则是用生产方式来定义的。生产方式是可以递归生成新的符号序列的替代规则。在JavaScript 中我们可以用const或者let来声明一个变量，于是我们可以用关键字符号定义下面的规则：

Keyword ::
    const
    let

这个关键字符号的规则有两个结果，这两个结果表示符号关键字可以是let或者const字符串。合成变量的关键字被称作非终结的，意味着他有结果并且可以被替代。这个替代性通常被认为能被分解成更小的单位。const和let所产生的结果被称为终结符，不能被分解成更小的单位。没有结果的终端符号在源码中找到。非终结符是可以被取代的符号。一个形式文法中必须有一个起始符号；这个起始符号属于非终结符的集合。ECMAScript定义了许多其他的非终结符关键字例如：if, else, for, do, while, function, class等等。

可以用下面的任意布局来定义ECMAScript语法：

non_terminal_symbol ::
  symbol1 symbol2  (production rule 1, Symbol1 followed by Symbol2)
  symbol3 symbol4  (production rule 2, Symbol3 followed by Symbol4)

在：：左边的称作左边部分，右边的称为右边部分。对于常规的和上下文无关语法非终结符只能在左边，右边可以是终结符也可以是非终结符
然而对于常规语法，只能是下面的一种：

只有终结字符的

或者有终结字符和单个非终结字符，并且终结字符在开始或者结尾。

non_terminal_symbol ::
  terminal_symbol
non_terminal_symbol ::
  terminal_symbol non_terminal_symbol   (right-linear)
non_terminal_symbol ::
  non_terminal_symbol terminal_symbol   (left-linear)

上下文无关语法更加宽松，允许任意数量的终结字符和非终结字符在右边。常规语法和上下文无关语法都可以有任意数量的符号在左边：

non_terminal_symbol ::
  production rule 1
  production rule 2
  ...
  production rule n