正规式的基础知识是软件评测师考试的重要考点，经常出现在上午场的客观选择题当中。正规式是在编译程序词法分析时用于描述词法规则的表达式，它产生的集合是语言基本字符集∑(字母表)上的字符串的一个子集，称为正规集。下面就该知识点并结合例题进行总结学习。
一、正规式的定义
对于字母表∑，其上的正规式及其表示的正规集可以递归定义如下。
（1）ε是一个正规式，它表示集合L(ε)= {ε}。注意：ε表示为空，{ε}表示空集。
（2）若a是∑上的字符，则a是一个正规式，它所表示的正规集为L(a)= {a}。
（3）若正规式r和s分别表示正规集L(r)和L(s)， 则：
①r|s是正规式，表示集合L(r)UL(s)。
②r·s是正规式，表示集合L(r)L(s)。
③r*是正规式，表示集合(L(r))*。
④(r)是正规式，表示集合L(r)。
仅由有限次地使用上述三个步骤定义的表达式才是∑上的正规式。
运算符“|”、“·”、“*”分别称为“或”“连接”和“闭包”。运算符“|”表示“或”、并集；运算符“·”表示两个集合元素的连接；运算符“*”表示*之前括号里的内容出现0次或多次。在正规式的书写中，连接运算符“·”可省略。运算符的优先级从高到低顺序排列为“*”、“·”、“|”。
二、疑难字符解析
（1）字母表∑：元素的非空有穷集合。例如，∑={a, b}。
（2）字符：字母表∑中的一个元素。例如，∑上的a或b。
（3）字符串：字母表∑中字符组成的有穷序列。例如，a、ab、aaa 都是∑上的字符串。
（4）字符串的长度：字符串中的字符个数。例如，|aba|=3。
（5）空串ε：由0个字符组成的序列。例如，|ε|=0。
（6）连接：字符串S和T的连接是指将串T接续在串S之后，表示为S·T,连接符号“·可省略。显然，对于字母表∑上的任意字符串S，S·ε=ε·S=S。
（7）∑*：指包括空串ε在内的∑上所有字符串的集合。例如，设∑={a，b}， ∑*={ε，a，b，aa，bb，ab，ba，aaa，……}。
（8）字符串集合的运算：设A、B代表字母表∑上的两个字符串集合。
①或(合并)：AUB={a|a∈A或a∈B}；
②积(连接)：AB={ab|a∈A且b∈B}。
三、常见的正规式和对应的正规集
设∑={a，b}，在下表中列出了∑上的一些正规式和相应的正规集。
下面是近几年对该知识点考察过的真题，以后仍是考试出题的重点，大家要重视起来。
【2017年第17题】表示"以字符a开头且仅由字符a、b构成的所有字符串"的正规式为（ ）
A、a*b*
B、(alb)*a
C、a(alb)*
D、(ab)*
解析：本题考查正规式的基础知识。
选项A：a*b*={a}*{b}* 表示由若干个a后跟若干个b所组成的任何长度的字符串，此时需要注意的是若干个是可以是0个的；
选项B：(alb)*a ={a,b}*{a}表示以a结尾，前面有若干个a或b组成的字符串；
选项C：a(alb)*={a}{a,b}*表示a后面跟任意个a或b组成的字符串；
选项D：(ab)*={ab}* 表示每个ab所组成的任何长度的字符串(ab不能分离)。
ABCD四个选项只有C能保证以a开头。
故正确答案为：C
作者唯一官方个人微信公众号（昊洋与你一起成长）：HYJY20180101
写于2021年10月9日
作者：昊洋讲师
版权所有，侵权必究
