正规式的基础知识是软件评测师考试的重要考点,经常出现在上午场的客观选择题当中。正规式是在编译程序词法分析时用于描述词法规则的表达式,它产生的集合是语言基本字符集∑(字母表)上的字符串的一个子集,称为正规集。下面就该知识点并结合例题进行总结学习。
一、正规式的定义
对于字母表∑,其上的正规式及其表示的正规集可以递归定义如下。
(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日
作者:昊洋讲师
版权所有,侵权必究