正规文法和状态转换图在线视频

大家好

如果我们把一个程序设计语言的

每类单词看做是一种语言的话

那么各类单词它的词法都能用相应的

正规文法来描述

正规文法有左线性文法和右线性文法

我们先来回顾一下正规文法它的定义

假设A、B是非终结符

a是终结符

那么右线性文法它的产生式形如

A→aB或A→a

左线性文法它的产生式形如

A→Ba或者是A→a

左、右线性文法都是3型文法

定义语言是3型语言

也称为正则语言（RL）

需要注意的是

正规文法定义了程序设计语言当中的

多数词法特性

左、右线性文法是不可以混用的

凡是能够用正规文法描述的语言

都可以用一种非常直观的方式来进行分析

这就是状态转换图

例如右边的

这个图就是状态转换图

它是用有限个结点所组成的有向图

每个结点代表在识别分析过程当中

扫描器所处的状态

其中含有一个初始状态和若干个终态

在状态转换图中

状态用圆圈表示

终态用双层圆圈来表示

状态之间可以用一条有向边

或者有向弧来进行连接

我们来看这个图上面

标记一个字符a的这条有向边

表示从有向边射出状态0出发

识别一个字符后

将进入箭头所指向的状态1（结点）

状态转换图可以识别

相应正规文法所产生的句子

也就是单词

在状态转换图中

从初态出发

分别沿一切可能的路径到达终态结点

并将路径中弧线上所标记的字符

依次连接起来

便可以得到状态转换图

所识别的全部符号串

我们来看右边的这个状态转换图

它能够识别的字符串是

c cd

a后面连接n个d

然后接下来连接一个b

这样的字符串

那么这些符号串组成的集合就构成了

这个状态转换图所识别的语言

接下来我们来看

根据正规文法

是如何构建状态转换图的

我们首先来看一下

根据右线性文法

来构建状态转换图

假设右线性文法有K个非终结符（VN）

那么所要构健的状态转换图

共有K+1个状态

非终结符（VN）中的每个符号

分别表示了K个状态

文法的开始符号S是初始状态

新增加一个不属于文法的

非终结符F

用它来标记终止状态

接下来针对于文法当中的每一个产生式

转换的规则是这样子的

如果A是文法的开始符号

那么A就是初始状态

我们用一个箭头射入A状态

形如A→aB的产生式

从节点A引出一条有向弧到节点B

那么弧上标记为a

形如A→a的产生式

从A引出一条有向弧到终态F

并且用符号a来标记这条弧

对于产生式A->ε

可以将结点A设置为终态

或者从A引出有向弧到终态F

并用符号ε标记这条弧

那么我们来试着构建

文法G[S]

它的对应的状态转化图

首先根据这个文法我们看到了

一共有四个状态

S U V和新增加的终态F

S是初态

然后按照前面的转化规则

我们可以构建状态之间的转换弧

这样的话我们就获得了右线性文法

G[S]它对应的状态转化图了

那么这个状态转换图

是怎样识别符号串的呢

首先对于符号串W来说

从初态S出发

自左向右逐个扫描W当中的字符

那么在初态S状态下面

扫描到的符号a1

在节点S所射出的弧当中

去寻找标记为a1的矢线

如果不存在的话

说明W这个字符串是有错误的

读入a1之后

沿着弧的方向去到下一状态

在这个状态下面去扫描a2，……，

直到W当中的全部字符读完

而且进入到终态F

那么这个时候W就被接受了

譬如我们来看一下右边的这个状态转换图

是怎样识别baa的

从S状态出发

当前正在扫描的是符号b

那么到达的状态是V

在V状态下面扫描符号a

到达的状态U

在U状态下面扫描符号a

到达了终态F

那么说明baa是可以被状态转化图识别的

我们发现这个识别的过程实际上

是对字符串baa

建立了一个推导过程

每次的状态转换都模拟了

一步直接推导

这个识别方法

或者说这个分析方法

我们也称之为自顶向下的分析方法

也就是说从初态出发

沿某条路径到达某个状态

沿途当中的符号和到达状态

构成了字符串的序列

那么构成的这个字符串的序列

比如说在我们这个例子当中

bV baU baa

都是我们这个文法的一个句型

而且都是规范句型

那么到达终态的时候

baa才成为了文法的句子

那么接下来我们来看

根据左线性文法

如何构建状态转换图

首先为什么说

左、右线性文法是不可混用的呢

我们来看一下对于这个左线性文法

如果我们还是使用右线性文法

状态转化图的规则来识别aab的话

我们来看构造aab的推导过程是这样子的

S推出Vb

接下来再推出Uab

最后推出aab

我们发现从初态到终态路径的标记

连成的串其实是文法所定义串的左序

那么既然方向是相反的

解决这一矛盾的方法就是

把每一条的边改方向

并且把初态改成终态

所有的终态合成一个初态就可以了

那么我们来看根据左线性文法

是如何构建状态转换图的

和右线性文法一样

也是新增加一个不属于

文法的非终结符R

只不过是这个R是来标记初始状态的

转换的规则是这样子的

针对文法当中的每一个产生式

比如 如果A是文法的开始符号的话

那么A在状态转换图当中就是终止状态

对于形如A→Ba的产生式

从节点B引出一条有向弧到节点A

弧上标记为a

对于形如A→a的产生式

从初态R引出一条有向弧到状态A

并且用符号a来标记这条弧

状态转化图识别左、右线性文法

所定义的字符串W的过程非常相似的

我们来看一下我们根据

左线性文法

构建的这个状态转换图

是如何来识别字符串的

从左向右逐个扫描W当中的各个字符

在R下面扫描到的字符是a1

那么在节点R所有射出的弧当中寻找

标记为a1的矢线

如果不存在的话

说明这个字符串是有错误的

接下来读入

a1之后沿着矢线的方向到达下一个状态

在这个状态去继续扫描a2，……，

直到W当中的

全部的字符读完之后

而且进入终态S

那么这个时候W就被接收了

有所不同的是左线性文法

状态转换图识别aab的过程

是对串aab构建规约的过程

可以这样理解

在开始状态R下面

扫描到的第一个符号a

转到了状态U

表示a是句柄

归约到了U

接下来 在状态U扫描到了a

转到状态V

此时句柄为Ua

归约成V

最后扫描到了b

转移到了状态S

此时句柄为Vb

归约为S

这种识别方法

是自底向上的分析方法

我们看到

状态转换图可以

非常直观清晰地描述

单词识别的过程

我们也可以把状态转换图

看成词法分析程序的一个

特殊的流程图

有了它

我们能够方便地编写相应的

词法分析程序

也就是说一个程序设计语言当中

一般都含有若干个

种类的单词符号

我们首先为每一类单词符号

建立一张状态转换图

然后将这些状态转换图

合并成一张统一的状态转换图

根据这个状态转换图

来构造词法分析程序

那么如何让计算机利用状态转换图

来进行词法分析呢

一个简单实用的方法就是

将图以矩阵的形式来保存在内存当中

这就是所谓的状态矩阵法

状态矩阵以图当中的各个状态

S1,S2,…,Sn为行

以各个输入符号a1,a2, …,am为列

组成了一个n×m的矩阵B

这个矩阵当中的每一个元素Bij

指明的是下一状态Sk和扫描器

此时完成的语义动作

它的含义是这样子的

在Si状态下

扫描到了aj符号

按照序偶(Si,aj)查矩阵B

扫描器根据Bij的指示

先执行相应的语义动作

然后再转换成下一个状态Sk

如果Bij对象是“出错”的话

说明输入符号串是有错误的

拒绝接收

扫描器将调出出错处理程序

来进行相关的处理

在这一节当中

我们从状态转换图入手

讨论了词法分析器它的构造方法

根据右左线性文法

构造了对应的状态转换图

分析了利用状态转换图

识别单词字符串的过程

还讲了实现状态转换图的一种方法

就是状态矩阵法

这一节课就到这里

谢谢大家