编译器的各个阶段 - 词法分析

编译器是一个软件翻译程序，它将纯粹的高级语言指令转换为机器可理解的格式。通常，我们使用Python、C等语言编写程序……机器/计算机无法理解这些语言。它只能理解二进制语言。用二进制语言编写程序非常困难。因此，我们使用编译器作为媒介。

编译是机器语言处理系统的第二步。它展开#define给出的宏，然后将纯粹的高级语言代码提供给编译器。当我们用高级语言编写程序时，预处理器接收代码并执行一些操作，如宏展开和文件包含。当遇到#include和#define等预处理器指令时，预处理器包含指定的文件。

编译器然后将源程序翻译成汇编语言（高级语言和二进制语言的组合）。它将其传递给汇编器进行进一步编码成最低级别的机器码。

编译

编译器的任务不仅是翻译，还要确保给定代码在词法、语法和语义上是正确的。编译器的一个主要任务是检测和显示错误消息。

当我们编写并编译程序时，编译器一次性处理整个程序，然后一次性显示所有错误消息和警告列表，这与解释器不同。解释器是另一种类似于编译器的翻译器。它逐行读取程序，一旦发现错误，就会停止执行并显示错误消息。

它通过阶段性地工作，将所有要完成的任务进行划分。以下是编译中包含的所有阶段：

• 流程图中的前四个阶段代表分析阶段
• 最后两个阶段代表合成阶段。
• 在分析阶段，用高级语言给出的代码经过词法、语法和语义分析，并生成中间代码。相比之下，在合成阶段，利用分析阶段的结果生成汇编代码。
• 编译器的分析阶段是与机器无关且依赖于语言的，而合成阶段是依赖于机器且与语言无关的。
• 因此，如果我们想构建一个新的编译器，我们不必从头开始构建；我们可以借用另一个编译器的中间代码生成器，并在其基础上进行构建。这个过程称为“重定向”。
• 符号表是编译器用来存储和检索程序中使用的所有标识符的数据结构，以及按数据类型和作用域分类的必要信息。因此，符号表和错误处理程序在每个阶段都使用。

我们将详细讨论编译器的每个阶段。本教程解释第一个阶段——词法分析。

词法分析

词法分析器也称为“扫描器”。给定代码语句/输入字符串，它从左到右逐个字符地读取语句。词法分析器的输入是来自预处理器的纯高级代码。它从程序中识别有效的词素，并根据语法分析器的getNextToken命令，一个接一个地返回标记给语法分析器。

需要掌握三个重要的术语：

1. 标记（Tokens）：标记是预定义的字符序列，不能进一步分解。它就像一个代表单元的抽象符号。标记可以有一个可选的属性值。有不同类型的标记：
   • 标识符（用户定义）
   • 分隔符/标点符号（;, ,, {}, 等）
   • 运算符（+, -, *, /, 等）
   • 特殊符号
   • 关键字
   • 数字
2. 词素（Lexemes）：词素是源代码中匹配标记模式的字符序列。
   例如：(, ) 是标点符号类型的词素，其中标点符号是标记。
3. 模式（Patterns）：模式是扫描器遵循的一组规则，用于匹配输入程序中的词素以识别有效的标记。它就像词法分析器对标记的描述，用于验证词素。
   例如，关键字中的字符是识别关键字的模式。要识别标识符，创建标识符的预定义规则集就是模式。

词法分析器必须做的所有事情

1. 从程序中剥离注释和空格
2. 读取输入程序并将其划分为有效的标记
3. 查找词法错误
4. 将有效的标记序列返回给语法分析器
5. 当它找到一个标识符时，它必须在符号表中创建一个条目。

这里的问题是：

1. 词法分析器如何读取输入字符串并将其分解为词素？
2. 它如何理解模式并检查词素是否有效？
3. 词法分析器将什么发送到下一阶段？

我们将逐个问题地深入细节。

首先，词法分析器必须读取输入程序并将其分解为标记。这是通过一种称为“输入缓冲”的方法实现的。

输入缓冲

假设代码行是：

输入存储在缓冲区中，以避免访问二次存储器。

最初，我们使用单缓冲区方案

使用两个指针来读取和查找标记：*bp（开始）和*fp（前导）。*bp 保持在开头，*fp 遍历缓冲区。一旦*fp 遇到空格或分号等分隔符，*bp 和遇到的分隔符之间的部分就被识别为一个标记。现在，*bp 和*fp 被设置为分隔符的后续块，以继续搜索标记。

单缓冲区方案的缺点：当我们要读取的字符串比缓冲区长度长时，在读取整个字符串之前，缓冲区末尾就会到达，并且必须用字符串的其余部分重新加载整个缓冲区，这使得识别变得困难。

因此，引入了双缓冲区方案。

这里使用了两个相同大小的缓冲区。优点是当第一个缓冲区填满时，第二个缓冲区将被加载，反之亦然。我们不会在中间丢失字符串。

每当 fp* 向前移动时，eof 检查它是否正在到达末尾以重新加载第二个缓冲区。所以，这就是输入程序如何被读取和标记被划分的方式。

下一个问题是词法分析器如何将模式与词素匹配以检查词素与标记的有效性。

模式

词法分析器必须扫描并仅识别程序中有限数量的有效标记/词素，为此它使用模式。模式是用于从程序中查找有效词素的。这些模式使用“正则文法”指定。所有有效的标记都预先定义了模式，以检查程序中检测到的词素的有效性。

1. 数字

数字可以有以下形式：

1. 整数（0, 1, 2...）
2. 小数（0.1, 0.2...）
3. 科学计数法（1.25E），（1.25E23）

文法必须识别所有类型的数字。

示例正则文法

• ? 表示前一个表达式出现0次或多次
• * 表示基本表达式出现0次或多次
• + 表示基本表达式出现1次或多次

2. 分隔符

有不同类型的分隔符，如空格、换行符、制表符等。

示例正则文法

3. 标识符

标识符的规则是：

1. 它必须以字母开头。
2. 第一个字母之后，它可以包含任意数量的字母、数字和下划线。

示例正则文法

现在，我们已经检测到词素和每个标记的预定义模式。词法分析器需要使用这些模式来识别和检查每个词素的有效性。

为了识别和验证标记，词法分析器为每个模式构建有限自动机。可以构建转换图并将其转换为程序作为中间步骤。转换图中的每个状态都代表一段代码。每个已识别的词素都会在自动机中遍历。从自动机构建的程序可以包含switch语句来跟踪词素的状态。如果词素到达最终状态，则验证其为有效标记。

这里有一些转换图。这些只是手动绘制的示例，但编译器原始的规则和模式程序要复杂得多，因为它们必须以任何方式识别所有类型的词素。

1. 标识符

2. 分隔符

空格

当编译器识别到空格或其他分隔字符（如'\t'和'\n'）时，它不会将其发送给语法分析器。相反，它从紧随其后的下一个标记开始整个词法分析过程。这被称为剥离程序中的空格。

3. 数字

4. 关键字

识别 if、else 和 for。如前所述，关键字的字母是识别关键字的模式。

5. 关系运算符

GE：大于或等于

LE：小于或等于

GT：大于

LT：小于

EQ：等于

NE：不等于

标记的属性

在一个程序中，许多词素可以对应一个标记。我们知道词法分析器将标记序列发送给下一个阶段。但是，其余阶段需要有关词素的额外信息，以便执行不同的操作。

0 和 1 都被识别为数字。但是，如果发送程序中存在数字，则对代码生成器来说是不够的。因此，标记以 <标记名称, 属性值> 对的形式发送给语法分析器。

对于像标识符这样的复杂标记，属性值是指向符号表中标识符条目的指针，以关联关于标识符的更多信息。

那么，词法分析器到底将什么发送给语法分析器？

让我们以一个简单的 if-else 分支语句的文法为例：

这是此代码片段的词法分析器输出到下一阶段的结果：

词素就像一个标记的实例，属性列用于显示使用了哪个标记的词素。对于每个词素，将上面表格的第 1 列和第 2 列发送给语法分析器。

词法错误

查找词法错误是词法分析器的一项任务。但是，词法分析器很难在没有任何其他组件的情况下确定一个词素是否错误。假设它发现：

fi (a, b)...

对于词素 fi，词法分析器无法确定它是 if 的拼写错误还是未声明的函数调用标识符。'fi' 是一个有效的标识符。因此，词法分析器不引发任何错误，并将其验证为一个标识符。在后续的某个阶段，错误将被识别。

假设一个词素未与任何标记模式匹配，词法分析器将进入“恐慌模式”并执行一些错误恢复操作来修复输入。

1. 删除所有连续的字符，直到找到有效的词素
2. 删除剩余输入中的一个字符
3. 用另一个字符替换一个字符
4. 转置/交换两个字符
5. 插入一个丢失的字符到词素中以匹配标记模式。

通常，词法错误是由一个字符引起的。因此，这些转换足够了。词法分析器尝试通过较少的此类转换找到一个有效的词素。

本教程涵盖了“词法分析”的基本概念。在所有处理之后，词法分析器到语法分析器的输出是带有属性的标记序列。下一篇文章将讨论“语法分析”阶段的所有基本概念。