编译器设计 - 词法分析

---

---

词法分析是编译器的第一个阶段。它接收来自语言预处理器的经过修改的源代码，这些源代码以句子的形式编写。词法分析器通过去除源代码中的任何空格或注释，将这些语法分解成一系列标记。

如果词法分析器发现标记无效，它会生成错误。词法分析器与语法分析器紧密协作。它从源代码读取字符流，检查合法标记，并在语法分析器需要时将数据传递给它。

标记

词素被称为标记中的一系列字符（字母数字）。每个词素要被识别为有效标记，都有一些预定义的规则。这些规则由语法规则定义，通过模式来表达。模式解释了什么可以是标记，这些模式通过正则表达式来定义。

在编程语言中，关键字、常量、标识符、字符串、数字、运算符和标点符号可以被视为标记。

例如，在 C 语言中，变量声明行

int value = 100;

包含以下标记

int (keyword), value (identifier), = (operator), 100 (constant) and ; (symbol).

标记规范

让我们了解语言理论如何处理以下术语

字母表

任何有限的符号集 {0,1} 都是一组二进制字母表，{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F} 是一组十六进制字母表，{a-z, A-Z} 是一组英文字母表。

字符串

任何有限的字母（字符）序列称为字符串。字符串的长度是字母出现的总次数，例如，字符串 tutorialspoint 的长度为 14，表示为 |tutorialspoint| = 14。没有字母的字符串，即长度为零的字符串，称为空字符串，用 ε（epsilon）表示。

特殊符号

一个典型的高级语言包含以下符号：

语言

语言被认为是在某个有限字母集上的一组有限字符串。计算机语言被认为是有限集，并且可以在它们上执行数学集合运算。有限语言可以通过正则表达式来描述。

正则表达式

词法分析器只需要扫描和识别属于手头语言的有限集的有效字符串/标记/词素。它搜索由语言规则定义的模式。

正则表达式能够通过定义有限符号字符串的模式来表达有限语言。由正则表达式定义的语法称为正则语法。由正则语法定义的语言称为正则语言。

正则表达式是指定模式的重要表示法。每个模式都匹配一组字符串，因此正则表达式充当一组字符串的名称。编程语言标记可以通过正则语言来描述。正则表达式的规范是递归定义的一个例子。正则语言易于理解并且具有高效的实现。

正则表达式遵循许多代数定律，这些定律可用于将正则表达式操作为等价形式。

运算

语言上的各种运算为

• 两个语言 L 和 M 的并集写成

  L U M = {s | s 在 L 中或 s 在 M 中}

• 两个语言 L 和 M 的连接写成

  LM = {st | s 在 L 中且 t 在 M 中}

• 语言 L 的 Kleene 闭包写成

  L* = 语言 L 的零次或多次出现。

表示法

如果 r 和 s 是分别表示语言 L(r) 和 L(s) 的正则表达式，则

• 并集：(r)|(s) 是表示 L(r) U L(s) 的正则表达式

• 连接：(r)(s) 是表示 L(r)L(s) 的正则表达式

• Kleene 闭包：(r)* 是表示 (L(r))* 的正则表达式

• (r) 是表示 L(r) 的正则表达式

优先级和结合性

• *, 连接 (.) 和 |（管道符号）都是左结合的
• * 具有最高优先级
• 连接 (.) 具有第二高优先级。
• |（管道符号）具有最低优先级。

用正则表达式表示语言的有效标记

如果 x 是一个正则表达式，则

x* 表示 x 的零次或多次出现。

即，它可以生成 { e, x, xx, xxx, xxxx, … }

x+ 表示 x 的一次或多次出现。

即，它可以生成 { x, xx, xxx, xxxx … } 或 x.x*

x? 表示 x 的最多一次出现

即，它可以生成 {x} 或 {e}。

[a-z] 是英文的所有小写字母。

[A-Z] 是英文的所有大写字母。

[0-9] 是数学中使用的所有自然数字。

使用正则表达式表示符号的出现

letter = [a – z] 或 [A – Z]

digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 或 [0-9]

sign = [ + | - ]

使用正则表达式表示语言标记

Decimal = (sign)^?(digit)⁺

Identifier = (letter)(letter | digit)*

词法分析器剩下的唯一问题是如何验证用于指定语言关键字模式的正则表达式的有效性。一个被广泛接受的解决方案是使用有限自动机进行验证。

有限自动机

有限自动机是一种状态机，它以符号字符串作为输入并相应地更改其状态。有限自动机是正则表达式的识别器。当正则表达式字符串被馈送到有限自动机时，它会为每个字面量更改其状态。如果输入字符串成功处理并且自动机达到其最终状态，则它被接受，即，刚刚馈送的字符串被称为手头语言的有效标记。

有限自动机的数学模型包括

• 有限状态集 (Q)
• 有限输入符号集 (Σ)
• 一个起始状态 (q0)
• 一组最终状态 (qf)
• 转移函数 (δ)

转移函数 (δ) 将有限状态集 (Q) 映射到有限输入符号集 (Σ)，Q × Σ ➔ Q

有限自动机构造

令 L(r) 为某个有限自动机 (FA) 识别的正则语言。

• 状态：FA 的状态用圆圈表示。状态名称写在圆圈内。

• 起始状态：自动机开始运行的状态称为起始状态。起始状态有一个指向它的箭头。

• 中间状态：所有中间状态至少有两个箭头；一个指向它，另一个从它指向。

• 最终状态：如果输入字符串成功解析，则期望自动机处于此状态。最终状态用双圆圈表示。它可以有任何奇数个指向它的箭头和偶数个从它指向的箭头。奇数箭头的数量比偶数箭头多一个，即奇数 = 偶数 + 1。

• 转移：当找到输入中的所需符号时，就会发生从一个状态到另一个状态的转移。在转移时，自动机可以移动到下一个状态或保持在同一状态。从一个状态到另一个状态的移动显示为一个有向箭头，其中箭头指向目标状态。如果自动机保持在同一状态，则绘制一个从状态到自身的箭头。

示例：我们假设 FA 接受以数字 1 结尾的任何三位二进制值。FA = {Q(q₀, q_f), Σ(0,1), q₀, q_f, δ}

最长匹配规则

当词法分析器读取源代码时，它逐个字符扫描代码；当遇到空格、运算符符号或特殊符号时，它会确定一个单词已完成。

例如

int intvalue;

在扫描到“int”之前的两个词素时，词法分析器无法确定它是一个关键字int还是标识符 int 值的开头字母。

最长匹配规则规定，应根据所有可用标记中最长的匹配来确定扫描的词素。

词法分析器还遵循规则优先级，其中语言的保留字（例如，关键字）优先于用户输入。也就是说，如果词法分析器找到与任何现有保留字匹配的词素，它应该生成错误。