学习编译原理Time06 ~ 正规式

单词的描述工具-正规式 ：多数程序设计语言的单词的语法均可用正规文法来表示。

正规式（regular expression也叫正则表达式）：正规式是定义正规集的数学工具，是说明单词的模式(pattern)的一种表示法，用它描述单词符号时一般比正规文法更简洁。正规式和正规集 (即其描述的语言) 的定义可以用递归的形式给出。

正规式运算规律 :

设r,s,t为正规式，则它们满足如下运算规律：

r|s=s|r

r|(s|t)=(r|s)|t

(rs)t=r(st):交换律

r(s|t)=rs|rt; (s|t)r=sr|tr :分配律

εr=r ; rε=r : ε是 “连接”的恒等元素

r|r=r : “或”的抽取律

例 : 令∑={a,b},则∑上的正规式和相应正规集为

正规式	正规集
a	{a}
a|b	{a,b}
ab	{ab}
(a|b)(a|b)	{aa,ab,ba,bb}
a*	{ε ,a,aa,..,n个a的串}
(a|b)*	{ε ,a,aa, ……n个a的串}{ε ,a,b,aa,ab,bb ……所有由 a和b组成的串}
(a|b)* (aa|bb)(a|b)*	∑上所有含有两个相继的a或两个相继的b组成的串},例如：aaaa、bbaabb、abbaaa

例 : 令∑={a，d}

其中a代表字母,d代表数字，则∑上的正规式 r=a(a|d) * 定义的正规集为{a,aa,ad,add,……}， 即：字母(字母|数字) * ,它表示的正规集中的每个元素的模式是“字母打头的字母数字串”,也就是多数程序语言中标识符的词法规则.

记录

点点滴滴的笔记

欢迎关注，共同学习

小浩笔记