5 词法分析之正则表达式与有限自动机

在编译器的设计中，词法分析是一个重要的阶段，而在词法分析的实现过程中，正则表达式和有限自动机（Finite Automata, FA）扮演着至关重要的角色。本篇文章将深入讨论如何使用正则表达式来描述编程语言的词法元素，并如何将这些正则表达式转换为有限自动机，以用于词法分析器的构建。

正则表达式基础

正则表达式是一种用于匹配字符串的强大工具，通过定义字符模式来描述字符串的特征。在编译器设计中，正则表达式用于描述各种词法单元（如标识符、关键字、操作符等）。

1. 正则表达式的基本构造

常见的正则表达式元素包括：

• a：匹配字符 a
• .：匹配任意单个字符
• *：匹配前面的元素零次或多次
• +：匹配前面的元素一次或多次
• ?：匹配前面的元素零次或一次
• [abc]：匹配字符集中的任意一个字符
• [^abc]：匹配不在字符集中的任意字符
• (abc)：匹配括号中的序列
• |：表示“或”操作，例如 a|b 匹配 a 或 b

2. 示例

以简单的编程语言中的标识符为例，标识符的构成可以用如下正则表达式描述：

$$
IDENTIFIER ::= [a-zA-Z_][a-zA-Z0-9_]*
$$

这里的正则表达式表示一个标识符必须以字母或下划线开头，后面可以跟任意数量的字母、数字或下划线。

有限自动机

有限自动机是一个用于执行状态转移的数学模型，它可以用于实现正则表达式的匹配。有限自动机分为两类：确定性有限自动机（DFA）和非确定性有限自动机（NFA）。

1. 非确定性有限自动机（NFA）

NFA 允许在同一状态下对同一输入字符存在多条转移，也可以进行 ε（ε-转移）操作。NFA 可以通过正则表达式直接构建。对于上面的标识符例子，构建 NFA 的过程如下：

1. 创建一个初始状态。
2. 对于每个字符在正则表达式的定义中，添加状态和转移。

2. 确定性有限自动机（DFA）

DFA 是一种特殊类型的 NFA，其每个状态对于任何输入都有且仅有一个转移。每个 DFA 的状态都是由 NFA 的状态集组成的集合，因此可以通过子集构造法将 NFA 转换为 DFA。

3. NFA 到 DFA 的转换示例

考虑 NFA 的构造结果，假设我们有如下 NFA 对应于 IDENTIFIER 正则表达式：

(0) --[a-zA-Z_]--> (1) 
(1) --[a-zA-Z0-9_]--> (2)
(2) --[a-zA-Z0-9_]--> (2)  (自环)

在上面的 NFA 中：

• 状态 0 是起始状态，接受字母和下划线作转移到状态 1。
• 状态 1 接受字母或数字作转移到状态 2。
• 状态 2 是终止状态，并且具有自环，可以接收字母或数字。

通过子集构造法，我们可以将这个 NFA 转换为相应的 DFA。对应的 DFA 可能会减少为初始化状态转移到子状态。

实际案例

下面是一个简单的示例代码，展示如何使用 Python 的 re 模块来创建正则表达式并进行匹配：

import re

# 定义正则表达式
identifier_regex = r'^[a-zA-Z_][a-zA-Z0-9_]*$'

# 测试字符串
test_strings = ['variable', '_temp', '2invalid', 'valid123']

# 判断是否合法的标识符
for s in test_strings:
    if re.match(identifier_regex, s):
        print(f"'{s}' 是一个合法的标识符")
    else:
        print(f"'{s}' 不是一个合法的标识符")

输出结果

'variable' 是一个合法的标识符
'_temp' 是一个合法的标识符
'2invalid' 不是一个合法的标识符
'valid123' 是一个合法的标识符

小结

在本篇文章中，我们探讨了正则表达式与有限自动机在词法分析中的应用。通过正则表达式，我们能够清晰地定义词法元素的模式，而通过有限自动机，我们能够实现高效的模式匹配。这为构建一个高效的词法分析器打下了基础。

在下一篇文章中，我们将进一步讨论如何将这些理论应用于实际的词法分析器的实现中，帮助我们更好地理解词法分析的整个过程。