【程序语言与编译】正规式与正规集

适合读者软考中级备考同学阅读时间3分钟内容正规式的定义、基本运算、正规集、常用等价关系、例题1. 为什么需要正规式正规式Regular Expression是一种用特定符号表示字符串集合即正规集的代数表示法。它能够简洁地描述词法规则如标识符、整数、运算符等是词法分析的基础。软考中常考查正规式与正规集的转换以及正规式的化简。2. 基本定义正规式递归定义如下ε\varepsilonε空串是正规式表示集合{ε}\{\varepsilon\}{ε}。若aaa是终结符则aaa是正规式表示集合{a}\{a\}{a}。若rrr和sss是正规式则以下也是正规式r∣sr|sr∣s或表示集合L(r)∪L(s)L(r) \cup L(s)L(r)∪L(s)rsrsrs连接表示集合{xy∣x∈L(r),y∈L(s)}\{ xy \mid x \in L(r), y \in L(s) \}{xy∣x∈L(r),y∈L(s)}r∗r^*r∗闭包表示集合L(r)∗⋃i≥0L(r)iL(r)^* \bigcup_{i \ge 0} L(r)^iL(r)∗⋃i≥0​L(r)i包含ε\varepsilonε有限次使用上述规则得到的表达式都是正规式。正规集正规式所表示的字符串集合。3. 常用运算符号及优先级运算符含义优先级由高到低∗^*∗闭包克林闭包最高⋅·⋅连接先后连接中等∣|∣或选择最低通常括号( )用于改变运算顺序。4. 正规式表示的语言示例正规式正规集描述a∣ba|ba∣b{a,b}\{a, b\}{a,b}ababab{ab}\{ab\}{ab}a∗a^*a∗{ε,a,aa,aaa,… }\{\varepsilon, a, aa, aaa, \dots\}{ε,a,aa,aaa,…}a∣b∗a|b^*a∣b∗{a,ε,b,bb,bbb,… }\{a, \varepsilon, b, bb, bbb, \dots\}{a,ε,b,bb,bbb,…}注意优先级(a∣b)∗(a|b)^*(a∣b)∗所有由aaa和bbb组成的字符串包括空串a(a∣b)∗a(a|b)^*a(a∣b)∗以aaa开头的、由aaa和bbb组成的字符串a∗ba^*ba∗b任意个aaa后跟一个bbb(a∣b)∗aa(a∣b)∗(a|b)^*aa(a|b)^*(a∣b)∗aa(a∣b)∗至少包含连续两个aaa的串5. 常用正规式等价关系等价关系说明r∣ss∣rr|s s|rr∣ss∣r交换律(r∣s)∣tr∣(s∣t)(r|s)|t r|(s|t)(r∣s)∣tr∣(s∣t)结合律(rs)tr(st)(rs)t r(st)(rs)tr(st)连接结合律r(s∣t)rs∣rtr(s|t) rs | rtr(s∣t)rs∣rt分配律(s∣t)rsr∣tr(s|t)r sr | tr(s∣t)rsr∣tr分配律εrrεr\varepsilon r r\varepsilon rεrrεr空串为单位元r∗(r∗)∗r∗r∗ε∣r∗r^* (r^*)^* r^*r^* \varepsilon | r^*r∗(r∗)∗r∗r∗ε∣r∗闭包性质(r∣s)∗(r∗s∗)∗(r|s)^* (r^*s^*)^*(r∣s)∗(r∗s∗)∗常见变形6. 与有限自动机的关系正规式、正规集、有限自动机FA三者等价每个正规式对应一个正规集且能被一个有限自动机识别。每个有限自动机所识别的语言都可以用一个正规式表示。软考中常见题型给定正规式画出相应的状态转换图或给定DFA写出正规式。7. 经典例题题目1设正规式r(a∥b)∗abbr (a\|b)^*abbr(a∥b)∗abb求它所表示的语言。解析(a∥b)∗(a\|b)^*(a∥b)∗表示任意个aaa或bbb组成的串包括空串后面紧跟abbabbabb。因此该正规式表示所有以abbabbabb结尾的、由aaa和bbb组成的字符串。答案{w∈{a,b}∗∣w 以 abb 结尾}\{ w \in \{a,b\}^* \mid w \text{ 以 } abb \text{ 结尾} \}{w∈{a,b}∗∣w以abb结尾}题目2写出表示“以aaa开头后跟任意个bbb”的字符串的正规式。解析aaa开头aaa后面可以跟任意个bbbb∗b^*b∗。连接起来ab∗a b^*ab∗。答案ab∗a b^*ab∗题目3与正规式(ab)∗(ab)^*(ab)∗等价的是 。A.a∗b∗a^*b^*a∗b∗B.a∗b∗a∗a^*b^*a^*a∗b∗a∗C.(a∥b)∗(a\|b)^*(a∥b)∗D.ε∥ab∥(ab)(ab)∥…\varepsilon\|ab\|(ab)(ab)\|\dotsε∥ab∥(ab)(ab)∥…解析(ab)∗(ab)^*(ab)∗表示空串或ababab重复多次的串ab,abab,ababab,…ab, abab, ababab, \dotsab,abab,ababab,…。选项Aa∗b∗a^*b^*a∗b∗可以生成aaa和bbb任意顺序但无ababab重复模式如bababa也允许不对。选项B同理。选项C包含所有a,ba,ba,b串范围太大。选项D正是其定义。答案D题目4化简正规式(ε∥a)b∗(\varepsilon\|a)b^*(ε∥a)b∗。解析ε∥a\varepsilon\|aε∥a表示空串或aaa即{ε,a}\{ \varepsilon, a \}{ε,a}。与b∗b^*b∗连接{ε,a}⋅b∗b∗∪ab∗\{\varepsilon, a\} \cdot b^* b^* \cup a b^*{ε,a}⋅b∗b∗∪ab∗。而b∗b^*b∗已包含在ab∗a b^*ab∗中注意εb∗b∗\varepsilon b^* b^*εb∗b∗ab∗a b^*ab∗是单独的所以整体就是b∗∥ab∗b^* \| a b^*b∗∥ab∗。由于b∗b^*b∗是ab∗a b^*ab∗的一部分不b∗b^*b∗生成所有仅含bbb的串ab∗a b^*ab∗生成以aaa开头的串。二者无包含关系所以化简后为b∗∥ab∗b^* \| a b^*b∗∥ab∗。进一步可写作(a∥ε)b∗(a\| \varepsilon) b^*(a∥ε)b∗但通常保留原形即可。答案(ε∥a)b∗(\varepsilon\|a)b^*(ε∥a)b∗或b∗∥ab∗b^*\|ab^*b∗∥ab∗8. 记忆口诀正规式描述字符串空串闭包连接或。优先级闭包高连接次之或最低。等价转换多练习有限自动机可互换。9. 给备考同学的一句话正规式与正规集是词法分析的数学基础。软考中常考给定自然语言描述写出正规式。给定正规式解释其表示的语言。正规式的等价化简或与有限自动机的转换。记住基本运算的含义r∣sr|sr∣s或、rsrsrs连接、r∗r^*r∗零次或多次重复。多做题熟悉常见的等价关系考试时就能快速写出正确答案。本专栏日更2篇点击头像 → 专栏《软考中级高频考点》订阅#软考中级 #软件设计师 #正规式 #正规集 #词法分析