软考-软件设计师：程序设计语言-编译过程-词法分析-正规式与正规集 作者：马育民 • 2025-04-06 12:56 • 阅读：10006 # 概念 正规式与正规集是 **编译原理** 中 **词法分析** 中的概念 正规式：也叫 `正规表达式`，是描述程序语言单词的表达式 正规集：是正规式描述的单词的集合。 **提示：**此处的 `单词`，其实就是一个符号串，可以是数字、字母或者其他字符的组合 ### 优先级 - 闭包运算符 `*` 具有最高的优先级。**注意：**`*`指 `0-n` - 连接运算 `·` 具有次高优先级 - 或运算符 `|` 具有最低优先级。**注意：** 没有先后顺序 ### 例子 对于字母 `∑`，其上的正规式及其表示的正规集可以递归定义如下: - ε是一个正规式，它表示集合L(e)={e}。 - 若a是`∑`上的字符，则a是一个正则式，它所表示的正规L(a)={a}。 - 若正规式r和s分别表示正规集 `L(r)=L(s)`，则 - `r|s`是正规式，表示集合 `L(r) ∪ L(s)` - `r · s` 是正规式，表示集合 `L(r) L(s)` - `r*`是正规式，表示集合 `(L(r))*`; - `(r)`是正规式，表示集合 `L(r)`。 仅由有限次地使用上述三个步骤定义的表达式才是 `∑` 上的正规式。 **总结：**正规式要么为 `空`，要么由 `字母`、`或`、`连接`、`闭包运算符` 组成。 # 例 如果我们有两个字符a、b，那么有以下几种常用正规式写法： [](https://www.malaoshi.top/upload/0/0/1GWtZGkSZ4G.png) - 正规式 `ab`，表示由两个字符 `ab` 的元素，对应只有1个元素的正规集 `{ab}`。 - 正规式 `a|b`，表示单一字符 `a` 或者 `b`，对应有2个元素的正规集 `{a,b}`。**注意：** 没有先后顺序 - 正规式 `a*`，`*` 表示任意个，对应正规集`{空,a,aa,aaa,...}`。**注意：**`*`指 `0-n` - 正规式 `(a|b)*` ，可以表示任意由 `a`、`b` 组成的串的集合，对应正规集 `{空,a,b,ab,aa,bb...}` 扩展： - 正规式 `a`，表示单一字符a，对应的正规集 `{a}`。 - 正规式 `ab(a|b)`，`ab` 是确定的部分，然后再添加 `a` 或 `b` ，对应正规集 `{aba,abb}`。 # 题 由字符a、b构成的字符串中，若每个a后至少跟一个b，则该字符串集合可用正规式表示为（） A、`(b|ab)*` B、`(ab*)*` c、`(a*b*)*` D、`(a|b)*` ### 分析 选项 A：或者是 `b` 或者是 `ab`，满足 `a后至少跟一个b` 条件，A 正确 选项 B：`*`可以是0，当为 `(abº)¹` 就只有 `a`，不满足条件 选项 C：`*`可以是0，当为 `(a¹bº)¹` 就只有 `a`，不满足条件 选项 D：或者是 `a` 或者是 `b`，当是 `a` 时不满足条件 ### 答案 A 参考： https://blog.csdn.net/woshisangsang/article/details/108052122 原文出处：http://malaoshi.top/show_1GWtbM4n92q.html