编译器的各个阶段 – 逻辑分析

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

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

然后编译器将源程序翻译成汇编语言（高级语言和二进制语言的结合）。 它将其转移到汇编器，以便进一步编码为最低级别的机器码。

汇编

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

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

它按阶段工作，划分了所有必须完成的任务。以下是汇编中包括的所有阶段。

• 流程图中的前四个阶段代表分析阶段
• 最后两个阶段代表综合阶段。
• 在分析阶段，对高级语言中的给定代码进行词法、句法和语义的分析，并生成中间代码。相反，在合成阶段，使用分析阶段的结果来生成汇编代码。
• 编译器的分析阶段与机器无关，也与语言有关，而综合阶段则与机器有关，也与语言有关。
• 因此，如果我们想建立一个新的编译器，我们不需要从头开始建立；我们可以借用另一个编译器的中间代码生成器，并从那里建立它。这个过程被称为 “重定向”。
• 符号表是编译器用来存储和检索程序中使用的所有标识符的数据结构，以及按数据类型和范围分类的必要信息。因此，每个阶段都会用到符号表和错误处理程序。

我们将详细讨论编译器的每个阶段。本教程解释了第一个阶段–逻辑分析。

词汇分析

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

有三个重要术语需要抓住：

1. 代号：代号是一个预先定义的字符序列，不能进一步细分。它就像一个抽象的符号，代表一个单位。一个令牌可以有一个可选的属性值。有不同类型的令牌。

• Identifiers (user-defined)

• Delimiters/ punctuations (;, ,, {}, etc.)

• Operators (+, -, *, /, etc.)

• 特殊符号

• Keywords

• Numbers

2. 词素：词素是源程序中匹配的字符序列，与标记的模式相匹配。
   例如 :（, ）是标点符号类型的词组，其中标点符号是标记。
3. 模式。模式是扫描器遵循的一套规则，用于匹配输入程序中的词素，以识别有效的标记。它就像词法分析器对一个标记的描述，以验证一个词素。
   例如 ，关键词中的字符是识别关键词的模式。为了识别一个标识符，预先定义的一套规则来创建一个标识符的模式是

Token	Lexeme	Pattern
Keyword	while	w-h-i-l-e
Relop	<	<, >, >=, <=, !=, ==
Integer	7	(0 – 9)*-> 至少有一个数字的数字序列
String	“Hi”	用””括起来的字符
Punctuation	,	; , . ! etc.
Identifier	number	A – Z, a – z 由一个字符发起的一系列字符和数字。

词法分析器必须做的一切

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

这里的问题是：

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

我们将从问题的角度来探讨细节。

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

输入缓冲

假设，假设这行代码是。

int i, j;
i = j + 1;
j = j + 1;

输入被存储在缓冲区，以避免进入二级存储器。

最初，我们使用一个缓冲方案。

两个指针 .*bp被保留在开头，而*fp被遍历缓冲区。一旦*fp找到一个分界符，如空格或分号，*bp和遇到的分界符之间的遍历部分就被识别为一个标记。现在，*bp和*fp被设置为分界符的后续块，以继续搜索令牌。

单一缓冲区模式的缺点。 :当我们要读取的字符串长于缓冲区的长度时，在读取整个字符串之前，就已经到达了缓冲区的末端，整个缓冲区必须重新加载剩余的字符串，这就使得识别变得困难。

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

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

每当fp* 向前移动，eof检查它是否到达终点以重新加载第二个缓冲区。所以，这就是一个输入程序的读取方式，并对令牌进行划分。

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

模式：

词汇分析器必须扫描和识别程序中有限的有效标记/词组，为此它使用了模式。模式是为了从程序中找到有效的词组。这些模式是用 “常规语法 “指定的。所有的有效标记都被赋予预定义的模式，以检查程序中检测到的词组的有效性。

1.数字

一个数字的形式可以是：

1.一个整数（0、1、2…）。
2.一个十进制的数字（0.1，0.2……）。
3.科学符号（1.25E），（1.25E23）。

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

样本常规语法：

Digit -> 0|1|....9
Digits -> Digit (Digit)*
Number -> Digits (.Digits)? (E[+ -] ? Digits)? 
Number -> Digit+ (.Digit)+? (E[+ -] ? Digit+)? 

• 代表前一个表达式的0次或更多次出现
• 代表基础表达式的0个或更多出现。
• + 代表1个或多个基础表达的出现

2.分隔符

有不同类型的定界符，如空白、换行符、制表符等。

样本常规语法：

Delimiter -> ' ', '\t', '\n'
Delimiters -> delimiter (delimiter)*

3.标识符

标识符的规则是：

1.它必须只从一个字母开始。
2.在第一个字母之后，它可以有任何数量的字母、数字和下划线。

样本常规语法：

Letter -> a|b|....z
Letter -> A|B|...Z
Digit -> 0|1|...9
Identifier -> Letter (Letter/ Digit)*

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

为了识别和验证标记，词法分析器为每个模式建立有限自动机。 作为一个中间步骤。过渡图中的每个状态代表一段代码。每个被识别的词素都会在自动机中行走。由自动机构建的程序可以由开关语句组成，以跟踪词素的状态。词素如果达到最终状态，就被验证为有效的标记。

这里有一些过渡图。这些只是手工绘制的例子，但编译器的原始规则和模式程序要复杂得多，因为它们必须识别所有类型的词素，无论它们以何种方式使用。

1.标识符

2.分隔符

白色的空间：

当编译器识别到一个空白或其他分隔字符，如’\t’和’\n’，它不会将其发送到语法分析器。而是从紧接着的下一个标记开始进行整个词汇分析过程。这就是所谓的从程序中剥离空格。

3.数字

4.关键词

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

5.关系操作符

GE :大于或等于

LE :小于或等于

GT :大于

LT :少于

EQ :等于

NE :不等于

代币的属性。

在一个程序中，许多词条可以对应于一个标记。我们了解到，词法分析器将一连串的标记发送到下一个阶段。但是，其余的阶段仍然需要关于词素的额外信息来执行不同的操作。

0和1都被认定为数字。但是，如果我们发送程序中有一个数字，这对代码生成器来说是不够的。因此，这些标记被作为一个对子<Token name, Attribute value>发送到语法分析器。

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

现在，词法分析器究竟向句法分析器发送什么？

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

Stmt -> if expr then Stmt
              If expr then stmt else Stmt
              ε
expr -> term relop term
              term
term -> id
              number

下面是词法分析器对这个片段的下一阶段的输出。

LEXEMES	TOKEN NAME	ATTRIBUTE VALUE
Any white space	–	–
if	if	–
then	then	–
else	else	–
Any Identifier	id	指向id的符号表条目的指针
Any number	number	指向id的符号表条目的指针
<	relop	LT
>	relop	GT
>=	relop	GE
<=	relop	LE
==	relop	EQ
<>	relop	NE

词汇错误

查找词法错误是词法分析器的任务之一。但是，如果没有任何其他成分，词法分析器很难确定一个词素是否有问题。假设它发现

fi (a, b)…

对于词素fi，词法分析器无法弄清它是if的拼写错误，还是一个未声明的函数调用标识符。’fi’是一个有效的标识符。因此，词法分析器并没有引发任何错误，而是将其作为一个标识符进行验证。在接下来的某个阶段，这个错误将被识别出来。

如果一个词素没有与任何标记模式相匹配，词汇分析器就会进入 “恐慌模式”，并执行一些错误恢复动作来修复输入。

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

一般来说，词汇错误是由于一个字符引起的。因此，这些转换的作用是充分的。词汇分析器试图在较少的此类转换中找到一个有效的词组。

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