编译器设计 - 词法分析

词法分析是编译器的第一阶段。它从语言预处理器中获取以句子形式编写的修改后的源代码。词法分析器通过删除源代码中的任何空格或注释，将这些语法分解为一系列标记。

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

标记

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

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

例如，在 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] 是数学中使用的所有自然数字。

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

字母 = [a – z] 或 [A – Z]

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

符号 = [ + | - ]

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

十进制 = (符号)^?(数字)⁺

标识符 = (字母)(字母 | 数字)*

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

有限自动机

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

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

• 有限状态集 (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 value 的首字母。

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

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