正规式与有限自动机：词法分析核心概念

"该资源是一份来自西安交通大学的关于词法分析的PPT，主要讲解了正规式的代数性质，包括正规式的或运算、连接运算和闭包运算，并介绍了正规文法与有限自动机的相关概念。" 在词法分析中，正规式起着至关重要的作用，它们用于描述字符串模式。正规式由一些基本元素组成，如大写字母代表正规式，`|` 表示或运算，`` 表示连接运算，`*` 表示闭包运算。这些运算符具有特定的代数性质： 1. **可交换性**：正规式的或运算符 `|` 具有可交换性，这意味着 U|V = V|U，即两个正规式连接的顺序可以互换而不影响其表示的语言。 2. **可结合性**：正规式的或运算符 `|` 和连接运算符 `` 都是可结合的。这意味着 (U|V)|W = U|(V|W)，同时 (UV)W = U(VW)，表示无论括号如何放置，结果都是相同的。 3. **对|的分配律**：正规式运算的分配律指出，U(V|W) = UV|UW 以及 (U|V)W = UW|VW，这意味着或运算可以分别应用于连接运算的两边。 4. **幂等性**：正规式的闭包运算符 `*` 具有幂等性，即 U** = U*，表示任意正规式重复零次或多次都等于自身。 正规式可以由基本正规式（单个字符）通过上述运算符组合而成，形成的正规集就是所有匹配该正规式的字符串集合。例如，正规式 ba* 表示所有以 b 开头，后面跟着任意数量 a 的字符串，正规集包括 ba, baa, baaa 等。 正规式与有限自动机（Finite Automata, FA）之间存在等价性，特别是确定有限自动机（Deterministic Finite Automaton, DFA）。DFA 是一种状态转换机器，能够识别正规集。每个正规式都可以构建一个对应的 DFA，反之亦然，这使得正规式成为描述语言的强大工具。 在PPT的后续部分，还可能涉及如何设计和实现词法分析器，词法分析器的自动生成工具，以及如何化简确定自动有限自动机以优化性能。词法分析是编译器设计过程中的第一步，它将源代码分解成一个个有意义的符号单元，为语法分析和编译过程做准备。