2.2 Regular form在线视频

各位同学大家好

这节课我们继续学习

词法分析的相应内容

通过上一节课

我们学习到了词法分析

它通过把源程序进行拆分

得到一个一个的词法单元

并且通过模式的映射

我们可以得到对应词法单元的相应记号

那么在这个过程当中

起到主要作用的就是模式

也就是规则

通过上一节课的学习

我们了解到了

这种规则的描述的一种数学上的表示方法

但是这种表示方法

仍然和我们程序上能表达的内容

有一定的距离

因此在这节课当中

我们会继续学习

这种模式上的运算

也就是说

通过一种更接近于程序上的这样的表示方式

把词法单元对应到词法记号上

因此这节课

我们将要介绍两方面的内容

第一个就是正规式的定义以及运算

这个正规式我们这节课要介绍的

一种非常规范化的模式的表示方法

另外第二点内容就是

正规式和状态转换图之间的关系

正规式尽管它的表示很规范

但是如果想让计算机来实现它

还有一定的距离

通过我们以往学过的课程 数据结构

我们可以想象到

用程序来表示图

也就是说状态转换图是没有鸿沟的

因此我们可以通过

把正规式转换成状态转换图

进而把这种规则描述出来

这就是我们这节课

将要学习的两方面的内容

首先我们给正规式一个定义

正规式又称为正则表达式

也就是它是描述规则的一种形式

那么对于正规式来说

通常有以下几个部分来组成

它可以按照一组规则由较简单的正规式来构成

也就是说 它的规则的描述方式

是通过简单的规则逐渐扩展成为较复杂的规则

第2个定义规则来说明

正规式 L(r)

r 表示正规式

那么 L(r) 表示正规式

或者说规则下所对应的语言

那么第3个就是正规式可以表示简单的语言

也称为正规集

那么可以看出

正规式用来说明

词法单元是如何对应到词法记号上的相应的规则

我们来看一下

它有哪些表示方法

接下来我们来

看一下正规式的详细的例子

我们看这样一共分成三列

最左侧的一列就是正规式的对应的定义

那么它所定义的语言在第2列

最后一列是指当前语言

它是表示什么样的形式

我们先从第一行来看

ε 就是一个正规式的一个最简单的表示

它对应的语言就是这样的一个集合

集合里面只有 ε 这个串本身

它对应的语言

我们可以看出

它就是表示一个空串

第2个和第1个很类似

整个正规式里只有一个字母

这个字母就是a 那么所定义的语言

就是只有 a 存在的这样的一个集合

接下来 r 或 s

这里面

r 和 s 都表示一系列的正规式

它可能是简单的

也可能是复杂的

在这里表示一个选择关系

也就是两个规则

任何一个都正确

因此它所对应的语言

就是两个正规式对应的集合的一个并集关系

接下来第4排 r 和 s

我们称其为这样的写法 称为连接

所谓连接

就是刚才所看到的

两个规则对应的语言上的一个连接

任何一个语言上拿出一个串

作为整个串的开始

然后接上第2个规则对应的串就可以了

接下来

r 的上面一个星号表示 r 的闭包

闭包就是自身和自身连接

可以连接零次

也可以连接若干次

那么它对应的语言

就是 r 这个规则本身的对应的语言集合的一个闭包

既然是集合的一个闭包

那就是在集合当中

每一次连接的过程当中

可以选择任何一个词来做连接

最后 r 加上一个括号

这个规则加上括号对应的语言还是它本身

没有任何额外的操作

最后我们来看一下

在整个运算过程当中

是有一定的优先级的关系的

那么通常的优先级

通过我们之前的学习

也可以了解到

单目运算符的优先级往往最高

那么也就是闭包运算大于连接运算

连接运算又优先于选择运算

因此如果我们给一个例子

a 和 b 的闭包做一个连接

再和 c 做选择的话

我们可以简写成 a 连接 b 的闭包 或 c

这样的一个形式

那么接下来我们来看一系列正规式的例子

我们看第1个例子

是 a 和 b 做选择

那么 a 和 b 就是字母表上的两个对应的这样的字母

那么对应的语言集合就是 a 和 b

接下来我们看

a 和 b 做选择 再做连接

那么对应的集合

就是在前面的这里选择一个和后面做连接

那么这样一共有4种方式

也就有4种结果

接下来这是直接选择的关系

我们看 那和上面的结果是一样的

最后 a 的闭包

那么闭包就有零次的连接、一次的连接 及若干次的连接

零次连接就是一个空串

因此它表示的是由 a 构成的所有的串集

a 或 b 的闭包

就在闭包的过程当中

可以一直选择 a 一直选择 b

也可以选择a 一次 选择b 一次

因此它表示的是

a 和 b 构成的所有的这样的串集

接下来

我们看一个更复杂的例子

在这个例子里面

整体来看

这是一个大的闭包

在这个大的闭包里面有三个选择关系

其中最后的选择关系之间

又是一个连接关系

连接里面又有选择和闭包

看起来很复杂

但是我们在整个分析过程当中

我们可以给它拆分来看

也就是说整体来看

这三个选择关系

每一次闭包都可以选择其中的一项

我们看下面复杂的句子

实际上它就是由上面的闭包得到的

我们看01 第1次选择的它

选择它之后

那么接着进入到连接00

然后因为这是一个选择的一个闭包

所以这0011可以在这选

最后跳出来到这01

那么整个的句子

我们可以在课下再详细分析一下

它就是当前的正规式组成的比较复杂的一个规则

那么关于正规式的命名

我们可以来了解一下

比如说刚才我们看到的那个例子

整个正规式写起来非常的长

因此表示一个规则

如果每次想说这个规则

都要重新写一遍

就比较麻烦

因此我们可以把一些

复杂的规则来命名

那么整个命名的过程

是由简单的命名开始

比如说 r1 表示一个规则

给它命名成左侧的这样的一个 d1

然后 r2 表示一个规则命名成 d2

这样依次往下来

要注意的是因为每个正规式

所要对应的规则不同

因此名字要有差别

而且最重要的一点

就是要保证每个名字对应的正规式

前面已经出现过

也就是说比如说

在 rn 这个正规式里面

它可以使用

从 d1 直到 d n-1这样的名字

不能用后面的

如果用后面的

这就会出现

大家在操作系统当中

学习过的这样的一种现象就是死锁

你用我的名字定义

我又要用你的名字定义

这样就会引起混乱

因此我们通常不这样做

那么最后我们来看一下

相应的正规式

来表示一些规则的这样的例子

首先就是Pascal语言

Pascal语言的标识符

我们在上一节当中介绍过

就是由字母开始的 然后字母数字的这样的一个组合

为了表示这样一个规则

以正规式的基本定义为基础

我们知道

我们需要从简单的规则开始定义

也就是说

我们先定义它的字母的部分

有大写 有小写

26个小写 26个大写

那么用一个记号

也就是 letter 来表示

这就是当前正规式的名字

进而 0~9 的这个数字

可以用 digit 来表示

这是它的名字

最后的这个规则

就是我们最终要定义的Pascal 的 ID 的形式

也就是字母开始的字母和数字形成的串

那么第1个 letter 表示了

所有的都是这里面的字母开始

后面字母数字有一个闭包

它可以是任意长度

可以随意选择

那么在这最后ID就表示了这样的一个内容

接下来

我们来看一下

我们最熟悉的一种编程语言

C 语言的表示形式

那么 C 语言我们知道

它首字母必须是下划线或者是字母

那么后面可以跟若干个字母、数字和下划线

这就是用语言描述的规则

但是这种语言很显然不是编译程序

我们需要把它用正规式来表示出来

我们可以仿照Pascal语言的形式

来给它表示

我们看它和Pascal唯一不同的 就是

它可以由下划线开始

因此可以在原来的基础上

我们看在letter部分加上一个选择

加入一个下划线

其他整个都不用改变

这样就可以了

那么接下来

我们再看一下

Pascal 无符号数的这样的一种定义方式

那么想定义无符号数

我们首先要了解无符号数

它有什么样的特点

它本身有什么样的规则

然后我们进而用正规式来给它表示出来

首先我们看对于数字表示来说

可以只有整数部分

可以有整数加一个点 再加小数部分

也可以是科学计数法

这一个 E 后面加上一个正的或者是负的一个整数

那么想完成这样的一系列的规则

我们知道最基本的

我们需要有一系列的数字

因此最开始

我们可以定义

这样的一个正规式

也就是从 0 一直到 9 的这样的一个选择关系

那表示最基本的数字

接下来

我们从简单的规则一点一点的扩展

从数字 我们可以最基本的得到一个整数的表示

那整数就是由若干个数字结合到一起的这样形成的串

因此我们在digit这个规则的基础上

定义digits 这样的一个正规式

就是说

有基本的数字和对应的数字串的一个连接

那么在这里和闭包连接

保证的就是

当前 整数不能为空 不能是 ε

我们通过上节课的学习

也可以了解到

自身和自身闭包的一个连接实际上就是正闭包

接下来我们来定义小数部分

所谓小数部分

就是由点开始的、点后面有若干个数字

这样的数字串在刚才已经定义好了

因此可以直接拿过来

而小数部分又是可有可无的

因此我们说可选的小数部分

我们给起这样的一个名字

然后只有一个选择关系

接下来

和小数部分一样

它可以是有科学计数法部分的

那么就是科学计数法部分由字母 E 开始

接下来可以是正的

也可以是负的

那也可以不存在

也就是说科学计数法这部分

正的和负的可以不存在

如果是省略的话

直接表示是正的 的意思

那么 E 后面要跟一个整数

整数 刚才已经定义好了

最后

我们看整个科学计数法部分 也可有可无

因此也可以用一个选择和 ε 来表示

最后

整个的数字

我们看就可以表示出来了

它表示的就是

整数部分作为最开始的一个部分

因为表示数字

最基本的要有数开始

然后接下来是可选的小数部分

以及可选的科学记数法部分

而后面这两部分

都可以通过

选择 ε 给它省略掉

这就是从简单到复杂的一个例子

这里面我们再来了解一些简化规则

第1个是刚才我们接触到的

就是通过自身和闭包的连接

可以表示成正闭包的形式

第2部分就是当前的规则

后面画一个问号 那就表示

当前这个规则可有也可无

那也就是我们可选的小数

以及科学计数法部分

都是这样的一种形式

最后我们通常会把基本的一些字母和数字的规则

通过选择的方式

给它表示出来

这样从头写到尾

我们看会非常的麻烦

因此可以用第3种简化规则来表示

就是用一个中括号

给它括起来

a 一个小横线 一个 z 就表示a到z这样的26个字母

通过以上简化规则

我们就可以把刚才比较复杂的

这样五个正规式简写成这样的一个形式

就可以了

我们看这就是正闭包

然后问号表示一种选择关系

接下来我们看一个程序上的例子

就是正规定义的一个例子

do while 语句

那么 while 本身就是它自己

do 也是它自己就表示

由这两个字母构成的这样的串

接下来这个规则

我们知道

do while语句

一个循环语句

需要有关系判断

因此需要有关系运算符

这里的关系运算符

就是小于、等于这样的一系列的选择关系

ID在之前我们定义过了

Number我们也定义过了

整个就可以形成

Do while语句当中

所有可能出现的词的

一个规则定义

除了这些词之外

我们不要忘记

还会有一些空白

也就是大家最初

接触程序语言的时候

老师都会告诉你

在一些关系运算符

或者赋值运算符之间

加减乘除

这些运算符之间

词和词之间

最好有一些空格

看起来比较清晰

因此对此法单元来说

我们也需要把这些空白给识别出来

那么它对应的规则就是

空白一般有以下几种表示

第1个就是空白

第2个是 tab 键构成的这样的空白

第3个就是回车

那么真正的空白行

可以由这样的若干个

它们之间的结合来表示

因此我们可以用下面两个规则

来实现对空白的这样的一个识别

那么前面我们所讲到的记号

从这里我们可以看出来什么呢？

实际上就是我们正规式的名字

因为整个箭头后面的

都是在描述这个规则

而箭头前面的就是给规则定义的名字

符合当前规则的

用一个语言来表示

这个语言有统一的记号

这就是我们这节课

一直在所说的 词法记号

它和正规式的名字是一一对应的

那么对于词法记号的识别来说

我们看可以用正规式来表示

但是如果想让正规式

直接来判断这个词法单元符不符合规则

还有一定的难度

因此我们想把一个串和一个规则进行匹配

我们可以借助有限状态自动机来表示

下面我们来看

正规式和状态转换图之间

是如何对应起来的

我们先从一些简单的例子来看

比如说第一个

如果正规式

只是识别一个简单的符号a的话

那么它对应的状态转换图

就是这样的例子

那么我们看状态 0 就是起始状态

双圈的E表示接受状态

从起始的状态到接触状态中间

通过一个箭头以及一个字母来表示

字母的意思就是说

两个状态之间

跳转的一个必要的元素

也就是说通过识别一个字母 a 就

可以从这样的一个状态到另一个状态

这种方式就保证了

我们在扫描源程序的过程当中

从起始状态开始

如果源程序出现了一个字母 a 的话

那就说明它正确了

就会到达一个接受状态

同理

我们再来看一个

相对复杂的例子

正规式我们知道

它识别的就是a 和b的一个连接

也就是说

如果源程序正确的话

应该先出现a再出现b

那么这样的一个转换图

也表示了同样的道理

也就是从开始状态开始

如果源程序出现了一个a

扫描源程序指针往后移

那就会到达状态 1

进而如果接下来

指针指向的是 b 那么它就会跳转到一个接触状态

也就是状态 2

进而正规式连接 a 或 b

就可以用这样的一个选择关系来表示

也就是从这个状态识别a

可以到达接受状态

那么识别 b 也可以到达一个接受

最后是一个闭包的一个形式

闭包它的顾名思义

就是我可以连接零次

也就是直接就到达一个接触状态

也可以在这循环若干次

这是对应的正规式形式

那么对于最后 d ->

它对应的正规式是 a 一个问号

通过刚才的简化规则

我们知道问号

表示的是

可以有也可以没有

有的话只能有一次

如果没有

那就直接开始状态 就是接受状态

如果有一次

那么就是连接一个 a 到达一个接受状态

这样就可以了

最后是一些复杂的例子

我们看对于关系转换图的这样复杂的例子

开始状态

通常我们都会用一个箭头上面写一个开始来表示

然后通过识别一个 <

我们看可以到达状态1

再识别一个 =

到达一个接受状态

这就是识别<=的这样的一个过程

那么扫描源程序

如果第1个来的是=

它就直接会跳转到5号状态

如果来的是一个>

那么先跳到6号状态

接着识别的是一个 = 到7号

如果是其他的东西 那我们就到8号

这里面说一说 要注意的是

4号和8号状态

也就是说对于关系运算符来说

可以直接<是一个这样的一个句子结束

也可以和后面的= 共同来构成

这样的一个词法单元

因此我们需要来判断

它到底是到<结束了呢？

还是后面还有= ？

所以我们需要判断完< 之后或者是>之后

再往后看一个(符号)

如果接下来的是=

那就表示它是一个<=

如果出现的是空白或者是一个数字

那就表示当前

这个关系运算符已经识别完了

那么在这种情况下

我需要把指针来回退

这个星号就表示指针回退的意思

为了保证在每次这个词识别结束之后

都能把指针，即扫描源程序的指针

停留在当前词的最后一位

这是识别 letter 的这样的一个状态转换图

从开始 开始识别一个letter

那么这里可以有若干个letter 或者若干个digit

这样的一个运算

最后一旦遇到其他的空白了

那么当前这个词结束了

这就可以到达结束状态了

那么这是刚才我们看到的这个例子

识别数字的这样的一个例子

看起来很复杂

我们先从开始一直到接受状态来看一下

从开始状态识别数字

那么可以识别若干个数字

如果它就是整数结束

我们看就可以走这条路 other 这样回来

如果接下来有小数出现

那就会识别一个点

到达下一个状态

进而再识别数字

那么如果结束了

那么也可以通过 other 到达接受状态

那还可以更复杂

有科学计数法的部分

有科学计数法了之后

那么就是识别一个E

那么到达一个16号状态

可以直接连数字

然后到19号状态也可以

这过程当中

有正号或者是负号

那么这样就可以到达18号状态

进而最后到达19号状态

那么这是空白的一个转换关系

就是可以识别一个空格

tab 键或者回车

也可以是它们若干个

这样的一个闭包在这循环

最后通过识别非空白的一个字母

或者数字这样的来结束

以上就是我们这节课讲的内容

谢谢大家