当前位置：首页 > news >正文

编译原理复习---正则表达式+有穷自动机

news 来源：原创 2025/5/24 9:39:22

适用于电子科技大学编译原理期末考试复习。

1. 正则表达式

正则表达式（Regular Expression，简称regex或regexp）是一种用于描述、匹配和操作文本模式的强大工具。它由一系列字符和特殊符号组成，这些字符和符号定义了一种搜索模式，可以用来检查一个字符串是否包含某个子串、将匹配的子串进行替换或者从字符串中提取符合条件的子串等。

总结来说，正则表达式就是通过特定字符与文法符号的组合来描述一种语言的方式。

正则语言 == 上下文无关文法 == 正则表达式，三者之间可以相互转换

编译原理这门课中，正则表达式所使用的符号与标准的定义好像不太相同，我只能凭借做题的经验列举出大致的用法：

$(a_1|a_2|...|a_n)$ ：表示集合{ $a_1$ ， $a_2$ ，...， $a_n$ }中的任意一个字符。

每一个单元(正则表达式中的一个字符或用括号包围起来的一组符号)后可加上" * "(克林闭包)、" + "(正闭包)。

" . "表示字母表中的任意字符。

例如： $a(a|b)^*(\varepsilon | (.|\_)(a|b)(a|b)^*)$

2. 有穷自动机

有穷自动机（Finite Automaton, FA），也称为有限状态机，是一种计算模型，用于描述和识别特定类型的语言。它由以下几个基本组成部分构成：

状态集合（Q）：有限个状态的集合。

字母表（Σ）：有限个输入符号的集合。

转移函数（δ）：定义了从一个状态和一个输入符号到另一个状态的映射，即 δ: Q × Σ → Q。

初始状态（q0）：自动机开始处理输入前所在的状态，q0 ∈ Q。

接受状态集（F）：状态集合的一个子集，表示当自动机停止时可以处于的状态，这些状态表明输入字符串被接受，F ⊆ Q。